Определение оптимального варианта перевозки грузов

Задача. Составить оптимальный план перевозки грузов от трёх поставщиков с грузами 240, 40, 110 т к четырём потребителям с запросами 90, 190, 40 и 130 т. Стоимость перевозок единицы груза от каждого поставщика к каждому потребителю даны матрицей

.

РЕШЕНИЕ. Запасы грузов у поставщиков: т. Запросы потребителей: т; так как , то вводим фиктивного поставщика с грузом а_4ф = 450 – 390 = 60 т.

Тариф фиктивного поставщика 4ф примем равным 20 усл. ед.

B j Ai	1	2	3	4	ui
	90	190	40	130
1 240	7	13 130	9	8 110	0
2 40	14	8 0	7 40	10	-5
3 110	3 90	15	20	6 20	-2
4ф 60	20	20 60	20	20	7
vj	5	13	12	8

Так как т + п – 1 = 7, а число занятых клеток равно 6, то для исключения вырожденности введём в клетку (2, 2) нулевую поставку. Оценки свободных клеток: , .

Оценка свободной клетки (1, 3) больше нуля, перераспределим грузы:

Запишем полученное перераспределение грузов в табл. :

B j Ai	1	2	3	4	ui
	90	190	40	130
1 240	7	13 90	9 40	8 110	0
2 40	14	8 40	7	10	-5
3 110	3 90	15	20	6 20	-2
4ф 60	20	20 60	20	20	7
vj	5	13	9	8

Имеем

, , , , , , , , .

Получили оптимальное решение:

Стоимость транспортных расходов – 3120 усл. ед.

Приложение транспортных моделей к решению некоторых экономических задач.

Алгоритм и методы решения транспортных задач могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов c_ij имеют различный смысл в зависимости от конкретной экономической задачи. Виды подобных задач:

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

- оптимальные назначения, или проблема выбора. Имеется т механизмов, которые могут выполнять т различных работ с производительностью c_ij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;

- задача о сокращении производства с учётом суммарных расходов на изготовление и транспортировку продукции;

- увеличение производительности автомобильного транспорта за счёт минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность;

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