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

Общая постановка транспортной задачи. Пусть имеется m () поставщиков, располагающих некоторой однородной продукцией в объемах , , единиц соответственно, которая должна быть доставлена n (j = ) потребителям с объемами потребления по единиц. Задана матрица , где – стоимость перевозки единицы продукции от i-го поставщика j-му потребителю, называемой матрицей тарифов (издержек или транспортных расходов). Требуется составить план перевозок , т. е. найти, сколько единиц продукции должно быть отправлено из i-го пункта отправления в j-й пункт потребления так, чтобы суммарные издержки на перевозки были минимальными. При этом продукция от производителей должна быть полностью вывезена, а потребности потребителей должны быть удовлетворены.

Для наглядности условия транспортной задачи можно представить в виде распределительной таблицы (таблица 5.1).

Таблица 5.1

Поставщики	Потребители	Запас однородного продукта
	…		…
		…	с	…
…	…	…	…	…	…	…
		…		…
…	…	…	…	…	…	…
		…		…
Потребность в продукте		…		…

Если , то задача называется закрытой, в противном случае – т.е. если или - открытой.

Построим математическую модель закрытой задачи. Для этого обозначим через – количество груза, перевозимого от i -го поставщика j -му потребителю. Требуется построить планперевозок продукции, матрицу , . При этом целевая функция, описывающая общие суммарные затраты, связанные с реализацией плана перевозок, должна стремиться к минимуму:

(5.1)

Запишем ограничения, которым должны удовлетворять переменные величины , учитывая, что:

а) запасы продукции у поставщиков должны быть полностью вывезены:

, ; (5.2)

б) запросы потребителей должны быть полностью удовлетворены:

, ; (5.3)

в) должны быть устранены обратные перевозки – условие неотрицательности:

, , . (5.4)

Матрицу , удовлетворяющую ограничениям (5.2)-(5.4), называют допустимым планом перевозок, а переменные – допустимыми перевозками.

Таким образом, транспортная задача формулируется так: требуется найти среди допустимых планов перевозок такой план, который доставляет целевой функции (5.1) минимальное значение.

Допустимый план Х, доставляющий целевой функции (5.1) минимальное значение, называется оптимальным.

Транспортную задачу можно сформулировать и в сетевой форме.

Отрезок или линию, соединяющую i -го поставщика с j -м потребителем, назовем коммуникацией и обозначим (ij) или (). Если на всех коммуникациях (ij) поставлены величины перевозок , то получим транспортную сеть. Графический способ задания транспортной задачи указан на рис. 5.1.