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

Одной из типичных задач линейного программирования является так называемая транспортная задача. Она возникает при планировании наиболее рациональных перевозок грузов. В одних случаях это означает определение такого плана перевозок, при котором стоимость последних была бы мини-мальной. В другом случае чтобы время перевозок было бы минимальным

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

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

Пусть в m пунктах отправления находится соответственно а₁,а₂,…а_m

единиц однородного груза, который должен быть доставлен n потребителям в количествах b₁,b₂,…b_n (единиц). Заданы стоимости с_ik единицы перевозок груза из пункта отправления i в пункт потребления k.

Через х_ik 0, i = 1,2,…m, k = 1,2,…n обозначим количество единиц груза, перевозимых из i - ого склада к k - ому потребителю. Очевидно, должно выполняться

= а_i i = 1,2,…m , (12)

= b_k k = 1,2,…n (13)

Приведенные условия означают, что (18) – количество груза вывезенного от i-ого поставщика ко всем n потребителям равно количеству груза имеющегося у этого i – ого поставщика, и (19) – количество груза доставленного k – ому потребителю от всех m поставщиков равно количеству груза требуемого этому потребителю.

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

F=с₁₁х₁₁+с₁₂х₁₂+...+с_mn x_mn (14)

Получили задачу ЛП: Требуется найти m·n переменных х_ik ≥0, удовлетворяющих указанным условиям (12) и (13) и минимизирующих целевую функцию F (14).

Решение такой задачи разбивается на 2 этапа.

1. Определение исходного опорного решения.

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

Построение первоначального опорного плана и его дальнейшие преобразования производятся в так называемой распределительной таблице

Таблица 3

потребители поставщики	b1	b2	…	bn
a1	с11 х11	с12 х12	…	с1n x1n
a2	с21 х21	с22 х22	…	c2n x2n
…	…	…	…	…
am	cm1 xm1	cm2 xm2		cmn xmn

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