Тема 3. Транспортная задача

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

Пусть имеется n пунктов отправки, запасы грузов в которых равны аi, i=1…n; их следует доставить в m пунктов назначения, потребности которых в грузах равны bj , j=1…m. Стоимость перевозки 1 т груза из i-го пункта отправления в j-й пункт назначения задается матрицей C=(cij).

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

Xij – исходно неизвестное количество груза, которое перевозится из пункта i в пункт j. Непосредственно из условий задачи получаем следующую математическую модель данной задачи:

n m
Z =∑ ∑ cij x ij → min.	(1)
i=1 j=1
m
∑ X ij = ai, i=1,2,…,n	(1.1)
j =1
n
∑ X ij =bj, j=1,2,…,m	(1.2)
i =1
xij ≥0 , i = 1,2,…, n; j = 1,2,…,m	(1.3)

Целевая функция (1) минимизирует совокупные затраты на транспортировку всех партий грузов из всех пунктов отправления во все пункты назначения. Система ограничений (1.1) говорит о том, что весь груз из каждого пункта отправления должен быть вывезен. Система ограничений (1.2) свидетельствует о том, что потребность в грузе в каждом пункте назначения должна быть удовлетворена. Система ограничений (1.3) говорит о том, что по любому маршруту либо перевозится некоторое количество груза, либо нет.

Таким образом, транспортная задача является задачей линейного программирования с (n + m) ограничениями-уравнениями и (n + m) неизвестными.

Постановка транспортной задачи в форме: все грузы вывезены и все потребности удовлетворены − возможна лишь тогда, когда суммарное наличие груза А совпадает с суммарной потребностью B, т.е. выполняется равенство:

n	m
А = ∑ a i = ∑bj = B j		(1.4)
i=1	j=1

Если A=B, то задача называется закрытой (сбалансированной, замкнутой). Если условие (1.4) не выполняется, то транспортная задача называется откры-

29

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

Если A < B, вводим фиктивный пункт отправки Aфn+1 и полагаем, что его запасы равны дисбалансу, т.е. an+1 = B – A. Тарифы перевозок от фиктивного поставщика ко всем потребителям полагаются равными 0, т.к. грузы в действительности не перевозятся. При записи ответа фиктивный поставщик не учитывается, а потребители, получающие грузы от фиктивного поставщика, в действительности не дополучают их.

Если A > B, вводим фиктивный пункт назначения Bфm+1 и полагаем, что его запасы равны дисбалансу, т.е. bm+1 = A – B. Тарифы перевозок из всех пунктов отправки в фиктивный пункт назначения полагаются равными 0, т.к. грузы в действительности не вывозятся. При записи ответа фиктивный пункт назначения не учитывается, поставщики, отправляющие грузы фиктивному потребителю в действительности не вывозят их.

Специфика транспортной задачи:

1.Целевая функция задается на минимум.

2.Все ограничения имеют форму точных равенств.

3.Каждая переменная входит ровно в два ограничения.

4.Если A = B, то транспортная задача всегда разрешима.

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

Алгоритм решения транспортной задачи:

I этап. Построение 1-ого опорного плана.

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

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

Условия транспортной задачи представлены в табл. 2.1.13.

	Транспортная таблица № 1				Таблица 2.1.13
ПН	В1 = 18	В2 = 27	В3 = 42	В4 = 12	В5 = 26
ПО
А1 = 48	10	8	5	6	9
А2 = 30	6	7	8	6	5
А3 = 27	8	7	10	8	7
А4 = 20	7	5	4	6	8

Будем заполнять транспортную таблицу№ 2 перевозками постепенно, начиная с левой верхней ячейки («северо-западного угла» таблицы). Пункт В1 подал заявку на 18 единиц груза. Удовлетворим эту заявку за счет запаса 48, имеюще-

30

гося в пункте А1, и запишем перевозку 18 в клетке (1,1). После этого заявка пункта В1 удовлетворена, а в пункте А1 осталось еще 30 единиц груза. Удовлетворим за счет них заявку пункта В2 (27 единиц), запишем 27 в клетке (1,2); оставшиеся 3 единицы пункта А1 назначим пункту В3. В составе заявки пункта В3 остались неудовлетворенными 39 единиц. Из них 30 покроем за счет пункта А2, чем его запас будет исчерпан, и еще 9 возьмем из пункта А3. Из оставшихся 18 единиц пункта А3 12 выделим пункту В4; оставшиеся 6 единиц назначим пункту В5, что вместе со всеми 20 единицами пункта А4 покроет его заявку. На этом распределение запасов закончено: каждый пункт назначения получил груз, согласно своей заявки. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце – заявке. Таким образом, нами сразу составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является опорным решением транспортной задачи (табл. 2.1.14).

		Транспортная таблица № 2				Таблица 2.1.14
	ПН	В1 = 18	В2 = 27 В3 = 42 В4 = 12 В5 = 26
ПО
А1	= 48	10	8	5	6	9
		18	27	3
А2	= 30	6	7	8	6	5
				30
А3	= 27	8	7	10	8	7
				9	12	6
А4	= 20	7	5	4	6	8
						20

Составленный нами план перевозок не является оптимальным по стоимости, так как при его построении мы совсем не учитывали стоимость перевозок − Сij .

Так, в нашем примере общие затраты на транспортировку по плану, составленному данным способом, таковы:

F0 = 10×18 + 8×27 + 5×3 + 8×30 + 9×10 + 8×12 + 7×6 + 8×20 = 1039.

Другой способ – способ минимальной стоимости по строке – основан на том, что мы распределяем продукцию из пункта Ai не в любой из пунктов Bj, а в тот, к которому стоимость перевозки минимальна. Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетов и находим минимальную стоимость перевозки из оставшихся пунктов Bj. Во всем остальном этот метод схож с методом северо-западного угла. В результате, опорный план, составленный способом минимальной стоимости по строке, выглядит так, как показано в транспортной таблице № 3 (табл. 2.1.15).

При этом методе может получиться, что стоимости перевозок Cij и Cik от пункта Ai к пунктам Bj и Bk равны. В этом случае, с экономической точки зрения, выгоднее распределить продукцию в тот пункт, в котором заявка больше. Так, например, в строке 2: C21 = C24, но заявка b1 больше заявки b4, поэтому 4 единицы продукции мы распределим в клетку (2,1).

31

						Таблица 2.1.15
		Транспортная таблица № 3
	ПН	В1 (18)	В2 (27)	В3 (42)	В4 (12)	В5 (26)
ПО
А1	(48)	10	8	5	6	9
				42	6
А2	(30)	6	7	8	6	5
		4				26
А3	(27)	8	7	10	8	7
			27		0
А4	(20)	7	5	4	6	8
		14			6

Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными, занятыми. Их число должно равняться m + n – 1. Необходимо отметить также, что встречаются такие ситуации, когда количество базисных клеток меньше чем (m + n – 1). В этом случае распределительная задача называется вырожденной. В одной из свободных клеток следует поставить количество перевозок, равное нулю. Так, например, в таблице 2.1.15:

m + n − 1 = 4 + 5 − 1 = 8,

а базисных клеток 7, поэтому нужно в одну из клеток строки 3 или столбца 2 поставить значение «0». Например, в клетку (3,5).

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

F0 ′= 1×47 + 6×4 + 27×7 + 42×5 + 6×6 +6×6 + 26×5 = 723.

II этап. Проверка опорного плана на оптимальность. Метод потенциалов. 1. Находим потенциалы строк Ui и потенциалы столбцов Vj по формуле:

Ui+ Vj = сij для занятых клеток, сij – тариф.

Количество потенциалов равно (m + n), а количество занятых клеток равно (m + n – 1). Т.е. однозначно потенциалы не находятся. Обычно полагают, что U1 = 0, тогда остальные потенциалы вычисляются однозначно.

2. Находим оценки свободных клеток.

ij = сij – (Ui + Vj)

Критерий оптимальности

Если все оценки свободных клеток ij ≥ 0, то опорный план является оптимальным, если при этом все ij > 0, то оптимальный план является единственным. В противном случае имеет место альтернативная оптимизация.

Если хотя бы одна из оценок ij < 0, то опорный план допускает улучшения. В нашем примере (табл. 2.1.16):

32

	Транспортная таблица № 4					Таблица 2.1.16
ПН	В1 (18)	В2 (27)	В3 (42)	В4 (12)	В5	(26)	Ui
ПО
А1 (48)	10	8	5	6		9	0
	3	2	42	6	3
А2 (30)	+ 6	7	8	6		5	-1
	4	2	4	1	-	26
А3 (27)	8	- 7	10	8	+	7	1
	0	27	4	1		0
А4 (20)	- 7	+ 5	4	6	2	8	0
	14	-1	-1	6
Vj	7	6	5	6		6
U1 + V3 = 5, U1 = 0, V3 = 5
U1 + V4 = 6, U1 = 0, V4 = 6
U4 + V4 = 6, V4 = 6, U4 = 0,
U4 + V1 = 7, U4 = 0, V1 = 7
U2 + V1 = 6, V1 = 7, U2 = -1,
U2 + V5 = 5, U2 = -1, V5 = 6
U3 + V5 = 7, V5 = 6, U3 = 1,
U3 + V2 = 7, U3 = 1, V5 = 6
Все потенциалы найдены. Находим оценки свободных клеток							ij:
11=10-(7+0)=3		12=8-(6+0)=2			15=9-(6+0)= 3
22=7-(6+(-1))=2		23=8-(5+(-1))=4			24=6-(6+(-1))=1
31=8-(7+1)=0		33=10-(5+1)=4			34=8-(6+1)=1
42=5-(6+0)=-1		43=4-(5+0)=-1			45=8-(6+0)=2
В транспортной таблице № 4 оценки стоят в клетке в нижнем левом углу.
Среди оценок есть отрицательные, следовательно, построенный план не является
оптимальным.
III этап. Построение нового базиса.

1.Среди свободных клеток с отрицательными оценками находим клетку с наименьшей оценкой и обозначаем ее « ».

2.Строим контур: замкнутый многогранник, одна вершина которого распо-

ложена в клетке « », остальные вершины в занятых клетках и все углы прямые. Существует несколько вариантов контура:

1)

2)

3)

не вершина

Контур всегда существует, причем единственный.

33

3.В вершинах контура расставляем поочередно знаки «+» и «–», начиная с «+» в вершине « ».

4.Среди занятых клеток, отмеченных знаком «−» находим ту, в которой располагается минимальный груз. На следующем этапе эта клетка станет свободной.

В нашем примере, в таблице № 4, клетку (4,1) обозначим « ». Строим замкнутый контур, расставляем знаки.

IV этап. Построение нового опорного плана.

Из всех клеток, отмеченных знаком «–», вычитаем минимальный груз, ко всем клеткам, отмеченным знаком «+», прибавляем его.

Полученный опорный план вновь проверяем на оптимальность, т.е. возвращаемся к этапу II. Если при построении нового базиса минимальный груз, отмеченный знаком «−», встречается в нескольких клетках, то на следующем этапе освобождаем только одну из них. Из остальных клеток вычитаем этот груз, получая нулевые значения, при этом клетки считаются занятыми, а переменные − базисными.

Внашем примере в таблице № 4 мы строим замкнутый контур и переходим

ктаблице № 5 (табл. 2.1.17), в которой будет новый опорный план.

	Транспортная таблица № 5						Таблица 2.1.17
ПН	В1 (18)	В2 (27)	В3 (42)	В4 (12)	В5 (26)		Ui
ПО
А1 (48)	10	8	5	6		9	0
	4	3	42	6	4
А2 (30)	6	7	8	6		5	0
	18	2	3	0	12
А3 (27)	8	7	10	8		7	2
	0	13	3	0	14
А4 (20)	7	5	4	6		8	0
	1	14	1	6	3
Vj	6	5	5	6	5

Т.к. в таблице № 5 нет отрицательных оценок, то построенный опорный план является оптимальным. Общие затраты на транспортировку по этому плану составят:

F1 = 18×6 + 42×5 + 6×6 + 12×5 + 13×7 + 14×7 + 14×5 + 6×6 = 709.

	0	0	42	6	0
		0	0	0	12
18
Хопт1 =	0	13	0	0	14
	0	14	0	6	0

Т.к. в таблице № 5 есть оценки, равные нулю, то существует альтернативный оптимум. Сделав перераспределение грузов относительно клетки, имеющей ij = 0, получим новое оптимальное решение, при этом значение целевой функции не изменится.

34

Произведемперераспределениегрузовотносительноклетки(3, 4) (табл. 2.1.18):
			Транспортная таблица № 5.1						Таблица 2.1.18
ПО	ПН	В1	(18)	В2 (27)	В3 (42)	В4 (12)	В5 (26)		Ui
А1 (48)			10	8	5	6		9	0
		4		3	42	6	4
А2 (30)			6	7	8	6		5	0
			18	2	3	0	12
А3 (27)			8	7	10	8		7	2
		0		7	3	6	14
А4 (20)			7	5	4	6		8	0
		1		20	1	0	3
Vj		6		5	5	6	5

Получили еще одно решение:

	0	0	42	6	0
	18	0	0	0	12
Х опт 2 =	0	7	0	6	14
	0	20	0	0	0

Вопросы для самоконтроля

1.Какие специфические свойства позволяют выделить транспортные задачи

вотдельный класс из множества задач ЛП?

2.Опишите метод построения исходного допустимого плана транспортной задачи.

3.Какая задача называется открытой, замкнутой?

4.Как свести открытую задачу к замкнутой?

5.Сформулируйте признак существования альтернативного оптимума.

Задачи

Задача 1. Для строительства 4-х дорог используется гравий из 3-х карьеров, запасы гравия в карьерах равны 30, 20, 50 т., потребности дорог в гравии − 20, 40, 30, 50 т. Стоимость перевозки 1т гравия задается матрицей С.

3		2	4	5
	5	4	7	3
С =
	6	3	2	6

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

35

Задача 2. На 3-х станках различных типов можно выполнить 3 операции по обработке деталей, при этом за каждым станком может быть закреплена лишь одна операция, каждая операция может выполняться только на одном станке, время выполнения i-ой операции на j-ом станке задается матрицей С.

5	7	9
	10	12
С = 14
	13	16
15

Требуется составить такое распределение операций между станками, при котором суммарные запасы времени будут минимальны. Какая операция на каком станке будет выполняться?

Задача 3. Найти оптимальный план перевозки топлива из 3-х хранилищ, в которых имеется 300, 150, 200 т топлива, на 5 автозаправочных станции, потребности которых составляют 80, 170, 180, 70 т. Если затраты на перевозку 1 т. топлива задаются матрицей С.

4		7	1	5	2
	6	2	4	1	3
С =
	5	6	7	4	8

Задача 4. Решить транспортную задачу, заданную следующей распределительной таблицей, причем перевозки от 2-го поставщика ко 2-му потребителю и от 3-го поставщика к 1-му потребителю временно закрыты. В таблице данных № 7 (табл. 2.1.19) эти тарифы обозначены большим числом М.

Таблица 2.1.19

	Таблица данных №7
ai	bj	1	2	3
		5	5	3
1	6	6	4	9
2	3	5	М	2
3	4	М	3	6

Задача 5. В трех пунктах производства имеется одинаковая продукция в объеме 200, 170, 130 т. Эта продукция должна быть доставлена потребителям в количестве 50, 220, 80, 110, 140 т. Стоимость перевозок единицы продукции от каждого поставщика к каждому потребителю заданы матрицей:

	2	10	8	15	5
	4	2	3	4	6
	7	3	12	2	3

В связи с неплатежеспособностью перевозки от 1-ого производителя до 1-ого потребителя и от 2-го производителя до 3-го потребителя закрыты. Составить оптимальный план перевозок, при котором суммарные затраты на них минимальны.

36