Материал: 5462

76

50

Рис. 1. Исходная транспортная сеть

первоначальный план, при котором все ресурсы поставщиков должны быть отправлены и весь спрос потребителей удовлетворен. Стрелками показываем направление грузопотоков, а цифрами над ними – количество перевозимой продукции (рис. 2).

Из пункта отправления 1 идут две дуги (1,2) и (1,9) до пунктов потребления. Груз можно развозить произвольно. Например, в пункт 9 отправить грузопоток 50, а в пункт 2 – оставшиеся 250. Оставив 80 ед. груза в пункте 2, оставшиеся 170 повезти в пункт 3 и т.д. Из пункта 10 груз можно перевозить в пункты 11 и 7, 40 и 60 единиц соответственно. Из пункта отправления 6 груз в количестве 200 единиц можно везти в пункт 5, затем оставшиеся 140 ед. – в пункт 4.

Вариантов составления первого опорного плана множество. Рассмотрим один из них. Из пункта отправления 1 направим грузопоток по дуге (1,2) 250 ед. груза и по (1,9) – 50 ед. В пункте 2 оставляем 80 единиц груза и оставшиеся 170 единиц направим по дуге (2,3). Из пункта отправления 10 направим по дуге (10,3) 60 ед., а по дуге (10,11) – 40 ед. груза. Суммарный грузопоток в пункт 3 по дугам (2,3) и (10,3) составит 230 ед. груза. Оставив в пункте 3 120 единиц груза оставшиеся 110 направляем по дуге (3,4).

Из пункта отправления 6 груз отправляем по дугам (6,7) – 100 ед. и (6,5) – 100 ед. Оставив 60 ед. груза в пункте 6, оставшиеся 40 единиц направим по дуге (5,4). К пункту потребления идут два грузопотока (3,4) – 110 ед. и (5,4) – 40 ед., что составляет в сумме потребность в 150 единиц груза.

77

50

Рис. 2. Первоначальный план распределения

2. Присваиваем потенциалы вершинам. Например, вершине 1 присваиваем любой достаточно большой потенциал, чтобы впоследствии не иметь дело с отрицательными числами (допустим, 100). Потенциалы остальных вершин вычислим по правилу: при продвижении по дугам в направлении следования грузопотока к потенциалу предыдущей вершины прибавляем длину звена, а при движении по дугам против потока эту длину из потенциала предыдущей вершины вычитаем.

Это правило легко объясняется тем, что движение по потоку происходит от станции отправления груза до станции его назначения, поэтому общее расстояние перевозок будет расти. В обратном направлении – от станции назначения до станции отправления, следовательно, общее расстояние перевозок уменьшается. Число грузопотоков в невырожденном плане равно (n 1) 11 1 10 , n – число

вершин транспортной сети. Схема перевозок с проставленными потенциалами показана на рис. 3.

Рис. 3. Первоначальный план с потенциалами вершин

оптимальным, т.к. при переводе грузопотоков на данные дуги общее расстояние перевозок уменьшится. В примере отсутствуют грузопотоки на дугах (8,9), (1,10), (3,11), (5,11), (6,10), (7,10) и (9,10).

Условие оптимальности нарушено на дугах (8,9) и (7,10).

4. Выбираем дугу (8,9) с наибольшим нарушением условия оптимальности и направляем по ней грузопоток от меньшего потенциала к большему по замкнутому контуру, состоящему из дуг с грузопотоками и выбранной дуги без грузопотока с нарушением условия оптимальности. Этот контур единственный и состоит из дуг (8,9)-(8,7)-(7,6)-(6,5)-(5,4)-(4,3)-(3,2)-(2,1)- (1,9).

Продвигаясь по контуру в направлении от меньшего потенциала дуги с нарушением условия оптимальности к большему (в данном случае против часовой стрелки), находим дугу (8,6) с наименьшим встречным грузопотоком, равным 75. Вычитая его из всех встречных и прибавляя ко всем попутным грузопотокам, получаем улучшенный план перевозок (рис.

4).

Рис. 4. Улучшенный план перевозок

Повторяем шаги 2 и 3. Теперь нет необходимости заново вычислять все потенциалы вершин сети. Достаточно исправить потенциалы тех вершин,

79

где изменилось направление грузопотоков. В нашем случае это вершина 8. На рис. 4 видно, что при новом варианте распределения грузопотоков последние отсутствуют на дугах (7,8), (1,10), (3,11), (5,11), (6,10), (7,10), (9,10). Проверяем эти дуги на оптимальность.

Условие оптимальности нарушено на дуге (7,10). Повторяем шаг 4. Находим замкнутый контур, состоящий из дуг с потоками и дуги (7,10). Это контур, образованный из дуг (7,10), (10,3), (3,4), (4,5), (5,6), (6,7). Движение по нему следует осуществить от вершины с меньшим потенциалом до вершины с большим потенциалом (от 10-й к 7-й). В данном случае против часовой стрелки. В этом контуре с наименьшим встречным потоком является дуга (6,7) с грузопотоком мощностью 25 ед. Это число прибавляем ко всем попутным и вычитаем из всех встречных потоков. В результате получаем новый вариант перевозок (рис. 5):

Рис. 5. Оптимальный план

Снова повторяем шаги 2 и 3. Теперь потенциал меняется лишь к вершине 7 и равен 210.

В новом варианте без грузопотоков остались дуги (6,7), (7,8), (1,10), (3,11), (5,11), (6,10) и (9,10). Проверяем на оптимальность дуги (6,7) и (7,8) в связи с тем, что изменился только потенциал вершины 7

(6,7) v j ui 210 190 20 80 ;

80

(7,8) 220 210 10 60 .

Получим оптимальный план.

На рис. 6 изображена лишь та часть сети, по которой проходят грузопотоки:

2 3

4

5

+

Рис. 6. Дерево грузопотоков

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

Вопросы для самопроверки

1.В чем смысл транспортной задачи в сетевой постановке?

2.Как составляется первоначальный опорный план в транспортной задаче на сети?

3.Сколько дуг с грузопотоками содержит невырожденный план задачи?

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

5.Как находятся потенциалы вершин сети?

6.Как строится контур и определяется направление грузопотока в контуре?

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