книги / Математические методы принятия решений
..pdfравен 4 + 1 = 5 (ед.). Дуги получают пометки (изменяют пометки только на дугах (s, 2), (1, 2) и (7, t)), представленные на рис. 3.9.
И т е р а ц и я 5. Приписываем источнику s пометку [оо; —]. Из узла s мы можем попасть только в узел 3. Для узла 3 имеем <?з = min{gs; us3 — f a3} = min{oo; +1} = +1; узел 3 получает помет
ку [+1; s]. Из узла |
3 попадаем в сток t : qt = m in{<73; u-ц —h t} = |
|||
= m in{l; 1} = +1. |
Сток t |
получает пометку [+1;3]. Изменение |
||
дуговых |
потоков для / аз и |
h t равно 1; соответственно получим |
||
/s 3 = 1, |
h t = 2 |
(на |
второй |
итерации /з* = 1). Максимальный по |
ток F равен 5 + |
1 = 6 (ед.). Дуги получают пометки, представлен |
|||
ные на рис. 3.10. |
|
|
Рис. 3.9. Четвертая итерация Рис. 3.10. Оптимальное решение
И т е р а ц и я 6. Приписываем узлу s пометку [оо; —]. Аугментальный поток не может быть найден, т. е. построенные дуговые потоки образуют оптимальное решение. Максимальный поток (мак симальное количество информации) из источника s в сток t ра вен 6 ед.: 2 ед. потока идут из источника s через узел 1 в сток t; 1 ед. потока идет из источника s через узел 3 в сток t; 3 ед. потока идут из источника s в узел 2 , затем 2 ед. потока поступают из узла 2 в сток t, a l ед. потока поступает в сток t через узел 3. Через дугу (7 ,2) информация не идет.
§ 3.8. Задача о многополюсном максимальном потоке
Мы рассмотрели задачу о максимальном потоке из единствен ного узла s в единственный узел t. В целом ряде технических и экономических приложений возникают задачи, в которых на до определить максимальный поток между любыми выбранными парами узлов в сети. Примерами таких систем являются: сети
автомобильных дорог, где автострады изображаются дугами, про пускные способности которых соответствуют максимально допу стимой интенсивности движения; телефонная или информационная сеть, где линии представляются дугами, а их пропускные способ ности соответствуют максимальному числу вызовов (или объему информации), которые могут обслуживаться в каждый момент вре мени; электрические и электроэнергетические системы, где линии электропередачи представлены дугами, а пропускные способности соответствуют максимальному объему электроэнергии, который мо жет передаваться по линиям в единицу времени, и т. п.
Задачи о многополюсных максимальных потоках бывают двух видов: анализа и синтеза сети.
1.Задача анализа сети. Задана сеть с ограниченными пропуск ными способностями дуг. Следует определить, каковы величины максимальных потоков, которые можно пропустить между всеми парами узлов в заданной сети.
2.Задача синтеза сети. Требуется построить сеть, в которой величины максимальных потоков fij между всеми парами узлов удовлетворяют заданным ограничениям снизу и в которой общая пропускная способность всех дуг максимальна.
Задачу о многополюсном максимальном потоке можно решить, опираясь на рассмотренную задачу о максимальном потоке между единственным источником и единственным стоком. Если пропуск ная способность каждой дуги не зависит от направления движения потока по этой дуге и если каждую пару узлов можно рассматривать как пару источник-сток, то общее число задач о максимальном по токе, которое должно быть решено, равно п(п —1)/2, где п —число узлов в сети. Рассмотрим здесь алгоритм Гомори—Ху, согласно ко торому максимальный поток в задаче о многополюсном максималь ном потоке определяют только п — 1 раз. Основная идея алгоритма состоит в итеративном построении максимального остова дерева, ветви которого соответствуют разрезам, а параметры ветвей — вели чинам разрезов.
Пусть G = (N , А) — неориентированная сеть, где N — множе ство узлов, А — множество дуг, и пусть Cij — пропускная способ ность дуги (г, j) из множества А, причем Су = Cji. Максимальный поток между узлами г и j равен г^-; (X , X ) ÿ —минимальный разрез,
отделяющий узел г от узла j (г е X ; j e Х )\ с{Х, Х )ц —пропускная способность минимального разреза, отделяющего узел г от уз ла j. Согласно теореме о максимальном потоке и минимальном разрезе Уц = с(Х, X)ij. Если некоторый узел к принадлежит X , то Vik ^ с(Х, X)ij, а если к е X , то Vkj ^ с(Х, X ) ÿ . Следовательно, Vij ^ Щк и vij ^ Vkj- Поэтому Vij ^ min{vifc; Vkj}. Если рассмотреть в общем случае связанное подмножество узлов {t, р, к, q,j}, то
Vij ^ min{uip; vpk; vkq; vqj}.
С другой стороны, для максимального остовного дерева
^ min{vjP; vpk', Vkq, vqj },
где (г, j) —произвольная дуга, не принадлежащая данному дереву. Если это не так, то вместо любой дуги пути из узла г в узел j можно взять дугу (г, j), в результате чего будет построено дерево с большим весом. Отсюда для любой дуги, не принадлежащей де реву, имеем
v^ = min{vjp; vpk', Vkql vqj }.
Максимальное остовное дерево, удовлетворяющее последнему равенству, называют деревом разрезов потому, что каждая его ветвь соответствует разрезу, а вес ветви равен пропускной способности разреза. Если требуется определить величину максимального пото ка между двумя противоположными узлами, необходимо в дереве найти путь, соединяющий эти два узла, и выбрать на этом пути дугу с минимальным весом. Ее вес равен величине максимального потока между рассматриваемыми узлами.
Если некоторый узел рассматривать как источник s, а другой узел как сток t, то максимальным потоком между ними является vat = с(Х, X)st. Если затем в качестве источника и стока выби рают другую пару узлов г, j, удовлетворяющих такому условию, что они оба принадлежат подмножеству X (или X), то подмно жество узлов X (или X , если узлы г, j принадлежат X ) может быть объединено в один конденсированный узел. При этом величи на максимального потока из узла i в узел j будет одной и той же для исходной и конденсированной сетей и в алгоритме Гомори—Ху при определении величины v^ используют решение задачи о мак симальном потоке, найденное на предыдущем шаге.
Пусть Nij —множество узлов, образуемое в результате конден сации всех узлов, лежащих по ту сторону разреза, где не содержатся узлы i и j; Aij — множество дуг, соединяющих узлы из множе ства Nij. Если известны пропускные способности дуг, принадле жащих А ^, то для нахождения величины максимального потока между узлами г, j можно воспользоваться процедурой расстановки пометок.
В свою очередь, пропускные способности дуг из А ц опреде ляют следующим образом. Пусть •••, j r — узлы из подмноже ства X , непосредственно связанные с узлом i е X . При конденсации подмножества X дуги (г, j\), (г, j{), ■.., (г, j r) заменяют одной дугой, соединяющей узел i и конденсированный узел подмножества X . Пропускная способность такой дуги вычисляется по формуле
|
Г |
CiX = °*31 ^32 + |
+ °гЗт = 2 °*3т ■ |
|
771=1 |
Для определения величины vij вновь надо найти минималь ный разрез (X , X)ij с минимальной пропускной способностью, от деляющий узел i от узла j. Теперь можно выбрать другую пару узлов, принадлежащих либо X , либо X , и построить конденси рованную сеть. В результате выполнения процедуры расстановки пометок можно будет определить другой разрез и построить новую конденсированную сеть и т. д.
Задача. В сети (рис. 3.11) для каждой пары узлов определить величину максимального потока информации между ними.
Рис. 3.11. Исходные данные для зада- |
Рис. 3.12. Начало построе- |
чи о многополюсном максимальном |
ния дерева разрезов |
потоке информации |
|
Р е ш е н и е . Для простоты сначала найдем максимальные пото ки между узлами N\, N3, N4 и N5.
И т е р а ц и я 1. Выберем два произвольных узла, скажем Ni и ЛГ3, и найдем максимальный поток между ними (путем процедуры расстановки пометок). Получим минимальный разрез (Ni, N2, Ne | Nз, N4, N5). Пропускная способность дуги, соединяющей конден сированные узлы, равна 4 + 2 + 2 + 2 + 3 = 13. Начало построения дерева разрезов представлено на рис. 3.12.
И т е р а ц и я 2. Найдем максимальный поток между узлами N 3 и Ni (рис. 3.13). Здесь узлы Ni, N 2 и Ne объединены в кон денсированный узел. Узел N3 соединен с узлами N2 и Ne, т. е. пропускная способность дуги от конденсированного узла к узлу N 3 будет равна 4 + 2 = 6. Узел N5 соединен с узлами N2 и Ne, т. е. пропускная способность дуги, соединяющей конденсированный узел с узлом N5, равна 2 + 3 = 5. Величина максимального пото ка равна 5 + 2 + 7 = 14, минимальный разрез имеет вид (Ni, N2, Ne, N3, N5 I N4). По минимальному разрезу определим, что узлы (N3, N5) и (Ni, N2, Ne) лежат по одну сторону в минимальном раз резе, разделяющем узлы N3 и N4. Получим дерево, представленное на рис. 3.14.
Рис. 3.13. К определе- |
Рис. 3.14. Построение |
нию максимального пото- |
дерева разрезов |
ка между узлами N 3 и Ni |
|
И т е р а ц и я 3. Найдем |
максимальный поток в той же сети |
(см. рис. 3.13) между узлами N3 и N5. Получим минимальный раз рез (Ni, N2, Ne, N5, N4 I N3). Величина максимального потока равна 5 + 4 + 7 = 16. Символическое изображение сети представ лено на рис. 3.15. Теперь каждая интересующая вершина в полу ченном дереве (см. рис. 3.15) содержит только по одному полюсу
и максимальные потоки будут / п = /14 = /15 = 13 (они равны мини мальной пропускной способности дуги на данном пути), /34 = /45 = = 13, /35 = 16. Эти потоки равны соответствующим максимальным потокам в исходной сети (см. рис. 3.15).
Рис. 3.15. Символическое |
Рис. 3.16. Нахождение мак |
изображение сети с помо |
симального потока между |
щью дерева разрезов |
узлами N\ и ЛГ6 |
Если необходимо найти величины максимальных потоков меж ду всеми парами узлов, то следует процесс продолжить.
|
И т е р а ц и я 4. Найдем максимальный поток между узлами N\ |
||
и Ne в сети, изображенной |
на рис. |
3.16. Минимальный раз |
|
рез |
(N \, N2 I Ne, Ni, N4, N$), |
имеющий |
пропускную способность |
6 + |
3 + 8 = 17, изображен на рис. 3.17. |
|
Рис. 3.17. Построение дерева разрезов
И т е р а ц и я 5. Найдем максимальный поток между узлами N\ и N 2. Минимальный разрез (N\ | N 2, N 2, N4 , N5, Ne), имеющий пропускную способность 10 + 8 = 18, приведен на рис. 3.18. С по мощью дерева, представленного на рис. 3.18, можно определить
Рис. 3.18. Дерево разрезов
величины максимальных потоков между всеми парами узлов (табл. 3.9).
Т аблица 3 .9
Величины максимальных потоков между узлами сети
Узел |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
оо |
18 |
13 |
13 |
13 |
17 |
2 |
18 |
00 |
13 |
13 |
13 |
17 |
3 |
13 |
13 |
оо |
14 |
16 |
13 |
4 |
13 |
13 |
14 |
оо |
14 |
13 |
5 |
13 |
13 |
16 |
14 |
оо |
13 |
6 |
17 |
17 |
13 |
13 |
13 |
оо |
Если в двух сетях равны величины максимальных потоков меж ду парами узлов, принадлежащих некоторому заданному множе ству, то эти сети называют потоко-эквивалентными по отноше нию к заданному множеству узлов. Заметим, что существует много деревьев, которые потоко-эквивалентны некоторой заданной сети. Потоко-эквивалентное дерево (см. рис. 3.18) обладает следующей особенностью: каждая ветвь этого дерева соответствует некоторо му минимальному разрезу в исходной сети. Поэтому его называют деревом разрезов. На дереве разрезов для сети, содержащей п узлов, показано п — 1 минимальных разрезов исходной сети, не пересека ющихся друг с другом (см. рис. 3.11).
§ 3.9. Методы ветвей и границ. Задача коммивояжера
Методы ветвей и границ предназначены для решения широкого круга дискретных оптимизационных задач. Различные методы вет вей и границ существенно используют специфику конкретных задач и поэтому заметно отличаются друг от друга, но все они основа ны на последовательном разбиении допустимого множества реше ний D на подмножества (ветвления) и вычислении оценок (границ), позволяющих не рассматривать подмножества, заведомо не содер жащие решения задачи.
Пусть требуется найти точку минимума функции /(х ) при х е D. В зависимости от специфики задачи выбирается способ вычисле ния оценок снизу d(Df) функции /(х ) на подмножествах D f a D
(может быть, что D' = D):
f{x)>dlD'), x e D '
Оценка снизу часто вычисляется путем релаксации, т. е. замены задачи минимизации функции /(х ) на множестве D' задачей мини мизации по некоторому более расширенному множеству. Например, в целочисленных задачах не учитывают требование целочислен ное™.
Выбирается также правило ветвления, состоящее в выборе раз ветвляемого подмножества D' из числа подмножеств, на которые к данному шагу разбито множество D, и выборе способа разбие ния D' на непересекающиеся подмножества: ветвлению подверга ется подзадача минимизации функции /(х ) на подмножестве D' Обычно для ветвления выбирается подмножество D' с наимень шей оценкой значения целевой функции, поскольку в таком мно жестве естественно искать минимум в первую очередь. При этом рассматриваются только такие способы вычисления оценок снизу, в которых оценки для подмножеств, получившихся в результате раз ветвления подмножества D', не меньше d(D').
При решении релаксированной задачи может оказаться, что:
а) допустимое множество этой задачи пусто и, стало быть,
D' = 0 ;
б) значение минимума d(D') для релаксированной задачи боль ше или равно наименьшему из уже вычисленных значений функ
ции /( х ) (текущему значению рекорда), и потому min /(х ) достига-
1 6 D
ется вне множества D';
в) точка минимума для релаксированной задачи принадлежит множеству D' и, стало быть, является точкой минимума /(х ) на D' Во всех трех случаях подмножество D' далее не разветвляется.
В случае а) текущее значение рекорда полагается равным миниму му из предыдущего текущего значения и вычисленного значения
min /(х ). xeD'
В методе ветвей и границ на каждом шаге искомое значение не больше текущего значения рекорда (верхней границы) и не мень ше наименьшей из оценок снизу для подзадач, входящих на данном шаге в число кандидатов на ветвление (нижней границы).
Существуют варианты метода ветвей и границ, разработанные специально для нахождения приближенного решения различных задач.
Пример. Рассмотрим решение целочисленной задачи линейного программирования:
|
|
/(ж) = |
CjXj -» min |
|
при |
П |
3 = 1 |
|
|
|
|
|
||
|
|
|
|
|
|
^ Q*ijXj ^ |
bj, % 1,2,..., 771, |
Xj ^ 0 , J 1, 2, ..., U, |
|
|
3 = 1 |
|
j e J a {1,2, ...,n } . |
|
|
X j e { 0 , 1,2,...}, |
|||
|
Допустимое |
множество Z? задачи |
предполагается ограничен |
ным, оценки снизу вычисляются с помощью релаксации — без усло вия целочисленности переменных. Оценку снизу получают с помо щью симплекс-метода.
Если после применения симплекс-метода решение не являет ся целочисленным, то на первом шаге алгоритма выбирается лю бая нецелочисленная компонента ж ' ,, r \ e J, полученного решения и исходная задача разветвляется на две подзадачи: первая — с допол нительным ограничением жГ| ^ [ж£ ], вторая —с дополнительным
ограничением х Т[ ^ [х^] + 1, где [ ] —целая часть числа. Вычис ляются оценки снизу, и если обе подзадачи остаются в числе кан дидатов на дальнейшее ветвление, то для ветвления на втором шаге выбирается подзадача с минимальной оценкой.
На к-м шаге выбранная на (к — 1)-м шаге подзадача разветвля ется на две новые с дополнительными ограничениями х Гк ^ [x£fc] и х Тк ^ [x £ j + 1 соответственно, где х Гк, е J, —любая нецело численная компонента решения х к задачи ЛП, получающейся ре лаксацией подзадачи, выбранной на (к — 1)-м шаге. Для новых под задач вычисляются оценки снизу. Формируется список кандидатов на ветвление. Для ветвления на (к + 1)-м шаге из числа кандидатов на ветвление выбирается подзадача с минимальной оценкой.
Конечность алгоритма следует из ограниченности множества D. Процесс ветвления существенно упрощается, если в задаче име
ются ограничения
Xj £ {0,1}, j e J e {1,2, ...,n } .
Задача коммивояжера. В гл. 1 мы упоминали задачу о Кё нигсбергских мостах, в которой требовалось обойти все мосты, не проходя ни один из них дважды, т. е. пройти все мосты по крат чайшему пути.
Можно привести и другую постановку этой задачи в более об щем виде. Некто решил, что настало время посмотреть жизнь в дру гих странах. Он выбрал семь мест, которые намеревался обязатель но посетить, получил информацию о стоимости билета на самолет в каждый из выбранных городов и стоимости проезда из одного города в другой. Учел все льготы, предоставляемые авиакомпания ми, и составил матрицу стоимостей (табл. 3.10) проезда в выбран ные города и обратно. Зная матрицу стоимостей, путешественнику надо так составить маршрут, чтобы затраты на это путешествие были минимальными и чтобы выполнялось естественное требова ние: каждый пункт посещается только один раз. Матрица стоимо стей проезда из-за льгот авиакомпаний оказалась несимметричной. При симметричной матрице стоимостей процедура решения задачи
не изменяется.
Таблица 3.10
М атр и ц а стоимости проезда (уел. ед.)
№ |
Пункт |
Исходный |
Токио |
Гонконг |
Лондон |
Сидней |
Рим |
|
1 |
2 |
3 |
4 |
5 |
6 |
|||
|
|
|||||||
1 |
Исходный |
— |
270 |
430 |
160 |
300 |
260 |
|
|
|
|
|
|
|
|
||
2 |
Токио |
70 |
— |
160 |
10 |
300 |
300 |
|
3 |
Гонконг |
200 |
130 |
— |
350 |
50 |
0 |
|
4 |
Лондон |
210 |
160 |
250 |
480 |
180 |
180 |
|
5 |
Сидней |
120 |
460 |
270 |
— |
50 |
||
6 |
Рим |
230 |
50 |
50 |
90 |
50 |
— |
Примечание. В процессе проведения расчетов все стоимости будут уменьшены в 10 раз.
Подобные задачи в математическом программировании называ ются задачей коммивояжера. Ее формулируют следующим обра зом. Коммивояжер должен выехать из исходного пункта и побывать в каждом из остальных п — 1 пунктов ровно один раз и вернуть ся в исходный пункт. Задача заключается в определении после довательности посещаемых пунктов, при которой коммивояжеру требуется минимизировать некоторый критерий эффективности: