7. Теоремы двойственности и их экономический смысл.

7.Двойственность в линейном программировании. Связь между двойственными задачами. Основные теоремы двойственности и их экономический смысл.

Пусть на предпри­ятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы сырья т видов в объемах b_i единиц (i = 1,…, m). Из этих отходов можно наладить выпуск п видов неосновной продукции. а_ij - норма расхода сырья i-го вида на единицу j-ой (j = 1,…, п) продукции, с_j - цена реализации единицы j-й продукции. Неизвестные величи­ны: х_j - объемы выпуска j-ой продукции, обеспечи­вающие предприятию максимум выручки.

 (1)

Предположим, что на предприятии появилась возможность реал-ции отходов некоторой орг-ции. Надо установить прикидочные оценки (цены) y₁,…y_m на эти отходы. Оценки должны быть установлены исходя из следующих требований:

1) общую стоимость отходов сырья покупающая организация стремится мини­мизировать;                         

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

Эти требования форма­лизуются в виде следующей ЗЛП:

   (2):                                                      

Переменные y₁,…y_m называются двойственными оценками. Из (1), (2) можно показать, что если в качестве прямой принять задачу (2) об определении оптимальных оценок на сырье, то двойственной к ней будет задача (1) об определении оптимального плана выпуска про­дукции. Имея матем. модель одной из задач, можно построить модель двойственной к ней задачи. Задача, двойственная двойственной, сов­падает с исходной, поэтому безразлично, какую задачу принять в качестве прямой, а какую – в качестве двойственной. Свойства двойственных задач:

1. Если прямая задача на max, то двойственная к ней – на min, и наоборот.

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

3. Число переменных прямой задачи = числу ограничений двойственной, и наоборот..

4. Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу.

5. Коэфф-ты целевой ф-ии прямой задачи явл-ся свободными членами ограничений двойственной задачи, и наоборот.

6. Число ограничений прямой задачи = числу пере­менных двойственной, а число ограничений двойствен­ной = числу переменных прямой.

7. Все переменные в обеих задачах неотрицательны.

            Основные теоремы двойственности и их экономическое содержание

            Теорема1(основное нер-во двойс-ти) Для любых допустимых планов Х =   и   Y =   прямой и двойственной ЗЛП справед­ливо неравенство F(X) Z(Y), т. е.

                                                          (3.3)

Доказательство. Учитывая ограничения обеих ЗЛП, получаем

т. е. имеем неравенство (3.3), которое называется основ­ным неравенством теории двойственности.

Экономическое содержание неравенства (3.3) состоит в том, что для любого допустимого плана производства Х и любого допустимого вектора оценок ресурсов Y общая созданная стоимость не превосходит суммарной оценки ресурсов.

            Теорема 2. (критерий оптимальности Канторовича). Если для некоторых допустимых планов Х* и Y* пары двойственных задач выполняется равенство z(X*) = f(Y*), то Х* и Y*являются оптимальными планами соответст­вующих задач.

Доказательство. Согласно основному неравенству двойственности, для любого допустимого плана Х прямой задачи и допустимого плана Y* двойственной справедливо неравенство z(X)   f(Y*). Но по условию  z(X*) = f(Y*). Отсюда, в силу транзитивности отношений   и =, получим z(X)   z(X*). Так как Х - произвольный план, то z(X*) = max Z, т.е. Х* - оптимальный план прямой ЗЛП.

Аналогично доказывается, что план Y* является опти­мальным для двойственной задачи.

Экономическое содержание теоремы 3.2 состоит в том, что план производства Х и вектор оценок ресурсов Y явля­ются оптимальными, если цена всей произведенной про­дукции и суммарная оценка ресурсов совпадают.

            Теорема 3 (малая теорема двойственности). Для су­ществования оптимального плана любой из пары двойст­венных задач необходимо и достаточно существование допустимого плана для каждой из них.

 

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

            Рассмотрим пару симметричных двой­ственных задач представленных выше. Введем доп. переменные х_n+1, ..., х_n+m в прямую зада­чу и  y_m+1, ..., у_т+п в двойственную, приводим модели задач к канони­ческому виду. Теперь м/у переменными двойственных задач можно установить соответствие, сопоставляя свободнвм перемен­ным одной задачи базисные переменные другой, и на­оборот:

Экономическое содержание: если задача определения оптимального плана, максимизирующего выпуск продук­ции, разрешима, то разрешима и задача определения оценок ресурсов. Причем цена продукции, полученной при реализации оптимального плана, совпадает с суммар­ной оценкой ресурсов. Совпадение значений целевых ф-ций для соответствующих планов пары двойственных задач достаточно для того, чтобы эти планы были опти­мальными. Двойст­венные оценки обладают тем свойством, что гаранти­руют рентабельность оптимального плана и позволяют сопоставить и сбалансировать затраты и результаты системы. Т.о., оптимальность плана означает точное воплощение в оценке произведенной по этому плану про­дукции оценки всех израсходованных ресурсов, т.е. пол­ное отсутствие непроизводительных затрат.

            Теорема 5 (о дополняющей нежесткости). Для того чтобы планы х* и у* пары двойственных задач были опти­мальными, необходимо и достаточно выполнение условий:

,      .

Экономическое содержание: двойственные оценки могут служить мерой дефицитности ресурса. Если они   0, то в силу условия дополняющей жесткости разница между расходом ресурса и его запасом должна = 0, т.е. ресурс является дефицитным и расходуется в процессе производства полностью. Если же расход ресурса < используемого запаса, т.е. ресурс недефицитный, то в силу условия дополняющей жесткости, ее двойственная оценка = 0.

            Теорема 6 (об оценках). Двойственные оценки пока­зывают приращение ф-ции цели, вызванное малым из­менением свободного члена соответствующего ограниче­ния задачи математического программирования, точнее . Двойственные оценки характеризуют эластичность оптимального плана по каждому виду ресурсов, =>, перейдя от дифференциалов к конечным приращениям можно получить   оценку изменения прибыли в зависимости от изменения ресурсов , при   имеем  .

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

НА 8 ВОПРОС НЕ ОТВЕТИЛА!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!