9.3. Сетевые постановки транспортных задач

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

Сетевая постановка закрытой транспортной задачи. Граф должен представлять ориентированное дерево. Построение его можно начинать с любой вершины. Если начальная вершина положительная (+), то продукция из нее вывозится и она является началом дуги (стрелки), которая должна входить в одну из смежных вершин. При построении графа с отрицательной вершины (–), в которую ввозится продукция, она должна быть концом дуги (стрелки), выходящей из любой смежной вершины. Стрелка вдоль ребра символизирует превращение его в дугу. На стрелке указывается величина перемещаемой продукции:

Составление базисного плана. В качестве начальной вершины выбрана положительная вершина а – поставщик, имеющий 70 единиц продукции (рис. 9.6). От нее направлены две стрелки: а) в отрицательную вершину d, которой требуется 50 единиц продукции; б) в вершину f (+20) перемещаем 20 единиц продукции.

Исчерпав возможности поставщика a, переходим к распределению продукции поставщика b (+90). Из вершины b отправляем в вершину с всю продукцию (90 ед.). В ней оставляем (вершине с) необходимые 55 единиц, а лишнюю часть (35 ед.) передаем в вершину h, куда необходимо поставить 75 единиц продукции. Недостающую продукцию 40 единиц должны получить от соседнего поставщика g , который имеет 15 единиц. Этого недостаточно, поэтому вершину h пополняем недостающими единицами из вершины е (+25), пройдя через вершину g. В результате проведенных операций все поставщики отправили продукцию всем потребителям.

Рис. 9.6.Базисный план закрытой транспортной задачи в сетевой постановке

Однако мы получили пока несвязный граф (имеется пробел между стрелками). Он состоит из двух связных компонент. Число стрелок в графе (рис. 9.6) равно 6, а должно быть 7, так как в графе 8 вершин. Следовательно, на одном из ребер ставим стрелку любого направления с нулевой поставкой продукции, чтобы образовать контур. Для этого подходит соединение вершин а–b, а также d–e и не подходит соединение c–e, d–f, чтобы не образовать контуры.

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

Проверка допустимого плана на оптимальность проверяется методом потенциалов. Для этого вначале любой вершине присваивается любая величина потенциала (λ). Однако его величина должна быть большая, по сравнению с c_ij ребер графа, чтобы не получить отрицательных потенциалов вершин и не усложнять работу.

В вершине а потенциал устанавливаем равным λ_а = 10. Двигаясь по дугам со стрелками, вычисляем потенциалы других вершин сети с учетом направления стрелок. Если стрелка выходит из вершины, то к ее потенциалу прибавляется величина c_ij ребра; если стрелка входит в вершину, то с ее потенциала вычитается c_ij соответствующего ребра. Потенциалы вершин (λ) заключаем в прямоугольник у вершины.

Функционал можно рассчитывать с использованием c_ij или λ:

Z =∑λ_i · х_ij = 10 · 70 + 13 · 90 + 18 · (–55) + 12 · (–50) + 16 · 25 + 17 · (–20) + + 17 · 15 + 22 · (–75) = –1055.

Z =∑c_ij · х_ij = 3 · 0 + 90 · 5 + 7 · 20 + 2 · 50 + 1 · 25 + 4 · 35 + 5 · 40 = 1055.

Величины функционалов получены одинаковые, но с противоположными знаками. Следует проверить план на оптимальность.

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

E_df = c_df – (λ _f – λ _d) = 2 – (17 – 12) = –3.

В нашем графе план неоптимальный, так как имеет два ребра с отрицательными характеристиками E_ij: ребро d – e (–2) и d – f (–3). Поэтому производим перераспределение поставок. Для этого на ребро с наибольшей отрицательной E_df = –3 ставится стрелка, которая имеет направление от вершины с меньшим потенциалом к вершине с большим потенциалом d→f.

Размер поставки на новой стрелке зависит от следующих обстоятельств. Новая стрелка привела к образованию псевдоконтура a→d→f←a, что требует изъятия одной стрелки для соблюдения правила: число вершин минус единица равно числу стрелок в графе. Кроме того следует разрушить псевдоконтур, которого не должно быть в графе. В возникшем псевдоконтуре выбираем стрелку противоположного направления новой стрелке d→f. Выбираем, если есть несколько, ту стрелку которая имела наименьшую величину поставки (af = 20) до появления новой стрелки d→f.

Минимальную поставку (20) перераспределяем по псевдоконтуру следующим образом: она прибавляется на стрелках, имеющих одинаковое направление с новой стрелкой и вычитается из поставок на стрелках, которые имеют противоположное направление новой стрелке.

В рассматриваемом псевдоконтуре стрелка a→d имеет одинаковое направление с новой d→f. На a→d прибавляется поставка 20 к прежней 50 и получается новая поставка 70. Излишек поставки 20, образовавшийся в вершине d передается вершине f по новой стрелке d→f. Прежняя поставка 20 между вершинами a→f убирается вместе со стрелкой (рис. 9.7). В результате перемещения минимальной поставки 20 по псевдоконтуру ликвидирован сам контур, потребители получили необходимую продукцию.

Рис. 9.7. Первое перераспределение поставки (20) по псевдоконтуру

Новый план стал более оптимален, так как величина функционала уменьшилась на 100 (см. рис. 9.7). Однако при расчете потенциалов вершин и характеристики ребер получена отрицательная величина минус 2 между вершинами d – e. Значит, необходимо произвести новое перераспределение продукции.

Для этого на ребро с отрицательной характеристикой ставим стрелку d→e. Образуется псевдоконтур a→d→e→g→h←c←b←a, в котором одна из встречных стрелок a→b имеет минимальную поставку, равную нулю. Ее перераспределяем по псевдоконтуру, как описано выше, и получаем новый допустимый план (рис. 9.8).

Рис. 9.8. Второе перераспределение поставки (0) по псевдоконтуру

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