Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 229
Скачиваний: 0
244 |
|
|
|
ГЛ . |
11. М Н О ГО П РО ДУ К ТО В Ы Е п о т о к и |
|
|
|
|||||
|
|
|
Таблица 11.3 |
|
|
|
Таблица 11.4 |
|
|||||
|
1 |
Sj |
s 2 |
s3 |
s4 |
S5 |
4 |
|
1 |
^1 |
$2 |
S3 s4 |
s5 |
0 |
8/10 |
|
|
1/10 |
|
1/5 |
—1 |
0 |
1 |
1/10 |
|
1/10 |
1/10 |
Si |
2 |
1 |
|
0 |
|
—1 |
10* |
*3 |
1/5 |
1/10 |
|
0 |
—1/10 |
s2 |
1 |
|
1 |
- 1 /2 |
|
0 |
5 |
s2 |
0 |
—1/2 |
1 |
—1/2 |
1/2 |
S3 |
1/2 |
|
|
1/6 |
|
0 |
0 |
X i |
1/2 |
0 |
|
1/6 |
0 |
s4 |
11/5 |
|
|
2/5 |
1 |
—6/5 |
6 |
s4 |
1 |
-6 /1 0 |
|
2/5 |
-6 /1 0 |
x 2 |
3/10 |
|
|
—1/15 |
|
1/5 |
0 |
x 2 |
3/10 |
0 |
|
1—1/15 |
1/5 |
В табл. 11.4 я = (1/10, 0, 1/10, 0, 1/10). При таком я любая допустимая сеть обладает стоимостью яа^-, большей или равной 1 .
Следовательно, |
0 больше увеличить нельзя. Имеем: xi = 1/2, |
|||||
х2 |
= 3/10, х 3 = |
1/5. |
Убедимся, |
что сеть на |
рис. 11.8 являет |
|
ся |
допустимой. |
Имеем: (1/2) |
[2, |
3, 6 , 0, 2] = |
[1, 3/2, 3, 0, 1]; |
|
(3/10) [5, 0, 0, 6 , |
5] = |
[3/2, 0, |
0, |
9/5, 3/2]; (1/5) |
[10, 5, 0, 6 , 0] = |
|
= [2, 1, 0, 6/5, 0]. На рис. 11.10 изображены 3 сети, которые обеспечивают выполнение соответственно 50, 30 и 20% всех тре бований к потоку, заданных на рис. 11.9.
Перейдем к изучению задач о многопродуктовом потоке мини мальной стоимости. Рассмотрим задачи, аналогичные (1) и (2), усложненные наличием дуговых стоимостей. Пусть каждой дуге i сети соответствует величина с; — стоимость перевозки по этой дуге единицы потока. Требуется перевезти заданное общее коли чество продуктов из источников в стоки с минимальными затра тами.
Пусть Ъ0 — заданное общее количество продуктов. Введем, как и в задаче (1 ), матрицу [ац] инциденций дуги-цепи и обозначим
через Xj величину потока, |
пропускаемого по цепи /. Пусть стои |
||||
мость перевозки |
единицы |
потока по |
j-й цепи равна с*. |
Тогда |
|
задача заключается в минимизации |
|
|
|||
|
|
Z = 2 |
C*Xj |
|
|
дри условиях |
|
3 |
|
|
|
|
|
|
|
|
|
|
2 / ^0 = Ь0, |
|
|
|
|
|
3 |
|
|
|
|
2 |
aijXj + S i = b i |
(г = 1, |
2, |
( 3 ) |
|
S 0 , S j ^ ^ O j
11.2. МНОГОПРОДУКТОВЫЕ потоки |
245 |
где каждый столбец матрицы [ац\ представляет собой цепь, веду щую из источника в сток некоторого продукта.
Пусть для сети на рис. 11.8 заданы дуговые стоимости, пред ставленные на рис. 11.11. Пусть дуговые пропускные способности
будут такими же, как и на рис. 1 1 . 8 и требуется найти поток минимальной стоимости из Ny в N 3 и из N 2 в jV4 при Ь0 = 8 .
Начальная таблица, соответствующая задаче (3), представлена в табл. 11.5 (кроме трех правых ее столбцов).
В табл. 11.5 произвольным образом введены 3 столбца, соот ветствующие 3 цепям. Первая цепь содержит дугу г = 5 стоимо сти 4. Ей соответствует столбец [4, —1, 0, 0, 0, 0, —1] под пере менной Ху. Вторая компонента этого вектора равна —1: это коэф
фициент при Ху в |
уравнении — 2 х) + |
so = |
— |
Вторая цепь |
|
содержит дуги г = |
3 |
|
|
с4 = |
4 + 6 = |
1 и i = 4 общей стоимости Су + |
|||||
= 10. Она представлена столбцом [10, —1, |
1, 0, |
0, |
1, 0] |
под пере |
|
менной хг. |
|
|
|
|
|
246 |
ГЛ. 11. |
МНОГОПРОДУКТОВЫЕ потоки |
|
Так как табл. 11.5 |
не является прямо допустимой, мы введем |
||
3 цепи, чтобы сделать |
ее прямо допустимой. |
В результате выпол |
|
нения |
итерации симплекс-метода и введения |
последовательно хи |
|
Таблица 11.5
х2 и xs получим табл. 11.6. Заметим, что относительные оценки с* —с* — яа*. Здесь каждый столбец имеет вид [ — 1, aj]. Поэтому
с* — яа* = с* — ( —я0, я4) [ — 1, а7] = —я0 + 2 |
(с* ~ пд ath гДе Ло— |
г |
|
цена, стоящая под переменной sQ. |
примененная к таб |
Следующая итерация симплекс-метода, |
лице 11.6, приводит к табл. 11.7 (кроме крайнего правого столбца).
В |
табл. |
11.7 |
сг — я г |
можно |
интерпрети |
||||
ровать |
как длины дуг и искать кратчай |
||||||||
шую цепь из |
Ni |
в N 3 |
или |
из IV2 в А+ |
|||||
Имеем: |
ct — Я1 = |
4 + 0 = 4, с2 |
— я 2 |
= |
|||||
= 5 + 0 = 5, с3 — я 3 = 7 + 0 = 7, с4 — |
|||||||||
— я4 = |
6 + |
2 = 8 , |
с5 — я5 = |
4 + |
8 = 12. |
||||
Таким |
образом, кратчайшая |
цепь из |
N i |
||||||
в |
N 3 имеет |
длину 4 + |
5 = 9 , |
а из |
N 2 |
||||
в |
iV4 — длину 4 + |
8 |
= |
5 + |
7 = 12. Сле |
||||
довательно, мы вводим столбец [9, —1, 11, |
|||||||||
О, |
0, 0]. |
Этот столбец (после корректи |
|||||||
ровки) записывается с правого |
края в табл. |
11.7. |
После итера |
||||||
ции симплекс-метода таблица |
превращается |
в табл. 1 1 .8 . |
|
||||||
После следующей итерации симплекс-метода табл. 11.8 пре |
|||||||||
вращается в табл. 11.9, |
в которой |
сх — я4 = |
4 + |
3 = |
7, с2 — |
||||
— я 2 = 5 + 1 = 6 , с3 — я 3 = 7 + 0 = 7, с4 — я4 = 6 + 0 = 6 ,
1
■— z - 8 0
501
511/2
x3 |
5/2 |
S3 |
1/2 |
x 2 |
4 |
*1 |
5/2 |
|
|
Т а б л и ц а 1 1 .6 |
|
|
|
|
|
||
so |
S1 |
s2 |
S3 |
s4 |
|
S5 |
|
x 2 |
x 3 |
0 |
0 |
—12 |
0 |
—10 |
|
—4 |
0 |
0 |
0 |
1 |
|
1 * |
|
1 |
|
1 |
0 |
0 |
0 |
|
1 |
|
|
—1 |
|
|
0 |
0 |
0 |
|
|
1 |
|
|
|
|
0 |
0 |
1 |
|
|
— 1 |
1 |
|
|
|
0 |
0 |
0 |
|
|
|
|
1 |
|
|
0 |
1 |
0 |
|
|
|
|
|
|
1 |
1 |
0 |
0 |
|
|
Таблица 11.7 |
|
|
|
|
|
||
1 |
s0 |
Sj |
s2 |
s3 |
s4 |
s5 |
x i |
|
|
|
|
|
Таблица 11.8 |
|
|
||
|
1 |
«о |
Si |
S2 |
S3 |
s4 |
S5 |
— z - 6 6 ,5 |
12 |
3 |
|
|
- 1 |
8 |
|
s 2 |
1 |
1 |
|
1 |
|
1 * |
1 |
x k |
1 /2 |
|
1 |
|
|
—1 |
0 |
x 3 |
1 |
—1 |
—1 |
|
|
0 |
—1 |
S3 |
2 |
1 |
1 |
|
1 |
0 |
1 |
x 2 |
4 |
|
|
|
|
1 |
0 |
x { |
5/2 |
|
|
|
|
0 |
1 |
|
|
|
Таблица |
11.9 |
|
|
|
|
1 |
|
so |
S1 |
s2 S3 |
s4 |
S5 |
— Z - 6 5 ,5 |
13 |
3 |
1 |
0 |
9 |
||
s4 |
1 |
|
1 |
|
1 |
1 |
1 |
x k |
3/2 |
|
1 |
1 |
1 |
0 |
0 |
x 3 |
1 |
|
—1 |
—1 |
|
0 |
—1 |
s3 |
2 |
|
1 |
1 |
1 |
0 |
1 |
x 2 |
3 |
|
—1 |
|
— 1 |
0 |
—1 |
X i |
5/2 |
|
|
|
|
.0 |
1 |
248 |
ГЛ. |
11. МНОГОПРОДУКТОВЫЕ п о т о к и |
с5 — я5 = 4 + |
9 = |
13. При таких длинах дуг в исходной сети |
нет цепей из iVi в |
N 3 или из |
N 2 в 1V4, длина которых меньше 13. |
|
Так как я 0 = 13, |
то —л0 + |
2 |
(с; — я г) ац ^ 0. Следовательно, |
|
|
г |
оптимальным. |
полученное решение является |
|||
11.3. Синтез коммуникационных сетей (Гомори и Ху (91])
Сети, изучаемые в этой главе, можно рассматривать как модели коммуникационных сетей, в которых узлы соответствуют стан циям, а пропускные способности дуг — пропускным способностям каналов связи. Потоки в сети можно интерпретировать как потоки сообщений. Так как потоки сообщений имеют определенные пунк ты отправления и назначения, то они являются многопродуктовы ми потоками с общими для всех продуктов пропускными способ ностями каналов. Коммуникационная сеть должна обладать способностью одновременно пропускать несколько разных потоков сообщений в любой момент времени.
Обозначим через f pq величину потока из источника N р в сток N q, а через xft — поток по дуге Ац, текущий из источника N p в сток N q. Условие сохранения потока в узлах имеет вид
|
|
— |
f p q , |
если |
1 |
= Р , |
|
2 ^ |
- 2 |
* $ |
0 , |
если |
j |
ф р, q, |
(1) |
|
|
|
f p q , |
если |
j |
= q . |
|
Обозначим через уц пропускную способность дуги Ац; тогда |
|||||||
должно выполняться |
условие |
|
|
|
|
|
|
|
2 |
для всех |
|
i , |
]■ |
(2) |
|
|
р , |
а |
|
|
|
|
|
Обозначим через |
rpq (t) требуемую |
величину потока из |
N p в N q |
||||
в момент времени t. Условие, что сеть должна быть способна пропускать требуемые величины потоков в каждый момент вре
мени, запишется в |
виде |
|
f p q > T p q (t ) |
для всех р, q и t = 1, 2 , . . ., Т . |
(3) |
Как и раньше, будем рассматривать два основных типа задач — анализа сети и синтеза сети. В задаче анализа сети заданы уц и rpq (t), требуется найти xtj, удовлетворяющие условиям (1 ) — (3).
Если при этом заданы дуговые стоимости, то требуется миними зировать общую стоимость при ограничениях (1) — (3). В задаче синтеза сети заданы rpq (t) и стоимости Сц построения дуг Ац единичной пропускной способности. Требуется найти уц, чтобы выполнялись ограничения (1 ) — (3) и общая стоимость построен
ной сети 2 Сцуц была бы минимальна.
11.3. СИНТЕЗ КОММУНИКАЦИОННЫХ СЕТЕЙ |
249 |
В реальных коммуникационных сетях требования rpq (t) зави сят от времени t, так как с течением времени меняется нагрузка сети. Трудность решения задач анализа и синтеза зависит от вида функций rpq (t). Рассмотрим 3 возможных случая.
Случай 1. Величины rpq (t) не зависят от времени; все требова ния к потокам должны выполняться одновременно.
Анализ сети для этого случая проводится в § 11.2 и заклю чается в решении задачи линейного программирования с большим числом переменных с помощью модифицированного симплексметода. Для получения столбцов, вводимых в таблицу, решается вспомогательная задача нахождения кратчайшего пути. В случае двухпродуктового потока задачу удается решить без привлечения аппарата линейного программирования (см. § 1 1 . 1 или [106]).
Синтез сети заключается в решении многополюсной задачи о кратчайшем пути (см. [111]). Используя величины ctj в качестве
длин, |
находим кратчайшие цепи между каждой парой узлов N p |
и N д. |
Затем каждой дуге такой цепи приписываем пропускную |
способность, равную требованию грд к потоку. Искомая сеть полу чается в результате «наложения» друг на друга всех найденных кратчайших цепей.
Случай 2. Величины rvq (t) зависят от времени, но весь период |
||
времени Т может быть разбит |
на отрезки, в течение |
каждого |
из которых в сети пропускается |
поток только одного |
продукта |
между некоторой парой полюсов.
Анализ сети заключается в нахождении максимального (одно продуктового) потока между всеми парами полюсов. Для неориен тированных сетей решение имеет простую и наглядную форму
(см. гл. 9 или [89]).
Синтез сети, если сеть неориентированная и все ctj одинако вые, был рассмотрен в гл. 9. Если Сц различны, используется аппарат линейного программирования (см. [90]). Решается задача линейного программирования с большим числом ограничений. Для уменьшения размера симплексной таблицы запоминаются только строки, используемые при вычислениях. Для получения строк, вводимых в таблицу, решается вспомогательная задача о макси мальном потоке.
Случай |
3. Величины rpq (t) произвольным образом зависят |
от времени. |
Этот случай является более общим, чем случаи 1 и 2. |
Анализ сети. Если разбить весь период времени на Т различ |
|
ных отрезков, то получится Т систем неравенств типа (3), соот ветствующих каждому из отрезков. На каждом из них получается задача, рассмотренная в случае 1 1).
9 Если период Т разбит на такие мелкие отрезки, что rpq (г) можно считать на них независимыми от времени.— Прим, перев.