Транспортная задача в сетевой постановке

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

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

a_i . Если a_i  < 0, то в этом пункте продукция производится, если а, > 0, то продукция потребляется, а если a_i  = 0, то данный пункт является транзитным, т.е. все, что в него привезено, должно быть вывезено.

Пусть транспортная сеть содержит s участков пути. Под участком пути понимается часть сети, соединяющая любые два ее пункта. Рассмотрим q-ый участок пути, на котором осуществляется перевозка:

                        x_q

i_q                                  c_q                                    j_q

где:

i_q - пункт, из которого груз вывозится;

j_q - пункт, в который груз завозится;

c_q - стоимость перевозки единицы груза на этом участке пути:

x_q - объем перевозки из пункта i_q  в пункт j_q.

Стрелка → показывает направление перевозки груза.

Требуется найти такой план перевозки груза, при котором из пунктов производства вывозится вся продукция, в пунктах потребления удовлетворяются их потребности, а суммарные затраты на перевозку грузов были бы минимальных, т.е. необходимо найти такой вектор X = (x₁, x₂, … x_s), для которого:

                             (5)

при условии

 , ; , ;

где

- объем груза, ввозимого в пункт i,

 - объем груза, вывозимого из i .

Необходимым и достаточным условием разрешимости данной задачи является

;                               (6)

т.е. все, что произведено, должно быть потреблено.

Решение задачи осуществляется методом потенциалов. Опорный невырожденный план транспортной задачи должен содержать ровно (N - 1) положительную перевозку, не иметь замкнутых маршрутов и «висячих» пунктов.

Первоначальный опорный план строится по методу наименьшей стоимости. Затем для каждого пункта сети находятся потенциалы по формуле

V_jq - V_jq =C_q, X_q > 0,                    (7)

где V_jq и V_jq - потенциалы пунктов, ограничивающих один и тот же q-ьм участок пути, a C_q - стоимость единицы перевозимого по этому участку груза.

Для оптимального плана транспортной задачи в сетевой постановке для всех участков пути должно выполняться условие:

       ,  .           (8)

Если условие (8) не выполняется, то для тех участков пути, где оно не выполняется, рассчитывается невязка по формуле:

;

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

Пример.

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

Рис. 1

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

,

и, таким образом, эта задача разрешима. Следовательно, начинаем строить опорный план с участка пути с наименьшей стоимостью перевозки. Для удобства решения поименуем все пункты латинскими буквами. Наименьшая стоимость перевозки находится на участках пути AG и FH. Так как А - пункт производства, то с участка AG и начинаем строить опорный план. Полученный план указан на рисунке 1.

Всего получилось 9 перевозок, что точно равно N - 1, замкнутые маршруты также отсутствуют, следовательно, план является опорным. Теперь строим систему потенциалов, начиная с пункта А. Значение потенциала для этого пункта задаем произвольно, например, V_А = 100.

Используя условие (7), находим все остальные потенциалы:

V_B = 97; V_C = 85; V_D = 96; V_E = 102; V_F = 107;

V_G = 105; V_H =112; V_K = 103; V_L = 93.

Проверяем план на оптимальность, используя условие (8), которое нарушается один раз на участке BF (V_F - V_B > C_BF = 8). Следовательно, на этом участке необходимо ввести ε -перевозку и произвести перераспределение плана. Направление
ε-перевозки определяем исходя из величины потенциалов пунктов Вир направление задается из пункта с меньшим потенциалом, т.е. из Вв F, что и отмечаем на рисунке 1. С введением
ε-перевозки мы получаем замкнутый ε-маршрут, проходящий через пункты В, F, Н, К, L, E, D, С, по которому и происходит перераспределение плана, что отмечается знаками «+» и «-». Определяем величину с -перевозки как наименьшую из всех перевозок, стоящих на ε -маршруте со знаком «-», т.е. ε = min {x_q } В данном случае ε = min {5; 22;10;10} =5. Определив
ε -перевозку, строим новый план, в котором учитываем изменение перевозок на величину ε (т.е. уменьшаем их, если стоит знак «-» и увеличиваем, если стоит знак «+»). Новый план представлен на рис. 2.

Проверяем его на оптимальность, для чего сначала строим систему потенциалов:

V_A=100; V_B=99; V_С=87; V_D=98; V_E=104;

V_F = 107; V_G = 105; V_H =112; V_K = 105; V_L = 95.

Проверяя условие оптимальности, приходим к выводу, что, поскольку условие (8) выполняется для всех участков пути, данный план является оптимальным, а целевая функция равна:

т.е. суммарные затраты на транспортировку 90 единиц продукции составляют в оптимальном плане 985 единиц.

Рис. 2

Таким образом, оптимальное решение предполагает транспортировку 16 единиц продукции из пункта А в пункт G, 19 единиц из пунктов Л и С в пункт АУ (14 и 5 единиц, соответственно, через пункт F), 20 единиц продукции из пункта С в пункт В, 5 и 13 единиц продукции из пунктов Си Lb пункт Е и, наконец, 17 единиц продукции из пункта L в пункт К.