Математическая экономика

x2 →(+x3,min[δ(x3); c32 − p32 ] = (+x3,min[20; 8 − 0]) = (+x3;8).

Для x4 по правилу 2 а получаем x4 →(+x3; min[20; 17 −0]) =(+x3; 17). Так как сток t = x4 получил метку, стадию А прекращаем и перехо-

дим к изменению потоков.

Шаг 4. Берем вершину xi =t , анализируем ее метку (+x3,17) и, используя δ =17 , переходим к следующему шагу.

Шаг 5 а. Поток в дуге (x3, x4 ) меняем с p34 = 0 на p34 = 0 +17 =17 . Для вершины x3 по метке (+x1,20) определяем, что поток дуги (x1, x3)

x2 →(+x3,min[3; 8 − 0]) = (+x3,3);

x4 не рассматриваем, так как p24 = c24 =17.

Г(x2 ) ={x4}, Г-1(x2) ={x1, x3};

x4 →(+x2,min[3, 12 −10]) = (+x2,2); x1 и x3 уже имеют метки.

111

Сток x4 = s получил метку, переходим к стадии Б, изменяя потоки на δ = 2;

для дуги ( x2 , x4 ) меняем p24 =10 на p24 =10 + 2 =12 ; для (x3, x2 ) меняем p32 = 0 на p32 = 0 + 2 = 2 ;

для (x1, x3) меняем p13 =17 на p13 =17 + 2 =19 . Перечерчиваем граф с новыми метками (рис. 4.11, б). Четвертая итерация (рис. 4.12).

как p24 = c24 =12 . Никаких других меток поставить нельзя. По условию, предусмотренному шагом 3, это означает конец решения.

Полученное на графе рис. 4.12 распределение потока соответствует искомой максимальной величине потока сети:

P = p12 + p13 =10 +19 = p24 + p34 =12 +17 = 29.

Оформление решения. Оно состоит в формулировке решаемой задачи, записи матрицы пропускных способностей, задающей транспортную сеть, построении соответствующего графа, выполнении нужного числа итераций по алгоритму Форда – Фалкерсона с изображением графов вида рис. 4.8 – 4.12, соответствующих каждой итерации, и кратких пояснений, касающихся расстановки меток вершин и изменений потоков дуг.

112

§ 4.6. Задача об оптимальном распределении заданного потока в транспортной сети

Важное прикладное значение имеет следующая задача. Для исходной транспортной сети с известной величиной максимального потока Pmax

найти распределение по дугам заданного потока P = P0 < Pmax , наилучшее

с точки зрения некоторого показателя. Речь идет, например, о составлении наиболее рационального плана перевозок какого-либо груза по имеющейся транспортной магистрали, при котором общая стоимость всех перевозок была бы минимальна. Такая задача называется транспортной задачей. Ей можно придать следующую математическую формулировку.

Дана некоторая сеть G = (X ,U ) , каждой дуге (xi , x j ) U которой помимо пропускной способности cij приписана еще одна числовая характеристика dij , трактуемая как стоимость прохождения единицы потока по соответствующей дуге (xi , x j ) . Требуется найти распределение pij задан-

Решение. Для отыскания решения поставленной задачи можно использовать следующий итерационный алгоритм [18].

Шаг 1. Пусть заданы граф G =G0 и потокP = P0 , который должен

в качестве длин дуг соответствующие стоимости dij .

Шаг 3. Определяем пропускную способность с(Lk ) этого пути Lk как min[cij ] по всем дугам, вошедшим в Lk .

тока Pk нужно осуществить по найденному пути Lk ; после чего перейти к шагу 8. Если же Pk > c(Lk ) , то переходим к следующему шагу.

113

Шаг 8. Суммируя для каждой дуги значения потоков, пропущенных через эту дугу на каждой итерации, находим искомое оптимальное распределение заданного потока.

Замечание. При отыскании кратчайших путей Lk в графах Gk можно использовать алгоритм, описанный в § 4.3.

Пример. Для пояснения изложенного алгоритма рассмотрим простой пример транспортной сети, заданной табл. 4.5 из предыдущего § 4.6, дополнив ее следующей матрицей стоимостей D:

Первая итерация.

Шаг 1. Пусть Gk – исходный граф (рис. 4.13, а), а Рk = P0 = 22 .

Шаг 2. В Gk выбираем кратчайший путь от s = x1 к t = x4, используя в качестве длин дуг числа dij . В данном графе имеется всего три пути от s к t, они изображены на рис. 4.13, б – г. Определяя для каждого из них дли-

114

ну пути (см. рис. 4.13), выбираем кратчайший путь, приведенный на рис. 4.13, б. При этом d(Lk ) =34.

х1 d(L) = 36 х4

в) х3

г)

Рис. 4.13

Шаг 3. Определяем пропускную способность этого пути, используя числа cij , приписанные дугам, вошедшим в этот путь:

c(Lk ) = min{20, 8,12} =8.

Шаг 4. Так как Pk = 22 > c(Lk ) =8 , то по пути Lk (см. рис. 4.13, б) пропускаем поток P(Lk ) =8.

Шаг 5. Поскольку Pk > c(Lk ) , переходим к шагу 6.

Шаг 6. Строим новый граф (рис. 4.14, а), в котором пропускные способности дуг, вошедших в Lk , уменьшаем на c(Lk ) =8 , при этом дугу

( x3, x2 ), получившую с32′ = 0, исключаем из графа, а пропускные способ-

ности остальных дуг не меняем.

Шаг 7. Принимаем в качестве Gk полученный граф (рис. 4.14, а), полагаем Pk = 22 −8 =14 и переходим к шагу 2.

Вторая итерация.

Из двух возможных путей от s к t в графе (рис. 4.14. б, в) выбираем кратчайший путь Lk (рис. 4.14, в) и определяем его пропускную способ-

ность c(Lk ) =12 .

При этом c(Lk ) =12 < Pk =14. Пропускаем по Lk поток P(Lk ) =12 .

Строим на базе графа рис. 4.14 новый граф, в котором пропускные способности дуг ( x1, x3 ), (x3, x4 ) Lk уменьшены на c(Lk ) =12 , причем дуга

( x1, x3 ), получившая c13′ = 0, исключена из графа. Принимаем в качестве

115

б)

Рис. 4.15

Третья итерация.

Полученный граф (см. рис. 4.15, а) представляет собой единственный путь от s к t. Его пропускная способность c(Lk ) = min [10, 4] = 4. При этом Pk = 2 < c(Lk ) . По условию шага 5 через этот путь пропускаем поток Pk = 2 и переходим к шагу 8.

Шаг 8. Получение оптимального распределения потока.

Суммируя потоки, пропущенные по дугам на каждой итерации, на-

116

Контрольные вопросы

1.Что называется графом?

2.Какой граф называется ориентированным, а какой – неориентированным?

3.Каким образом можно граф задать с помощью матриц, как называются такие матрицы?

4.Какой граф называется связным?

5.Что представляет собой путь в графе, какой путь называется простым?

6.Какой граф называется взвешенным?

7.Как формулируется задача о кратчайшем пути в графе?

8.Какой метод используется для решения задачи о кратчайших путях в графе?

9.Что представляют собой метки, используемые при решении задачи о кратчайших путях, каков алгоритм, по которому они определяются?

10.Как формулируется задача о критическом пути в графе?

11.Что представляет собой сетевой график и какие задачи позволяет он решать?

12.Как формулируется задача о графе минимальной длины, какую структуру имеет такой граф?

13.Какой граф называется транспортной сетью?

14.Как формулируется задача о максимальном потоке в транспортной сети?

15.Какое содержание имеют и по какому правилу формируются метки в алгоритме Форда – Фалкерсона?

16.Для какой цели и каким образом используются метки в алгоритме Форда – Фалкерсона при решении задачи о максимальном потоке в транспортной сети?

17.Как формулируется задача об оптимальном распределении заданного потока в транспортной сети?

117

Задачи для самостоятельного решения

1. Задача о кратчайших путях в графе

Неориентированный граф с десятью вершинами x1...x10 задан верхней треугольной «половиной» матрицы весов. При этом отсутствие элемента cij в матрице указывает на отсутствие в графе ребра, связывающего

вершины xi и x j .

Необходимо найти кратчайший путь из истока в каждую из остальных вершин графа.

118