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

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

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

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