<<
>>

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

Если условия транспортной задачи заданы в виде схемы, на которой условно изображены поставщики, потребители и связывающие их дороги, указаны величины запасов груза и потребности в нем, а также числа Су, являющиеся показателями принятого в задаче критерия оптимальности (тарифы, расстояния и т.
п.), то говорят, что транспортная задача поставлена в сетевой форме (рис. 8.1).

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

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

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

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

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

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

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

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

План распределения груза, отвечающий этим требованиям, представлен на рис. 8.2.

Ш

и

ВЭ

Далее следует проверить план на оптимальность. Для этого вы-числяем потенциалы.

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

оптимальности, если же направление стрелки противоположно, Су вычитаем (см. рис. 8.2).

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

Если все ребра без стрелок имеют неотрицательные характери-стики, то составленный план является оптимальным.

Вычислим характеристики ребер без стрелок

Ssj = 5 - (13 - 7) = —1; ?4,6 = 1; 54,3 = 0; S2,3 = -2.

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

В нашем примере новая стрелка направлена от вершины II к вершине III (штриховая линия (см. рис. 8.2).

Ш

Для определения величины поставки (р) для ребра S23 рассматриваются все стрелки образовавшегося замкнутого контура, имеющие направление, противоположное новой стрелке (участок *У2з), и среди них находится стрелка с наименьшей поставкой А (в нашем примере X = 15 на ребре 56 7). Выбранная таким образом величина прибавляется ко всем поставкам в стрелках, имеющих то же направление, что и новая стрелка, и вычитается из поставок в стрелках, имеющих противоположное направление. Поставки в стрелках, не входящих в контур, сохраняются неизменными. Стрелка, на которой выбрано число Л, ликвидируется и общее число стрелок остается прежним. Новый опорный план представлен на рис. 8.3.

Полученный план исследуется на оптимальность, подобно предыдущему.

Сделав еще шаг, получим оптимальный план (рис. 8.4), когда все характеристики Sy на участках без стрелок неотрицательны.

И Ш

ш

он ш

Определим значение целевой функции: zmin = 100 • 2 + 25 • 1 + 15 • 3 + 70 • 3 + 10 • 6 + 20 • 5 = 640.

Вырождение плана транспортной задачи в сетевой постановке проявляется в том, что при полном использовании запасов и полном удовлетворении потребностей количество стрелок оказывается меньше чем т + п — 1, где п — поставщики, а т — потребители.

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

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

<< | >>
Источник: Бережная Е.В., Бережной В.И.. Математические методы моделирования экономических систем: Учеб. пособие. — 2-е изд., перераб. и доп. — М.: Финансы и статистика,2006. - 432 е.. 2006

Еще по теме 8.5. Транспортная задача в сетевой постановке: