Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 20
Текст из файла (страница 20)
Программа для прямо-двойственного алгоритма в общих чертах представлена на рис. 5.2 5.3 Комментарии н прямо-двойственному алгоритму Весьма удобно то обстоятельство, что на каждой итерации решение задачи ОП можно начать с оптимального решения, полученного на предыдущей итерации.
Это вытекает из того, что никакая переменная, входящая в У и входящая также в оптимальный базис задачи ОП в конце итерации, не может выйти из о' в этот момент. Более формально справедлива Теорема 5.3. Лгобой допустимый столбец в оптимальном базисе задачи ОП остается допустимым в начале следующей итерации. Доказательспгво. Если столбец Аг входит в оптимальный базис задачи ОП в конце итерапии, то его относительная стоимость )в ОП) равна с,=- — и'А!=0. Отсюда и" А, = Я'А, + П,п'Аг — — с, поэтому ! остается в множестве у д Этот факт не только дает возможность начинать итерацию с пре. дыдущего допустимого решения, но также позволяет использовать модифицированный симплекс-метом поскольку мы можем не бояться, что какой-нибудь базисный столбеп стал недопустимым.
В заключение рассмотрим вопрос о конечности пряча-двойственного алгоритма. Заметим, во-первых, что если минимум в )5.)6) при вычислении О, достигается при )=)„то !. становится новым элементом множества /, так как, согласно (5. )5), и"'А и=си. Кроме того, относительная стоимость нового столбца )в в ОГ! равна — и'А,,(0, поэтому на новой итерации в ОП будет выполняться по крайней мере одна операция замещения. Если рассмотреть все переменные в ОП, соответствующие исходным столбцам, как допустимым, так и недопустимым, плюс все искусственные переменные, то получается, что мы переходим от одного бдр к другому. При отсутствии вырожденности в ОП стоимость $.„, монотонно убывает на каждой итерации прямо-двойственного метода, никакой базис в ОП не повторяется и метод является конечныч.
Если имеются вырожденные бдр в ОП, то можно гарантировазь конечность, используя какое-нибудь правило, устраняющее повторение базисов, как в любом прямом симплекс-алгоритме. 5.В. Задача а кратчайшем кути пз Подытожим сказанное выше следующей георемой. Теорема 5.4. Прямо-двойственный алгоритм, приведенный на рис. 5.2, корректно решает задачу П за конечное время.
5.4 Прямо-двоиственный метод в применении к задаче о кратчайшем пути Для иллюстрации прямо-двойственного метода вернемся к задаче о кратчайшем пути (ЗКП), сформулированной с помощью матрицы инциденций вершин и дуг. Это также послужит для нас основой его эффективного применения к более общим задачам на сетях. Итак, имеем задачу щ(п с'Г г строка в -1- 1 1 0 (П) о ~)О, где А — это (т — 1)хл-матрица инциденций вершин и дуг ориентированного графа 6=()', Е) с т верщинамн н и дугами, в которой строка, соответствующая стоку О опущена (она является излишней); 1 Е еч" — вектор потока (в данной задаче с компонентами 0 нли 1), с Е е(" — вектор стоимости. Двойственной задачей будет щах л„ л,— л (сео для всех дуг (1,1) ЕЕ, л,~~О для всех 1, (Д) д =(дуги ((, 1): л,— л =с, ), где мы должны положить л,=О, так как соответствующая строка в А опущена. Множество допустимых дуг определяется тогда следующим образом: Гя.
5. праио-дводственнма алгоршпи 114 и ограниченная прямая задача принимает внд га-1 ш(п$= Х х,', ! ' + 1 ' — строка з 0 Аг+ х' = (ОП) 0 ~~)0 для всех 1, ~1=0, 4>0. Наконец, задача, двойственная к ограниченной прямой задаче, имеет вид тахш= и„, и,— и (0 для всех дуг (1, 1) Е /, и, (1 для всех 1, л1 ~~ О. Теперь ДОП очень легко решить: так как п,(1 и мы хотим мак- симизировать п„то испытаем п,=1.
Если нет пути из з в й ис- пользующего только дуги из l,* то можно продвинуть 1 из з во все вершины, достижимые из з по некоторому пути, так, что не бу- дут нарушаться ограничения п,— п1(0, и оптимальным решением для ДОП тогда будет 1 для всех вершин, достижимых из з по путям, использующим дуги из l, 0 для всех вершин, из которых 1 достижимо с (5.17) использованием дуг из у, 1 для всех остальных вершин. (Заметим, что это и не единственно возможное.) Затем можно вычислить О~ а1п (сп — (и,.— и )), и. пез:а,.-й~> з найти новые л и У и заново решить ДОП.
Если мы придем к тому, что имеется путь из з в 1 с использованием дуг из У, то п,=О, н решение оптимально, так как е,„=ш,„=-0. При этом любой путь из а в 1, использующий только дуги из з', оптимален. Таким образом, благодаря прямо-двой:твенному алгоритму задача о кратчайшем пути сводится к многократному решению более простой задачи нахождения множества вершин, достижимых из данной вершины. д.е. Задача о кратчайшем пути Пример 5.1. На рис. 5,3 представлена задача о кратчайшем пути, несколько более сложная, чем наш предыдущий пример.
Так как стоимости неотрицательны, можно начать с п=О в задаче Д. На ! 3 3 2 О! 4 Рис. 5.3. Пример задачи о кратчайшем пути. Числа в кружках — веса дуг. рис. 5.4 показана последовательность пяти итераций прямо-двойственного метода, приводящая к оптимальному решению п=(6, 5, 5, 2, 4) и соответствующему множеству дуг а', которое содержит оптимальный путь. Любой путь из з в ! в окончательном допустимом множестве дуг будет удовлетворять условию дополняющей нежесткости и, следовательно, будет оптимальным; в данном случае оптимальным будет путь (е„е„е„, е,) со стоимостью 6=па, Отметим теперь те свойства этого алгоритма, с помощью которых можно дать очень простую интерпретацию происходящему.
Первое, если мы определим на каждом шаге нашего алгоритма множество Яу=(ю': 1 достижимо из 1 по допустимым дугам) (ю: я!=О), тогда переменная и, остается фиксированной с момента, когда 1 попадает в Ф', до конца алгоритма, так как соответствующее пе всегда будет нулем. Второе, каждая дуга, которая становится допу. стимой (входит в з'), остается допустимой в течение всего алгоритма, так как если и, †я!==;; для дуги (1, !) Е Е, то мы всегда изменяем и; и и, па одну и ту же величину в соответствии с (5.!7). Нетрудно понять, что по 1 Е йт, — это длина кратчайшего пути из 1 в 1 и что на каждом шаге алгоритма к 1Г добавляются вершины из Т», ближайшие к 1.
С некоторым уточнением этот прямо-двойственный алгоритм, примененный к задаче о кратчайшем пути, является на самом деле алгоритмом нахождения кратчайшего пути Дейкстры. который мы опишем более подробно в гл. 6 (1)!). Гл. 5. Прямо-даойсшаанный алеорятм 11О В заключение отметим, что имеется определенная граница числа шагов, необходимых длв прямо-двойственного алгоритма, приме- ДОП ш)! О о о л = (о, о, о, о.о) 1 1 л-(»,,»,,!) И! раи«» ! 1 о е;::,7 1 !7! с:::'у (а>-г д, ° (ду!и еа 1 ( 2 2 л-(2 2 2 22) л = (>, 1, >, О, 1) 1 О И!»рация 2 ш:р 7.(7,6( Ш,> л=(4,4,4,2,4) л-(>,>,>,О,О) >>~ >ми«а 5 0,=1»»» »УЕИ Ез л=(55,5,2,4) >!тара«и» 4 л-(>,о,о,о, о) о о С-„' .1 - ',7,6,5,4,2' С:ф О О О Л (6, 5,5,2, 4) Итараци» 5 я=(0,0,0,0,0) Рис. 5.4, Решение зала«и о кратчайшем пути с использояаиием прямо-даойстяеииого алгоритма.
ненного к задаче о кратчайшем пути, Так как множество (р' растет по крайней мере на одну вершину на каждом шаге, то не может быт! более чем ()7~ шагов, 5 2 о >-ъ' У = > 7, 6, 5, 4 ! — ъ> 1 ° 5 (а =2 д»» 1() ду«ц е. а Пт о.е. Эадача о максимальном аооьокг Замечания по методологии Давайте ненадолго вернемся назад и посмотрим, что делает прямо-двойственный алгоритм. Мы начали с общей задачи линейного программирования П н вектора стоимости с; заменили их итеративным решением задачи ОП, которая не зависит явно от вектора стоимости с, а зависит от него только через множествоl допустимых переменных. Ценой итеративного цикла, представленного на рис.
5.1, избавились от сложностей, связанных с рассмотрением общего вектора стоимости. Для краткости будем говорить, что мы «комбинаториализовали» стоимость. Можно также взглянуть на проделанное с точки зрения двойственной задачи. Переходя от Д к ДОП, мы комбннаториализовали правую часть. Схематично можно записать П вЂ” ОП комбинаториализует стоимость, Д ДОП комбннаториализует правую часть. (5.18) В задаче о кратчайшем пути правая часть в П, по существу, тривиальна, и все численные данные задачи входят в нее через вектор стоимости. Поэтому ОП и двойственная ей задача вообще не зависят явно от численных данных исходной задачи, а зависит только от допустимого множества /, н мы получаем чисто комбинаторную задачу, которая в данном случае оказалась задачей о достижимости.
Метод, состоящий в том, чтобы начиная с одной задачи итеративно решать подзадачи, которые «более комбинаторны», с применением прямо-двойственного алгоритма, является центральным в комбинаторной оптимизации. Это основа почти любого эффективного алгоритма для задач о потоках н паросочетаниях. Применим теперь эту идею к задаче о максимальном потоке. 5.6' Прямо-двойственный метод в применении к задаче о максимальном потоке Наш план в данном параграфе следующий: сначала сформулиру'ем задачу о максимальном потоке в форме вершин и дуг. В этой задаче ЛП будет, по существу, тривиальный вектор стоимости; численный вход задачи (пропускные способности) появится в правой части. Затем будем рассматривать задачу о максимальном потоке .как двойственную задачу (вспомните (5.18)), с тем чтобы комбинаториализовать ее данные.
Подзадачи опять будут задачами достижимости, которые в данном случае являются задачами нахождения увеличивающих путей. Рассмотрим' этот путь подробнее. Пусть И=(з, й к', Е, Ь)— »потоковая сеть с и= (1~( вершинами и т= )Е~ дугами, и пусть поток -на дуге (х, у) обозначается через )(х, у). Тогда поток величины и Гл. Б. Прямо-двойственный алгоритм ич э в 1 определяется условиями +о для строки з, А~ = — о для строки 1, О для других строк, Г<Ь, авэо, (5.19) где А — матрица инциденций вершин и дуг ориентированного графа ()', Е) и 1, ЬЕР" — соответственно векторы потока и пропускных способностей. Задача состоит в максимизации о при ограничениях (5.19).
Несколько переделаем эту задачу, используя вектор с(Е!с", определиемый равенством — 1, 1=а, с(,= +1, 0 в остальных случаях. (5.20) Тогда наша задача ЛП принимает вид шах о, А)+с(о<0, 1<Ь, (Д) (5.2 !) — )<О, тахо А1+с(о<0 для всех строк, ) < для всех строк, где ) =Ь в Д, — ) <О для всех строк, где Г=О в Д, Г< 1, о<1, Эта задача имеет следующую интерпретацию. Требуется найти путь из а в ! (для потока величины !), в котором насыщенные дуги могут (Заметим, что из неравенства А!+Но~0 следует А)+г(о=О, так как дефицит в балансе потока в любой вершине влечет за собой излишек в некоторой другой вершине.) Итак, мы достигли нашей цели, а именно представили задачу о максимальном потоке в виде задачи, двойственной к некоторой задаче ЛП в стандартной форме; теперь мы хотим комбинаториализовать правую часть путем рассмотрения ДОП. Сравнение задач Д и ДОП, приведенных выше в этой главе, дает для этого очевидное правило: мы заменяем правую часть на О, вычеркиваем строки, не входящие в л', и добавляем ограничения ), о~!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
