Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 12
Текст из файла (страница 12)
В противном случае можно было бы взять вектор стон. мости О, АиМ, с = 1, А~Е еь'„— ый, у' пМ в противном случае, где М вЂ” подходящее большое число, например то, которое определено в лемме 2.1 Тогда у было бы единственным оптимальным решением и любое допустимое решение с ненулевыми компонентами вне М„ц М„имело бы стоимость, большую, чем х. Таким образом, симплекс-алгоритм, начиная с х, не смог бы найти последовательность смежных бдр с невозрастающей стоимостью, приводящую к оптимуму, что является абсурдным. Следовательно, такое в~х, у действительно сущесгвует и, более того, ю не лежит на (х, у), поскольку точки в, х, у соответствуют различным вершинам многогранника Р.
Пусть г=(х+у)/2. Рассмотрим разнос~ь д=г — ш. Она о~лична от нуля только для столбцов из ыг„ц я', и, следовательно, сушеу' ствует положительное число О, такое, что и,=а+84 и и,=г — Ос( допустимы. Отсюда г=(и,+и,)/2, где й, и й, не лежат на !х, у), что проз иворечиз свойству (б). 67 2.9. Геомепуичеииие асленти замещения (в) => (а). Пусть ߄— базис, соответствующий х, ߄— базис, соответствующий у, н Же=Я„0(Ат) — (А„) для некоторйх столбцов Аь Аь. Зададим вектоР стоимости с следУющим обРазом: / О, если А ЕЯч(1 Я„', 1 в противном случае.
Все допустимые решения, являющиеся выпуклыми комбинациями х и у, оптимальны. Более того, только они будут оптимальными решениями, Чтобы показать это, допустим, что г оптимально. Тогда, У, хч Рнс. 2.7. а) Точная окрестность Гч'; . о) Точная окрестность чтя(хч)=(у„у„уч). ' согласно теореме 2.3,г есть выпуклая комбинация бдр, и в частноьсти тех бдр, базисы которых являются подмножествами множества ' Я„(1 Я,. Но такими бдр могут быть только х н у.
Получаем, что условиям Аш=Ь, пл)0 и с'еа ~с'х удовлетворяют е(только выпуклые комбинации ц бдр х и у. Поэтому в Р только "...'точки за сегмента (х, у) удовлетворяют неравенству е('еа ~е('х, где с(, атак же как в доказательстве теоремы 2.4, определяется следующим „- 'образом:. е(т=с,— ~~ Ь„+,,с„+ . /=! ', -Таким образом, отрезок (х, у) представляет собой пересечение .; некоторого полупространства с Р и является, следовательно, ;р бром.
Ф. Приведем в заключение еще одно замечание относительно симпелекс-алгоритма. Как мы видели в гл. 1, задача ЛП является задачей пуклого программирования, и, следовательно, система евкливых окрестностей й(, точная. То есть, если для некоторого х, Е Р Гл, 2. Симплекс-алгоритм 68 мы просматриваем окрестность, состоящую из всех точек множества Р, отстоящих от х, не более чем на е, и не находим решения, лучшего, чем лщ тогда х, глобально оптимально (рис. 2.7(а)).
В симплекс-алгоритме обнаруживается другая точная система окрестностей, комбинаторно и вычислительно намного более важная. Во-первых, мы не должны рассматривать все (несчетное) множество г", достаточно рассмотреть лишь конечное множество базисных допустимых решений. Кроме того, в этом множестве бдр имеется система окрестностей й(л(х,) =(у: у — бдр, смежное с х,). Из теоремы 2.8 следует, что 7лгл является точной для задачи ЛП (см. рис.
2.7(б)). Более того, Фл(х,) содержит мало (не более и — и) бдр, и они могут быть просмотрены очень быстро. Для этого достаточно на самом деле смотреть только на знаки сл Таким образом, симплекс-алгоритм можно рассматривать просто как умное применение общего метода поиска по окрестностям для точной структуры окрестностей Ул.
Задачи !. Покажите, что утверждение, обратное теореме 2.5, не верно, т. е. что мо. жет существовать вырожденная вершина, такая, что соответствующий ей базис является единственным. 2. Покажите, что многогранник Р, определяемый индивидуальной задачей ЛП, яВляется ЗВмкпутым мцожестВом. 3. Пусть в некоторой индивидуальной задаче ЛП и переменных не ограни. чены по знаку. Покажите, как можно заменить их лл+! переменными, на которые наложены ограничения неотрицательностн. 4. Проверьте утверждение В доказательстве георемы 2,4 о том, что множество л) может быть расширено до базиса, и аналогичное утверждение в доказательстве теоремы 2.!. 5*.
Покажите, что критерий оптимальности из теоремы 2.8 не является необходимым в оптимальной вершине. 6*. Покажите, что из условия 0„=0 для любого возможного ведущего элемента в симплекс-алгоритме не следует оптимальность. 7+. Покажите, что задача линейного программирования не может зациклить ся до тех пор, пока хотя бы две базисные переменные не станут равными нулю. 8.
Покажите, что множество оптимальных точек индивидуальной задачи ЛП является выпуклым множеством. 9. Пусть даны индивидуальная задача ЛП А в стандартной форме щ!п с'х, Ах=Ь, х~п, и индивидуальная задача ЛП В ппп — с'х, Ах=Ь, к ТЯО. Могут ли обе задачи А и В иметь допустиллые решения с произвольно малой стои- мсстьюр Если да, приведите пример, если нет, докажите. 69 10.
Покажите, что множество 0 в доказательстве георемы 2.2 аамкиуто. - (згкпэакиз; покажите, что любая точка вне 0 имеет окрестность, целиком лежащую . вне 0.) П. Обязазельно ли из тога факта, что каждая вершина некоторой задачи . ЛП невырожденна, следует единственность решения? Если да, то докажите, если .
вет, приведите нонтрп ример 12. Дайте ответ на следующий вопрос и обоснуйте ваш ответ. Может ли : замещение в симплекс-алгоритме сдвинуть допустимую точку на положительное расстояние в )?ч, оставив прн этом стоимость неизменной? 13. Может ли вектор, который только что покинул бахи. в симплекс-алго) ритме, вернуться в базис при следующем замещении? 14. Следующий фрагменг программы на языке Фортран вычисляет су для ~операции оценивания в симплекс-алгоритме н решает, произвести ли замещение, ' при котором столбец ! войдет в базис: СВАЙ = С(0) 001 ! =1,М 1 СВАЙ = СВАЙ - С(ВАВ!3(!))эХ(1,,)) 1Р(СВАЙ.(.Т,О,)00 ТО 3 "?Допустим, что переменные С, ВАВ!Я и Х определены соответствующим образом йв данном месте программы, Объясните, почему этот фрагмент не будет правильно работать на практике. и пр«дложите простую модификацию, которая будет рзбоявть.
(Ответ здесь пе завися~ от языка.) 15 (задание по нрограччнрованию) Напншит«программу для ЭВМ, которая лизует двухэтаппый симплекс.алгоритм для задачи ЛП н стандартной форме. одом должны быть векторы Ь и г и ма~рина А. Программа должна останзвлиься в одном из следующих четырех случаев. Нз этапе ! найдено неограниченное решение. Это невозможно (почему?), но должна быть логическая ветвь в программе для проверки ошибок.
~ . На этапе 1 найдено оптимальное решение с положи ге ~«ной стоимостью. Это означает, что исходная задача недопустима. 4 На этапе П найдено неограниченное решение. Это озцачаец что исходная задача имеет неограниченную стоимость ° На этапе П найдено оптимальное решение, Это означает, что исходная задача решена.
Ваша программа должна ныдавзгь: (а) данные задачи; (б) строку, столбец и стоимость после каждого замещения на обоих лапах; (в) сообщение после этапа 1 и после этапа П, если будут достигнуты эти точки; (г) заключительные базис, таблицу и сгоимостгь независимо от того в какой ,мочке программа остановится. Проверьте вашу программу на задачах, которые заканчивают работу всеми йвпвможиыми способами. 16. Докажите следующее утверждение: если Р является й-мерной гранью выклого многогранника Р в )?л, го Р чакж«есть выпуклый многогранник и, более , каждая вершина Р будет гакже вершиной Р 17.
Если задача ЛП не ограничена, то существует рациональный вектор а, ой, что (а) с'эх<0, и (б) если к допустимо и й>0, то х+йа также допустимо. кажите. 70 Гл. 2. Сцкллекс-цггорамм Комментарии и ссылки Снмплекс-алгорнтм был нзобретен Данцнгом в 1947 г., так что мы не можем слншком широко рекламировать его книгу [Ра1) Рап1г!6 О. В. 1Лпеаг Ргойгапнпгпй апг) Ех!епшопь, Рипсе1оп, )4. Лл Рипсе1оп !Лцггегьйу Ргеьь, 1963. [Имеется перевод: Данциг Д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
