Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 19
Текст из файла (страница 19)
Пусть модифицированный симплекс-алгоритм используется длн решения задачи линейного программирования, в которой все данные состоят из д-разрядных двоичных чисел и исходная таблица имеет размеры тХл. Сколько двоичных разрядов необходимо сохранять в каждом слове в процессе вычислений, с тем чтобы получить абсолютно точный ответ? Комментарии и ссылки Дополнительную информацию о практических вычислительных аспектах симилекс-алгоритмз и модифицированного симплекс-алгоритма можно найти в книгах )Ве! Веа!е Е. М. ь. Ма!йеша!!са! Ргайгашпз!пй !п РгасНсе, Меж '»'огй.
Лойп 1«'1!еу й 5опз, !пс., 1968. )ОН) Огсйагб-Науа '««*. Адчаисеб 1шеаг-Ргодгапппшй Сошры!пй Тес!»п!анез. Кеч Уагйл МсОгаш.Н!!! Воо1« Сатрапу, 1968. )паз) 'ьазбап ь. 5. Ор1ппшзноп Тйеогу 1ог ьагйе 5умешз. ьопдоп; МасМ!!!ап, 1пс !970. Метод декомпозиции был впервые опубликован в рабате )ОЪ') Пап(г!й О. В., )ь'о!!е Р.
Оесошроз!1!оп Риис!р!е (ог )Дпеаг Ргойгашгп(пй, О)(, 8, !»)о 1 (1960), 10! — 111. Данциг обыграл идею о том, что метод декомпозиции является математическим выражением децентрализованного планирования в четырехактной пьесе с дей. ствующими лицами «штаỠ— координатор нагрузочных операций и «Р, М. Оа)йз» вЂ” вымышленный (но сложный) консультант. См. [(?а!) (?ап1г!й О. В.
ь!пеаг Ргодгашш!пй апб Бх!епшопз. Рнпсе!оп, и. Лл РНп. се1оп 1Лп!тегзйу Ргезз, 1963. )Имеется перевод: Данциг Д. Б. Линейное программирование, его применения и обобщения — Мл Прогресс, 1966.] Прямо-двойственный алгоритм 5.1 Введение Данная глава посвящена прямо-двойственному алгоритму, который является общим алгоритмом для решения задач ЛП. Этот метод в действительности развился из менее общего алгоритма, разработанного для некоторых задач о сетях, и, как мы увидим в этой и последующей главах, дает основную идею построения специализированных алгоритмов для многих задач, связанных с графами.
Начнем с неформального описания метода. Пусть дана задача ЛП в стандартной форме, которую мы назовем прямой задачей П; ш(п ° = с'х Ах =Ь)0, х ) О. (П) Рассмотрим двойственную к ней задачу Д: шах ш =-= л'Ь, л'А (с', о. (Д) Заметим, что там, где необходимо, уравнения в П умножены на — ! так, чтобы было Ь)0. Напомним условия дополняющей нежесткости (теорема ЗА); если х допустимо в П, а л — в Д, то для одновременной оптимальности х и л необходимо и достаточно, чтобы выполнялись следующие условия: л;(а',х — Ь;)==0 для всех (, (5.1) (с,— л'А,) х,=О для всех 1. (5.2) Соотношения (5.1) удовлетворяются для любого х, допустимого в П, поскольку П представлено в стандартной форме, поэтому мы сосредоточим внимание на равенствах (5.2). Предположим, что у нас имеется точка л, допустимая в двойственной задаче Д.
Если бы мы смогли найти точку х, допустимую в П, в которой ха=О для любого ), такого, что с, — л'Ат)О, то эта точка х (и, конечно, л) была бы оптимальной. Прямо-двойственный аягоригпм н основан на идее поиска такого х для данного л, для Гм б. Прямо-двоасоменнма оягорио>м 108 чего и решается вспомогательная задача, называемая ограниченной прямой (ОП) задачей, определяемая текущим значением л. Если в результате поиска нам не удается найти подходящее х, мы тем не менее получаем информацию из задачи, двойственной к ОП, которую мы назовем ДОП, о том, как улучшить текущее и.
Продолжая Рвс. 6.1. Общая схема прямо-двойственного метода. этот процесс, мы за конечное число шагов достигнем оптимальности (обсуждение конечности алгоритма см. в 3 5.3). Описанный метод представлен в схематическом виде на рис. 5.!. 5.2 Прямо-двойственный алгоритм Прямо-двойственный алгоритм правильно назван двойственным алгоритмом, поскольку он начинает работу с допустимой точки я в Д и сохраняет допустимость в двойственной задаче на протяжении всей работы.
Если с~)О, то в качестве начальной допустимой точки в двойственной задаче можно взять я=О. Если с не является неотрицательным, можно тем не менее легко найти допустимое я, используя прием, приписываемый наряду с другими Билу (0ЕЕ). Введем в прямой задаче П переменную х„+, и добавим ограничение х,+х,+... +х„+х„+1 — — Ь +,, (5.3) где Ь +1 выбирается ббльшим, чем сумма значений х„..., х„ любого возможного решения задачи П (например, и, умноженное на М из леммы 2.!), и положим стоимость с„+, равной О.
Очевидно, что условие (5.3) на изменяет решения задачи П. Задача, двойственная к новой прямой задаче, будет содержать одну новую переменную и„+1, одно новое ограничение и будет иметь вид шах и> = л'Ь+ ям+1Ьм+1 ет'4~+я„,ет сП 1 )> ° > н> л„„е.„, О, о.л. Прямо-двойственный алгоритм В качестве допустимого решения этой задачи У!П можно взять просто пг — — О, ( 1, ..., т, и„+, —— пнп (с?) ( О. 1~/ал Последнее неравенство следует из предположения о том, что с не является неотрицательным.
Учитывая возможность применения описанного выше приема, будем далее, не изменяя обозначений в Д, считать, что нам дана точка и, допустимая в Д. 'Тогда некоторые из неравенств я'А?(сг будут строгими неравенствами, а некоторые обратятся в равенства. Определим следующее множество индексов Х: У=(/: я'А =с~). (5,ф) Из (5.1) и (5.2) следует, что допустимая точка х в П оптимальна тогда и только тогда, когда х = 0 для всех 1 ( У. (5.5) Это приводит к задаче нахождения х, удовлетворяющего условиям Хаых Ьо 1=1, ..., т, х?) О, (Е/, (5.6) х =О, ((l. В этих условиях используются только те столбцы матрицы А, ко- торые соответствуют равенствам в Д, которые в свою очередь соответствуют множеству л; по этой причине мы назовем г* мно- жеством допустимых столбцов, Для нахождения такого х рассмо- трим новую задачу ЛП, называемую ограниченной прямой (ОП) задачей, определяемую следующим образом: в ш(п$= Х х,', е=1 Х а, х,+х,'=Ьо 1=1, ..., т, ! ° г (ОП) х?~ )О, =О, Ф, х', )~ О.
Здесь мы ввели искусственные переменные х;, 1=1,..., т, по одной для каждого уравнения в П. Для решения ограниченной прямой задачи ОП можно применить обычный симплекс-алгоритм. Если для оптимального решения задачи ОП $,„,=-0, то это будет означать, что найдено решение для (5.6) и, следовательно, оптимальное решение для П. А что будет, если 1,„,)0 в ОП? 110 Гл. д. Прямо.доойотоеннай ол«оршпм Чтобы ответить на этот вопрос, необходимо рассмотреть задачу ДОП, двойственную к ограниченной прямой задаче ОП, имеющую вид шахш=л'Ь, (5.7) л'Аг«-. О, 1'Е У, (ДОП) (5.8) л,<1, (=1, ..., лг, (5.9) л; ~ О.
(5.10) Обозначим оптимальное решение задачи ДОГ1, полученное после решения задачи ОП, через л, Мы пришли теперь к следующей ситуации; мы пытались найти допустимое х, используя только допустимые столбцы, однако это сделать иам не удалось, поскольку $,„,=»0. Все, что нам удалось получить,— это оптимум в ОП и соответствующее двойственное решение л в ДОП. Это наводит на мысль рассмотреть «исправленное» л, задаваемое линейной комбинацией нашего исходного л и л: л = +Ел. (5. 1 1) По аналогии с обычным симплекс-алгоритмом нас будет интересо.
вать, как выбрать О так, чтобы л' осталось допустимым в Д и привело бы к улучшению стоимости. Рассмотрим сначала новую стоимость л" Ь = л'Ь+ Ол Ь. (5.12) Так как ОП и ДОП образуют прямо-двойственную пару, то их оптимальные стоимости при одновременной оптимальности равны, поэтому л'Ь=$„о) О, (5,13) Таким образом, для увеличения (и, следовательно, улучшения) стоимости в Д необходимо взять О)0. Посмотрим теперь, как влияет добавление Ол к л на допустимость в Д. Для того чтобы л' осталось допустимым в Д, должны выполняться условия (5.14) л" А =л'А,+Ол'Аг с,.
Если л'А1(0, то нет никаких проблем. Более того, если л'А1(0 для всех!, то сразу видно, что можно увеличивать О в (5.11) неограниченно, получая, таким образом, сколь угодно большую стоимость в (5.12). Отсюда в свою очередь следует, что задача Д неограниченна и, следовательно, что исходная прямая задача П недопустима. Так как л оптимально (и, следовательно, допустимо) в ДОП, то л'А1(0 для )Ел'. Таким образом, мы установили следующий факт. 5.2. Прина-д«оестагнныа алгоритм Теорема 5.1.
Если в ОП $,„,)0 и оптимальное решение двойственной задачи удовлетворяет условиям л'А.(0 для 1(У, то задача П недопустима. Таким образом, за сохранением допустимости нужно следить только в том случае, если л'Ау)0 для некоторого Я,(. Критерий допустимости в этом случае принимает вид л" А =л'А.+Ол'А (ср где 1(У и л'А ) О. (5.15) Получаем ситуацию, аналогичную ситуации в обычном симплекс- алгоритме, а именно О может изменяться в указанных пределах н ргосевнге ПРЯМО-ЛВ010СТВЕННАЯ Ьед!и недопустима; = «нет», онт: = «нет»; пусть и допустима в О (сопппепг: возможно использование (5.3)); пЫ!е нгдалустпма=«нет» и опт= «нет» во Ьее(п положить 3----(1: и'А!=с)); решить задачу ОП симплекс-алгоритмом; И $»от=о Гьеп опт: = «да» е1»е и и'А)..-О для всех 1ф3 гьеп недопустим»Е= «да» е1зе л: = и+ О,п (сопппеп1: см.
(5.16)) епв епв Рис. 5ак Прямо.двоиственный алгоритм. не далее. Более точно можно сформулировать этот результат в виде еще одной теоремы. Теорема 5.2. Если $,„, 0 в ОП и л'Аг)0 для некоторого 1(.(, то наибольшее О, при котором л*= — л+Оч остается допустимым, равно Г с.— и'А 1 (5, 15) г'егп й'лу ~ в При этом новая стоимость равна гс»=лЪ+0»лЪ=и»+О,л'Ь) гс.
Решив ограниченную прямую задачу и получив улучшенное решение задачи Д, мы заново определяем множество г и повторяем эту процедуру до тех пор, пока не возникне! одна пз след)югцнх ситуаций: либо $,„,=0 и в П будет достигнута оптимальность, !!2 Гл. д. Поямо-двойственный алгоритм либо, согласно теореме 5.1, иуде! показано, что П недопустима.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
