Потенциалы

Цена цикла пересчета

Таблица 5.6

Пн По	В1	В2	В3	Запасы
А1	2 0	3	1
А2	4 60	2	5
А3	3	2 40	6
Потребности				150=150

Видим, что в результате двух сдвигов мы значительно улучшили план перевозок. Это произошло потому, что циклы пересчета, по которым производились сдвиги, выбирались специальным образом. Для выяснения сути происшедшего потребуется понятие цены цикла пересчета.

Ценой цикла пересчета называется разность между суммой стоимостей, стоящих в положительных клетках, и суммой стоимостей, стоящих в отрицательных клетках.

Например, цена цикла пересчета, указанного в таблице 5.5, равна (– 4).

Цена цикла пересчета - это приращение целевой функции при сдвиге h=1 по циклу пересчета.

Если, например, сделать единичный сдвиг по циклу пересчета таблицы 5.5, получится план перевозок, суммарная стоимость которого 430–4 = 426.

Имеет место, следующее утверждение: при сдвиге на величину h ≥ 0 по циклу пересчета, имеющему цену γ, приращение Δf целевой функции вычисляется по формуле

Δf = γ · h (5.5)

В справедливости формулы (5.5) можно убедиться и на примерах (таблицы 5.4, 5.5, 5.6). Из формулы (5.5) вытекает, что при положительном сдвиге по циклу пересчета с отрицательной ценой значение целевой функции уменьшается. Поэтому поиск оптимального плана перевозок сводится к выявлению циклов пересчета с отрицательной ценой и осуществлению максимально допустимых сдвигов по ним. А если циклов пересчета с отрицательной ценой не окажется?

Теорема: Опорный план перевозок, при котором все циклы пересчета имеют неотрицательные цены, оптимален.

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

Пусть в транспортной задаче с пунктами отправления А₁, А₂,..., А_m и пунктами назначения В₁, В₂,..., В_n имеется некоторый опорный план перевозок. Сопоставим каждому пункту отправления A_i число α_i (), каждому пункту назначения В_j - число β_j () так, чтобы для каждой базисной клетки (p,q) выполнялось равенство

α_p + β_q = c_pq (5.6)

Числа α_i и β_j называются потенциалами пунктов отправления и назначения соответственно.

Для отыскания потенциалов нужно для каждой базисной клетки составить уравнение вида (5.6) и решить полученную систему m + n – 1 уравнений с m + n неизвестными. Такая система имеет бесконечно много решений. Чтобы получить конкретное решение, один из потенциалов полагают равным 0.

Найдем, например, систему потенциалов для опорного плана, данного в таблице 5.6. Составим систему уравнений:

Положим α₁=0. Тогда β₁=2; β₃=1; α₂=2; α₃=1; β₂=1.
Дополним таблицу 5.6 столбцом с потенциалами α_i и строкой с потенциалами β_j, получим таблицу 5.7.