Методическая разработка урока "ТРАНСПОРТНАЯ ЗАДАЧА"

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

Постановка задачи

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

Составленный план должен обеспечивать выполнение таких условий, как:

-          Полное удовлетворение спроса потребителей;

-          Вывоз всей продукции от поставщика;

-          Минимизация транспортных затрат.

Математическая модель

Рассмотрим простейший вариант транспортной задачи. В т пунктах отправления (складах) А_1, А₂, …, А_т находится однородный груз в количестве а_1, а_{2, …,} а_т единиц соответственно. Потребность в этом грузе в п пунктах назначения (магазинах) В₁, В₂, …, В_п составляет b₁, b₂, …, b_n  соответственно. Будем считать, что сумма запасов на складах равна суммарным потребностям в магазинах, т.е. = . Такая модель называется замкнутой.

Обозначим через С_ij удельные затраты, т.е. затраты на перевозку единицы груза из i-го пункта в j-й пункт назначения, а через X_ij – неизвестный объем груза, который надор перевезти из  j- го пункта отправления в j-й пункт назначения.

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

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

Рассмотрим транспортную задачу на примере четырех складов и четырех магазинов.

Задача. Известно, что на складах имеется запас муки в количестве 45, 100, 20, 75 мешков. А магазины имеют потребность в этом товаре в количестве 30, 80, 95, 35 мешков.

		Магазин № 1	Магазин №2	Магазин №3	Магазин №4
		b1 = 30	b2 = 80	b3 = 95	b4 = 35
Склад № 1	a1 = 45	6	3	7	10
Склад № 2	a2 = 100	10	4	12	10
Склад № 3	a3 = 20	5	9	8	11
Склад № 4	a4 = 75	4	2	4	8

Ячейки, выделенные фоном, содержат удельные стоимости перевозок C_ij. Например, стоимость перевозки единицы груза (мешка) со склада № 3 в магазин № 4 составляет 11 денежных единиц. Проверим замкнутость модели. Для этого просуммируем все запасы муки на складах: 45 + 100 + 20 + 75 = 240. Найдем суммарные потребности магазинов в муке: 30 + 80 + 95 + 35 = 240. Таким образом, модель является замкнутой, т. е. потребность  магазинов в муке равна запасу на складах.

Весь груз со складов должен быть вывезен. Этот факт для i-го склада можно отразить следующим образом: X_i1 + X_i2 + X_i3 + X_i4 = a_i. Весь груз в магазины должен быть ввезен. Для  j-го магазина будет справедливо следующее: X_1j + X_2j + X_3j + X_4j = b_j.

Таким образом, удовлетворению спроса магазинов отвечает выполнение системы уравнений:

Вывоз всего груза со складов достигается при выполнении системы уравнений:

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

Z = C₁₁ ×X₁₁ + … + C₁₄×X₁₄ + C_{21 ·} X ₂₁ + … + С_{24  ·}  X₂₄ + C_{31 ·} X₃₁ +…+ C_{34 ·}  X₃₄ +C_{41 ·}  X₄₁ +…+ C_{44 ·} X₄₄.

Решение с помощью электронных таблиц

Рассмотрим решение задачи на примере табличного процессора Microsoft Excel.

Представим данные в виде, показанном в таблице 1.

	A	B	C	D	E	F	G
1		Матрица перевозок
2			Магазин 1	Магазин  2	Магазин  3	Магазин 4
3		Склад № 1					=сумм
4		Склад № 2					=сумм
5		Склад № 3					=сумм
6		Склад № 4					=сумм
7			=сумм	=сумм	=сумм	=сумм
8
9
10
11		bj	30	80	95	35
12	ai		Магазин 1	Магазин  2	Магазин  3	Магазин 4
13	45	Склад № 1	6	3	7	10
14	100	Склад № 2	10	4	12	10
15	20	Склад № 3	5	9	8	11
16	75	Склад № 4	4	2	4	8
17
18
19		Сумм. затраты:	=СУММПРОИЗВЕД(С3:F16;C13:F16)

Исходными данными являются  удельные затраты на перевозки (диапазон ячеек C13:F16), запасы муки на складах (диапазон ячеек A13:A16), потребности магазинов в муке

 ( диапазон ячеек С11:F11).

Диапазон ячеек C3:F6  предназначен для получения искомого решения-объемов перевозок груза. Суммируя объемы перевозок в каждой строке, задаем левые части уравнений-ограничений, обеспечивающий вывоз всего груза с каждого склада. Суммированием  объемов  перевозок по столбцам задаются левые части уравнений-ограничений, удовлетворяющих спрос каждого магазина в муке. Формула =СУММПРОИЗВ (С3:F6; C13:F16), вычисляющая целевую функцию(суммарные затраты) Z, размещена в ячейке С19. Встроенная функция  СУММПРОИЗВ суммирует  произведения, полученные построчным  перемножением содержимого ячеек из диапазонов С3:F6; C13:F16.

Например, СУММПРОИЗВ (А1:В2;А3:B4) =A1*A3+B1*B3+A2*A4+B2*B4.

Установите курсор в ячейку С19, в которой должно быть выполнено значение целевой функции. Выполним команду Поиск решения из меню Сервис. В окне необходимо провести установки, показанные на рис.1.

В результате будет найдено решение, представленное в таблице 2.

	A	B	C	D	E		F		G
1		Матрица перевозок
2			Магазин 1	Магазин  2		Магазин  3		Магазин 4
3		Склад № 1	0	10		35		0	45
4		Склад № 2	30	70		0		0	100
5		Склад № 3	0	0		20		0	20
6		Склад № 4	0	0		40		35	75
7			30	80		95		35
8
9
10
11		bj	30	80		95		35
12	ai		Магазин 1	Магазин  2		Магазин  3		Магазин 4
13	45	Склад № 1	6	3		7		10
14	100	Склад № 2	10	4		12		10
15	20	Склад № 3	5	9		8		11
16	75	Склад № 4	4	2		4		8
17
18
19		Сумм. затраты:	1455

Искомые  объемы перевозок представлены в ячейках C3:F6. Со склада №1 мука будет отправлена в магазины №2 и 3 в объемах 10 и 35 мешков соответственно, со склада №2 – в магазины №1 и 2 в объемах 30 и 70 мешков, со склада №3 - в магазин №3 в объеме 20 мешков, со склада №4 в магазины №3 и 4 в объемах 40 и 35 мешков. Минимальные затраты на перевозки составляют 1455 денежных единиц.

Литература:

Информатика и ИКТ. Профильный уровень:  учебник для 11 класса. / И.Г. Семакин,Е.,К.Хеннер, Л.В.Шестакова.— М.: БИНОМ, Лаборатория знаний, 2012. — 330 с.