Моделирование потока машин

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Задача

Система автодорог представлена двухполюсной транспортной сетью. Определить, чему равен максимальный поток автомашин (количество машин в час) для данной системы автодорог, если пропускные способности дорог заданы в матрице.

граф поток автомашина дуга

Таблица 1

1. Построение ориентированного графа (орграфа) сети

Задача сводится к отысканию максимального значения потока в двухполюсной транспортной сети, которая задана матрицей пропускных способностей (табл. 1).

Построим орграф, соответствующий матрице пропускных способностей двухполюсной транспортной сети (табл. 1). Каждый элемент этой матрицы равен пропускной способности дуги u_ij, если из вершины x_i выходит дуга в вершину x_j, и 0 - в противном случае.

Над каждой дугой проставим ее пропускную способность, а в скобках - начальное значение потока, равное нулю (0) (рис. 1). Тогда величина потока в цепи равна нулю:

V = 0.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис. 1

2. Построение максимального потока

1. Рассмотрим цепь (s x₃ x₄ t).

Цепь является увеличивающей, так как все дуги, входящие в нее допустимые (увеличивающие):

(s x₃) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 0 < 15.

(x₃ x₄) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 0 < 8.

(x₄ t) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 0 < 14.

Следовательно, данная цепь увеличивающая.

2. Вдоль дуги (s x₃) поток можно увеличить на величину

= 15 - 0 = 15.

Вдоль дуги (x₃ x₄) поток можно увеличить на величину

= 8 - 0 = 8.

Вдоль дуги (x₄ t) поток можно увеличить на величину

= 14 - 0 = 14.

3. д = min {15, 8, 14} = 8. Вдоль цепи (s x₁ x₂ t) поток можно увеличить на д = 8, увеличивая его на д = 8 по каждой увеличивающей дуге (рис. 2). Дуга (x₃ x₄) стала насыщенной.

После такого изменения, величина потока стала равной

V = 8+0 = 8:

Величина потока, выходящего из вершины s равна величине потока, входящего в вершину t:

V_s = 0 + 8 = 8 и V_t = 0 + 8 = 8.

Условие сохранения потока выполняется.

1. Рассмотрим цепь (s x₁ x₄ t).

Цепь увеличивающая, так как все дуги допустимые (увеличивающие):

(s x₁) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 0 < 19.

(x₁ x₄) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 0 < 10.

(x₄ t) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 8 < 14.

2. Вдоль дуги (s x₁) поток можно увеличить на величину

= 19 - 5= 19.

Вдоль дуги (x₁ x₂) поток можно увеличить на величину

= 10 - 0 = 10.

Вдоль дуги (x₂ t) поток можно увеличить на величину

= 14 - 8 = 6.

3. д = min {14, 10, 6} = 6. Вдоль цепи (s x₁ x₄ t) поток можно увеличить на д = 6, увеличивая его на д = 6 по каждой увеличивающей (рис. 3). Дуга (x₄ t) стала насыщенной.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис. 2

После такого изменения, величина потока увеличилась на 6 и стала равной

V = 6+ 8 = 14:

Величина потока, выходящего из вершины s равна величине потока, входящего в вершину t:

V_s = 6+8 = 14 или V_t = 0+14= 14.

Условие сохранения потока выполняется.

1. Рассмотрим цепь (s x₁ x₄ x₂ t).

Цепь увеличивающая, так как все дуги допустимые (увеличивающие).

(s x₁) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 6 < 19.

(x₁ x₄) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 6 < 10.

(x₄ x₂) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 0 < 14.

(x₂ t) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 0 < 16.

2. Вдоль дуги (s x₁) поток можно увеличить на величину

= 19 - 6 = 13.

Вдоль дуги (x₁ x₄) поток можно увеличить на величину

= 10 - 6= 4.

Вдоль дуги (x₄ x₂) поток можно увеличить на величину

= 14 - 0 = 14.

Вдоль дуги (x₂ t) поток можно увеличить на величину

= 16 - 0 = 16.

3. д = min {13, 4, 14, 16} = 4. Вдоль цепи (s x₁ x₄ x₂ t) поток можно увеличить на д = 4, увеличивая его на д = 4 по каждой увеличивающей (рис. 4). Дуга (x₁ x₄) стала насыщенной.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис. 3

После такого изменения, величина потока увеличилась на 4 и стала равной V = 14 + 4 = 18:

Величина потока, выходящего из вершины s равна величине потока, входящего в вершину t:

V_s = 10 + 8 = 18 или V_t = 4 + 14 = 18.

Условие сохранения потока в вершинах выполняется.

1. Рассмотрим цепь (s x₁ x₂ t).

Цепь увеличивающая, так как все дуги допустимые (увеличивающие).

(s x₁) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 10< 19.

(x₁ x₂) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 0 < 5.

(x₂ t) - допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 4 < 16.

2. Вдоль дуги (s x₁) поток можно увеличить на величину

= 19 - 10 = 9.

Вдоль дуги (x₁ x₂) поток можно увеличить на величину

= 5 - 0 = 5.

Вдоль дуги (x₂ t) поток можно увеличить на величину

= 16 - 4 = 12.

3. д = min {9, 5, 12} = 5. Вдоль цепи (s x₁ x₂ t) поток можно увеличить на д = 5, увеличивая его на д = 5 по каждой увеличивающей (рис. 5). Дуга (x₁ x₂) стала насыщенной.

После такого изменения, величина потока увеличилась на 5 и стала равной V = 18 + 5 = 23:

Величина потока, выходящего из вершины s равна величине потока, входящего в вершину t:

V_s = 15 + 8 = 23 или V_t = 9 + 14 = 23.

Условие сохранения потока в вершинах выполняется.

Больше увеличивающих цепей нет. Минимальный разрез (пунктирная линия), соответствующий этому потоку, включает дуги: (x₁ x₂), (x₁ x₄), (x₃ x₄), и его пропускная способность равна: C(U) = 5+10+8 = 23.

Величина максимального потока равна величине минимального разреза:

V = 23, C = 23.

Размещено на Allbest.ru