Математическая экономика

			υ =1,																				υ				= 0,
		1																				3
			υ2		= 2,																		υ4				= 4,
			u2 =1;
																							u3 = 0.
Эти значения для удобства внесены в дополнительный столбец и до-
полнительную строку табл. 3.5.
Затем рассматриваем свободные																								клетки						и	находим для них
~
cij =ui +υj , сравнивая эти значения с cij :
																												Т а б л и ц а 3.5
	ПН	B1				B2											B3								B4				Запасы			ui
	ПО																													ai
			1		-					2									4									1
	A1																							+						50		0
		30
						20
	A2		2							3									1									5		25		1
																											-
				+ 10										10								5
	A3		3							2									4									4		15		0
																						15
	Заявки	30			30									10								20								90
	bj
	υi	1			2									0								4

~	= 0 < c13 = 4 ;	~	= 4 > c14 =1;
c13		c14
~	= 2 = c21 ;	~	=1 < c13 = 3;
c21		c31

~	= 2 = c32 ;	~	= 0 < c33	= 4 .
c32		c33
				~	имеется	~	> c14 , то
Так как среди найденных псевдостоимостей cij						c14

план, соответствующий табл. 3.5, не является оптимальным.

Используя свободную клетку (1, 4), формируем цикл, представленный в табл. 3.5. Его цена равна

α = +1−5 +3 − 2 = −3.

Величина продукта (груза), который следует перераспределить по этому циклу,

γ = min{5; 20} =5.

71

В результате такого перераспределения получаем новый план, представленный в табл. 3.6. Общая стоимость перевозок по этому плану составляет 180 у.е. Этот результат на αγ =15 у.е. лучше, чем стоимость, соответствующая плану из табл. 3.5.

Т а б л и ц а 3.6

ПН		B1				B2											B3											B4					Запасы	ui
ПО																																	ai
				-						2
A1			1										0							4					1 +							1	50	0
	30					15																			5
A2			2							3										1					2							5	25	1
						15										10
A3	4		3	5						2					3					4												4	15	3
				+																					15 -
Заявки		30		30												10									20								90
bj
υi		1		2												0									1

Для базисных клеток этой таблицы составляем систему уравнений:

u + υ =1,				u	2	+ υ		2	=3,
1		1							=1,
u1	+ υ2 = 2,			u2		+ υ3
u1 + υ4 =1;
				u3 + υ4 = 4.
Из системы находим:
	u1 = 0,				u	2	=1,
	υ =1,
	1				υ3 = 0,
	υ2
		= 2,
	υ4	=1;			u3 =3.

Получаемые по этим значениям псевдостоимости c~ij проставлены в табл. 3.6 в левом верхнем углу свободных клеток. Сравнивая их с cij , видим, что в двух клетках (3, 1) и (3, 2) получается c~ij > cij .

Примем за основу клетку (3, 2) и для нее сформируем цикл, представленный в табл. 3.6.

Заметим, что его цена α = +2 −2 +1− 4 = −3 совпадает с разницей c~ij −cij = 5 −2 = 3. По этому циклу следует перераспределить 15 ед. про-

дукта. В результате получаем табл. 3.7. 72

																		Т а б л и ц а 3.7
	ПН			B			B		B					B					Запасы		u
	ПО			1			2		3							4			a			i
																			i
	A1		30		1		0	2	0		4	20					1		50		0
	A2		2		2		15	3	10		1	2					5		25		1
	A3		1		3		15	2	0		4	1					4		15		0
	Заявки			30			30		10						20				90
	bj
	υi			1			2		0						1
Для этой таблицы составляем уравнения:
	u + υ =1,											u	2			+ υ		2	=3,
1		1		= 2,
	u1	+ υ2										u2				+ υ3			=1,
	u1 + υ4 =1;
												u3 + υ2 = 2.
Откуда получаем:
			u1 = 0,									u		2		=1,
			υ =1,
		1										υ3 = 0,
			υ2
				= 2,								u3 = 0.
			υ4	=1;
																			~	≤ cij , значит соот-
Во всех клетках табл. 3.7 выполняется условие cij

ветствующий ей план перевозок является оптимальным.

Для него общая стоимость перевозок y=ymin = 30 + 20 + 45 + 10 + 30 = = 135 [у.е.].

Замечание 1. В процессе решения ТЗ может возникнуть ситуация, когда при перераспределении перевозок по циклу не одна, а две или более базисных переменных обратятся в нуль. В рассмотренном примере такая ситуация возникает на последнем этапе. Данное решение называется вырожденным. Однако вырожденность не требует никаких специальных мер, в соответствующей базисной (вырожденной) клетке следует проставить 0 в отличие от свободных клеток, где x = 0 , но по принятым правилам нулевое значение x не проставляется. С нулевыми базисными переменными оперируют точно так же, как и с переменными, имеющими положительное значение [3, 32].

73

Замечание 2. Если в исходных данных все ai и bj целые, то в иско-

мом оптимальном решении все переменные тоже будут целыми [3].

§3.5. Неклассические транспортные задачи

Врассмотренной выше формулировке ТЗ предполагается, что во всех ПО сосредоточен однотипный продукт, в котором нуждаются ПН. Из каждого ПО груз перевозится непосредственно в ПН. Суммарные запасы продукта в ПО совпадают с суммарными заявками в ПН. В реальных условиях каждое из этих предположений может не выполняться. Рассмотрим особенности ТЗ в подобных случаях и приемы, позволяющие решать такие задачи.

Несбалансированная транспортная задача

В классической формулировке (3.1 – 3.4) содержалось важное условие (3.4) – предполагалось, что суммарные запасы продукта в ПО совпадают с суммарными заявками в ПН. Однако этот баланс может не выполняться. Получающаяся ТЗ называется несбалансированной [32], ТЗ с неправильным балансом [6] или открытой ТЗ [14].

Рассмотрим ТЗ с избытком запасов, т.е. задачу, в которой

m

∑ai

i=1

n

> ∑bj .

j=1

В этом случае вместо ТЗ (3.1 – 3.4) получаем следующую задачу. Найти xij ≥ 0 , при которых

	m	n
	y = ∑∑cij xij → inf ,
	i=1 j=1
	n
	∑ xij ≤ ai	(i =1,..., m),
	j=1
	m
	∑xij =bj
		( j =1,...,n).
	i=1

74

Такую задачу можно свести к классической сбалансированной ТЗ, а затем решать рассмотренными выше методами, если ввести еще один дополнительный, фиктивный пункт назначения B* , которому будет приписана фиктивная заявка

m	n
b* = ∑ai −∑bj .
i=1	j=1

При этом удельные стоимости перевозок из всех ПО в фиктивный ПН полагаются равными нулю [6, 32].

Следует отметить, что при решении такой модифицированной задачи для каждого ПО Ai будет получаться некоторая величина xi* , которая должна быть отправлена в фиктивный ПН B* . Однако в действительности это будет означать, что такое количество груза xi* будет оставаться в Ai неотправленным.

Пример несбалансированной ТЗ с избытком запасов дан в табл. 3.8 [6].

Т а б л и ц а 3.8

									Благодаря введению фик-
ПН	B		B		B		Запасы
									тивного ПН B	*	с заявкой в 38 еди-
ПО	1		2		3		ai
A1		5		7		6	50		ниц эта задача сведена к сбаланси-
									рованной (табл. 3.9). Процесс ее
A2		6		6		5	40		решения представлен в табл. 3.9 –
									3.12. Финальную таблицу, соот-
		8		4		5
A3							20		ветствующую оптимальному пла-
									ну, нужно интерпретировать сле-
Заявки								110
	18		21		33				дующим образом:
bj							72
									− из 50 ед. груза, имеющихся
в ПО A1 , 18 ед. направляются в ПН B1 , а 32 ед. остаются в A1 и не перево-

зятся;

−из 40 ед. груза, имеющихся в ПО A2 , 1 ед. груза направляется в ПНB2 , 33 ед. – в ПН B3 , а 6 ед. остаются не вывезенными;

−все 20 ед. груза, имеющихся в ПО A3 , направляются в ПН B2 .

75

Т а б л и ц а 3.9

Т а б л и ц а 3.10

ПН	B1		B2		B3									Bф			Запасы	Платежи
ПО																	a	u
																	i	i
A1	5	5	7	7	6				6			1				0	50	0
					-							+
	18		21		11
A2	4	6	6	6	5				5				0		-	0	40	-1
					22+
													18
A3	4	8	6	4	5				5			0				0	20	-1
												20
Заявки	18		21		33							38					110
bj
Платежи	5		7		6							1
υi

ПН	B1		B2		B3		Bф			Запасы	Платежи
ПО										a	u
										i	i
A1	5	5	7	7	5	6	0		0	50	0
	18		21-				11+
A2	5	6	7	6	5	5	0		0	40	0
					33		7
A3	5	8	7	4	5	5	0		0	20	0
			+				20	-
Заявки	18		21		33		38			110
bj
Платежи	5		7		5			0
υi

Т а б л и ц а 3.11

Т а б л и ц а 3.12

ПН	B1		B2		B3			Bф			Запасы	Платежи
ПО											a	u
											i	i
A1	5	5	7	7	5	6	0			0	50	0
			1-
	18						31 +
A2	5	6	7	6	5	5	0			0	40	0
			+		33		7	-
A3	2	8	4	4	2	5	-3			0	20	-3
			20
Заявки	18		21		33			38			110
bj
Платежи	5		7		5			0
υi

ПН	B1		B2		B3		Bф		Запасы	Платежи
ПО									a	u
									i	i
A	5	5	6	7	5	6	0	0	50	0
1	18						32
A2	5	6	6	6	5	5	0	0	40	0
			1		33		6
A3	3	8	4	4	3	5	-2	0	20	-2
			20
Заявки	18		21		33		38		110
bj
Платежи	5		6		5		0
υi

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

n

∑bj

j=1

m

> ∑ai .

i=1

Втакой ТЗ имеющихся в ПО запасов недостаточно для удовлетворения всех заявок в ПН. Следуя [6], можно указать два подхода к решению такой задачи.

Впервом случае при решении задачи исходят из того, что нужно вывести из ПО все имеющиеся там запасы и минимизировать общую стои-

76

мость перевозок, не заботясь о том, в какой мере заявки различных ПН окажутся удовлетворенными. В этом случае для решения задачи вводят фиктивный ПО A* с запасом:

n	m
a* = ∑bj −∑ai ,
j=1	i=1

а стоимости перевозок из A* в каждый ПН полагают равными нулю.

Во втором случае несбалансированную исходную задачу сводят к сбалансированной ТЗ, корректируя заявки ПН. Можно, например, следуя [6], умножить каждую заявку на один и тот же коэффициент:

m	n
K = ∑ai / ∑bi .
i=1	j=1

В этом случае потребности каждого ПН будут удовлетворяться в равной доле.

Можно исправлять заявки по-разному в зависимости от важности того или иного ПН. В каждом из указанных выше случаев исходная задача сводится к сбалансированной ТЗ, а затем решается изложенными выше методами.

Многопродуктовая ТЗ

Рассмотрим ситуацию, когда в пунктах отправления Ai сосредоточены различные виды продукции и каждый пункт назначения Bj нуждается

в своем ассортименте продукции. Пусть, например, имеется четыре вида продукции P1,..., P4 , которые выпускаются на трех заводах (ПО) A1, A2 , A3 , и необходимо развести эту продукцию в два магазина (ПН) B1 и B2 [14, 32].

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

Удельные затраты на перевозки единицы продукции (1 шт., 1 т и т.п.) представлены в табл. 3.14. Предполагается, что от вида продукции они не зависят.

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

77

		Т а б л и ц а 3.13
ПН		Виды продукции
ПО	P1	P2	P3	P4
Заводы
A1	-	-	70	30
A2	50	60	-	40
A3	80	40	-	-
Магазины
B1	70	50	50	60
B2	60	50	20	10

Т а б л и ц а 3.14

ПН	B	B
ПО	1	2
A1	8	21
A2	10	12
A3	11	7

Эту задачу можно свести к классической (однопродуктовой) задаче двумя способами.

Можно каждый ПО (завод) рассматривать условно как несколько заводов, выпускающих один вид продукции. Соответственно каждый ПН (магазин) будем заменять на несколько ПН, нуждающихся в одном виде продукции. В результате получим транспортную таблицу, которую называют полной [32] (табл. 3.15).

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

									Т а б л и ц а 3.15
	ПО	ПН		B1				B2	Запасы
		P1	P2	P3	P4	P1	P2	P3
									P4
	A1	P3							70
		P4							30

		P1										50
A2		P										60
	2
		P4											40
A3		P1										80
		P2										40
Заявки			70	50	50	60	60	50	20	10

78

Однако многопродуктовую задачу необязательно описывать одной моделью (полной таблицей). Можно рассмотреть задачу об организации поставок по каждому виду продукции в отдельности. В этом случае для анализируемого примера вместо одной полной таблицы нужно будет использовать четыре частные таблицы (табл. 3.16 – 3.19).

		Т а б л и ц а 3.16					Т а б л и ц а 3.17
	Продукция P1						Продукция P2
ПН	B		B			ПН	B	B
ПО	1		2			ПО	1	2
A2				50		A2			60
A3				80		A3			40
	70		60				50	50

Т а б л и ц а 3.18 Продукция P3

	ПН	B	B
ПО		1	2
A1				70
		50	20

		Т а б л и ц а 3.19
	Продукция P4
ПН	B		B
ПО	1		2
A1				30
A2				40
	60		10

Изложенные приемы позволяют многопродуктовую задачу свести к одной (для полной таблицы) или нескольким (по каждому виду продукции) задачам классического типа, к которым можно применять рассмотренные в § 3.2 – 3.4 методы решения.

ТЗ с промежуточными пунктами

В классической транспортной задаче предполагается, что продукция из ПО Ai по прямому маршруту отправляется в выбранный ПН B j . На

практике может оказаться целесообразной перевозка продукции (полно-

79

стью или частично) транзитом через другие ПО или ПН. Например, чтобы удовлетворить заявку ПН B4 в размере b4 груз отправляется из A2 сначала в A5 , там он объединяется с имеющимся запасом a5 и потом объединенный груз отправляется в ПН B4 . Аналогично товар может быть отправлен сначала в один из ПН, а затем передан в другой ПН.

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

Следуя [32], в этих случаях ПН нужно рассматривать как возможные ПО, поэтому в формируемой для решения транспортной таблице нужно список ПО дополнить списком ПН и наоборот. Подробнее см. в [32].

ТЗ с минимизацией времени перевозок

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

В этом случае для каждой пары ( Ai , B j ) задается время tij , за кото-

рое можно осуществить соответствующую перевозку. Предполагается, что оно не зависит от количества перевозимого груза xij . При этом в модели

ТЗ (3.1 – 3.4) критерий оптимальности (3.1) следует заменить на условия

T = max t	ij	→ inf .	(3.6)
x >0
ij

Этот критерий представляет собой максимальное время из всех клеток транспортной таблицы, содержащих ненулевые перевозки. Сами величины перевозок назначаются так, чтобы удовлетворить все заявки и исчерпать все ресурсы (3.2 – 3.3).

Следует отметить, что величина T , определяемая соотношением (3.6), не является линейной функцией перевозок xij , поэтому рассматри-

ваемая задача не является задачей линейного программирования. Методики и примеры решения такой задачи см. в [6, 14].

80