Транспортная задача

Транспортные модели описывают перемещение (перевозку) какого-либо товара из пункта отправления (исходный пункт, например место производства) в пункт назначения (склад, магазин, грузохранилище). Назначение транспортной задачи — определить объем перевозок из пунктов отправления в пункты назначения с минимальной суммарной стоимостью перевозок. При этом должны учитываться ограничения, налагаемые на объемы грузов, имеющихся в пунктах отправления (предложения), и ограничения, учитывающие потребность грузов в пунктах назначения (спрос). В транспортной модели предполагается, что стоимость перевозки по какому-либо маршруту прямо пропорциональна объему груза, перевозимого по этому маршруту. От того, насколько рационально будет прикрепление пунктов потребления к пунктам производства, зависит объем транспортной работы.

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

Возникает задача о наиболее рациональном прикреплении потребителей к поставщикам, при котором удовлетворяются их потребности, а суммарные затраты на перевозку минимальны. При этом величина транспортных расходов прямо пропорциональна объему перевозимой продукции и задается с помощью тарифов на перевозку единицы продукции.

Параметры задачи.

Имеется m пунктов производства А₁, …, А_m однородного продукта и n пунктов потребления В₁,…, В _n.

Предложение поставщика в каждом i-м пункте составляет а_i единиц, i = 1, . . ., m.

Спрос потребителя в каждого j-ом пункте составляет b_j единиц, j = 1, . . .. n.

Транспортные расходы на перевозку единицы продукции из А_i в В_j составляет c_ij (себестоимость, расстояние, тариф, время, расход топлива).

Требуется определить оптимальный план перевозок, при котором суммарные транспортные расходы минимальны продукции (управляющий параметр - количество продукции, перевозимой от каждого поставщика к каждому потребителю).

Обозначим x_ij – количество продукции, перевозимой от i-го поставщика j-му потребителю

i = 1, . . ., m, j = 1, . . .. n.

Математическая модель задачи

Суммарные затраты на транспортировку из всех пунктов производства во все пункты потребления:

тр

Управляющий параметр: x_ij ≥ 0 , - количество единиц продукции, поставляемой из А_i в В_j – перевозки из пунктов потребления в пункты производства исключены.

Ограничения

Суммарное предложение должно быть не меньше суммарного спроса

В каждый пункт потребления доставляется продукции не менее необходимой

,

От каждого поставщика вывозится продукции не более имеющейся

.

Всякое неотрицательное решение систем уравнений называется опорным планом (совокупность чисел x_ij , , , удовлетворяющая приведенным ограничениям). Решение X*=(x_ij ), при котором функция S принимает минимальное значение - называется оптимальным планом транспортной задачи.

Это общая задача линейного программирования – ограничения в виде неравенств (несбалансированная транспортная модель).

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

Несбалансированная модель может быть приведена к сбалансированной – неравенства заменены равенствами (в общем случае путем введения фиктивных неотрицательных переменных – фиктивного поставщика или потребителя продукции).

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

- сумма спроса равна сумме предложений;

- спрос каждого пункта потребления удовлетворяется полностью;

- весь продукт из каждого пункта производства должен быть вывезен.

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

На пересечении i-ой строки и j-го столбца стоит тариф с и сюда же заносится значение х_ij – количество продукции, поставляемой от i-го поставщика j-му потребителю.

При большой размерности задачи (m x n) отыскание оптимального плана путем непосредственного перебора становится трудоемкой. Решение транспортной задачи состоит из двух этапов: нахождение начального плана, улучшение его и получение оптимального плана перевозок.

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

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

Хотя транспортная задача может быть решена как обычная задача линейного программирования, ее специальная структура позволяет разработать алгоритм с упрощенными вычислениями(на основе симплекс-метода).

Для решения транспортной задачи составляется транспортная таблица.

Номер поставщика	Номер потребителя						Предло-жение
	1	2	. . .	j	. . .	n
1	c11 x11	c12 x12	. . .	c1j x1j	. . .	c1n x1n	a1
2	c21 x21	c22 x22	. . .	c2j x2j	. . .	c2n x2n	a2
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
i	ci1 xi1	ci2 xi2	. . .	cij xij	. . .	cin xin	ai
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
m	cm1 xm1	cm2 xm2	. . .	cmj xmj	. . .	cmn xmn	am
Спрос	b1	b2	. . .	bj	. . .	bn