Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 13
Текст из файла (страница 13)
Б. Лннейкое программнрованне, его применения и обобщения.— Мл Прогресс, 1966.) Читатель найдет в ней детальное описание нз первых рук истоков линейного программнровання наряду с развнтнем симплекс-алгоритма и его вариаций. Кроме этой книги есть много других прекрасных кинг, посвященных линейному программированию. Среди ннх [ВЛ) Вахагав М. Б., Лагчи Л. Л. )Ппеаг Ргойтащшшй апд Ые1вогК Р1овь. 5)ев 'т'огК: Лойп %Пеу Лг Боль. !пс., 1977. [СБ) Соорег Е., Б)е!пЬегй Р. Мерподь апд АррПсаПопь о1 Е)пеаг Ргойгаппп)пй, РЫ1аде)рЬ!а: тч". В. Баипдегь, 1974.
[ОаЦ Оа1е Р., ТЬе ТЬеогу о! 1лпеаг Есопогп!с Моде)з. )чев Уогй: Мсбгав-НП1 Воой Сошрапу, 1960. [Имеется перевод: Гейл Д. Теорня линейных экономнческнх моделей.— Мл ИЛ, 1963.[ [Оаь) Оаьь Б. 1. Е[пеаг Ргойгашшшй (41Ь ед). Нев Уогй: МсОгав-Н(П ВооК Сошрапу, 1975. [Имеется перевод: Гасе С. Линейное программнрованне,— Мл Фнзматгяз, 1961.! [Над2[ Над1еу О. [Лпеаг Ргойгашшшй.
Веад!пй, Мазал Адд(ьоп.рт(еь!еу РиЫИЬ- !пй Со., (пс., 1962. [Ни[ Ни Т. С, 1п1ейег Ргойгаппп!пй апд )че(во!К Г1овм Веад!пй, Мнил Адд!ьопЪтГеь1еу Риыиыпй Со., (пс., 1970. [Имеется перевод: Ху Т. ((елочнсленное программирование и патоки в сетях.— Мл Мнр, 1974.! [51) Бипоппагд М.
!Лпеаг Ргойгапип!пй. Еп91евоод С)ПЬп )4. Лл РгепПсе-НаП, 1пс. 1966. [ЮГ) Юдин Д. Б., Гольштейн Е, Г, Линейное программнрованне.— Мл Наука, 1969. Данциг [Ра1) прнпнсываег формулировку задачи о диете Стнглеру [БН) 5119)ег О. Л. ТЬе Соь( о) БиЬь(ь(епсе. Л. Рапп Есоп., 27, (чо. 2 (Мау 1945), 303 †3. Он также первым опубликовал снмплекс-алгорнтм в работе [Ра2[ Рап(х(6 О. В. Ргойгапип)пй о! !п1егдерепдеп1 Ас((ч(1)еь, 11, Марпегпаиса! Моде1, рр. 19 — 32, !и Аснчцу Апа!унь о! Ргодцс~оп апд Акоса11оп, ед. Т. С.
Кооршапь )сев Уогй; ЛоЬп Тч'Пеу дг Боль, )пс., 195!. См. также: Есопогпе1гкь 17, !)о, 3, 4 (Ли1у — Ос!. 1949), 200 — 211. Теорему 2.3 можно рассматривать как частный случай общего утверждения о том, что любое замкнутое ограниченное выпуклое множество является выпуклой оболочкой свонх экстремальных точек. Для более широкого знакомства с много. гранннкамн см [Оги) ОгйпЬашп В, Сопчех Ро!у1ореь. Ыев Уогй: Лойп ЖПеу Зг Боль, (пс. 1967. [Кос) Восйа!енаг Кц Т. Сопчех Апа1ушь.
Рг1псе(оп, (ч. Лл Рипсе1оп 1)п!чегм1у Ргеьь, 1970. [Имеется перевод: Рокафеллар Р. Выпуклый анализ.— Мл М яр, Г973.) Вацнклнванне в практнческнх задачах описано в статье [КБ[ Ко(гап Т. С. Т., Б!е!пЬегй Р. 1. Оп Гне РоьнЫ1Пу о1 Сус!шй вПЬ 1Ье Бппр1ех Мердод ОК, 26, Ио. 2 (МагсЬ вЂ” Арш! 1976), 374 — 376. Комментарии и еемлки 71 Правило устранения зацикливания, приведенное з $ 2.7, взято нэ работы !В!) В!апд К. О. Хем Г!п!ге Р~чо1!пд Ко!еь, Омспззюп Рарег 7612, Сеп1ег !ог Орегагюпз йезеагсЬ эпд Есопове1г!о )СОКЕ), !Лп!чегз!ге Сайо!к!ие де Ьоича!и, Нечет!ее, Ве!3!ов, Липе !976 (геч!ьед Лапиагу 1977). Приведенное доказательство врииадлежнт Куну )Ко) КцЬп Н.
йг. С!азз Хо!ее, РНпсе1оп 0п!чегзйу, 1976. Вычислительные эксперименты по сравнению различных правил выбора столбца описаны в работе )Кф КпЬп Н. %., гЛиапд1 й. Е. Ап Ехрш!вен!а! 51иду о! йе Б!вр!ех Ме1Ьод, рр. 107 — 124, !п Ргосеед!пбз о1 5увроз!а оп Арр!!ед Ма)Ьева1!сз, чо!. ХЧ, ед. Х. Ме1горо1Ь апд ойегз. Агпеысап МайегпаНеа1 Бове1у, Ргоч!депсе, К. 1., 1963. Метод иаискоребшего спуска относительно всех переменных описан в ататье 1ОК! ОоЫ1агЬ О., !1еЫ Л. К.
А Ргас1!саЬ!е 51еерез1-Ед9е 5!вр!ех А!догйв, Ма1Ь. Ргоб., 12, Хо. 3 (Липе !977), 361 — 371. Пример зацикливания взят иэ работы 1Ве!) Веа!е Е. М. й Сус!!пд )п йе Оца! Вугпр!ех А!бог!1Ьв, Хама! КезеагсЬ 1.обкд!сз !диас)ег!у, 2, Хо. 4 (1955), 269 — 275. Двойственность Э.1 Двойственная задача линейного программирования в общей форме (3.2) где А = ~Агь ! Е)У1(А,, — А ), (Е )У! — 'Ем . х=со! (х~, (Е Ь))(х';, ху), 1 Е)у!х',, (ЕМ), с = со1 (с „) Е )У1(с, — с ), 1 Е Д) / 0).
Из критерия оптимальности с «О и симплекс-алгоритма выте- кает, что если задача (3,2) имеет оптимальное решение х„то существует базис УЗ для системы уравнений в задаче ЛП (3.2), Если бы в линейном программировании не было ничего, кроме симплекс-алгоритма, то уже одно это давало бы большую пользу. Однако в рассматриваемой задаче есть также много интересных тео- ретических аспектов, особенно в связи с комбинаторными задачами.
Все они так или иначе связаны с идеей двойственности, к рассмот- рению которой мы сейчас н перейдем. Рассмотрим задачу ЛП в общей форме;. ппп с'х, ах=Ь,, (РМ, а';х~)Ь;; (ЕМ, (3. 1) х/ ~» О, 1 Е )у, х,~О, /Е)у. Мы хотим воспользоваться критерием оптимальности из теоре- мы 2.8 и с этой целью преобразуем данную задачу к стандарт- ной форме, )(ля каждого неравенства нз М введем переменную избытка хь (Е М; для каждой неограниченной переменной х, (Е У, введем две новые неотрицательные переменные, поло- жив х, = х,' — х, н заменив столбец А, двумя столбцами Ах и — А .
Получим задачу ЛП пппсх, Ах=Ь, х)0, В.!. двойспменная видани линейного программирования 73 такой, что с' — (свВ ') Л'= О. Таким образом, и'=свВ ' — допустимое решение системы линейных ограничений и'Л (с', (3.3) где и Е Ь™ и т — число строк в исходной матрице А. Неравенства (3.3) распадаются на три части, в зависимости от того какое множество столбцов матрицы А в них участвует. Первое множество дает просто и'Л! ~ см ! Е !с).
(3.4) Следующее множество соответствует неограниченным переменным кс, ! Е Л', и связанные с ним неравенства идут парами: А, (см — и'Л ( — с, ! / !' что эквивалентно равенствам и'А! —— сс, ! Е сс). (3.5) Последнее множество соответствует неравенствам с номерами ! ЕМ: — пс(0, с СМ, или я; -О, )ЕМ. (3.6) Двойственная задача Прямая задача тах л'Ь -о л,)о и'Ас ( сс а'Ас = сс пиисх а'к = Ь, а)х-'~ Ь, хс)О .хв ~о ссМ сс М ! е оС /с и Теорема 3.1.
Если неквторпя задачи ЛП имеет оптимальное реисение, тп двойственная задача тпксге имеет оптимальное решеоние, при этом оптимпльные значения ик спсосс костей равны. Уеловия 3.4, 3.5 и 3.6 определяют ограничения новой задачи ЛП, . называемой двойственной к исходной задаче ЛП, при этом исходная задача ЛП называется прямой. Вектор п'.=-с„'В ' допустим в двойственной задаче. Если определить функцию стоимости в двойственной задаче как снах и'Ь, то и' не только допустим, но и оптимален! Суммируем это в следующем определении и теореме. Определение 3.!. Пусть дана задача 3!П в общей форме, называемая прямой. Тогда двойственная задача определяется следующим .
образом: г . з. дева Доказательство. Пусть х н и — допустимые решения соответственно для прямой и двойственной задач. Тогда с'х)н'Ах~я'Ь, (3.7) Теорема 3.2. Задача, двойственная к двойственной задаче ЛП, совпадает с пряной задачей ЛП, Доказательство. Запишем двойственную задачу в виде ш(п и'( — Ь), ( — А)п - — с~, /ЕЛI, ( — А;) и= — сг, 1ЕЖ, п,~)0, 1ЕМ, п,~~О, 16М, и рассмотрим ее как прямую. Согласно определению 3.1, задача, двойственная к этой двойственной задаче ЛП, будет иметь вид шах х'( — с), х~ =э О, х,~~О, — а;х ( — Ь, — а';х = — Ь, 1' Е Й, ! Е ~Ч, (ЕМ, 1~М, которая, как нетрудно видеть, совпадает о исходной прямой задачей.
( ) Задача линейного программирования всегда относится ровно к одной из следующих трех категорий; (1) она обладает конечным оптимумом, (2) она обладает решением неограниченной стоимости, (3) она не имеет допустимых решений. Таким образом, для прямой задачи и двойственной к ней имеется девять возможных комбинаций, показанных на рис. 3.1, Теоремы 3.1 и 3.2 исключают все клетки в первой строке и первом столбце, кроме того случая, когда и прямая, и двойственная То есть стоимость в прямой задаче всегда не меньше стоимости в двойственной задаче. Поскольку мы считаем, что прямая задача имеет допустимое решение, то двойственная задача не может обладать решением неограниченной стоимости.
Двойственная задача имеет допустимое решение и', рассмотренное выше, поэтому, согласно симплекс-алгоритму, она имеет оптимальное решение. Заметим, что стоимость этого и' равна и'Ь=свд 'Ь=сзх„что является оптимальным значением стоимости в прямой задаче. Отсюда вытекает, согласно (3.7), что и' оптимально в двойственной задаче. Важной чертой двойственности является симметрия, выраженная в следующей теореме.
Зд. Двойственная задача линейного программирования 75 задачи имеют конечный оптимум. Исключенные случаи отмечены крестиками, и таблица заполнена в соответствии со следующей теоремой. Теорема 3.3 !тХ, Оа, ОКТ). Если дана пара, состоящая из прямой и двойственной задач г7П, то возможна в точности одна из трех сиптиат1ий, показанных на рис. 3.1.
Доказательство. Согласно (3.7), если прямая или двойственная задача имеет неограниченную стоимость, то другая задача не может Рнс. 3.1. Возможные нзтегорнн прнмо-двойственной пары. иметь допустимого решения. Остаются только два случая, указанные на рис, 3.1 как случаи 2 и 3. Простые примеры показывают, что оба зтих случая возможны. Случай 2 имеет место, когда обе задачи недопустимы. Рассмотрим недопустимую прямую задачу гп)их„ х, +х,в1, — х,— хе~ ~1, х, ~~1, хе~~О, Двойственная к ней задача имеет вид гпахл, +л„ л,— л,=1, л — л =О, 1 е л,)О, и также недопустима. Гл. 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
