7.2. Общая постановка и решение транспортной задачи

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

где i – индекс пунктов отправления груза j – индекс пунктов назначения груза X_ij – количество груза, перевозимого от i – го пункта отправления до j – го пункта назначения, т. При решении задачи должны соблюдаться следующие условия допустимости (ограничения):

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

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

т.е. объем перевозок между любыми пунктами не должен быть величиной отрицательной. Условия оптимальности: Схема доставки груза будет оптимальной, если оценочные числа пунктов отправления(а1,а2,а3) и оценочные числа пунктов назначения груза(b1,b2,b3) будут удовлетворять следующим условиям:

т.е. для пунктов, между которыми осуществляются перевозки;

т.е. для пунктов, между которыми перевозок нет.

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

Пусть а1=700, тогда: b2=700+690=1390 b3=700+447=1147 a2=1390-333=1057 a3=1390-686=704 b1=1057+301=1358

Составляем матрицу решения задачи (табл.21).

Таблица 21

Матрица решения задачи №1

i	Qi	j	Саранск			Астрахань			Ульяновск
		Vi	60			180			140
		bj ai	1358			1390			1147
Череповец	200	700	-	460	60		690	140		447
Саратов	100	1057	60	301	40		333	-		284
Углич	80	704	-	398	80		686	-		447

Так как все условия допустимости соблюдены, проверяем матрицу на выполнение условий оптимальности: 1)1358-301=1057=> нарушений нет; 1390-690=700=> нарушений нет; 1390-333=1057=> нарушений нет; 1390-686=704=> нарушений нет; 1147-447=700=> нарушений нет. 2)1358-700=658>460=>есть нарушение; 1358-704=654>398=>есть нарушение; 1147-1057=90<284=> нарушений нет; 1147-704=443<447=>нарушений нет.

Данная матрица является неоптимальной, для чего перераспределяем объем перевозок груза и составляем новую матрицу(табл.22). Пусть а1=700, тогда: b2=700+690=1390 b3=700+447=1147 a2=1390-333=1057 a3=1390-686=704 b1=704+398=1102

Таблица 22

Матрица решения задачи №2

i	Qi	j	Саранск			Астрахань			Ульяновск
		Vi	60			180			140
		bj ai	1102			1390			1147
Череповец	200	700	-	460	60		690	140		447
Саратов	100	1057	-	301	100		333	-		284
Углич	80	704	60	398	20		686	-		447

Так как все условия допустимости соблюдены, проверяем матрицу на выполнение условий оптимальности после корректировки: 1)1102-398=704=> нарушений нет; 1390-690=700=> нарушений нет; 1390-333=1057=> нарушений нет; 1390-686=704=> нарушений нет; 1147-447=700=> нарушений нет. 2)1102-700=402<460=>нарушений нет; 1102-1057=45<301=>нарушений нет; 1147-1057=90<284=>нарушений нет; 1147-704=443<447=>нарушений нет.

Для всех клеток условия оптимальности выполняются.

В данном разделе мы распределили грузопотоки между пунктами отправления и назначения так, чтобы суммарная плата за доставку всех грузов была минимальной. Таким образом, оптимальным является следующий вариант доставки груза: Череповец-Астрахань: 60*690=41400 тыс.руб(ВС); Череповец-Ульяновск:140*447=62580 тыс.руб(ВС); Саратов –Астрахань:100*333=33300 тыс.руб(ЖД); Углич – Саранск: 60*398=23880 тыс.руб(ЖД); Углич – Астрахань: 20*686=13720тыс.руб(ЖД). Т.е. суммарная стоимость составит:

Σ=41400+62580+33300+23880+13720=174880 тыс.руб.

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