Доказательство: Запишем прямую задачу

Двойственной задачи.

Задачи являются значениями переменных в оптимальном решении

Ах , x 0, b , F = C^Tx .

Запишем задачу в стандартном виде Ах + х^Р = b, где х^Р = (х₁,…,х_n+m)-

дополнительные, уравновешивающие переменные, ^Т-

симплекс-множители оптимального решения. Известно, что прямая задача

разрешима, следовательно, можно определить значения симплекс-

множителей оптимального решения. Получим оптимальное выражение

целевой функции, то есть

+

(-С^T+)x+= F + b^T. (*)

Так как это оптимальный вид целевой функции, то все коэффициенты

неотрицательны.

или .

Т.о., если y = , то ограничения двойственной задачи выполняются.

Так как (*) – оптимальный вид целевой функции, то коэффициенты перед

базисными переменными равны нулю, а свободные переменные сами равны

нулю F_min = -b^T или F_max = b^T. Если y = , то это и есть целевая

функция двойственной задачи, то есть Z = F_max = Z_min. Что и требовалось

доказать.

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

то прямая задача имеет конечное оптимальное решение F = F_max. При

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

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