Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 43
Текст из файла (страница 43)
11.1 имеется одно !) См. упр. 2 к гл. 9 и работу [90).— Прим. иерее. т) Следовательно, в исходной сети не могут быть реализованы одновременно заданные требования к потоку. )(ействительно, нетрудно показать, что если в некоторой сети одновременно реалиаованы заданные требования к потоку, то эта сеть представима в виде линейной выпуклой комбинации допустимых сетей.— Прим. иерее. 112Ь МНОГОПРОДУКТОВЫЕ ПОТОКИ Таблица 11.1 1) Б! Ба Ба Ба ББ Таблица 11.2 Б1 ББ Ба Ба ББ ха 1/2 1/6 — 1 7/2 1 — 1/3 5 1 — 1/2 О 1/2 1/6 4 О 1 6 3/2 — 1/3 1 5 е М Все вуетые иеета в таблицах еавачают вули. небольшое отличие от записи, используемой в гл.
5: ранее стоящий справа столбец Ь теперь является нулевым столбцом. В верхнем левом углу таблицы ааписывается значение целевой функции. В табл. И.1 я = [О, О, О, О, 0), поэтому любая сеть, удовлетворяющая требованиям к потоку, будет самой дешевой. В частности, можно взять такую сеть: [2, 3, 6, О, 2). Здесь, чтобы пропуетить 2 единицы 1-го продукта иэ Л/1 в Л/2, взята дуга 5 = 1 с пропускной способпостью 2; второй продукт величины 3 из Л/а в Л/е пропускается по дугам 5 = 2 и 5 = 3, каждая пропускной способности 3; чтобы пропустить'3-й продукт из ЛББ в Л, величины 3 используется снова дуга 1 = 3, для чего ее пропускная способность увеличивается еще на 3 единицы (в результате становится равной 6); наконец, 4-й продукт величины 2 из Л/1 в Л15 пропускается по дуге Б = 5 пропускной способности 2.
Эта сеть [2, 3, 6, О, 2) представлена самым правым столбцом в табл. И.1. Применив итерацию симплекс-метода к табл. И.1, получим табл. И.2 (кроме самого правого ее столбца). В табл. И.2 я = [О, О, 1/6, О, 0). При таком я самой дешевой допустимой сетью будет такая: [5, О, О, 6, 5). Она записана в самом правом столбце табл. И,2.
(Заметим, что столбец [5, О, О, 6, 5) нужно скорректировать перед введением его в табл. И.2. В данном случае скорректированный столбец снова имеет вид [5, О, О, 6, 5).) После очередной итерации симплекс-метода получится таблица И.З (кроме самого правого ее столбца). Здесь я = [О, О, 1/10, О, 1/5), а самая дешевая сеть такая: [10, 5, О, 6, О). Применив итерацию симплекс-метода к табл. И.З, получим табл.
И.4. 16* Гл. 11. мкегопгодуктовыв потОкн 244 Таблица 11А и аа аз 11 и Таблица 11.б 1 11 11 аз з=-~ с1хз при условиях Х1 — ао = /1а Х Х а11хт+з1 =51 хп з„з1 иО, (3) (1=-1, 2, ..., т), В табл. 11.4 и = (1/10, О, 1/10, О, 1/10). При таком аг любая допустимая сеть обладает стоимостью яани болыпей илк равной 1. Следовательно, 8 болыпе увеличить нельзя. Имеем: х, = 1/2, ха = 3/10, ха — — 1/5. а'белимся, что сеть на рис.
11.8 является допустимой. Имеем. "(1/2) [2, 3, 6, О, 2] = И, 3/2, 3, О, 1]; (3/10) [5, О, О, 6, 5] =- [3/2, О, О, 9/5, 3/2];.(1/5) [10, 5, О, 6, О] = = [2, 1, О, 6/5, О]. На рпс. 11.10 изображены 3 сети, которые обеспечивают выполнение соответственно 50, 30 и 20айа всех требовапий к потоку, заданных на рис. 11.9. Перейдем к пзучеки1о задач о многопродуктовом потоке минимальной стоимости. Рассмотрим задачи, аналогичные (1) и (2), усложненные наличием дуговых стоимостей.
Пусть каждой дуге 1 сети сойтветствует величина с1 — стоимость перевозки по втой дуге единицы потока. Требуется перевезти заданное общее количество продуктов из источников в стоки с мипимальпымн затратами. Пусть Ьа — заданное общее количество продуктов. Введем, как и в задаче (1), матрицу [аы] инциденцкй дуги-цепи и обозначим через х1 величину потока, пропускаемого по цепи 1. Пусть стоимость перевозки единицы потока ко 1-й цепи равна с,*. Тогда задача заключается в минимизации 245 1г.ю многопгодгктовыв потоки где каждый столбец матрицы!аы! представляет собой цепь, ведущую из источника в сток некоторого продукта. Пусть для сети на рис.
11.8 заданы дуговые стоимости, представленные на ркс, 11.11. Пусть дуговые пропускные способности / ! / 61 сю Гб> ! 1 Ь' Р и с. 11.10. будут такими же, как и на рис. 11.8 и требуется найти поток минимальной стоимости нз Л; в Л'з и из Л"а в Л"е при Ьа —— - 8. Начальная таблица, соответствующая задаче (3), представлена в табл. 11.5 (кроме трех. правых ее столбцов).
В табл. 11.5 произвольным образом введены 3 столбца, соответствующие 3 цепям. Первая цепь содержит. дугу 1 = 5 стоимости 4. Ей соответствует столбец !4, — 1, О, О, О, О, — 1) под.переменной хо Вторая компонента этого вектора равна — 1: зто коэффициент при х, в уравнении — ., х + аа = — Ь„. Вторая цепь содержит дуги 1 — — 1 и ~ = 4 общей стоимости с, + с4 = 4 + 8 = = 10. Она представлена столбцом ИО, — 1, 1, О, О, 1, 0) под переменной хю ГЛ. 11. МПОГОПРОДУКТОВЫЕ ПОТОКИ Так как табл. И.5 не является прямо допустимой, мы введем 3 цепи, чтобы сделать ее прямо допустимой. В результате выполнения итерации симплекс-метода и введения последовательно х1, Табаиза 11.а $0 Х1 Х1 аа и аа Х1 Х2 ХЗ хз и хз получим табл.
И.6. Заметим, что относительные оценки с,* =с,".— яа,*. Здесь каждый столбец имеет вид [ — 1, а,[. Поэтому ст — лат =с,* — ( — яо, я1) [ — 1, ат) = — — яо+~(с1 — и;)асв где пав цена, стоящая под переменной гэ. Следующая итерация симплекс-метода, примененная к таблице И.бх приводит к табл. И.7 (кроме крайнего правого столбца). С1=4 В табл.
И.7 с1 — я; можно интерпрети- 2 ровать как длины дуг и исиать кратчайшую цепь из Л11 в ЛГз или из Л"а в Л1~. Имеезг: с, — я, = 4 + 0 = 4, с, — я, = са=б с1=4 с1=а . 5 [ 0 =-5 сз яз =7+0 = 7 с — я, =6+2=8, с„.— л, =-4+8=12. Таким образом, кратчайшая цепь из Л'1 в Л'з имеет длину 4+ 5 = 9, а из Ла в Л1, — длину 4 + 8 = 5 + 7 = 12. Следовательно, мы вводим столбец [9, — 1, И, О, О, 0]. Этот столбец (после корректировки) записывается с правого края в табл. И.7.
После итерации симплекс-метода таблица превращается в табл. И.8. После следующей итерации симплекс-метода табл. И.8 превращается в табл. И.9, в которой с1 — п1 — — 4+ 3 = 7, с,— — Яа = 5 + 4 = 6, сз — 'Яз = 7 + 0 = 7, сг — Я1 = 6 + 0 = 6, гл. ы.
мпогопт одгктовыв потоки 248 сз — яз — — 4 + 9 .= 13. При таких длинах дуг в исходной сети нет цепей из У, в й'з или из ))гз в Ф„длина которых меньше 13. Так как яе — — 13, то — ле + У (с; — я;) ан ) О. Следовательно, полученное решение является опткмальпып. 11.3. Синтез коммуникационных сетей (Гомори и Ху (91)) Сети, изучаемые в этой главе, можно рассматривать как модели коммуникационных сетей, в которых узлы соответствуют станциям, а пропускные способности дуг — пропускным способностям каналов связи.
Потоки в сети можно интерпретировать как яотокн сообщений. Так как потоки сообщений имеют определенные пункты отправления и назначения, то опи являются мпогопродуктовыми потоками с общими для всех продуктов пропускными способностями каналов. Коммуникационная сеть должна обладать способностью одновременно пропускать несколько разпых потоков сообщений в любой момент времени. Обозначим через ~ „величину потока из источника )Ур в сток ДГю а через х(л — поток по дуге Лн, текущий из источника Ур в сток Л'~. Условие сохранения потока в узлах имеет вид — ~рю если / -= р, ~ хзэ — '~' хЕ~ = О, если 1~ р, д, (1) 1 ь ~ р,.
если ) =- д. Обозпачнм через у;; пропускную способность дуги Аы, .тогда должно выполняться условие ~~ ) хрт((ун для всех С у.. (2) Обоаиачим чеРез грч (Г) тРебУемУю величипУ потока из Л'в в Дгч в момент времени й Условие, что сеть должна быть способна пропускать требуемые величины потоков в каждый момент времени, запишется в виде ~рч)грч(Г) Дла всех Р, д и 1.— -1, 2,..., Т.
(3) Как и раньше, будем рассматривать два основных типа задач— анализа сети и синтеза сети. В задаче анализа сети заданы ум и грч (г), требуется найти хм, удовлетворяющие условияп (1) — (3). Если при этом заданы дуговые стоимости, то требуется мипнмизировать общую стоимость при ограничениях (1) — (3).
В задаче синтеза сети заданы грч (1) и стоимости сы построения дуг Агг единичной пропускной способности. Требуется найти у;;. чтобы выполнялись ограничения (1) — (3) и общая стоимость построенной сети ~ сну;; была бы минимальна. «.з. скнтвз коммхииклционных свтвй 249 В реальных коммуникационных сетях требования гр«(1) зависят от времени з, так как с течением времени меняется нагрузка сети.
Трудность решения задач анализа и синтеза зависит от вида функций гр«(»).'Рассмотрим 3 возможнь>х случая. Случай 1. Величкяы гр«(1) не зависят от времени; все требования к потокам должны выполняться одновременно. Анализ сети для етого случая проводится в $11.2 и заключается в решении задачи линейного программирования с большим числом переменных с помощью модифицированного симплекс- метода. Для получения столбцов, вводимых в таблицу, решается вспомогательная задача нахождения кратчайшего пути. В случае двухпродуктового потока задачу удается решить без привлечения аппарата линейного программирования (см.
з 11.1 или [106]). Синтез сети заключается в решении мпогополюсной задачи о кратчайшем пути (см. [111]). Используя величины см в качестве длин, находим кратчайшие цепи между каждой парой узлов Хр и Х«. Затем каждой дуге такой цепи приписываем пропускную способность, равную требовали>о гр«к потоку. Искомая сеть получается в результате «паложепня» друг па друга всех найдепвых кратчайших цепей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
