Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 37
Текст из файла (страница 37)
9. Алгоритм дефекта является итеративной процедурой, выполняющей для заданной сети с ограниченной пропускной способностью ~поиск циркуляции, минимизирующей суммарную стоимость потоков по всем дугам. 3.2. СВЕДЕНИЕ ИСХОДНОИ ЗАДАЧИ К ЗАДАЧЕ ЛИНЕИНОГО ПРОГРАММИРОВАНИЯ Рассмотрим ориентированную дугу, соединяющую узел 1 с узлом 1. Пусть )и — величина потока по этой дуге. ттудем предполагать, что: 1. Ь=О, если поток по дуге отсутствует; 2. )п)О, если поток протекает из узла Г в узел г. С помощью введенных обозначений на рис.
3.4 изображена часть некоторой сети. Рис. Зчй Обозначения для сетей е ограниченной пропуенной способностью. (3.2) 15' Рассматриваемая потоковая задача может быть сформулирована в виде специальной задачи линейного программирования. Поскольку стоимость прохождения единицы потока по дуге ((, !) равна сп, то задача минимизации суммарной стоимости формулируется следующим образом: минимизировать ')'„с,Д~ (3.1) (г. пта при ограничениях ~на пропускные способности дуг Ум<(~;и (г,!) Р» )м > ~ц. (1 д Ф. Для того чтобы количество продукта, поступающего в узел, равнялось количеству продукта, выходящего из этого узла, требуется выполнение условия сохранения потока, т. е. ~~)' 7п — '~~~~м — — О для всех ю9Ч, 1 ~ /. (3.3) тен /ек 228 Глава 3 Кроме того, требуют, чтобы потоки были неотрицательными: »(»> О для всех дуг ((,)).
Задача нахождения циркуляции минимальной стоимости представляется в виде специальной задачи линейного программирования (3.!) — (3.3). Именно на основе этой основной формулировки будет описан алгоритм дефекта. При этом используются условия оптимальности, которые следуют из теории двойственности линейного программирования.
Перепишем (3.1) — (3.3) в более удобной форме: максимизировать ~~~~~ — с,Д» ((, пбз при условии, что )„)(» — )»»( — — О для всех (ЕХ (условие сохранения потока), »ен»ен »(»< (»(» (ограничения на потоки сверху), — »(» < — ».(» (ограничения на потоки снизу), »'(» > О (условие неотрицательности потока). В данной формулировке для удобства последующего описания алгоритма целевая функция умножена на — 1. При этом задача минимизации трансформировалась в задачу максимизации, ко- торую будем называть прямой задачей.
Согласно известному в линейном программировании результату, для любой прямой за- дачи существует соответствующая ей двойственная задача. В рассматриваемом случае двойственная задача формулирует- ся следующим образом: минимизировать ~~)' У(»а(» — Е(»6(» (с и Ез при условии, что я,— и»+(х(» — 6(» > — с(» для всех ((, 1) Е$, »(( не имеют ограничений по знаку для всех (аХ, а(»>О для всех ((,»)ЕЬ, 6(,>О для всех ((,»)ЕЗ. В данной формулировке переменные г( соответствуют ограниче- ниям, описывающим условие сохранения потока для прямой задачи, и могут принимать произвольные значения, поскольку эти ограничения имеют вид равенств.
Переменные а в двойст- венной задаче соответствуют ограничениям сверху на потоки по 229 Алгоритм дефекта дугам в:прямой задаче, а переменные б — ограничениям снизу Каждой переменной ~п в прямой задаче соответствует некоторое ограничение в двойственной задаче. В качестве, примера предположим, что из источника 1 в сток 4 по сети, изображенной на рис.
3.5, требуется доставить. трн единицы продукта. Каждой дуге (1, 1) сети приписана трой- <з.з.о1 Рис. 3.5. Открытая сеть с ограничен- Рис. 3.6. Замкнутая сеть с ограии. иой пропускной способностью. чеииой пропускной способиосгью. ка (Уп, 1.гь сн). Для данной задачи необходимо «замкнуть» исходную сеть, добавив к ней возвратную дугу (4, 1).
Величина потока, который требуется доставить из источника 1 в сток 4, будет равна величине потока по дуге (4, 1) и поэтому определять ее можно, полагая г'.е1=0м — — 3. Стоимость единицы потока по дуге (4, 1) должна быть нулевой, т. е. со=О. Полная сеть циркуляции изображена на рис. 3.6. Прямая и двойственная задачи для данного примера сформулированы в табл.
3.1 и 3.2. Таблица Д1. Прямая задача 236 Алгоритм дефекта Обратимся к рассмотрению прямой и двойственной задач с тем, чтобы разработать метод, который позволял бы: 1. Всегда находить оптимальные решения (если они существуют). 2. Вычислять оптимальные решения более эффективно, чем это позволяют сделать общие алгоритмы решения задачи линейяого программирования. В следующем разделе с помощью теории д~войственности в линейном программировании будут получены условия оптимальности.
з.з. ОснОВные теоремы Решения прямой и двойственной задач являются оптимальными в том и только в том случае, если: 1. Оба решения допустимы. 2. Для любой положительной двойственной переменной соответствующее ограничение в прямой задаче является жесткимо. 3. Для любого ограничения в двойственной задаче, не являющегося жестким, значение соответствующей переменной в прямой задаче равно нулю.
Последние два условия называются условиями дополняющей нежестяости и вместе с условиями допустимости они составляют необходимые и достаточные условия оптимальности решения задачи о циркуляции минимальной стоимости [71. Условия допустимости для прямой задачи Р,: ~~)' )ц — '«~~7тз — — О для всех!9Ч (сохранение потока), ! г Р;.
7.ц < г'ц < (7ц для всех ((,)) Е8 (ограничения на пропускную способность). Условия допустимости для двойственной задачи 17;. и,— пт+ац — йц > — сц для всех ((,)) ЕВ, .У;. ссц й для всех (Е,)) 68, Рзг бц)~ О для всех (1,)) ЕЯ. Условия дополняющей нежесткости Ст. 'если пз — ят + сец — бц ) — сц то )ц = О о жестким называется такое ограничение, что при заданном решении левая его часть раааа правой.
232 Глава 8 в~~: если ац> О, то Гц — Уц, С,: если бц) О, то 1ц — — 1,ц. Эквивалентная форма условий оптимальности задается следующими соотношениями 131: 1. Если и,— и, > ец, то ац > 0 и 1ц=Уц. 1!. Если ат — и, (ец, то бц) 0 и ~ц=1.ц. 111. Если п~ — п,.=сц, то Уц>1ц>Ец' при условии, что 1Ч. ац=гпах10, пт — и,— сц1, Ч. 6ц = шах 1О, — и, + и, + ец1, Ч1.
'«~ Гц — ~~,~д — — 0 для всех Е ! ! Данные условия позволяют проводить очень эффективный поиск оптимального решения путем последовательных изменений век- тора решения, поскольку требуется проверять только условия .!, 11 и П1, которые не содержат двойственных переменных а и 6. Предполагая, что условия 1Ч и Ч выполнены, и вводя обо- значение ец=сц+я; — пь перепишем условия 1, П, П1 и Ч1 в более удобной форме: Ац если ец(0, то Ь=Уц', йв. если ец>0, то 1ц=.1,ц, вз' если ец=О, то 1.ц(~ц(Уц, Ал. условие сохранения потока.
Если для узлов 1 и / и дуги, соединяющей их, выполнено одно из условий оптимальности йь лв нли лв, то говорят, что дуга яв- ляется бездефектной. Если же одно из условий Аь йв или йв на- рушено, то дуга называется дефектной. Решение является оп- тимальным, если устранены дефекты всех дуг и выполнено ус- ловие сохранения потока !условие йл). Если же таких потоков по дугам не существует, то допустимого решения задачи не су- ществует. ЗЛ. АЛГОРИТМ ДЕФЕКТА ДЛЯ РЕШЕНИЯ ЗАДАЧИ О ЦИРКУЛЯЦИИ МИНИМАЛЬНОЙ СТОИМОСТИ Прн работе алгоритма дефекта определяются значения п~ и 1ц, для которых выполнены условия оптимальности Аь йц лв и А4. Работу алгоритма можно начать, приписывая дугам произвольные потоки, удовлетворяющие условию сохранения, а узлам — произвольные величины пь При работе алгоритма каждая дуга может находиться в одном из девяти взаимно исклю- 233 Алгоритм дефекта Таблица 8.8. Возможные состояния дуги чающих состояний, связанных с условиями оптимальности (табл.
3.3). Проверяя состояния дуг, можно изменять потоки по ним до тех пор, пока не будут выполнены условия оптимальности. По значению си можно однозначно определить, является ли дуга дефектной или нет, а также выявить, что нужно делать — увеличивать или уменьшать поток по дуге, для того чтобы она перестала быть дефектной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
