- •Элементы линейнОй и нелинейнОй
- •Оптимизации
- •Москва, 2005
- •Введение
- •1. Производственная задача или задача планирования
- •2. Типы задач линейного программирования и их преобразование
- •3. Геометрическая трактовка основной задачи
- •4. Методы решения задач линейного программирования
- •4.1. Графический метод
- •4.2. Табличный симплекс-метод решения задачи линейного
- •4.2.1. Метод единичных векторов
- •4.2.2. Расширенная задача и метод искусственного базиса
- •5. Двойственные задачи линейного программирования
- •5.1.Прямая и двойственная задача
- •5.2. Геометрическая интерпретация двойственной задачи. Леммы и теоремы двойственности
- •5.3. Нахождение решений двойственных задач
- •5.4. Параметрическая устойчивость задачи линейного программирования и физическая трактовка двойственной задачи
- •6. Транспортная задача линейного программирования
- •6.1. Математическая постановка задачи
- •6.2. Нахождение опорного плана транспортной задачи
- •6.3. Оценка опорного плана транспортной задачи на оптимальность
- •7. Элементы теории игр
- •7.1. Предмет теории игр
- •7.2. Терминология и классификация игр
- •7.4. Смешанные стратегии
- •7.5. Геометрический метод решения игр
- •II. Нелинейное программирование
- •1. Задачи нелинейного программирования
- •2. Геометрическая интерпретация задач
- •3. Некоторые проблемы решения задач нелинейного
- •4. Решение задач условной оптимизации методом Лагранжа
- •5. Градиентные методы решения задач динамического
- •5.1. Метод наискорейшего спуска
- •5.2. Метод штрафных функций
- •5.3. Симплекс-метод поиска глобального экстремума
- •Контрольные вопросы к курсу «Методы оптимизации»
5. Двойственные задачи линейного программирования
5.1.Прямая и двойственная задача
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другого (но также линейного) типа задачу, называемую двойственной (или сопряженной) по отношению к исходной, или прямой.
Прямая ЗЛП заключается в том, чтобы найти максимум значения функции цели
(16)
при условиях ,
,
……………………………..
, (17)
,
………………………………….
,
, (j=1…l, l≤ n).
О п р е д е л е н и е. Задача, состоящая в нахождении минимального значения функции
(18)
при условиях
,
,
……………………………….
, (19)
,
………………………………
,
, (i=1…k, k ≤ m),
называется двойственной задачей по отношению к задаче (16)-(17).
Задачи (16)-(17) и (18)-(19) образуют пару задач, называемую в линейном программировании двойственной парой.
Сравнивая две сформулированные задачи, видим, что двойственная задача по отношению к исходной составляется согласно следующим правилам.
1.Функция цели прямой задачи задается на максимум (минимум), а функция цели двойственной задачи – на минимум (максимум).
2. Матрица коэффициентов при переменных в системе ограничений прямой задачи
и аналогичная матрица в двойственной задаче
получаются друг из друга транспонированием (т.е. строки становятся столбцами, а столбцы – строками).
3. Число переменных в двойственной задаче равно числу ограничений в прямой задаче, а число ограничений в двойственной задаче – числу переменных в прямой задаче.
4. Коэффициентами при переменных в функции цели двойственной задачи являются свободные члены в системе ограничений прямой задачи, т.е. вектор B=(b1, b2, b3, …, bm), а свободными членами в ограничениях двойственной задачи становятся коэффициенты при переменных в функции цели прямой задачи, т.е. вектор С=(с1, с2, с3, …, сn).
5. а) Если переменная xj в прямой задаче может иметь только положительное значение, то j – е ограничение в двойственной задаче является неравенством типа “ ≥ ” (в двойственной задаче не может быть ограничений –неравенств типа “ ≤ ”);
б) если переменная xj в прямой задаче может принимать любое (в том числе и отрицательное) значение, то соответствующее ограничение (т.е. j-е) в двойственной задаче записывается в виде уравнения (равенства);
в) если i – е ограничение в прямой задаче записано в форме неравенства, то i – я переменная yi в двойственной задаче будет принимать только положительное значение;
г) если i – е ограничение в прямой задаче записано в форме уравнения (равенства), то i – я переменная yi в двойственной задаче может принимать любое значение.
Вышеприведенные соотношения в формировании прямой и двойственной задач в кратком виде представлены в таблице 11.
Таблица 11
Алгоритмы записи прямой и двойственной ЗЛП
-
Прямая задача
Двойственная задача
→max
→min
, X ≥ 0
, Y ≥ 0
, X - любое
, Y ≥ 0
, X ≥ 0
, Y - любое
, Х - любое
, Y - любое
Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре ограничения как в прямой, так и в двойственной задаче выражаются через неравенства (соответственно все переменные – положительные числа).
З а д а ч а 8. Для задачи, состоящей в максимизации функции
при условиях ,
,
,
сформулировать двойственную задачу.
Р е ш е н и е . Для прямой и двойственной задач прежде всего составим матрицу коэффициентов в ограничениях:
, .
В соответствии с общими правилами задача, двойственная по отношению к прямой, формулируется следующим образом: найти минимум функции при условиях
,
,
,
.
Заметим, что в записанной двойственной задаче переменная y2 может принимать любое значение, так как второе ограничение прямой задачи - равенство.