Математические методы теории принятия решений: Курс лекций, страница 4

Z=2x₁ + 3x₂ = 8 – 2x₁ + 3x₂ ® max

x₃ = 2 + x₅ – x₂                     (1)

x₄ = 4,5 + x₅ - 2x₂                (2)

x₁ = 4 – x₅                             (3)

x₆ = 3 – x₂                             (4)

Видно, что значение ЦФ выросло до величины Z = 8, а значения базовых переменных уменьшились: x₃ = 2, x₄ = 4,5. Свободная переменная x₁ = 4. На третьем шаге к нулю приравнивались значения переменных x₅ = 0 и x₂ = 0. Теперь уже точно определяется угол наклона линии ЦФ и значения, отсекаемые этой прямой на каждой из осей:
x₁ = 4 x₂ = 2,67. Тогда и направление ЦФ в начале координат также становится известным – оно параллельно линии Z = 8.

Четвертый шаг. Проделав аналогичные операции преобразования, для увеличения ЦФ только за счет x₂, и положив значение
x₂ =2 + x₅ - x₃ , получим следующие значения отыскиваемых переменных: x₁ = 4, x₂ = 2, x₃ = 0, x₄ = 0,5, x₅ = 0, x₆ = 1. Здесь в качестве базовых переменных были x₃ и x₅. Значение Z = 14 проходит через новую угловую точку С(4;2) параллельно линии Z = 8.

Пятый шаг. Осталась возможность улучшить значение ЦФ за счет x₅. Поскольку x₅ = 0,5 + 2x₃ - x₄, получим преобразованную систему уравнений:

Z = 2x₁ + 3x₂ = 14,5 – x₃ - x₄ ® max

x₂ = 2,5 + x₃ – x₄                          (1)

x₄ = x₁ =2x₃ -2x₃ + x₄           (2)

x₁ = 3,5 –2x₃ + x₄                 (3)

x₆ = 0,5 –x₃ + x₄                   (4)

Поскольку на этом шаге свободными переменными оказались x₃, x₄, их значения надо приравнять к нулю. Тогда Z = 14,5; x₁ = 3,5;
x₂ = 2,5. Свободные же переменные значительно отличаются от их первоначальных значений: x₃ = 0 (а было равно 6); x₄ = 0 (было 8,5); x₅ = 0,5 (было 4); x₆ = 0,5 (было 3).

Таким образом, в случае решения линейных оптимизационных задач мы получили надежный математический аппарат, пригодный для решения задач и со многими переменными.

Но линейные задачи оптимизации обладают чудесными свойствами дополнительных информационных ресурсов.

Условия возникновения двойственности при оптимизации проблемных ситуаций, возникающих в экономике

Экономия ресурсов является наилучшей характеристикой эффективности планово-экономической работы на предприятии. В связи с этим вопросом сформулируем такую задачу.

Для выпуска двух видов изделий  используются отходы 4-х видов  в количестве 15, 18, 16 и 8 единиц . Затраты отходов на единицу изделия составляют: для 1-го изделия – 3, 2, 4, 1; для 2-го – 3, 6, 0, 2 (ед. отходов/ед. изделия). Предполагаемая величина прибыли: для первого изделия  ден.ед., для 2-го  денежных единиц.

При каких условиях возможна, вместо организации производства, продажа отходов руководством фирмы другому покупателю?

Сопоставим величину прибыли  со стоимостью отходов :

где - стоимость единицы отходов - ресурса [ден.ед./ед.рес.].

Позиция руководства фирмы:

позиция покупателя:

Это значит, что покупатель признает позицию производителя, а именно: , но сам бы он хотел минимизировать сумму денежных расходов на ресурсы.

Требования производителя описываются следующими соотношениями:

Это постановка прямой задачи (А); требование покупателя
(В) – это двойственная постановка («ДЗ») той же задачи.

Неравенство (3) является основным неравенством теории двойственности. На основе этого неравенства можно записать критерий оптимальности Канторовича:

где звездочкой «*» отмечены оптимальные значения X_j и V_i.

В теории двойственности рассматриваются три теоремы, основное содержание которых сводится к следующему.

Первая теорема двойственности математически строго доказывается на основе соотношения (4). Если одна из двойственных задач имеет оптимальное решение, то и другая его имеет. Причем экстремальные значения целевых функций совпадают. Если же в одной задаче целевая функция не ограничена, то двойственная ей задача противоречива.

Вторая теорема двойственности. Допустимые решения  исходной и  двойственной задачи будут оптимальными тогда и только тогда, когда выполнены каждая из следующих групп соотношений: