Алгоритм метода частичных потоков

Транспортная задача

Транспортная задача – задача наиболее рационального распределения потока по дугам транспортной сети.

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

1 задача - транспортная задача по критерию стоимости;

2 задача - транспортная задача по критерию времени.

Часто транспортная задача трактуется как задача по организации перевозки некоторого груза.

Считают, что есть пунктов отправки груза, пунктов потребления груза: , .

В пунктах отправки имеется груз в количестве , а в пунктах приёма необходимо получить груз .

Необходимо выполнение условия баланса:

Транспортная задача по критерию стоимости

Известно, что стоимость перевозки по дуге единицы груза .

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

Задача решается исходя из теории потоков.

Введём обозначения:

- пропускная способность дуги из в ;

- стоимость прохождения единицы потока по дуге ;

- поток, проходящий по дуге .

Стоимость всего пути по дуге : .

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

где , поток по дуге не должен превышать пропускную способность.

Считаем, что - длина пути, тогда стоимость прохождения некоторого потока по пути из в равна: .

Существует два варианта решения транспортной задачи:

1 вариант. На пропускную способность дуг не накладывается никаких ограничений. Тогда задача решается простым нахождением кратчайшего пути.

2 вариант. На пропускную способность дуг накладываются ограничения. В этом случае задача решается методом частичных потоков.

1. В простейшем графе ищем кратчайший путь из в , .

2. Пусть в результате пункта 1 определили путь , имеющий пропускную способность , т.е. .

3. Пропускаем по данному пути поток , так что

4. Производим замену пропускной способности дуг по правилу:

5. Поток, который необходимо пропустить по транспортной сети, уменьшаем на , .

6. Исключаем из дальнейшего рассмотрения дуги, у которых .

7. Рассматриваем новый граф , как частичный граф исходного и переходим к пункту 1 для пропуска по транспортной сети потока .

Данные потоки и т.д., полученные на определённых шагах итерации называются частичными потоками.

8. Алгоритм останавливается, когда , .

Общая стоимость перевозки определяется по формуле (1).

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

Дата добавления: 2014-01-06