Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Теория двойственности в линейном программировании
|
|
Любой задаче математического программирования можно поставить в соответствие так называемую двойственную задачу оптимизации. Между этими задачами обнаруживаются тесные связи, изучение которых составляет предмет теории двойственности. Эта теория тесно связана с теорией условий оптимальности.
В данной книге мы рассмотрим теорию двойственности только применительно к задачам линейного программирования. Что касается общей теории двойственности, ее основы обстоятельно изложены в книге [1].
1. Общая схема построения двойственной задачи. Двойственная задача к задаче линейного программирования также является задачей линейного программирования, причем, как будет видно из определения, ее можно выписать в явном виде с помощью данных исходной задачи.
| Определение 3.8.Если задана общая задача ЛП f (x) = c 1 x 1 +…+ cj xj + cj+ 1 xj+ 1 +…+ cn xn ® min, x Î X, (3.20) где Х определяется системой уравнений и неравенств: a 1, 1 x 1 + a 1, 2 x 2 + … + a 1, n xn ³ b 1, ... ai , 1 x 1 + ai , 2 x 2 + … + ai , n xn ³ bi, ai+ 1, 1 x 1 + ai+ 1, 2 x 2 + … + ai+ 1, n xn = bi+ 1, ... am , 1 x 1 + am , 2 x 2 + … + am , n xn = bm, x 1 ³ 0, …, xj ³ 0, то двойственной по отношению к ней называется общая задача ЛП g (x) = b 1 u 1 +…+ biui + bi+ 1 ui+ 1 +…+ bmum ® max, u Î U, (3.21) где Х * определяется системой уравнений и неравенств: a 1, 1 u 1 + a 2, 1 u 2 + … + am , 1 um £ c 1, ... a 1, j u 1 + a 2, j u 2 + … + am, j um £ cj, a 1, j+ 1 u 1 + a 2, j+ 1 u 2 + … + am.j+ 1 um = cj+ 1, ... a 1, n u 1 + a 2, n u 2 + … + am , n um = cn, u 1 ³ 0, …, ui ³ 0. Соответственно, задача (3.20) по отношению к задаче (3.21) называется прямой (или исходной). |
Из определения 3.8 вытекает важное свойство - симметричность отношения двойственности, т.е. задача, двойственная по отношению к двойственной, совпадает с прямой (исходной) задачей. Тем самым имеет смысл говорить о паре взаимно двойственных задач.
Подчеркнем, что перед тем как строить двойственную задачу, исходную задачу ЛП следует привести к виду (3.20).
Правила построения задачи, двойственной по отношению к общей задаче ЛП, наглядно представлены схемой, показанной на рис. 3.2.
| c 1 | … | cj | cj+ 1 | … | cn | ® | min | |||
| £ | £ | = | = | max | ||||||
| | ||||||||||
| 0£ | u 1 | a 1, 1 | … | a 1, j | a 1, j+ 1 | … | a 1, n | ³ | b 1 | |
| … | . | . | . | … | ||||||
| 0£ | ui | ai , 1 | … | ai, j | ai, j+ 1 | … | ai, n | ³ | bi | |
| ui+ 1 | ai+ 1, 1 | … | ai+ 1, j | ai+ 1, j+ 1 | … | ai+ 1, n | = | bi+ 1 | ||
| … | . | . | . | … | ||||||
| um | am , 1 | … | am, j | am, j+ 1 | … | am, n | = | bm | ||
| x 1 | … | xj | xj+ 1 | … | xn | |||||
| ³ 0 | ³ 0 |
Рис. 3.2.
Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:
1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.
2. Вектор коэффициентов целевой функции с и столбец ограничений b меняются местами.
3. Матрица ограничений А транспонируется.
4. Множество индексов переменных, на которые наложено условие неотрицительности в прямой задаче (например, xj ³ 0) определяют номера ограничений, имеющих форму неравенств в двойственной задаче.
5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче, определяют множество индексов переменных в двойственной задаче, на которые налагается ограничение неотрицательности, (иi ³ 0).
Особо отметим как выглядят двойственные задачи к ЗЛП в упомянутых ранее частных формах.
1. Двойственной к ЗЛП в основной форме
является ЗЛП в канонической форме
2. Двойственной к ЗЛП в канонической форме
является ЗЛП в основной форме
2. Теоремы двойственности. В следующей теореме собраны воедино основные факты теории двойственности в линейном программировании, называемые теоремами двойственности. Все они являются прямыми следствиями соответствующих утверждений общей теории двойственности.
Теорема 3.6. 1) Для любых точек х Î Х, u Î U справедливо неравенство 
2) точки x* Î X u u* Î U являются решениями задач (3.20) и (3.21) соответственно тогда и только тогда, когда справедливо соотношение двойственности
(3.22)
3) задача (3.20) имеет решение тогда и только тогда, когда имеет решение задача (3.21), при этом, в соответствии с (3.22), значения их целевых функций в точках оптимума совпадают;
4) если допустимые множества задач (3.20) и (3.21) непусты то обе они имеют решение;
5) если допустимое множество прямой задачи (3.20) непусто, а задачи (3.21) пусто, то целевая функция прямой задачи неограничена снизу, и наоборот, если допустимое множество двойственной задачи (3.21) непусто, а задачи (3.20) пусто, то целевая функция двойственной задачи неограничена сверху;
6) пусть х* и и* - решения задач (3.20) и (3.21), тогда если j-я компонента точки х* строго положительна (хj > 0), то соответствующее j-е ограничение двойственной задачи (3.21) выполняется как равенство; если же j-я компонента точки х* имеет нулевое значение (хj = 0), то j-е ограничение задачи (3.21) выполняется как неравенство.
Полное доказательство утверждений этой теоремы можно найти, например, в книгах [1] или [3].
Утверждение 2) теоремы 3.6 имеет ключевое значение в теории линейного программирования, так как оно дает необходимые и достаточные условия оптимальности, т. е. критерий оптимальности для данного класса задач.
Практическое значение теорем двойственности состоит в том, что они позволяют заменить процесс решения прямой задачи на решение двойственной, которое в определенных случаях может оказаться более простым. Например, задача, допустимое множество которой описывается двумя уравнениями, связывающими шесть переменных (m = 2, n = 6), не может быть решена графическим методом. Однако данный метод может быть применен для решения двойственной к ней задачи, которая имеет только две переменные.