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

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

Исходная задача Двойственная задача
Стандартная форма записи
Понятие о двойственных задачах линейного программирования - student2.ru Понятие о двойственных задачах линейного программирования - student2.ru (4.1) Понятие о двойственных задачах линейного программирования - student2.ru . Понятие о двойственных задачах линейного программирования - student2.ru Понятие о двойственных задачах линейного программирования - student2.ru ; (4.2) Понятие о двойственных задачах линейного программирования - student2.ru .
Каноническая форма записи
Понятие о двойственных задачах линейного программирования - student2.ru Понятие о двойственных задачах линейного программирования - student2.ru ; (4.3) Понятие о двойственных задачах линейного программирования - student2.ru . Понятие о двойственных задачах линейного программирования - student2.ru Понятие о двойственных задачах линейного программирования - student2.ru ; (4.4) Понятие о двойственных задачах линейного программирования - student2.ru .
Оптимальное решение
Понятие о двойственных задачах линейного программирования - student2.ru . Понятие о двойственных задачах линейного программирования - student2.ru .

Связь исходной и двойственной задач состоит в том, что

1) коэффици­енты Понятие о двойственных задачах линейного программирования - student2.ru целевой функции исходной задачи являются свободными членами системы ограничений двойственной задачи;

2) свободные члены Понятие о двойственных задачах линейного программирования - student2.ru систе­мы ограничений исходной задачи служат коэффициентами целевой функции двойственной задачи;

3) матрица коэффициентов системы ограни­чений двойственной задачи является транспонированной матрицей коэффициентов системы ограничений исходной задачи;

4) одна из взаимно двойственных задач на максимум, а другая на минимум.

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

Первая теорема двойственности. Если одна из взаимно двойственных задач ЛП имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их целевых функций равны: Понятие о двойственных задачах линейного программирования - student2.ru ( Понятие о двойственных задачах линейного программирования - student2.ru ).

Если целевая функция одной из задач не ограничена, то условия другой задачи противоречивы.

Установим взаимнооднозначное соответствие между переменными взаимно двойственных задач в виде следующей схемы:

Переменные исходной задачи
Первоначальные переменные Балансовые переменные
Понятие о двойственных задачах линейного программирования - student2.ru   Понятие о двойственных задачах линейного программирования - student2.ru
Балансовые переменные Первоначальные переменные
Переменные двойственной задачи

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

Следствие ко второй теореме двойственности. Положительным (ненулевым) компонентам оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи:

1) если Понятие о двойственных задачах линейного программирования - student2.ru или Понятие о двойственных задачах линейного программирования - student2.ru ;

2) если Понятие о двойственных задачах линейного программирования - student2.ru или Понятие о двойственных задачах линейного программирования - student2.ru .

Следствие к третьей теореме двойственности: i-ую компоненту оптимального решения двойственной задачи Понятие о двойственных задачах линейного программирования - student2.ru можно найти из равенства Понятие о двойственных задачах линейного программирования - student2.ru , где Понятие о двойственных задачах линейного программирования - student2.ru - это изменение оптимального значения целевой функции исходной задачи, вычисленное в предположении, что правая часть i-го ограничения изменилась на Понятие о двойственных задачах линейного программирования - student2.ru единиц. Равенство справедливо только для достаточно малых значений Понятие о двойственных задачах линейного программирования - student2.ru .

Задача №4.1.

Построить и решить с использованием теории двойственности задачу двойственную задаче №1.1.

Решение.

Таблица с данными к задаче №1.1

  Понятие о двойственных задачах линейного программирования - student2.ru Понятие о двойственных задачах линейного программирования - student2.ru запасы
Понятие о двойственных задачах линейного программирования - student2.ru
Понятие о двойственных задачах линейного программирования - student2.ru
Понятие о двойственных задачах линейного программирования - student2.ru
Понятие о двойственных задачах линейного программирования - student2.ru
доход  
Исходная задача Двойственная задача
Стандартная форма записи
Понятие о двойственных задачах линейного программирования - student2.ru Понятие о двойственных задачах линейного программирования - student2.ru Понятие о двойственных задачах линейного программирования - student2.ru . (4.5) Понятие о двойственных задачах линейного программирования - student2.ru Понятие о двойственных задачах линейного программирования - student2.ru Понятие о двойственных задачах линейного программирования - student2.ru (4.6) Понятие о двойственных задачах линейного программирования - student2.ru .
Каноническая форма записи
Понятие о двойственных задачах линейного программирования - student2.ru Понятие о двойственных задачах линейного программирования - student2.ru Понятие о двойственных задачах линейного программирования - student2.ru . Понятие о двойственных задачах линейного программирования - student2.ru   Понятие о двойственных задачах линейного программирования - student2.ru Понятие о двойственных задачах линейного программирования - student2.ru (4.7) Понятие о двойственных задачах линейного программирования - student2.ru .  

Согласно первой теореме двойственности Понятие о двойственных задачах линейного программирования - student2.ru , так как Понятие о двойственных задачах линейного программирования - student2.ru , то Понятие о двойственных задачах линейного программирования - student2.ru .

Установим взаимнооднозначное соответствие между переменными взаимно двойственных задач в виде схемы:

Переменные исходной задачи
Первоначальные переменные Балансовые переменные
Понятие о двойственных задачах линейного программирования - student2.ru Понятие о двойственных задачах линейного программирования - student2.ru
Балансовые переменные Первоначальные переменные
Переменные двойственной задачи

Для нахождения компонент оптимального решения двойственной задачи, воспользуемся решением исходной задачи Понятие о двойственных задачах линейного программирования - student2.ru , полученным в задаче № 3.1

Так как Понятие о двойственных задачах линейного программирования - student2.ru ;

Понятие о двойственных задачах линейного программирования - student2.ru ;

Понятие о двойственных задачах линейного программирования - student2.ru ;

Понятие о двойственных задачах линейного программирования - student2.ru .

Подставляя в систему ограничений (4.7) нулевые значения переменных Понятие о двойственных задачах линейного программирования - student2.ru , получим систему: Понятие о двойственных задачах линейного программирования - student2.ru Понятие о двойственных задачах линейного программирования - student2.ru Решив, которую, найдем недостающие компоненты оптимального решения двойственной задачи: Понятие о двойственных задачах линейного программирования - student2.ru .

Оптимальное решение двойственной задачи имеет вид Понятие о двойственных задачах линейного программирования - student2.ru .

Замечание. Задача №1.1 и двойственная задача к задаче № 1.1 были решены симплексным методом в §3. Для того, чтобы убедиться в справедливости второй теоремы двойственности выпишем выражения целевых функций через свободные переменные на последнем шаге и

решения этих задач

Исходная задача Двойственная задача
Целевая функция на последнем шаге
Понятие о двойственных задачах линейного программирования - student2.ru Понятие о двойственных задачах линейного программирования - student2.ru .
Оптимальное решение
Понятие о двойственных задачах линейного программирования - student2.ru . Понятие о двойственных задачах линейного программирования - student2.ru .

Компоненты оптимального решения двойственной задачи Понятие о двойственных задачах линейного программирования - student2.ru равны коэффициентам при соответствующих переменных целевой функции прямой задачи, взятым по абсолютной величине. Аналогично, компоненты оптимального решения прямой задачи Понятие о двойственных задачах линейного программирования - student2.ru равны коэффициентам при соответствующих переменных целевой функции двойственной задачи, взятым по абсолютной величине.

Наши рекомендации