3.4 Улучшающие циклы и метод потенциалов

Т.к. цикл всегда обеспечивает переход от одной вершины к другой. Осталось найти способ построения улучшающего цикла, т.е. такого цикла, который снижает стоимость перевозки. Для этого введем потенциальные платежи за перевозку следующим способом. Пусть за перевозку единицы груза из i–го склада – неважно кому – вносится плата _i , а за доставку единицы груза j–му потребителю – неважно, откуда – вносится плата  _j. Тогда стоимость перевозки единицы груза из i–го склада j–му потребителю составит _ij = _i + _j (положительность всех потенциальных платежей _ij не предполагается). Можно считать, что потенциальные платежи это плата только за погрузку и разгрузку. Потенциалы ,  определим таким образом, чтобы в базисных клетках (т.е. при x_ij >0) потенциальные цены равнялись реальным _ij = _i + _j = c_ij Т.к. потенциалов , а заполненных клеток на единицу меньше, один потенциал нужно назначить - поэтому ₁ всегда полагают равным нулю.

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

1 Как видим, стандартная задача ЛП отличается от основной тем, что балансовые ограничения (8) в ней имеют форму неравенств.