Математическую модель задачи.

ТРАНСПОРТНАЯ ЗАДАЧА

Общий вид транспортной задачи:

	Запросы потребителей
Запасы поставщиков

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

Определение. Если сумма запасов груза равна суммарной потребности в нем, т.е.

(1)

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

Определение. Если условие (1) не выполнено, то транспортная задача называется открытой.

Закрытая транспортная задача

Математическую модель задачи.

Пусть x_ij − объем перевозки от - го поставщика к - му потребителю.

Целевая функция - суммарная стоимость перевозок:

(2)

Ограничения по запасам поставщиков ( ограничений):

(3)

Ограничения по запросам потребителей ( ограничений):

(4)

Условие неотрицательности:

.

и условие закрытости задачи (1).

Оптимальным решением этой задачи является матрица

Транспортная задача как ЗЛП можно решать симплекс-методом, однако наличие большого числа переменных и ограничений делает вычисления громоздкими. Поэтому для решения транспортных задач разработан метод потенциалов.

Опорным решением транспортной задачи называется любое допустимое базисное решение задачи.

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

			…
					…
					…
…	…	…	…	…
					…

Пример.