Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 16
Текст из файла (страница 16)
3, Обоснуйте аккуратно неравенства (3.7) в доказательстве теоремы 3.1 4. Найдите оптимальное двойственное решение задачи о кратчайшем пути из примера 3.4, начав симплекс-алгоритм с подходящей единичной матрицы, как предложено в примере 3.6, и проверьте, таким образом, двойственное решение, показанное на рис. 3.5. б. Физик производит измерения переменной у(х), при этом результаты получаются в виде пар (хг, у;). физик хочет найти прямую линию, которая наи. лучшим образом соответствовала бы этим данным в том смыслегчто максимальное расстояние по вертикали между шобой точкой (хь уй и этой линией должно быть как можно меньше.
Сформулируйте зту задачу как задачу ЛП. Из каких сообра. жений вы моглв бы перейти к решению двойственной задачи) 8*. [ЮГ). Докажите, что если задача ЛП в стандартной форме имеет оптимальное решение и все оптимальные решения невырожденны, то двойственная задача имеет единственное оптимальное решение 7*. Рассмотрим индивидуальную задачу ЛП в стандартной форме. Предпо. ложим, что зта прямая задача имеет вырожденное оптимальное решение. Будет ли оптимальное решение двойственной задачи обязательно не единственным? Если да, докажите. Если нет, приведите контрпример.
8. Покажите, что конус является выпуклым множеством. й*. Покажите, что конус является замкнутым множествохь (Обратите особое внимааие на зту задачу! Решение можно нэйти в (ЮП.) 1О. Проверьте, что лемма Фаркаша справедлива в том случае, когда множество (ай пусто. 11. Йстинны или ложны следующие утверждения: а) если задача линейного программирования недопустима, то двойственная к ней задача должна быть неограниченной; Гл. 3. Двойственность б) если задача линейного прогрзммироваиия неограниченна, то двойствеи.
ная к ней задача должна быть недопустимой 12. Покажите, что задача, двойственная к адзче ЛП в канонической форме, ханже окззывается в каноническов форме. 13. Пусть некоторая зздача о сети формулируется для ориентированного графа б=(У, Е) с использованием матриць инциденцпй вершин и дуг так же, как в примере 3.4. Покажите, что множество. состоящее нз (У! — 1 столбцов в этой матрице, линейно независимо тогда н только тогда, когда соответствующие дуги, рассматриваемые как неариентиронанные ребра в неориентнрованном нарианте графа О, обрззуют дерево (Таким образом, базис соответстнует дереву.) Дайте интерпретацию операции замещения з свете этого факта.
14. Рассмотрим следующую задачу ЛП, которую мы назовем задачей Рг ш)п хз+х,, х,+2хз ~5, ха+ 2хз= 6 хт, хэ, кз~О. а) Решите Р с помощью симплекс-алгоритма. б) Запишите задачу (), лвойсгаенную к Р. в) Запишите условия дополняющей нежесгкости для этой задачи и используйте их для решения двойственной задачи Г) Проверьте заш ответ, вычисляя оптимальные стоимости в задачах Р и П. 15. Еще раз решите задачу !4 заменив неравенство в Р неравенством х,+ +2хз~ — 5.
16. Предположим, что в задач~ о кратчайшем ну~и допускаются отрицатель. ные веса дуг, и мы рассматриваем пример, и котором имеется ориентированный цикл с отрицательным суммарным весом Что произойдем если применить сим. плекс-алгоритм? Постройте такой пример Что можно сказать о двойственной зз даче в этой ситуации? \7. Докажите, что в задаче ЛП, построенной дли задачи о кразчайшем пути, всегда имеется оптимальное решение, в котором каждое )!=0 илн 1 В каком случае имеются оптимальные решения, не удозле~норяющие этому условию? 13. Рассмотрите (пк и)-матрицу инциденций вершин и дуг ориентированного графа, имеющего в точности и вершин и и дуг Покажите, что ее определитель равен нулю. 19. Предположим, что задача ЛП в стандартной форме имеет единственное оптимальное решение.
Следует ли из этого, что двойственная задача имеет невы- рожденное оптимальное решение? Верно ли обратное утверждение? 20. Пусть задача ЛП а стандартной форме содержит два столбца, которые пропорциональны с положительным коэффициентом пропорциональности, По. стройте эквивалентную задачу ЛП, нмею,цую на один столбец меньше. 21. Другой формой леммы Фзркаша н теоремы двойственности является следующее утверждение. Система линейных неравенств Ах сЬ нззывается протизоречизой, если существует у, такой, что у'А=О, у Ьч.,О и У%О. Покажите, что система Ах~5 не имеет решения тогда и только тогда, когда она противоречива Комментарии и ссылки (чЫ) Джон фон Нейман был, как сообщает Д. Гейл, первым, кто сформулировал теорему двойственности (теорему 3.3) в заметках, имевших частное хождение, пз позднее 1947 года См [Сза! Сза!з В.
Тйе Тйеогу о1 !Апеаг Есопощ!с Мобе!з. Хетт УогК: Мсбгатч-Н!!1 ВооК Сошрапу, 1960. (Имеется перевод: Гейл Д. Теория линейных экономических моделей,— Мл ИЛ, 1963,! Гейл приводит первое докззательство, основанное нз заливках фон Неймана, в работе Комменаюрни и ссылки 91 [ОКТ! Оа1е 1). Кнйп Н. Ъ'. Тнсйег А. %. Оп Бушье!г!с Сашек, !п Соп1г!Ьн1!опз 1о Ьйе ТЬеогу о1 Сашез, еб Н. 9г. КпЬп апб А. Ж, Тпсйег, Апп. Ма!Ь. Янд!ез, Но. 24, Рппсе!оп, Н. 3л РПпсе1оп !)п!чегз!1у Ргезз, 1950. Лемма Фаркаша взята из статьи [Ра] Рагйаз Л ТЬеопе бег Е!п1асйеп 1)пй!е!сйнпйеп, 3. Ее!пе нпб Апнежап61е Ма1Ь., 124 (!902), ! — 27.
Элементарное доказательство утверждении из задачи 9 дано в книге [ЮП Юдин Л. Б. Гольштейн Е, Г. Линейное программирование.— Мл Науна, 1969. Задача 21 содержится в работе [Кн) Кнйп Н. %. Зо!чайн!!1у апб Сопжжепсу 1ог 1.!пеаг ЕцнаНопз апб 1пейна- 10!ез, Ашег. МаРш Моп[Ь!у, 63 (1956), 217 — 232 и была предложена в следующей интересной статье Хватала: [СЬ) Сйча1а! 'тг. Зоше Е !пеаг Ргойгашш!пй Азрес!з о1 СошЫпа1ог!сз, Рерог[ ЗТАЫС6-75-505, Сошрн!ег Зс!енсе Овраг!щеп1, Яап!огб 1)п!чета[!к !Зев)ешЬег 1975).
Вычислительные аспекты симплекс-алгоритма 4Л Модифицированный симппеис-алгоритм Если бы мы реализовали симплекс-метод так, как описано в гл. 2, то нам пришлось бы на каждой операции пересчитывать всю таблицу размера (т+1) к (и+ 1). Оказывается, что этого можно избежать, если хранить меньшую изменяемую матрицу размера (т+1)~~(т+1) и порождать относительные стоимости ст и столбцы Х~ тогда, когда они нужны.
Из этого вытекают важные практические следствия, которые мы обсудим после описания метода. Будет показано также, как этот метод, называемый модифицированным симплекс-методом (или иногда методом обратной матрицы), можно применить к важной задаче о максимальном потоке и как он приводит к принципу декомпозиции для задач определенного вида.
Мы видели в предыдущей главе, что начиная симплекс-алгоритм с единичной матрицы в исходной таблице, мы на любой последующей итерации с базисом В будем иметь на ее месте матрицу В '. Предположим, что мы начинаем с единичной матрицы, стоящей в левой части таблицы, и нулевой строки стоимости, и будем хранить только строки и столбцы с номерами от нуля до т. Эту матрицу размера (т+1)х(т+!) на итерации 1 назовем САВВУ"', ниже показана исходная матрица САйЯ)'"'. (Ф. 1) сляя ггч 4.д Модифицированнвей еинилексолеоринш После (-й итерации в симплекс-алгоритме получим (4,2) САкпу ~о Мы следим также за текуецими базисными переменными, а именно за упорядоченным множеством индексов В. Исходная таблица А, текущая матрица САКИ"" и базисное множество В достаточны для выполнения прямого симплекс-алгоритма.
При этом выполняются следующие шаги. 1. (Операция оцеиивания.) Вычислять по очереди относительные стоимости с =о,— и'А, (4.3) пока не найдется отрицательное с, (пусть, например, при /=з); если такого с, нет, остановиться, выдав оптимальное решение. 2.
(Порождение столбца.) Вычислить столбец Х, в том виде, в каком он стоял бы в (-й таблице, по формуле Х,= В 'Ав. (4.4) Затем определить ведущий элемент, скажем х„, обычной проверкой отношений ппп ( — ') "ев (4.5) нли сделать вывод, что стоимость неограниченна.
3. (Замещение.) Преобразовать САКИ"" в САРК)'о+и так, как если бы мы производили операцию замещения с ведущим элементом х„, и САРК)'и' стояла бы в левом конце таблицы. Эта операция использует вычисленный столбец Х,. 4. (Преобразование базиса.) Заменить г-й элемент В на индекс нового базисного столбца з. Центральный момент в описанном алгоритме — порождение столбца на шаге 2; имея обратную базисную матрицу В ' мы имеем достаточно информации для вычисления любой части таблицы, При использовании модифицированного симплекс-метода как двухэтапного алгоритма необходимо обратить внимание на некоторые детали.
Во-первых, если мы начинаем с искусственных пере- 94 Гл. Е. Пыеислителысые асаекиие симилекс-алеасииема менных с единичной стоимостью, то мы должны сделать строку стоимости нулевой. Для этого все строки вычитаются из строки О, поэтому на этапе! все су в (4.3) вычисляются по формуле сг — — 4 — и'А, У 7 I' где с! = — Ха, с=! (4. 6) и где, как обычно, ам — элемент исходной таблицы При переходе к этапу П необходимо следующим образом изменить строку стоимости, В качестве стоимости с(т в (4.6) необходимо взять исходную стоимость се и нулевую строку матрицы САИесУ в начале этапа П необходимо вычислить по формуле — и'= — с,',В-'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
