Первая теорема двойственности.
Если х - оптимальное решение исходной задачи, то двойственная задача также имеет оптимальное решение у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 - оптимальное решение двойственной задачи.