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

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

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

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

. (2)

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

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

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

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

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

. (3*)

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

. (4*)

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

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

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

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

Обычно данные транспортной задачи записывают в виде распределительной таблицы (таблица 1).

Таблица 1

Запасы груза	Потребности в грузе
	b1	b2	...	bn
a1	c11 x11	c12 x12	...	c1n x1n
a2	c21 x21	c22 x22	...	c2n x2n
...	...	...	...	...
am1	cm1 xm1	cm2 xm2	...	cmn xmn

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

(5)

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

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

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

1. Построение исходного плана перевозок.

2. Проверка плана перевозок на оптимальность.

3. Улучшение плана перевозок.

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