Понятие транспортной сети

Транспортная задача может быть задана в виде специальной схемы – транспортной сети. Пункты расположения поставщиков и потребителей изображаются кругами и называются вершинами сети. Мощности поставщиков будем отмечать положительными числами, а спрос потребителей – отрицательными числами. Дороги, связывающие поставщиков и потребителей, изображаются в виде линий и называются ребрами сети. Реальный масштаб не соблюдается. Возможны вершины с нулевым запасом груза – нулевые вершины.

В процессе решения открытая модель всегда сводится к закрытой модели. Поэтому сначала рассмотрим закрытую модель. Нужно построить первоначальный план поставок любым способом. Поставки груза из вершины в вершину будем обозначать стрелками с указанием величин поставок.

На план поставок налагаются следующие условия:

1) Все мощности поставщиков должны быть распределены;

2) Весь спрос потребителей должен быть удовлетворен;

3) К каждой вершине должна подходить или выходить из нее хотя бы одна стрелка;

4) Число стрелок = числу -1;

5) Стрелки не должны образовывать замкнутый контур (при этом неважно, двигаемся мы по стрелкам или против них).

Особый случай транспортной задачи в сетевой постановке проявляется в том, что при полном использовании мощностей поставщиков и полном удовлетворении спроса потребителей число стрелок < n – 1, где n – общее число вершин (в том числе и нулевых). Тогда дополнительно вводится нужное количество стрелок. При этом должны образовывать замкнутый контур.

Задана следующая транспортная сеть:

3

4 2

4 7

Верхнее число вершины – это номер соответствующего поставщика или потребителя, нижнее число вершины – это мощность поставщика (для положительных чисел) или спрос потребителя (для отрицательных чисел).

У поставщиков 1, 4 и 7 есть 190, 30 и 250 единиц груза соответственно. Потребителям 2, 3, 5 и 6 требуется 120, 70, 150 и 130 единиц груза соответственно.

Стоимость перевозки единицы груза от поставщика 1 до потребителя 2 равна 1,стоимость перевозки единицы груза от поставщика 7 до потребителя 5 равна 3 и т. д.

Суммарная мощность поставщиков равна 190 + 30 +250 = 470, суммарный спрос потребителей равен 120 + 70 + 150 + 130 = 470. Это закрытая модель.

Первоначальный план поставок

Найдем первоначальный план поставок. Способ расстановки стрелок может быть любым. Важно только выполнение условий 1 – 5. Все поставки указаны стрелками.

3

70

1 30

120 4 2

4 7

3 120

У нас 5 стрелок и 7 вершин. Не выполняется следующее условие:

число стрелок = число вершин – 1, так как 5 = 7 – 1. Введем еще одну стрелку с нулевой поставкой. Например, 1 5. Получим следующий первоначальный план поставок.

0

3

1 30

120 4 2

4 7

3 120

Затраты на перевозку равны 120*1 + 70*3 + 0*2 + 30*2 + 120*3 + 130*7 = 1660

Проверка плана поставок на оптимальность

Нужно проверить план поставок на оптимальность. Для этого требуется вычислить потенциалы вершин.

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

1) Если мы двигаемся по стрелке, то к потенциалу вершины прибавляем стоимость перевозки единицы груза по этой стрелке (а не число, которое написано на стрелке);

2) Если мы двигаемся против стрелки, то из потенциала вершины вычитаем стоимость перевозки единицы груза по этой стрелке.

После вычисления потенциалов вершин нужно найти характеристики ребер без стрелок по следующему правилу: стоимость перевозки единицы груза для данного ребра – большой потенциал вершин этого ребра + меньший потенциал вершин этого ребра.

Если нет ребер с отрицательными характеристиками, то получен оптимальный план поставок.

Проверим полученный план на оптимальность. Для вершины 1 принимаем потенциал равный 0. Из вершины 1 в вершину 2 ведет стрелка.

1 1

Стоимость перевозки единицы груза для данного ребра равна 1. Поэтому потенциал вершины 2 равен: потенциал вершины 1 + стоимость перевозки груза по ребру 1→2 (двигается по стрелке):

0 + 1 =1

Из вершины 1 в вершину 5 ведет стрелка. Стоимость перевозки единицы груза для данного ребра равна 2. Поэтому потенциал вершины 5 равен 0 (потенциал вершины 1) + 2 (стоимость перевозки единицы груза по ребру 1→5) = 2

В вершину 5 из вершины 7 ведет стрелка. Стоимость перевозки единиц груза для данного ребра равна 3. Поэтому потенциал вершины 7 равен: потенциал вершины 5 минус стоимость перевозки единицы груза по ребру 7→5 (двигаем против направления стрелки):

Повторяем данную процедуру до тех пор, пока не будут найдены потенциалы всех вершин:

Потенциал вершины 3 = 0 + 3 = 3

Потенциал вершины 4 = 2 – 2 = 0

Потенциал вершины 6 = -1 + 7 = 6

3

1 30

4 7

3 120

Далее находим характеристики ребер без стрелок (их оценки)

Характеристика ребра (1,6) = стоимость перевозки единицы груза для ребра (1,6) + меньший потенциал вершин ребра (1,6) = 4 – 6 + 0 = -2 < 0

Характеристика ребра (2,4) = стоимость перевозки единицы груза для ребра (2,4) – большой потенциал вершин ребра (2,4) + меньший потенциал вершин ребра (2,4) = 7 – 1 + 0 = 6

Характеристики ребра (3,4) = стоимость перевозки единицы груза для ребра (3,4) – большой потенциал вершин ребра (3,4) + меньший потенциал вершин ребра (3,4) = 4 – 3 + 0 =1

Характеристика ребра (4,6) = стоимость перевозки единицы груза для ребра (4,6) – большой потенциал вершин ребра (4,6) + меньший потенциал вершин ребра (4,6) = 3 – 6 + 0 = -3 < 0

Характеристики ребер (4,6) и (1,6) отрицательны, поэтому полученный план поставок не является оптимальным. (на схеме оценки отмечаем зеленым цветом – овал)

3

Улучшение плана поставок

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

В нашем случае у ребра (4,6) наименьшая отрицательная характеристика (-3). Рисуем к нему стрелку от вершины с меньшим потенциалом (4) к вершине с большим потенциалом (6).

Образуется замкнутый контур из стрелок 4 – 6 – 7 – 5 – 4 (при этом не важно, двигаемся мы по стрелкам или против них). В этом контуре направление стрелок 7→6 и 4→5 противоположно направлению новой стрелки 4→6.

30

2

3 120

Определяем минимум среди поставок для стрелок этого контура, направление которых противоположно направлению новой стрелки.

Для контура поставки на стрелках в направлении новой стрелки увеличим на этот минимум, а поставки на стрелках противоположного направления уменьшим на этот минимум. Стрелка, которой соответствует выбранный минимум, ликвидируется. Поставки для стрелок вне контура остаются без изменений.

Определим минимум среди поставок для стрелок 7→6 и 4→5:

Min (30, 130) = 30.

Для контура 4 – 6 – 7 – 5 – 4 поставки на стрелках в направлении новой стрелки 4→6 (4→6 и 7→5) увеличим на этот минимум: 0 + 30 = 30 и 120 + 30 = 150 соответственно.

Для контура 4 – 6 – 7 – 5 – 4 поставки на стрелках 7→6 и 4→5 уменьшим на этот минимум: 130 – 30 = 100 и 30 – 30 = 0 соответственно, то есть стрелку 4→5 ликвидируем.

2

3 150

Поставки для стрелок вне контура остаются без изменений. Число стрелок = 6 = число вершин – 1. Получаем следующий план поставок. Исследуем ее оптимальность.

3

4 7

Припишем вершине 1 потенциал 0 и пересчитаем потенциалы других вершин. У нас четыре ребра без стрелок: (1,6), (2,4), (3,4), (4,5). Найдем их характеристики.

Характеристика ребра (1,6) = стоимость перевозки единицы груза для ребра (1,6) – больший потенциал вершина ребра (1,6) + меньший потенциал вершины ребра (1,6) = 4 – 6 + 0 = -2 < 0.

Характеристика ребра (2,4) = стоимость перевозки единицы груза для ребра (2,4) – больший потенциал вершин ребра (2,4) + меньший потенциал вершин ребра (2,4) = 7 – 3 + 1 = 5.

Характеристика ребра (3,4) = стоимость перевозки единицы груза для ребра (3,4) – больший потенциал вершин ребра (3,4) + меньший потенциал вершин ребра (3,4) = 4 – 3 + 3 = 4.

Характеристика ребра (4,5) = стоимость перевозки единицы груза для ребра (4,5) – больший потенциал вершин ребра (4,5) = 2 – 3 + 2 = 1.

Характеристика ребра (1,6) отрицательна. Поэтому полученный план поставок не является оптимальным. Рисуем к ребру (1,6) стрелку от вершины с меньшим потенциалом (1) к вершине с большим потенциалом (6).

0

3

1 4

120 2

4 7

3 150

30 3

Образуется замкнутый контур из стрелок 1 – 6 – 7 – 5 – 1 (при этом не важно, двигаемся ли мы по стрелкам или против них). В этом контуре направление стрелок 7→6 и 1→5 противоположно направлению новой стрелки 1→6.

Определим минимум среди поставок для стрелок 7→6 и 1→5: min (100, 0) = 0. Поэтому все поставки остаются без изменений. Стрелку 1→5 ликвидируем.

Число стрелок = 6 = число вершин – 1. Получаем следующий план поставок. Проверим его на оптимальность.

1 4

120 2

4 7

Убеждаемся, что нет ребер с отрицательными характеристиками, то есть это оптимальный план поставок. Затраты на перевозку равны 120*1 + 70*3 + 0*4 + 30*3 + 150*3 + 100*7 = 1570.