Любому допустимому решению двойственной задачи

Прямой задачи, не больше значения функции Z, соответствующего

Теорема 2. Значение функции F, соответствующее любому допустимому решению

Доказательство: Пусть X и Y соответственно произвольные допустимые решения

прямой и двойственной задач. Следовательно,

1) Ах и Y Y^Т , Y^TAX Y^Tb = b^TY = Z.

2) A^TY C и X 0 X^Т , X^TA^TY X^TC = C^TX = F.

3) выражение X^TA^TY – скалярная величина (число) она равна своей

транспозиции, т.е. X^TA^TY = Y^TAX. Итак, имеем,

F X^TA^TY = Y^TAX Z F Z. Что и требовалось доказать.

Следствия: 1) если в прямой задаче допустимая область не пуста, а целевая функция не

ограничена сверху, то у двойственной задачи допустимая область пуста;

2) если в двойственной задаче допустимая область не пуста, а целевая

функция не ограничена снизу, то у прямой задачи допустимая область

пуста.

Теорема 3. Если прямая задача имеет конечное оптимальное решение F = F_max, то

двойственная задача имеет конечное оптимальное решение Z = Z_min. При

этом F_max = Z_min, а симплекс-множители оптимального решения прямой

Дата добавления: 2014-01-13