Курсовая работа: Решение транспортной задачи

Поток минимальной стоимости – задача о потоке минимальной стоимости состоит в нахождении самого дешевого способа передачи определенного количества потока через транспортную сеть.

Обозначения:

Для всех дуг имеется пропускная способность:

Стоимость пересылки единицы потока по дуге e: C(e)

Накладываются следующие условия:

1. Ограничение пропускной способности . Поток не может превысить пропускную способность.

2. Антисимметричность: . Поток из u в v должен быть противоположен потоку из v в u.

4. Описание алгоритма нахождения потока минимальной стоимости

Вход: транспортная сеть G=( V,E)с пропускной способностью дуг B(e)

Выход: максимальный поток с минимальной стоимостью.

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

Алгоритм:

Шаг 0

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

Шаг 1

Для текущего потока строится инкрементальный граф. Прямые дуги имеются, если поток на этой дуге меньше, чем пропускная способность:

Обратные дуги (дуги противоположны по отношению к ориентации прямых дуг) имеются, если на дугах имеется поток.

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

Назначаем длины дуг для инкрементального графа:

· Для прямой дуги: e:C(e)

· Для обратной дуги: e: - C(e)

Шаг 2

Нахождение кратчайшего пути в инкрементальном графе из источника vв сток u. Если такого пути нет, то происходит конец алгоритма. Найденный путь является максимальным.

Шаг 3

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

Для каждой прямой дуги: