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

Если условия транспортной задачи заданы в виде картосхемы, на которой условно изображены поставщики, потребители и связывающие их дороги, указаны величины запасов груза и потребностей в нем, а также числа c_ijявляющиеся

Рис.1

показателями принятого в задаче критерия оптимальности (тарифы, расстояния и т.п.), то говорят, что транспортная задача поставлена в сетевой форме (рис. 1, 2).

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

Рис.2

Такие вершины называют нулевыми (см. вершину II на рис. 2). Различия между транспортными задачами в матричной и сетевой формах весьма незначительны, так как методы их решения основаны на одних и тех же идеях. Далее мы будем использовать уже известный метод потенциалов.

Решение задачи на сети начинается с построения начального опорного плана. Поставки груза из вершины в вершину будем обозначать стрелками с указанием величин поставок.

Решение задачи на сети начинается с построения начального опорного плана.

Опорный план должен удовлетворять следующим требованиям:

1) все запасы должны быть распределены, а потребности удовлетворены;

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

3) общее количество стрелок должно быть на единицу меньше числа вершин;

4) стрелки не должны образовывать замкнутый контур

Далее следует проверить план на оптимальность.

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

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

Если план неоптимален.

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

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

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

Вырождение плана транспортной задачи в сетевой постановке внешне проявляется в том, что при полном использовании запасов и полном удовлетворении потребностей количество стрелок оказывается меньше, чем n - 1, где n - общее число вершин (включая и нулевые!).

Способ преодоления вырождения весьма прост: дополнительно вводится нужное количество стрелок с нулевыми поставками. Направления стрелок выбираются произвольно, однако они не должны образовывать замкнутый контур.

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