Теорема двойственности

Оглавление
Введение 3
1. Составление математических моделей двойственных задач 4
2. Первая теорема двойственности 7
3. Вторая теорема двойственности 11
4. Экономическое содержание первой теоремы двойственности 13
5. Экономическая интерпретация второй теоремы двойственности и ограни- чений двойственной задачи 17
Список литературы 22

3. Таха, Хемди А. Введение в исследование операций, 7-е издание: Пер. с англ. — М.: Издательский дом "Вильяме", 2005.
...

2. Первая теорема двойственности
Теоремы двойственности устанавливают взаимосвязь между оптимальными решениями пары двойственных задач. Решив одну из пары двойственных задач, можно или найти оптимальное решение другой задачи, не решая её, или установить его отсутствие.
Возможны следующие случаи:
• обе задачи из пары двойственных задач имеют оптимальные решения;
• одна из задач не имеет решения ввиду неограниченности целевой функции, а другая не имеет решения ввиду несовместности системы ограничений.
Теорема 1. 1. Если одна из пары двойственных задач имеет оптимальное решение, то и двойственная к ней задача тоже имеет оптимальное решение. При этом значения целевых функций задач на своих оптимальных решениях совпадают.
2. Если одна из пары двойственных задач не имеет решения ввиду неограниченности целевой функции, то другая задача не имеет решения ввиду несовместности системы ограничений.
Пример.
...

3. Вторая теорема двойственности
Пусть имеем симметрическую пару двойственных задач:

(7)


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

(8)

(9)

Иначе, если при подстановке оптимального решения в систему ограничений i-е ограничение исходной задачи выполняется как строгое неравенство, то i-я координата оптимального решения двойственной задачи равна нулю.
Наоборот, если i-я координата оптимального решения двойственной задачи отлична от нуля, то i-е ограничение исходной задачи удовлетворяется оптимальным решением как равенство.
Теорема 2 называется теоремой о дополняющей нежёсткости. Она показывает следующее.
a) Если, то ; если , то
b) Точно так же, если то если , то

Здесь и ˗ оптимальные решения пары двойственных задач.
Пример. Для данной задачи составить двойственную, решить её графическим методом и, используя теорему 2, найти решение исходной задачи:
;


Решение.
...

4. Экономическое содержание первой теоремы двойственности
Задачу линейного программирования можно рассматривать как модель
распределения ограниченных ресурсов, в которой целевая функция, отображающая прибыль или доход от производственной деятельности, подлежит максимизации [3, с. 158]. Если рассматривать задачу линейного программирования с этой точки зрения, соответствующая ей двойственная задача получает интересную экономическую интерпретацию.
Экономическое содержание первой теоремы двойственности (теорема 1) состоит в следующем: если задача определения оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения оценок ресурсов. Причем цена продукции, полученной при реализации оптимального плана, совпадает с суммарной оценкой ресурсов. Совпадение значений целевых функций для соответствующих планов пары двойственных задач достаточно для того, чтобы эти планы были оптимальными.
...