Метод потенциалов нахождения оптимального решения

Рассмотрим теорему об оптимальности решения транспортной задачи (3.61)-(3.64).

Теорема 2.10. Решение транспортной задачи будет оптимальным, если найдутся такие числа (i =1,2,…, m) и (j =1,2,…, n), называемые соответственно потенциалами поставщиков и потребителей, которые будут удовлетворять условиям:

для ;

для ,

i= 1,2,…, m; j= 1,2,…, n.

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

(i= 1,2,…, m) – оценка единицы запаса (потенциал поставщика),

(j= 1,2,…, n) – оценка единицы спроса (потенциал потребителя).

Тогда двойственная задача запишется так:

(2.65)

при ограничениях

, (2.66)

причем (i =2,3,…, m) и (j= 1,2,…, n) – произвольного знака.

Т.к. задача (2.61)-(2.64) имеет решение, то по основной теореме двойственности, и двойственная к ней задача также имеет решение, при этом .

На основании 5-го правила построения двойственных задач, устанавливающим взаимосвязь между значениями неизвестных и выполнением ограничений в оптимальных решениях взаимно двойственных задач, заключаем, что ограничения двойственной задачи из системы ограничений (2.66) выполняются как строгие равенства, если им в исходной задаче соответствуют положительные неизвестные ; а ограничения, соответствующие неизвестным =0, выполняются как неравенства. Таким образом,

для ; (2.67)

для . (2.68)

Теорема доказана.

Дата добавления: 2015-05-26