Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 14
Текст из файла (страница 14)
Двоасввеняхть Если добавить ограничения хо х,)0 в прямой задаче, то она остается недопустимой, однако двойственная становится неограниченной, что дает пример случая 3, Пример 3.! (задача, двойственная к задаче о диете). Вернемся к задаче о диете„обсуждавшейся в примере 2.1. Двойственная к ней задача имеет вид шах и'г, и'А =с', и') О. выражают зот факт, что стоимость в виде пилюль всех питательных веществ, содержащихся в !ьм продукте, не больше чем стоимость самого 1'-го продукта.
Функция стоимости и'г есть просто стоимость адекватной диеты. По теореме 3.1 оптимальная стоимость в прямой задаче домохозяйки совпадает с оптимальной стоимостью в двойственной задаче изготовителя пилюль. В действительности это два способа представления одной и той же задачи. (Д 3.2 Дополняющая нежестность Если внимательно рассмотреть определение двойственной задачи, то можно заметить нечто вроде противоборства прямой и двойственной задач, а именно, чем жестче ограничение в одной из них, тем свободнее соответствующее ему ограничение в другой.
Точным выражением этого баланса является условие, известное как условие дополняющей нежесткости, необходимое и достаточное для того, чтобы х ни давали оптимум соответственно в прямой и двойственной задачах. Теорема 3.4 (теорема о дополняющей нежесткости). Векторы х и и, допустимые соответственно в прямой и двойственной задачах, оптимальны в том и только в том случае, если иг=п,(а';х — Ь,)=0 для всех (, о;=(с; — и'Аз)х;=0 для всех /. (3.8) (3.9) Она допускает следующую интерпретацию. Изготовитель пилюль хочет выпустить на рынок пилюли, содержащие каждое из т питательных веществ; цена единицы (-го питательного вещества равна лп Он хочет быть конкурентоспособным по отношению к цене реальной пищи и в то же время максимизировать стоимость адекватной диеты.
Ограничения ги Х и;а;, .- см 1 = 1, ..., и, ~=! З.х. дополняющая кежесткость Доказаиж|ьство. Заметим, во-первых, что из соотношений двойственности вытекает и,)О для всех 1 и о,)О для всех 15 Положим и=Хи,)0, о=Хо .-О. ь' ! Тогда и=О в том и только в том случае, если выполняются равенства (3.8), и о=О в том и только в том случае, если выполняются равенства (3.9).
Далее, заметим, что и+о=с'х — пЪ, поскольку если мы сложим равенства (3.8) и (3.9) для всех! и 1, то все члены, содержащие как х, так и л, сократятся. Таким образом, равенства (3.8) и (3.9) выполняются в том и только в том случае, если и+о=О, или и'5=с'х, что, согласно (3.7), является необходимым и достаточным для того, чтобы х и и оба были оптимальными.
(З Из теоремы 3.4 вытекают важные следствия. Заметим, что если рассматриваемая пара х, и оптимальна и некоторое неравенство из ограничений двойственной задачи не обратилось в равенство, то соответствующая переменная в прямой задаче должна равняться нулю. Аналогично, если некоторая неотрицательная переменная строго положительна, то соответствующее неравенство должно обратиться в равенсзво.
Пример 3.2. Задача, двойственная к задаче линейного программирования из примера 2.6, имеет вид гпах и, + Зл„+ 4п,, Зп, +5л,+2п, < 1, 2п,+ и,,+бп,(1, п1+ пи+ ггв ~ ~1 и, 1, пг~)0 для всех й Поскольку прямая задача задана в стандартной форме, условия дополняющей нежесткости (3.8) автоматически выполнены, Условие (3.9) принимает вид с,— и'А,=О, с4 — и А,=О, с,— и'А,=О, поскольку в оптимальном решении прямой задачи х„х, и х, поло- жительны. Таким образом, второе, четвертое и пятое неравенства в двойственной задаче должны обратиться в равенства: 2п, + л., -1- 5п, = 1, л, =1, и,= 1.
Гл. 8. двойственность 7а Решение этой системы 5 л = 1 лв 1 лв соагвстствуев стоимости 9/2 в двойственной задаче, что совпадает с оптимальной стоимостью в прямой задаче. () з.з Лемма Фарнаша Лемма Фаркаша является фундаментальным фактом относительно векторов в всв, который в некотором смысле схватывает сущность двойственности. Эту лемму можно было бы использовать для получения результатов, описанных ранее в этой главе, где мы вместо нее Риа. 3.2, Пример конуса.
опирались на конструктивные аспекты симплекс-алгоритма. В дан ный моменв мы можем получить лемму Фаркаша как следствие некоторых известных нам результатов, относящихся к линейному программированию. Введем вначале полезное определение. Определение 3.2. Пусть дано множество векторов а, Е ь;», в= =1,..., и. Конусом, порожденным множеством (ав), обозначаемым через С(а,), называется множество С(аг) = х ~)с»: х= Х леан л,' »О, е=1, ..., и в =! Пример З.З.
На рис. 3.2 показаны два вектора в втв и соответствующий им конус. ( ) Предположим теперь, что нам дано множество векторов (а,) и некоторый вектор с~Я', и пусть следующее условие связывает вл. Лемма Фаркаи!а : (а,) и с: если проекции некоторого вектора у бр" на все а! неот! рицательны, !о его проекция на с также неотрицательна. Лемма фаркаша утверждае!, что это условие эквивалентно тому, что с принадлежит конусу, порожденному векторами аь Для векторов на рис. 3.2 это означает, что если каждый вектор из области, отмеченной дугой, имеет неотрицательную проекцию на с, то с Е С(а,), и обратно, если сЕС(а,), то каждый вектор из области, отмеченной дугой, имеет неотрицателы<ую проекцию на с.
Мы увидим сейчас, что этот результат непосредственно следует из теоремы 3.1. Теорема 3.5 (лемма Фаркаша) [Ра). Пусть даны векторы а! Е )(", !' = 1, ..., т, и с Е (к ", тогда (у'а!~)0 для всех !'~ у'с)0) еесЕС(а!). Докаэательси!во, Рассмотрим сначала импликацию С=, которая на самом деле тривиальна. Если м с= Х и,а!, и! .О, 1=! то у'в = Х и!(у'а,))0 !=! при условии, что у'а, О. Суть теоремы составляет импликация ~. Рассмотрим задачу ЛП пп'п с'у, а!у)0, !'=1, ..., т, у О Эта задача допустима, поскольку у=Π— допустимая точка.
Она также ограничена, так как по условюо из а;у) 0 для всех ! выте- кает у'с)0. Поэтому двойственная задача шах О, Р и Ау=с„ /=1, ..., и, л)0, где А,=со! (а!, 1=1, ..., т) ~Я'", е= Хп!а!, !=! и,.) О, (') а! = со! (а,, 1= 1, ..., и) ~ (х". 'Ф имеет допустимое решение. Следовательно, найдется и, такое, что 80 Гл, 3. двойственность 3.4 Задача е кратчайшем пути и двейственнан к ней задача Определение З.З. Пусть дан ориентированный граф 6=()к, Е), и пусть каждой дуге е, Е Е сопоставлен неотрицательный вес су) О. Рис.
3.3. Взвешенный ориентированный граф для ЗКРО! веса обведены кружком. Индивидуальная задача о кратчайшем пути (ЗКП) состоит в нахождении ориентированной цепи минимального общего веса из выделенной начальной вершины з в выделенную конечную вершину! П Если сформулировать эту задачу как задачу оптимизации, то допустимым множеством и функцией стоимости будут Е = (последовательности Р = (его ..., е; ), являющиеся ориентированными цепями из з в ! в графе 6), и о (Р) = ~~Рс; .
1=1 Индивидуальную ЗКП можно сформулировать как задачу ЛП, для чего вначале определим матрицу инциденций (вершин и дуг) А=1аы! графа 6 следующим образом: +1, если дуга еу выходит из вершины (/1=1, ..., !У!1 — 1, если дуга е входит в вершину !' (1=1, ...,)Е!к! 6 О в противном случае. Пример 3.4. На рис. 3.3 показан ориентированный граф и соответствующие веса дуг, которые определяют некотрую индивидуальную ЗКП. Соответствующая матрица инциденций имеет вид е, еа е, еа е, й! -1 ΠΠΠΠΠΠ†! †! — 1 О а! 1-1 ΠΠ†! — 1 О +! а! Зак Задача а кратчаивием пути Чтобы перейти к формулировке в виде общей задачи ЛП, свяжем с каждой дугой е! переменную ~п представляющую поток некоторого воображаемого продукта по дуге в направлении ориентации. Тогда закон сохранения потока в вершине ! выражается равенством и,'~=-0, где !' — вектор-столбец, в котором ~'-я компонента равна ..
~,, и, как обычно, а,' — это Ля строка матрицы А. Цепь нз з в ( можно рассматривать как поток одной единипы продукта, выходящий из з и приходящий в й Такой поток должен удовлетворять равенству А) ~+1 ! 0 0 0)ч где +1 соответствует строке з и — ! соответствует строке й Конечно, 7" может, вообще говоря, принимать не целые значения, однако, если рассмотреть задачу о потоке минимальной стоимости ппп с'7 (3.10) при условии А~ ~-(-1 1 0 0 0|т Р)0, .= можно интуитивно понять, что существусэ оптимальное решение, в '. котором каждое (, есть либо О, либо 1, представляющее единичный поток вдоль некоторого кратчайшего пути из з в ( в графе 6. (Мы докажем это позднее, в гл.
!3, в более общем контексте. См. также задачу 17.) Заметим далее, что !р'! уравнений в нашей задаче зависимы, поскольку из выполнения закона сохранения в любых !*у'! — ! вершинах вытекает его выполнение в оставшейся вершине. Поэтому можно ; выбросить любое одно уравнение. Пример 3.4 (продолжение). Опустим уравнение, соответствующее строке б Это дает то преимущество, что остается неотрицательный нулевой столбец.
В результате получаем таблицу Л Л Л Л Л ;: Прибавляя строку 1 к стро~ е ", получаем бдр, состоящее нз столб,;. цов 1, 4 и 5. Сделав относительные стоимости этих базисных столб- '. цов нулевыми, получаем таблицу Га. 3. даодспнмнность Л Л Ук Л У' г — — т 1 ' 1 Л= У4 У5 о о ~ о Л= Л= Л= Эта таблица соотвезшвует кратчайшей цепи (е„е,) со стоп мостью 3 и вырожденной дуге ем Рис. 3.4 иллюстрирует операцию ~вол оман ля а Нводнма ,яга Рис. Здк Базис (3 загнтрикованные дуги) и столбец, вводимый а базис (дважды заштрико. ванная дуга). замещения: одна дуга добавляется к базису и одна дуга вычитается из базиса, порождая новую цепь меньшей стоимости.
Возращаясь к формулировке (3.10) в виде общей задачи ЛП, можно следующим образом записать задачу, двойственную к не. которой индивидуальной ЗКП, приписав каждой вершине 1 пере- Произвольный базис представляет множество из )Ц вЂ” 1 дуг, некоторое подмножество из которых соответствует цепи данной сто. нмости из з в й Дуги, не входящие в эту цепь, представляют вырожденные компоненты базиса. В рассматриваемом примере текущий базис представляет цепь (е„е,) со стоимостью 4 и вырожденную дугу гм Операция замещения, вводящая в базис столбец, соответствующий гм дает приведенную ниже оптимальную таблицу (ведущий элемент выделен выше кружком). Л Л Л У4 Уь »дб. даоастаеяяая информация а таблице менную и»» »пах и,— пм и'А < с', и ~~0. (3А 1) Учитывая определение матрицы инциденций, можно записать нера.
венства в двойственной задаче просто как и,— п»(с» для каждой дуги (т, 1)ЕЕ. (3.12) Условия дополняющей нежесткости из теоремы 3.4 имею~ в дан- ной задаче простую интерпретацию. Цепь» и некоторые значения 5 Е 'Н Рнс. 3.5, Оптимальное решение и (е кзздрзти- нзх) для задачи, днойстаенной н задаче о крат- чайшем пути.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
