Файл: М.А. Тынкевич Потоки в сетях и транспортная задача по критерию времени.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