Файл: М.А. Тынкевич Потоки в сетях и транспортная задача по критерию времени.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 01.06.2024
Просмотров: 38
Скачиваний: 1
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
КУЗБАССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра вычислительной техники и информационных технологий
ПОТОКИ В СЕТЯХ И ТРАНСПОРТНАЯ ЗАДАЧА ПО КРИТЕРИЮ ВРЕМЕНИ
Методические указания и задания к практическим занятиям по курсам
“Исследование операций в экономике” и “Экономико-математические методы”
для студентов экономических специальностей
Составитель М.А.Тынкевич
Утверждены на заседании кафедры вычислительной техники и информационных технологий Протокол № 4 от 08.12.2000
Рекомендованы к печати методической комиссией по специальности 351400
Протокол № 1 от 08. 12.2000
Кемерово 2001
1
1. Задача о максимальном потоке
Рассмотрим транспортную сеть, в которой выделены пункты 0 (вход, источник) и n (выход, сток) и каждой дуге (отрезку), связывающей пункты
i и j, сопоставлено число dij > 0 , называемое пропускной способностью дуги. Величина пропускной способности характеризует максимальное допустимое количество вещества (воды, газа, самолетов, вагонов и т. п.), которое может проходить по соответствующей дуге в единицу времени.
Количество вещества, проходящего по дуге от i до j в реальности, будем называть потоком по дуге ( i , j ) и обозначать через Xij .
Очевидно, что |
|
|
|
0 ≤ |
Xij ≤ |
dij для всех i , j . |
|
Если учесть, что все вещество, |
вошедшее в промежуточный пункт сети, |
||
должно полностью выйти из него, |
получаем |
||
∑ |
X i j = ∑ |
X jk , j = 1 ..n . |
|
i |
|
k |
|
Для стационарных потоков, параметры которых в любой момент времени неизменны, естественно требовать равенства потоков на входе и на выходе :
∑ X 0 j = ∑ X i n = Z .
j i
Рассмотрим задачу максимизации величины потока в сети Z при указанных условиях .
Подобная задача возникает достаточно часто. Под каким давлением подавать воду в городскую сеть, чтобы не рвались (или хотя бы меньше рвались) трубы? Какое количество газа можно качать от месторождений Ямала к потребителям в Европе?
Решение задачи можно осуществлять методами линейного программирования, но едва ли эта возможность осуществима для сколь-нибудь реальной сети.
В случае т. н. (0, n) - плоских сетей, т. е. сетей, которые можно изобразить на плоскости по одну сторону от ли-
нии, соединяющей вершины 0 и n , без пересечения дуг вне вершин (наша сеть относится к таковым), можно предложить простой наглядный алгоритм решения.
Берем самый "верхний" (по принципу левостороннего движения) путь от вершины 0 к вершине 7: [0 - 1 - 5 - 7] и отыскиваем минимальную пропускную способность составляющих его дуг, равную 5 , и уменьшаем пропускные
2
способности дуг на эту величину. Очередной "верхний" путь [0 - 1 - 5
- 4 - 7] имеет пропускную способность 5.
Очередной путь [0 - 1 - 4 - 7] имеет пропускную способность 10. Последующий поиск обнаруживает потоки по путям [0 - 1 - 4 - 6 - 7] c величиной потока 5 и [0 - 1 - 2 - 3 - 6 - 7] c величиной 5 . В итоге сеть ока-
залась разорванной и максимальный поток равен 30 .
Естественно, что для больших сетей такой метод неприемлем. К тому же он не слишком удобен для компьютерной реализации.
Рассмотрим матричную реализацию алгоритма поиска в произвольной сети. Начальный этап алгоритма состоит в построении матрицы D0 , в которую заносятся значения пропускных способностей (для неориентированной дуги
берем симметричные значения элементов матрицы di j=dj i ).
Основные шаги алгоритма состоят в поиске некоторого пути и коррекции потока на этом пути.
При поиске пути используем процесс отмечаний.
Метим символом * нулевые строку |
и столбец матрицы (вход сети). В |
|
нулевой строке отыскиваем d0j |
> 0 и |
метим соответствующие столбцы ин- |
дексами |
|
|
|
j = 0 , |
V j = d0j |
и переносим метки столбцов на строки. |
Затем берем i-ю отмеченную стро- |
ку, ищем в ней непомеченный столбец с d i j > 0 и сопоставляем ему метки
j = i , Vj = min (Vj, di j).
Метки столбцов переносим на строки и этот процесс продолжаем до тех
пор, пока не будет отмечен n - й столбец. |
выясняем путь, приведший к n - |
Затем "обратным ходом" по индексам |
й вершине, и уменьшаем пропускные способности дуг пути (элементы мат-
рицы) на Vn и увеличиваем симметричные элементы на эту же величину. Такая процедура продолжается до тех пор, пока отмечание n - й вершины
не станет невозможным.
Максимальный поток может быть найден суммированием найденных промежуточных потоков или вычитанием из исходной матрицы D0 получаемой после вышеприведенной корректуры матрицы пропускных способностей
X = max (D0 - Dk , 0) .
Обратимся к рассмотренному выше примеру.
Из нулевой строки отмечаем вершины (строки-столбцы) 1 , 2 и 3 индексами =0 и V, равными 30 , 10 и 10.
Из помеченной строки 1 метим вершины 4 и 5 индексами =1 и
V4 = min( 30, 15 ) = 15 , V5 = min( 30,10 ) = 10 .
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
Из строки 3 |
метим вершину 6 |
и, наконец, |
из строки 4 |
- вершину 7. |
||||||||||||||||
|
|
* |
|
0/30 |
0/10 |
0/10 |
1/15 |
1/10 |
3/5 |
4/15 |
|
|
||||||||
|
|
|
0 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
* |
|
||||||
|
0 |
|
|
|
|
30 |
|
10 |
10 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
20 |
|
|
15 |
|
10 |
|
|
|
|
|
0/30 |
|
D0 = |
2 |
|
|
|
|
|
|
|
10 |
|
10 |
|
|
|
|
|
|
|
0/10 |
|
3 |
|
|
|
|
|
|
|
|
10 |
|
|
5 |
|
|
|
0/10 |
||||
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
15 |
|
1/15 |
||
|
5 |
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
5 |
|
1/10 |
||
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
|
3/5 |
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4/15 |
|
Обратным |
ходом по |
обнаруживаем путь: к вершине 7 от 4 , |
к верши- |
|||||||||||||||||
не 4 от 1 , к |
вершине 1 от 0; корректируем элементы |
|
D0 |
на |
величину |
|||||||||||||||
потока V7 =15. На очередном шаге находим путь [ 0 - 1 - 5 - 7 ] |
с потоком 5 . |
|||||||||||||||||||
|
|
* |
|
0/15 |
0/10 |
0/10 |
2/10 |
1/10 |
3/5 |
5/5 |
|
|
|
|||||||
|
|
|
0 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
* |
|
||||||
|
0 |
|
|
|
|
15 |
|
10 |
10 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
15 |
|
|
|
20 |
|
0 |
|
10 |
|
|
|
|
|
0/15 |
|||
D1 = |
2 |
|
|
|
|
|
|
|
10 |
10 |
|
|
|
|
|
|
|
0/10 |
||
3 |
|
|
|
15 |
|
|
|
10 |
|
|
5 |
0 |
|
0/10 |
||||||
|
4 |
|
|
|
|
|
|
|
|
|
|
5 |
|
2/10 |
||||||
|
5 |
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
5 |
|
1/10 |
||
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
|
3/5 |
|
|
7 |
|
|
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
5/5 |
с пото- |
|
Последующие шаги обнаруживают пути [0-3-6-7] и [0-2-4-6-7] |
||||||||||||||||||||
ками величиной 5. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
* |
|
0/10 |
0/5 |
0/5 |
2/5 |
1/5 |
|
|
|
|
|
|
|
|||||
|
|
|
0 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
* |
|
||||||
|
0 |
|
|
|
10 |
5 |
5 |
|
|
|
|
|
|
|
|
|
|
|||
|
1 |
|
20 |
|
|
20 |
|
0 |
5 |
|
|
|
|
|
0/10 |
|||||
D4 = |
2 |
|
5 |
|
|
|
|
10 |
5 |
|
|
|
|
|
|
|
0/10 |
|||
3 |
|
5 |
15 |
5 |
|
10 |
|
|
0 |
0 |
|
0/5 |
|
|||||||
|
4 |
|
|
|
|
|
|
|
|
0 |
|
2/5 |
|
|||||||
|
5 |
|
5 |
|
|
|
|
|
10 |
|
|
|
|
0 |
|
1/5 |
|
|||
|
6 |
|
|
|
|
|
|
|
5 |
5 |
|
|
|
|
10 |
|
|
|
||
Дальнейшее |
7 |
|
|
|
|
|
|
|
|
15 |
5 |
10 |
|
|
|
|
|
|||
|
отмечание невозможно. |
Отсюда получаем матрицу макси- |
||||||||||||||||||
мального потока: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
0 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
|||||
|
|
|
0 |
|
|
|
20 |
5 |
5 |
|
|
|
|
|
|
|
|
|
||
|
|
|
1 |
|
|
|
|
|
0 |
|
|
15 |
5 |
|
|
|
|
|
||
|
|
|
2 |
|
|
|
|
|
|
0 |
5 |
|
|
|
|
|
|
|
||
Xmax = |
3 |
|
|
|
|
|
|
|
|
0 |
|
|
5 |
15 |
|
|||||
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|||
|
|
|
5 |
|
|
|
|
|
|
|
|
0 |
|
|
|
|
5 |
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4
Этот алгоритм не накладывает никаких ограничений на транспортную сеть типа наличия ориентации или возможности размещения на плоскости без пересечения дуг, элементарно реализуется в программном виде; им можно пользоваться и при ручном поиске (разумеется, не перерисовывая таблицы, а пользуясь карандашом и резинкой) .
2. Транспортная задача по критерию времени
В отличие от традиционной транспортной задачи |
в рассматриваемой |
кри- |
|||||
терием |
качества организации перевозок являются |
не суммарные затраты, а |
|||||
время |
реализации перевозок (подобные проблемы |
возникают при транспор- |
|||||
тировке скоропортящихся грузов, при переброске |
сил быстрого реагирова- |
||||||
ния и т.д.). |
m |
|
|
в количествах ai (i=1…m) и n |
|||
Пусть имеется |
поставщиков |
продукта |
|||||
потребителей в |
количествах bj ( |
j = 1... n ) , |
причем соблюдается |
баланс |
|||
предложения и спроса. |
|
|
|
|
|||
Известно время ti |
j прямой поставки груза |
от i |
- го поставщика к |
j - му |
|||
потребителю, не зависящее от объема перевозки. |
|
|
|||||
Требуется среди всех допустимых планов |
перевозок X = { Xij } |
найти |
|||||
план, оптимальный |
по времени. Очевидно, что время, необходимое для реа- |
лизации плана, совпадает с наибольшим временем отдельных перевозок и оптимальное время перевозок равно
Topt |
= min |
max t |
i j |
(1) |
|||
|
|
|
|
X |
Xi j > 0 |
|
|
при условиях |
|
|
|
|
|
|
|
∑n |
X i |
j = ai |
, |
i = 1 .. m; |
(2) |
||
j= 1 |
|
|
|
|
|
|
|
∑m |
X i j = b j |
, |
j = 1 .. n; |
(3) |
|||
i= 1 |
|
|
|
|
|
|
|
Xi j ≥ |
0 |
|
, |
i = 1 .. m , j = 1 .. n; |
(4) |
||
∑m |
ai = ∑n |
b j = |
R . |
|
(5) |
||
i= 1 |
|
j=1 |
|
|
|
|
|
|
|
|
|
|
|
b1 |
|
|
a1 |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
b2 |
|
|||
|
|
a2 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|||
am |
|
|
|
|
|
||||
|
|
|
bn |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Для решения поставленной задачи воспользуемся весьма простой идеей.
Считая пропускные способности маршрутов транспортной сети скольугодно большими, построим вспомогательную сеть, дополнив исходную псевдовходом, из которого ведут дуги к поставщикам с пропускными способно-
стями ai (i = 1…m), и псевдовыхо-
дом, к которому ведут дуги от по-
5
требителей с пропускными способностями bj (j=1…n). В результате получаем сеть с одним входом и одним выходом, в которой осуществляется переброска R единиц груза от псевдовхода до псевдовыхода.
Выбираем минимальное из значений tij и строим т.н. допустимую сеть,
удаляя дуги со значениями tij , превышающими выбранное. В этой сети отыскиваем максимальный поток (алгоритм такого поиска рассмотрен выше). Если этот поток отвечает условиям задачи (его величина равна R), то выбранное время оптимально. В противном случае выбирается очередное наименьшее время, тем самым допустимая сеть расширяется и в ней вновь ищется максимальный поток.
Единственный недостаток такого решения в том, что придется оперировать с матрицами размерности m+n+2, в которой всего mn+m+n ненулевых элементов. Поэтому рассмотрим компактную схему поиска максимального потока, позволяющую работать с матрицами размерности m× n.
Пусть найден некоторый поток X в допустимой сети S, удовлетворяющий естественным условиям:
∑n |
X i j ≤ ai ( i = 1 .. m ) ; |
∑m |
X i j ≤ b j ( j = 1 .. n ) ; X i j ≥ 0 (i=1..m , j=1..n). |
j= |
1 |
i= 1 |
|
(поиск начального приближения для потока можно осуществлять любым методом, например, методом северо-западного угла).
Для строк i, в которых
|
|
|
|
∑n |
X i |
j |
< ai |
, |
|
|
|
|
(6) |
|
|
|
|
j= 1 |
|
|
|
|
|
|
|
|
|
сопоставим метки |
|
|
|
|
i = ai - ∑n |
|
|
|
|
|
|||
|
µ |
i = 0 |
, |
υ |
X i j . |
|
|
(7) |
|||||
|
|
|
|
|
|
|
|
j= 1 |
|
|
|
|
|
Выбираем отмеченные |
строки (например, |
i -ю) и отмечаем неотмеченные |
|||||||||||
столбцы j такие, что дуга (i j) |
S , |
метками |
|
|
|
|
|
|
|||||
|
|
λ j = i |
, |
ω |
j = |
υ i . |
|
|
|
(8) |
|||
Затем берем отмеченные столбцы (например, |
j - й) и |
неотмеченным |
|||||||||||
строкам i , в которых X i j |
> 0 , сопоставляем метки |
|
|
|
|
||||||||
|
|
µ i = |
j |
, υ |
i = |
|
min (ω |
j , Xi j |
) . |
|
(9) |
||
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
Повторяем процесс отмечания столбцов и строк до тех пор, |
пока |
не будет |
|||||||||||
отмечен "ненасыщенный" столбец j* , |
для которого |
|
|
|
|
||||||||
|
|
|
∑m X |
* |
< |
b * |
|
|
|
|
(10) |
||
|
|
|
i= |
1 |
i j |
|
j . |
|
|
|
|
||
Отыскиваем величину |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
∑m X |
|
|
|
|
|
|
Θ |
= min ( ω * |
,b * − |
i |
* ) |
, |
(11) |
||||||
|
|
|
|
|
j |
|
j |
|
i= 1 |
j |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|