SHPORA.net :: PDA

[ Back ]

Если х - оптимальное решение исходной задачи, то двойственная задача также имеет оптимальное решение у0, причем z(x0)=T(y0).

Док-во:

Пусть исходная задача имеет оптимальное решение х0, которое можно получить симплексным методом. Из системы

х = B 1b

zmax = c0 x0

Оценки s = c0D-c  0

Пусть у0 - соответствующее решение двойственной задачи. Тогда у0 = c0 B-1

Умножим обе части на А:

у0 А = с0 В-1 А

у0 А = с0 D

y0 A - c = c0 D - c  0

y0 A - c  0

y0 A  с

Отсюда получили, что у0 - допустимое решение двойственной задачи, т.к. оно удовлетворяет ограничениям двойственной задачи. Теперь покажем, что у0 - оптимальное решение.

T(y0) = y0 b = c0 B-1 b = c0 x0 = z (x0), где х0 - оптимальное решение, у0 - оптимальное решение двойственной задачи.