Математическая модель транспортной задачи

Обозначим через количество груза, перевозимого из пункта в пункт . План перевозок можно записать в виде матрицы .

По смыслу, переменные неотрицательны: . (1)

Целевая функция означает общие транспортные расходы, которые должны быть наименьшими:

. (2)

Система ограничений включает условия вывоза груза и доставки груза.

1) Если запас груза равен потребностям , то система ограничений примет вид:

, (условия вывоза имеющегося груза) (3)

. (условия доставки требуемого груза) (4)

2) Если запас груза больше потребностей , то все потребности будут удовлетворены, но не все запасы будут вывезены, и условие вывоза примет вид

. (3*)

3) Если же запас груза меньше потребностей , то все запасы будут вывезены, но не все потребности будут удовлетворены, и условие доставки груза примет вид

. (4*)

Математическая постановка транспортной задачи:

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

· План перевозок называется допустимым, если он удовлетворяет ограничениям (1), (3), (4).

· Допустимый план перевозок, доставляющий минимум целевой функции , называется оптимальным.

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

(5)

В этом случае транспортная задача называется сбалансированной, а модель - закрытой. Если же это равенство не выполняется, то задача называется несбалансированной (с неправильным балансом), а её модель – открытой.

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

Транспортные задачи решаются с помощью общего приема последовательного улучшения плана перевозок. Он включает в себя следующие этапы: