ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 20.10.2024
Просмотров: 72
Скачиваний: 0
N элементов н, к, і, /, ... |
(узлов) и множества А некоторых пар |
(і, /) элементов, взятых из |
N (дуг). |
Однородным потоком в сети будем называть функцию X, которая каждой дуге (iß ставит в соответствие численное значение х (iß потока в дуге, причем
X (Ni) — X (iN) = О
при любом і Ф н, к.
Величиной потока X будем называть число
*о = х («> 0 = 2 * (і, к).
ІІ
Сущность задачи о минимальном потоке состоит в следующем. Для сети, представленной графом G (N, А), найти однородный
поток Хт, удовлетворяющий условиям
хт (iß > z (г, /) > 0 |
для всех (iß £ А, |
xm0 = min, |
z ( i ß £ R , |
где R — множество чисел z (iß, поставленных во взаимное соответ ствие дугам (iß и представляющих собой ограничение пропускной способности дуги (iß снизу.
Рассмотрим произвольный непрерывный поток, удовлетворяю щий ограничениям потоков дуг снизу. Пусть х (iß > z (iß > 0— допустимый поток X. В каждой дуге будет избыток потока Ах (iß =
— X (iß — г (iß ;> 0. В каждой рассматриваемой отдельно от сети дуге (iß можно уменьшить величину потока на Ах (iß. При рас смотрении же дуги в составе сети возможное уменьшение потока вет ви X (iß будет ограничено условиями непрерывности, которые при водят к необходимости уменьшения потока на ту же величину и в других дугах, образующих цепь, проходящую из н в к через дугу (iß, и возможностями уменьшения потока в других ветвях такой цепи.
Очевидно, что уменьшение потока х (iß в линейной сети экви валентно наложению потока х (iß в этой же ветви в обратном на правлении. Следовательно, можно рассмотреть непрерывный поток
X от к к к, для которого пропускные направления ветвей обратны заданным в исходной сети, удовлетворяющий ограничению сверху:
X (iß < Ах (iß.
Рассмотрим некоторый результирующий поток
т.е. X* (iß = Очевидно,
т.е.
Х* = Х — X,
X (iß — X (iß, откуда х0 = х0 — х0. что
хт0 = min (хо) = х0 — max (х0),
хт = Х - Х а,
30
где Х м — максимальный непрерывный поток (т. е. хм0 = max (л:0)Д удовлетворяющий ограничениям сверху:
О < *„ (ij) < Ах (ij).
Докажем, что Х„ есть искомый минимальный поток, т. е.
ХтО“ Xmü’
Предположим, что
*
ХтО ХтО»
Поток Хт удовлетворяет тем же ограничениям снизу, что и Хт:
х'п (ij) = X (ij) — хы(ij) > X (ij) — Ах (ij) = z ((ij).
Поток Хт является непрерывным, т. е. при і = н, к
Хт (Ni) — Хт (іЫ) = [х (Ni) — хм(Ni)] — [X (iN) — ха (iN)] =
= [х (Ni) — л: (iN)] — [хи (Ni) — хы(iN)] = 0.
Однако, если Х*т удовлетворяет всем тем условиям, что и Х т, то
предположение х’то < . хт0 противоречит минимальности |
потока Х т. |
||
Предположим, ЧТО Хт0< ХтО- |
Рассмотрим ПОТОК |
Хм = X |
—с. |
— Хт. Он непрерывный, так как |
|
|
|
х'м (Ni) — х*к (iN) = [х (Nt) — хт (Ni)] — [(iN) х — хт (iN)] = . |
|||
= [X (Ni) — X (iN)] — [xm (Ni) — xm (iN)] = 0 |
|
|
|
при І Ф H, K. |
|
|
|
Этот поток удовлетворяет таким ограничениям сверху: |
|
|
|
х'ы(ij) = X (ij) — *м (ij) < * (ij) — г (ij) = Ax (ij). |
|
||
Следовательно, поток Х„ удовлетворяет всем условиям, что я |
Х к. |
||
В то же время из условий . |
|
|
|
« |
ХтО |
|
|
ХтО |
|
|
|
И
ХыО — Хд — Хтд,
ХиО — Х0 — ХтО
следует
X м0 ^ Хмо»
что противоречит максимальности потока Х„. Так как предположе-
аі
«ия х'по < |
л'то и х’п0 > хт 0 |
приводят к противоречию, остается |
принять, |
что |
* _ |
|
|
ХціО— Хто, |
|
|
хт= хт. |
Тем самым доказано следующее: минимальный поток в сети Х т, удовлетворяющий условиям хт (ij) > г (ij) > 0 , можно найти в
виде
хт= х - х ы,
где X — допустимый поток (произвольный непрерывный |
поток) в |
|
той же сети, удовлетворяющий ограничениям |
|
|
X (Ч) > |
г {ij), |
|
Х ы — максимальный избыточный |
поток (максимальный |
поток в |
той же сети), удовлетворяющий ограничениям
xu (ij)< x(ij) — z(ij).
Решение задачи о минимальном потоке выполняется за три этапа.
1.Поиск допустимого потока.
2.Поиск максимального избыточного потока.
3.Определение искомого минимального потока как разности первых двух.
Пе р в ы й э т а п . Один из возможных алгоритмов построения допустимого потока состоит в следующем:
а) каждая дуга (ij) сети получает |
исходную |
оценку |
Сх {ij) = |
||||||
= г {ij) и значение потока хх {ij) |
= 0 ; |
|
|
|
|
|
|||
б) полагая длину |
дуги |
|
|
|
|
|
|
|
|
1 п |
_ ! Сп (г/) |
|
при |
С" (£/) > °’ |
|
|
|||
ln (t/)- \ 0 |
|
|
при |
Сп {ij) < 0 , |
|
|
|||
находим дальнейший путь Sn\ |
|
|
|
|
|
|
|
||
в) для дуг, принадлежащих Sn, находим тп = |
min 1Сп {ij)] при |
||||||||
условии Сп {ij) > 0; |
|
|
|
|
|
|
|
|
|
г) для дуг, принадлежащих 5„, изменяем оценки и потоки: |
|||||||||
Сп+і {ij) = Сп {ij) — тп, |
xn+i {ij) = хп {ij) + тп, |
|
|||||||
для остальных дуг |
|
|
|
|
|
|
|
|
|
Сп+1 {ij) = с„ {ij), |
хп + 1 {ij) = Хп {ij); |
|
|
||||||
д) если есть C„+i |
(ij) > 0, то продолжаем, |
возвратившись к |
|||||||
п. в) и б), если все |
C„+i (ij) |
0 , |
то |
х „+i |
(ij) |
= х |
(ij) |
образуют |
|
искомый допустимый |
поток |
X |
и |
Ах (ij) = |
—С„+і |
(ij) |
образуют |
||
-систему ограничений для максимального избыточного потока. Величина этого потока х0 = 2х (н, і) — 2х (і, к).
II
Вт о р о й э т а п . Для исходной сети ищем максимальный до
пустимый поток Х и, удовлетворяющий условиям
хи (ij) < Ах (ij), |
хм0 = max. |
32
В результате получаем хи (ij) для всех дуг, или только величину
этого потока лгмо, если нас |
в конечном итоге интересует не весь |
||||
минимальный поток Х т, а только его величина хто- |
|||||
Т р е т и й |
э т а п . Определяем Хп следующим образом: |
||||
|
х т = |
х - х |
м |
|
|
т. е. хт {ij) = |
X {ij) — хы {ij) |
для |
|||
всех |
{ij) £ А |
и |
значение |
Х т та |
|
кое, |
что |
|
|
|
|
|
ХтО ~ |
Х 0 |
ХыО- |
|
|
Для иллюстрации приведенно го выше метода рассмотрим при мер. Пусть задан граф G {N, А) (рис. 9). Ограничения, налагаемые на поток, следующие:
г {ні) = 10; г {ік) = 4; г {ij) = |
2; |
г («/) = 5; |
г (/к) = 10. |
Требуется найти минимальный поток, удовлетворяющий огра ничениям
хт (Ф > 2 (*'/)• Допустимый поток определяется в табл. 2.
Таким образом, допустимый поток будет
X {ні) = 14; X {ік) = 4 ; х {ij) = 10; х («/) = 5; х {]‘к) = 15.
Величина допустимого потока
х0 = X {ні) + X {nj) = 14 -f- 5 = 19.
Система ограничений для максимального избыточного потока
Ах {ні) — 4; Ах {ік) = 0; Ах {ij) = 8 ; Ах (я/) = 0; Ах {jK) = 5.
3 |
3 -2595 |
33 |
Граф G с ограничениями для поиска максимального избыточно го потока изображен на рис. 10. В данном случае единственный воз можный путь ш'/'к определяет максимальный избыточный поток Хм:
х„ («0 = |
Я, (£7) = |
+, (+) = |
4. |
• |
|
|
|
^ |
м |
|
|
|
4 |
|
|
x w (nD = |
Хы (ік) = |
0, |
|
|
|
|
|
*мо = Х , («0 + |
X |
(«/) = |
4 + 0 |
= 4. |
|
||
|
|
|
Находим минимальный поток Х т : |
||||
|
|
|
|
( « 0 = * ( « 0 — ( « 0 = |
|||
|
|
|
|
|
= 1 4 - 4 = 1 0 , |
||
|
|
|
хт ІЧ) = |
* (Ч) — +, (*/) = |
|||
|
|
|
|
|
= |
10 — 4 = |
6, |
|
|
|
хт (ік) = |
л: (/к) — хы(I(к) = |
|||
|
|
|
|
|
= |
4 — 0 = |
4, |
|
|
|
хт(н/) = X (nj) — хм («/) = |
||||
|
|
|
|
|
= |
5 — 0 = |
5, |
|
|
|
*m(/K).= *(/'к) — |
(ік) = |
|||
|
|
|
|
|
= |
15 — 4 = |
11, |
*ыо = х0 — хи0 = |
19 — 4 = |
15. |
|
|
|||
С целью определения минимального потока транспортной сети при синтезе моделей применяется алгоритм, аналогичный алгоритму определения максимального потока. Этот алгоритм заключается в реализации операции суммирования параллельных потоков и опре деления участков с максимальной пропускной способностью.
Для задачи определения минимального потока справедлива сле дующая теорема [39].
Для любой транспортной сети минимальная величина потока из н в к равна максимальной пропускной способности разреза, отделяю щего н и к .
Однако здесь понятие разреза необходимо ввести более строго по сравнению с определением разреза для максимального потока. В задаче о максимальном потоке любой путь из к в к должен содер жать, по крайней мере, одну ветвь каждого разреза. Указанная тео рема для задачи о минимальном потоке справедлива только в том случае, если любой разрез транспортной сети содержит одну и только одну ветвь каждого пути, соединяющего н и к . Это обуслов лено тем', что минимальная пропускная способность каждого пути определяется пропускной способностью, ветви с максимальной вели чиной dij. Справедливость сказанного легко показать на примере.
'34