Метод потенциалов. Общий принцип определения оптимального плана транспортной задачи методом потенциалов аналогичен принципу решения задачи ЛП симплекс-методом

Общий принцип определения оптимального плана транспортной задачи методом потенциалов аналогичен принципу решения задачи ЛП симплекс-методом, а именно: сначала находят опорный план транспортной задачи (например, методом северо-западного угла), а затем его последовательно улучшают до получения оптимального плана.

Теорема 3.2. Если для некоторого опорного плана транспортной задачи существуют такие числа , что

при

при

для всех и , то - оптимальный план транспортной задачи.

Определение 3.3. Числа и называются потенциалами соответственно пунктов отправления (складов) и пунктов назначения (предприятий).

Теорема позволяет построить алгоритм нахождения оптимального решения транспортной задачи. Он состоит в следующем. Пусть найден опорный план транспортной задачи. Для каждого из пунктов отправления и назначения определяют потенциалы и . Эти числа находят из системы уравнений

(3.8)

где -тарифы, стоящие в заполненных клетках таблицы условий найденного опорного плана транспортной задачи.

Так как число заполненных клеток равно , то система (3.8) с неизвестными содержит уравнений. Поскольку число неизвестных превышает на одно число уравнений, одно из неизвестных можно положить равным любому числу, например , и найти последовательно из (3.8) значения остальных неизвестных. После того, как потенциалы найдены, для каждой из свободных клеток определяют число .

Если среди чисел нет положительных, то согласно теореме, найденный план является оптимальным. Если же некоторое , то план не является оптимальным и необходимо перейти к новому опорному плану. Для этого рассмотрим все свободные клетки, для которых , и среди данных чисел выбирают максимальное. Клетку, которой это число соответствует, следует заполнить, переместив часть груза по циклу.

Определение 3.4. Циклом в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках, а звенья вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое – в столбце.