Решение оптимизационных задач средствами EXCEL




Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений. - часть 3


(теорема о дополняющей нежесткости)

Пусть X=(x1,x2,...xn) - допустимое решение прямой задачи, а Y= (y1,y2,...ym) - допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задач необходимо и достаточно, чтобы выполнялись следующие соотношения:

                                                      *

                                                      **

Условия (*) и (**) позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой задачи.

Из второй теоремы двойственности в данном случае следуют такие требования на оптимальную производственную программу X=(X1,X2,...,Xn) и оптимальный вектор оценок Y=(Y1,Y2,...,Ym):

     (4)

        (5)

Условия (4) можно интерпретировать так: если оценка yi единицы ресурса i-го вида положительна, то при оптимальной производственной программе этот ресурс используется полностью, если же ресурс используется не полностью, то его оценка равна нулю. Из условия (5) следует, что если j-й вид продукции вошел в оптимальный план, то он в оптимальных оценках неубыточен, если же j-й вид продукции убыточен, то он не войдет в план, не будет вы­пускаться.

Рассмотрим еще одну теорему, выводы которой будут использованы в дальнейшем.

Теорема об оценках.

Значения переменных Yi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений-неравенств прямой задачи на величину

                                                                           

Решая ЗЛП  симплексным методом, мы одновременно решаем двойственную ЗЛП. Переменные двойственной задачи yi называют объективно обусловленными оценками.

Рассмотрим экономическую интерпретацию двойственной задачи на примере задачи оптимального использования ресурсов.

Пример. Сформулируем экономико-математическую модель двойственной задачи к задаче о коврах.

Прямая задача:

f(x) = 3Х1 +4Х2 +3Х3 +1Х4

Ограничения по ресурсам




Содержание  Назад  Вперед