В чём заключается метод потенциалов при решении транспортной задачи?

Метод потенциалов используется для решения транспортной задачи и заключается в оценке текущего базисного допустимого решения на оптимальность с помощью специально рассчитанных оценок и нахождении нового решения, приносящего лучший результат. 4

Алгоритм метода потенциалов: 2

1. Каждому поставщику (Ai) ставится в соответствие некоторое число (u), которое называется потенциалом Ai-того поставщика. 2 Каждому потребителю (Bj) ставится в соответствие некоторое число (v), которое называется потенциалом Bj-того потребителя. 2
2. Для каждой заполненной клетки, то есть для каждой базисной переменной, строится соотношение: ui+vj=cij. 2
3. Получают систему с числом уравнений, равным количеству базисных переменных. 2 Из этой системы определяют неизвестные потенциалы ui и vj, полагая ui=0. 2
4. Для каждой незаполненной клетки, то есть для каждой небазисной переменной, рассчитываются косвенные тарифы cij* по формуле: cij* = ui+vj. 2
5. Полученный план проверяют на оптимальность по критерию оптимальности dij. 2 Если для каждой незаполненной клетки выполняется условие: dij<=cij*<=0, то исходный план является оптимальным. 2
6. Если некоторые dij>0, то необходимо перейти к новому плану путём перемещения перевозки в клетку, отвечающую условию max(dij). 2 Если таких клеток несколько, то выбирают любую из них. 2
7. Для правильного перемещения перевозок, чтобы не нарушить ограничения задачи, строят так называемый цикл, то есть замкнутый многоугольник, соединяющий выбранную клетку с ней же самой и проходящий через заполненные клетки. 2
8. После этого заново подсчитывают платежи и псевдостоимости, и, если план ещё не оптимален, процедура улучшения продолжается до тех пор, пока не будет найден оптимальный план. 1

Метод потенциалов разработан Леонидом Канторовичем. 3