Достаточное условие минимальности стоимости перевозок

;(1)

;

Выпишем ограничения ТЗ

=

=

……………………………

=

+ + … + =

………………………………

+ + … + =

Каждое ограничение на предложение умножим на нек. перем величины , a каждое огр на спрос умножим на . Полученное выражение вычтем из целевой ф-ции (1):

Выберем значение перем таким образом чтобы выполн рав (2)

Решение с-мы (2) назыв потенциалами. С-ма ур. (2) имеет более одного решения т.к. сост из m+n-1 неизв величин. В качестве потенциалов можно выбрать любое решение с-мы (2). Вычислим величины по небазисному мн-ву клеток.

ТЕОР. Выполнение нер-ва по небазисному мн-ву клеток (i,j) является достат. для оптимальности плана перевозок.

Док-во. Из рав-ва (1) следует, что если значения небазисных перевозок для которых >0 изменить на положит., то ст-ть перевозок увеличится, или не изменится. С другой стороны, если существует <0, (i,j) , то путем увеличения соотв. значения перевозки с нулев. на положит.стоимость перевозок можно уменьшить.

Изменяя знач. Небазисной перевозки, для кот. <0 необходимо изменить другие значения базисных перевозок т.о. чтобы выполнялись все ограничения задачи и кол-во базисных перевозок осталось равным m+n-1.

Поиск по сайту: