![]() |
![]() |
Мастерская программиста Гирича Семёна Николаевича Решение задач линейного программирования |
|||||||||||
![]() |
|||||||||||||
|
|||||||||||||
![]() |
5. Двойственная задача |
5.1. Понятие двойственной задачи ЛП 5.2. Общая схема построения двойственной задачи 5.3. Пример построения двойственной задачи 5.1. Понятие двойственной задачи ЛП. Пусть задана каноническая задача ЛП
Если целевая функция f(x) = cx достигает максимального значения на множестве D, то обоснованным представляется вопрос о том, каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить некоторый m-мерный вектор, то cx = cx+u(-Ax+b) = (c-uA)x+bu Предположим, что и можно выбрать таким образом, чтобы иА ≥ с. Тогда при любых х≥0 справедливо неравенство сх≤bи (5.2) Стремясь получить наилучшую оценку (5.2), мы приходим к формулировке некоторой новой экстремальной задачи, которая в некотором смысле логически сопряжена с задачей (5.1) и называется двойственной. Оговоримся, что приведенные рассуждения не носят строгого характера и предназначены только для того, чтобы подготовить читателя к приводимому ниже формальному определению двойственной задачи линейного программирования. Если задана каноническая задача ЛП
то задача ЛП
называется двойственной по отношению к ней. Соответственно, задача (D, f) no отношению к (D*, f*) называется прямой (или исходной). 5.2. Общая схема построения двойственной задачи. Приведенное выше определение задачи, двойственной по отношению к канонической ЗЛП, может быть распространено на случай общей задачи линейного программирования. Если задана общая задача ЛП
где D определяется системой уравнений и неравенств то двойственной по отношению к ней называется общая задача ЛП
где D* определяется системой уравнений и неравенств Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной: 1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот. 2. Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами. 3. Матрица ограничений задачи А транспонируется. 4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, хj≥0 или ui≥0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (аjи≥сj или aix≤bi). 5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче (например, aix≤bi или аjи≥сj), определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче (ui≥0 или хj≥0). Из приведенного определения вытекает важное свойство — симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, совпадает с прямой (исходной) задачей: ((D*)*, (f*)*)≡(D, f), Тем самым имеет смысл говорить о паре взаимно двойственных задач. В матричной форме пара двойственных общих задач линейного программирования может быть кратко записана как:
и
5.3. Пример построения двойственной задачи Рассмотрим процесс построения двойственной задачи на конкретном примере. Пусть задана ОЗЛП fmax(x)= 5x1 -2x2 +7x3 +4x4 -3x5 D={x 4x1 +x2 -x3 +x4 ≤2, 5x2 +x3 -6x4 +2x5 =4, 2x1 +3x2 +6x3 +x4 -3x5≤5, x2, x5≥0 } тогда двойственной к ней будет задача f*min(u)= 2u1 +4u2 +5u3 D={u 4u1 +2u3=5, u1 +5u2 +3u3≥ -2, -u1 + u2 +6u3=7, u1 -6u2 + u3=4, 2u2 -3u3≥ -3, u1, u3≥0 }
Источник:
|
|
![]() |
![]() |
![]() |
|||||
© 2011 Семён Гирич, |
|
![]() ![]() |
|||||
![]() |
![]() |
![]() |