Двойственные задачи линейного программирования. Лекция 3

Рассмотрим задачу линейного программирования в виде
Назовем эту задачу исходной.
Постановка двойственной задачи линейного программирования
Тогда двойственной к ней будет называться задача вида

Двойственная задача линейного программирования ставится следующим образом.
1. В исходной задаче в двойственной
2. Коэффициенты при переменных в целевой функции исходной задачи являются коэффициентами в правой части при ограничениях двойственной задачи.
3. Коэффициенты при переменных в целевой функции двойственной задачи равны свободным коэффициентам ограничений исходной задачи.
Постановка двойственной задачи линейного программирования

4. Свободный коэффициент функции F равен свободному коэффициенту функции L.
5. Матрица коэффициентов ограничений двойственной задачи является транспонированной к соответствующей матрице исходной задачи.
6. Ограничения в исходной задаче имеют вид а в двойственной –
Между решениями исходной задачи и двойственной имеется тесная связь.
Постановка двойственной задачи линейного программирования

Лемма (основное неравенство)
Пусть и – допустимые наборы (то есть опорные планы) исходной и двойственной задач соответственно.
Тогда
Доказательство.
Обозначим для любого дополнительные переменные исходной задачи и для любого дополнительные переменные двойственной задачи.
Лемма (основное неравенство)

Рассмотрим
поскольку
для любого Отсюда
Теперь рассмотрим
поскольку
для любого Отсюда
Сравниваем полученные неравенства и замечаем, что
Тогда
Лемма доказана.
Лемма (основное неравенство)

Теорема (о двойственных задачах)
Пусть и – допустимые наборы исходной и двойственной задач соответственно. Равенство имеет место тогда и только тогда, когда и являются решениями соответствующих задач.
Если не ограничена сверху то область допустимых решений двойственной задачи пуста.
Теорема о двойственных задачах

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

Замечание.
Обратное ко второму утверждению неверно. Если область допустимых решений двойственной задачи пуста, то из этого не следует, что
Область допустимых решений исходной задачи также может быть пуста.
Теорема о двойственных задачах

Установим соответствие между переменными.
Соответствие между исходной и двойственной задачами линейного программирования

Лемма (о дополняющей нежесткости)
Пусть и – решения исходной и двойственной задачи соответственно. Выполнены следующие соотношения.
1). Если то
2). Если то
3). Если то
4). Если то
Лемма о дополняющей нежёсткости

Доказательство.
Рассмотрим
С другой стороны,
Заметим, что так и – решения, то
а, следовательно,
Отсюда,
Тогда получаем, что
Лемма о дополняющей нежёсткости

Но поскольку получаем
Так как то
для любого и для любого
Отсюда и следует утверждение леммы. Лемма доказана.
Лемма о дополняющей нежёсткости

Замечание.
Из второй теоремы двойственности для рассматриваемых симплекс-таблиц следует, что переменные, соответствующие базисным переменным исходной задачи, равны 0. Переменные, соответствующие свободным переменным исходной задачи, будут равны соответствующим числам первой строки (строки ) с противоположным знаком.
Следствие из второй теоремы двойственности

Пример решения двойственной задачи.
Вариант 50

Задача, соответствующая этой симплекс-таблице имеет вид
Ограничения можно записать в виде
Пример решения двойственной задачи

Двойственная задача ставится следующим образом
Пример решения двойственной задачи
Дополнительные переменные двойственной задачи удовлетворяют неравенствам

Было получено решение исходной задачи.
Пример решения двойственной задачи

Из второй теоремы двойственности
По лемме о дополняющей нежесткости
следовательно,
Это совпадает с полученными результатами.
Пример решения двойственной задачи

В двойственной задаче линейного программирования целевая функция …
исследуется на минимум;
исследуется на максимум;
неотрицательна;
равна нулю.
Задания для самоконтроля

Задания для самоконтроля
2. Ограничения в двойственной задаче задаются при помощи знаков…

3. Свободные коэффициенты целевых функций в прямой и двойственной задаче линейного программирования…
положительны;
равны;
взаимно обратны;
отличаются знаком.
Задания для самоконтроля

Задания для самоконтроля
4. Матрица коэффициентов ограничений двойственной задачи по отношению к соответствующей матрице исходной задачи является…
обратной;
вырожденной;
транспонированной;
противоположной.