Если обе задачи решаются прямым симплекс-методом)

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

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

Доказательство: В матричной форме двойственная задача имеет вид.

А^Тy C, y 0, С 0,Z =

1) Запишем в стандартном виде A^Ty – y^S = C, где y^S= (y_m+1,…,y_m+n)^T 0 –

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

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

двойственной задачи имеют то же значение, то есть

+

(b^T + = Z + . (**)

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

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

или .

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

удовлетворяются, значит это решение.

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

коэффициенты перед базисными переменными равны нулю, а свободные

переменные сами равны нулю. Следовательно,

Z_min = -, а это есть целевая функция прямой задачи,

если . Что и требовалось доказать.

Экономическое содержание теорем состоит в следующем: если задача оптимизации плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения оценок ресурсов. План производства и оценки ресурсов являются оптимальными тогда и только тогда, когда цена произведенной продукции и суммарная оценка ресурсов совпадают. Оценки выступают как инструмент балансирования затрат и результатов. Так как F Z, Z – F = - издержки производства, которые равны нулю когда F^* = Z^*.

Двойственные оценки обладают тем свойством, что они гарантируют рентабельность оптимального плана, то есть равенство общей оценки продукции и ресурсов, и обуславливают убыточность всякого другого плана, отличного от оптимального.

Кроме того, если y_i > 0, то при оптимальной производственной программе этот ресурс используется полностью; если y_i = 0, то ресурс используется не полностью.

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