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

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

Простейшими транспортными задачами являются задачи о перевозках однородного груза из пунктов отправления (от поставщиков) в пункты назначения (к потребителям) при обеспечении минимальных затрат на перевозки. Например, таблица для m поставщиков и n потребителей имеет вид.

Таблица 2.1

Поставщики	Потребители				Запасы поставщиков.
	1	2	j	n
1	C11	C12	С1j	C1n	B1
2	C21	C22	C2j	С2n	В2
m	Cm1	Cm2	Cmj	Cmn	Вm
Спрос потребителей	A1	A2	Aj	Аn

В таблице коэффициенты С означают затраты на перевозки одной единицы груза от каждого поставщика к каждому потребителю, В - запасы груза у каждого поставщика, А - спрос (потребность) каждого потребителя на определенный период. Обозначим через X количество груза (поставку), которое нужно перевезти от каждого поставщика к каждому потребителю.

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

При следующих ограничениях:

X_ij>=0

Если к системе ограничений добавить еще одно:

Суммарный запас поставщиков будет равен суммарному спросу потребителей, то мы получим закрытую модель задачи. Задачи, в которых это ограничение отсутствует, с оответствуют открытой модели.

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

Любое решение транспортной задачи, т. е. нахождение Х11, X12, ...X_mn, называется распределением поставок. Оптимальному решению транспортной задачи соответствует оптимальное распределение поставок. Так как поставки не могут быть отрицательными, то речь может идти только о допустимых решениях.

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

Свойства транспортной задачи.

1.ТЗ имеет оптимальное решение тогда и только тогда, когда

(20)

2. Если план X* является оптимальным, то ему соответствует система из m+n чисел u₁,…,u_m и v₁,…,v_n (называемых потенциалами), удовлетворяющих условию:

ui+vj=cij для всех xij>0, (21)

ui+vj≤cij для всех xij*=0, (22)

3. Если все числа a1,...,am и b1,...,bm - целые и выполнено условие (20), то элементы оптимального плана являются целыми числами.

4. Ранг системы векторов условий ТЗ (т.е. число линейно независимых столбцов матрицы ограничений) равен m+n-1. План перевозок X, содержащий ровно m+n-1 ненулевых перевозок, называется опорным планом (ОП) и играет роль д.б.р. в задаче ЛП. План, содержащий меньше чем m+n-1 ненулевых элементов называется вырожденным.

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