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

Транспортная задача – одна из распространенных задач линейного программирования. Её цель – разработка наиболее рациональных путей и спосо-бов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Всё это сокращает время продвижения товаров, уменьша-ет затраты предприятий, фирм, связанные с осуществлением процессов снабжения сырьём, материалами, топливом, оборудованием и т.д.

4.1 Варианты экономических задачи

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

• Оптимальное закрепление за станками операций по обработке деталей. За-дача позволяет определить, сколько времени и на какой операции нужно исполь-зовать каждый из станков, чтобы обработать максимальное количество деталей.

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

• Задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции.

• Увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега.

Задание

Пусть имеется 3 поставщика и 4 потребителя. Запасы продукта у поставщиков, спрос потребителей и транспортные расходы на доставку единицы продукта от i-ro поставщика к j-му потребителю заданы в таблице.

Поставщик	Потребитель				Запас
	1	2	3	4
1	3	5	6	2	170
2	6	4	7	5	250
3	5	4	6	5	180
Спрос	150	230	160	60

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

Решение

Обозначим x_ij – количество продукта, доставляемого от i-ro поставщика к j-му потребителю, c_ij – стоимость перевозки от от i-ro поставщика к j-му потребителю. Тогда модель имеет следующий вид:

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

Мы должны заполнить m+n–1 клеток, где m – число поставщиков, an- число потребителей. Если число заполненных клеток меньше m+n–1, то недостающие клетки выбираются произвольно и заполняются нулями.

Рассчитаем потенциалы на основе равенства

Присвоим первому поставщику потенциал равный нулю. Значения потенциалов заносим в таблицу 6.

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

Таблица 6 – Транспортная таблица

Поставщик		Потребитель								Запас
		1		2		3		4
		υ1 = 3		υ2 = 5		υ3 = 8		υ4 = 7
1	u1 = 0		3		5		6		2	170
		150		20
2	u2 = 1		6		4		7		5	250
				210		40
3	u3 = 2		5		4		6		5	180
						120		60
Спрос		150		230		160		60

L = 150×3 + 20×5 + 210×4 + 40×7 + 120×6 + 60×5 = 2690 (ден. ед.) – общая сумма транспортных расходов.

Осуществляем проверку:

Условие оптимальности не выполняется. Для улучшения плана необхо-димо переместить перевозку в клетку, где условие оптимальности нарушено больше всего, т.е. разность максимальна. Такой клеткой является клетка (1; 4).

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

Последовательное улучшение плана представлено в таблицах 7-10.

Таблица 7 - Транспортная таблица

Поставщик		Потребитель								Запас
		1		2		3		4
		υ1 = 3		υ2 = 5		υ3 = 8		υ4 = 7
1	u1 = 0		3		5		6		+ - ­- ­- 2	170
		150		20
2	u2 = 1		6	+	4		7		5	250
				210		40
3	u3 = 2		5		4	+	6		5	180
						120		60
Спрос		150		230		160		60

L = 2690 (ден. ед.) – общая сумма транспортных расходов.

Таблица 8 - Транспортная таблица

Поставщик		Потребитель								Запас
		1		2		3		4
		υ1 = 3		υ2 = 0		υ3 = 3		υ4 = 2
1	u1 = 0		3		5		6		2	170
		150						20
2	u2 = –4		6		4		7		5	250
				230		20
3	u3 = –3		5		4		6		5	180
						140		40
Спрос		150		230		160		60

L = 2590 (ден. ед.) - общая сумма транспортных расходов.

Таблица 9 - Транспортная таблица

Поставщик		Потребитель								Запас
		1		2		3		4
		υ1 = 3		υ2 = 1		υ3 = 3		υ4 = 2
1	u1 = 0		3		5		6	40	2	170
		130
2	u2 = –3		6		4		7		5	250
		20		230
3	u3 = –3		5		4		6		5	180
						160		20
Спрос		150		230		160		60

L = 2570 (ден. ед.) - общая сумма транспортных расходов.

Таблица 10 - Транспортная таблица

Поставщик		Потребитель								Запас
		1		2		3		4
		υ1 = 3		υ2 = 1		υ3 = 3		υ4 = 2
1	u1 = 0		3		5		6	60	2	170
		110
2	u2 = –3		6		4		7		5	250
		20		230
3	u3 = –2		5		4		6		5	180
		20				160
Спрос		150		230		160		60

L = 2550 (ден. ед.) - общая сумма транспортных расходов.

В таблице 10 условие оптимальности выполняется для всех свободных клеток. Следовательно, это решение является оптимальным.

Ответ: Оптимальный план содержит шесть перевозок: от первого поставщика – 110 ед. к первому потребителю и 60 ед. к четвёртому; от второго поставщика – 20 ед. к первому и 230 ед. ко второму; от третьего поставщика – 20 ед. к первому и 160 ед. к третьему потребителю. При этом общая сумма транспортных расходов минимальна и составляет 2550 ден. ед.