Элементы теории двойственности в линейном программировании
Пусть дана задача линейного программирования в симметричной форме записи
1)
(1)
Приведем определение еще одной задачи линейного программирования, тесно связанной с задачей (1).
Определение 1. Задача линейного программирования
………
при условиях
,
,
где вектор 
, называется двойственной к задаче (1).
В теории двойственности задачу (1)принятоназывать прямой. Легко убедиться, что задача, двойственная к двойственной, является прямой задачей линейного программирования. В связи с этим часто пару задач линейного программирования (прямую и двойственную к ней) называют парой взаимосопряженных задач линейного программирования.
Пусть теперь прямая задача линейного про-
граммирования записана в канонической форме
юю.юююююююююю(1)
(2)
Тогда задача двойственная к (2) определяется следующим образом:
………
при условиях
.
Многогранную область пространства 
, определяемую ограничениями двойственной задачи, будем обозначать 
.
Следующие три теоремы устанавливают свойства взаимосопряженных задач линейного программирования, вытекающие непосредственно из их определения.
Теорема 1. Пусть дана пара взаимосопряженных задач линейного программирования в симметричной форме, векторы 
и 
.
Тогда
.(3)
Доказательство. Легко увидеть, что из ограничений прямой и двойственной задач линейного программирования следуют неравенства:
.
Из них и получаем неравенство (3).
|
|
|
Теорема 2. Пусть дана пара взаимосопряженных задач линейного программирования в симметричной форме, векторы 
и 
таковы, что
. (4)
Тогда векторы 
являются решениями, соответственно, прямой и двойственной задач линейного программирования.
Доказательство. Из теоремы 1 следует, что
для любого . Отсюда и из равенства (4) имеем 
для любого . Таким образом, 
– решение прямой задачи линейного программирования. Второе утверждение теоремы доказывается аналогично.
Теорема 3. Для того, чтобы множество 
было пустым, достаточно, чтобы функция 
была неограниченна снизу на множестве .
Справедливость этого утверждения следует непосредственно из теоремы 1.
Очевидно, что утверждение теоремы 3 в применении к двойственной задаче принимает вид:
Для того, чтобы множество было пус-тым, достаточно, чтобы функция 
была неограниченна сверху на множестве .
Теорема 4. (Теорема двойственности) Пусть одна из пары взаимосопряженных задач линейного программирования в симметричной форме имеет решение. Тогда и двойственная к ней задача тоже имеет решение и для любых векторов 
и 
выполняется равенство
. (5)
Доказательство. Пусть имеет решение прямая задача линейного программирования. Тогда из теоремы 11.4 следует, что найдется такой вектор 
, что вектор 
– седловая точка функции Лагранжа прямой задачи. Таким образом, 
при всех 
. Отсюда, учитывая то, что для задачи (1) функция Лагранжа имеет вид 
, получаем неравенства 
при всех . Перепишем их в виде 
|
|
|
при всех 
, . Отсюда, так как функция Лагранжа для двойственной задачи имеет вид 
, получаем
. Последние неравенства означают, что вектор 
является седловой точкой функции Лагранжа для двойственной задачи. Тогда из теоремы 11.4 следует, что вектор 
– решение двойственной задачи линейного программирования.
Для доказательства второго утверждения теоремы выберем точки 
и . Так как 
– решение прямой задачи, то по теореме 11.4 существует вектор 
такой, что 
– седловая точка функции Лагранжа прямой задачи.Следовательно, как доказано выше, 
ивыполняется условие 
, то есть 
. С другой стороны, аналогично, вектор 
–седловая точка функции Лагранжа двойственной задачи, а значит, выполняется условие 
, то есть 
. Таким образом, 
. Откуда, учитывая, что 
, получаем равенство (5). Что и требовалось.
Заметим, что все результаты этого параграфа были изложены применительно к задачам линейного программирования в симметричной форме. Аналогичные утверждения справедливы и для за-дач в других формах записи с небольшими изменениями, связанными только лишь с конкретной формой.
|
|
|
Подводя итоги полученным в этом параграфе результатам, можно сделать вывод, что имеет место одна из следующих ситуаций:
– обе взаимосопряженные задачи линейного программирования имеют решения;
– обе задачи не имеют решений, так как целевая функция одной из задач неограниченна на допустимой области, а допустимая область двойственной к ней задачи пуста;
– обе задачи не имеют решений, так как их допустимые области пусты.
Дата добавления: 2015-12-16; просмотров: 14; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!