Мат_модели

z(X ) = 70 11+10 5 +50 4 +120 5 + 60 7 +90 10 = 2940.

тавшиеся запасы второго поставщика (120 единиц) записываем третьему потребителю. Имеем промежуточную таблицу

	B1	B2	B3	B4		ai
A1	11	5	4		2	80
	70	10
A2	1	4	5		9	170
		50	120
A3	9	8	7		10	150
bj	70	60	180	90		400

Потребности третьего потребителя окончательно удовлетворяем за счет поставщика A3 и вписываем в клетку A3 B3 перевозку 60 . Естественным завершением построения начального плана задачи с правильным балан-

сом является то, что как потребности последнего потребителя B4 ,									так и
(оставшиеся) запасы поставщика A3					равны		90 , поэтому в клетку		A3 B4
вписываем перевозку 90 . Получаем таблицу
	B1	B2	B3		B4		ai
A1	11	5	4			2	80
	70	10
A2	1	4	5			9	170
		50	120
A3	9	8	7			10	150
			60	90
bj	70	60	180		90		400
			70		10	0	0
с начальным опорным планом X =				0	50	120	0 и суммарная стоимость
				0	0	60
							90

перевозок равна Из решения видно, что метод северо-западного угла, с одной сто-

роны, достаточно прост с точки зрения построения, а с другой стороны, не учитывает стоимость перевозок. Поэтому опорный план, построенный методом северо-западного угла, как правило, далек от оптимального.

60

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

		B1		B2			B3			B4			ai
A1			11		5			4	2			80
A2			1		4			5	9			170
A3			9		8			7	10			150
bj		70		60		180			90			400
выбираем		клетку		с минимальным тарифом,							т.е. клетку			A2 B1 с тарифом 1.
Запасы поставщика A2					равны 170 , а потребности В1 – 70, поэтому в клет-
ку A2 B1	вписываем максимально возможную перевозку 70 , и потребителя
В1 исключаем из рассмотрения.								Получаем
		B1		B2			B3			B4			ai
A1			11		5			4		2			80
A2		70	1		4			5		9			170
A3			9		8			7		10			150
bj		70		60			180			90			400

и в оставшейся части таблицы выбираем минимальный тариф, т.е. клетку A1B4 с тарифом 2 . Запасы поставщика A1 равны 80 , а потребности В4

равны 90,		поэтому в клетку A2 B1				записываем перевозку 80 и поставщика
A1 исключаем из рассмотрения. Получаем таблицу
		B1	B2		B3		B4		ai
A1		11		5		4	80	2	80
A2		1		4		5		9	170
	70
A3		9		8		7		10	150
bj		70	60		180		90		400

61

В оставшейся части таблицы (вторая и третья строки; второй, третий и четвертый столбцы) выбираем минимальный тариф, т.е. клетку A2 B2 с

тарифом 4 . Запасы (оставшиеся) поставщика A2 равны 100 , а потребно-

сти В2 – 60, поэтому в клетку A2 B2 записываем максимально возможную

перевозку		60 и исключаем второго потребителя из дальнейшего рас-
смотрения. Заметим, что у поставщика								A2 осталось 40 единиц груза, а
потребности В3			равны 180 , поэтому вписываем в клетку A2 B3										перевозку
40 и получаем таблицу
		B1		B2	B3		B4			ai
A1		11		5		4	80	2		80
A2		1		4		5		9	170
	70			60	40
A3		9		8		7		10	150
bj		70		60	180		90		400
Из оставшихся двух клеток A3 B3 и A3 B4 минимальный тариф 7 имеет
клетка A3 B3 . Поэтому вписываем туда перевозку 140 и в клетку A3 B4 – 10 ,
получаем окончательную таблицу
		B1		B2	B3		B4			ai
A1		11		5		4	80	2		80
A2		1		4		5		9	170
	70			60	40
A3		9		8	140	7	10	10	150
bj		70		60	180		90		400
							0	0	0	80
с начальным опорным планом						X = 70		60	40	0 ,		и суммарная стои-
							0	0 140 10
мость					перевозок								равна
z( X ) = 80 2 + 70 1 + 60 4 + 40 5 +140 7 +10 10 =1750 < 2970.												Таким	образом,
начальный план, построенный с помощью									метода минимального тари-

62

фа, оказался гораздо эффективнее, чем план, построенный по методу северо-западного угла.

Пример 3. Применим теперь к исходной задаче метод аппроксимации Фогеля. Для этого найдем разность между двумя минимальными тарифами для каждой строки и столбца таблицы и запишем их в дополнительно образованные строки и столбцы

		B1	B2		B3		B4		ai		Разности по строкам
A1		11		5		4	80	2	80	2		2	–	–	–		–
A2	70	1	60	4	40	5		9	170	3		1	1	4	–		–
A3		9		8	140	7		10	150	1		1	1	3	3		0
bj		70	60		180		90		400
		8	1		1		7
Разности		–	1		1		7
		–	4		2		1
по
столб-		–	–		2		1
цам
		–	–		0		0
		–	–		–		0
									а следующий за ним 4, поэтому
В строке A1		минимальный тариф равен 2,
разность между ними 4 − 2 = 2 ;						в строке A2 минимальный тариф равен 1,

а следующий за ним 4, поэтому разность между ними 4 −1 = 3 ; аналогично, для строки A3 разность между минимальным тарифом 7 и следую-

щим за ним 8 равна 1. Итак, числа 2, 3 и 1 записываем в первый дополнительный столбец. Аналогично для столбцов разности 9 −1 = 8 , 5 − 4 =1 (два раза) и 9 − 2 = 7 записываем в первую дополнительную строку. Теперь из всех разностей выбираем максимальную, т.е. 8 в столбце B1 , и в клетку A2 B1 с минимальным тарифом в этом столбце записываем макси-

мально возможную перевозку 70 , а потребителя В1 исключаем из рас-

смотрения. Теперь аналогично вычисляем разности между оставшимися

63

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

ная разность получается в столбце B4 и перевозку 80 записываем в клет-

ку A1B4 с минимальным тарифом 2 в этом столбце. Строку A1 при этом исключаем из рассмотрения. Как видно из таблицы, на следующем шаге вписываем перевозку 60 в клетку A2 B2 и исключаем столбец B2 , затем – максимально возможную перевозку 40 в клетку A2 B3 и исключаем из рас-

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

тается единственная строка A3 , поэтому в качестве разностей по столб-

цам записываем нули. Далее, в клетку A3B3 записываем 140, а на послед-

нем шаге записываем перевозку 10 в			клетку		A3B4 . Получаем таблицу с
	0		0	0	80
начальным опорным планом		70	60	40	0		, который уже был по-
	X =
		0	0	140	10

лучен методом минимального тарифа. Отметим, что методом Фогеля обычно получается план, близкий к оптимальному, или сам оптимальный план.

Замечание. В общем случае опорный план транспортной задачи состоит из m +n −1 занятой клетки (по числу базисных переменных). Такой план называется невырожденным. Нередко при решении транспортной задачи возникает вырожденный план с меньшим числом занятых клеток (когда какие-то из базисных переменных равны 0 ). В этом случае выбирается свободная клетка (или несколько свободных клеток – в зависимости от вырожденности плана) с наименьшим тарифом, которая в дальнейшем формально считается занятой с нулевой перевозкой.

64

Задачи для самостоятельного решения

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

		B1	B2	B3		B4		ai
	A1	8	6	9	2			160
66.	A2	7	16	12	12			60
	A3	6	15	8	3			180
	bj	80	60	60	200
		B1	B2	B3		B4		ai
	A1	10	10	4	8		90
68.	A2	14	25	13	23		60
	A3	12	13	6	12		140
	bj	80	40	90	80
		B1	B2	B3		B4		ai
	A1	12	5	8		6		70
70.	A2	12	17	13		17		60
	A3	10	18	10		14		140
	bj	90	50	100		30
		B1	B2	B3		B4		ai
	A1	5	9	14	10		120
72.	A2	20	15	20	20		140
	A3	12	8	14	17		70
	bj	80	90	70	90

		B1		B2		B3			B4			ai
	A1	4		4		8		6			80
67.	A2	11		15		24		18			50
	A3	11		22		15		14			180
	bj	100		10		40		160
		B1		B2		B3			B4			ai
	A1	6		10		8		8			160
69.	A2	11		29		14		18			80
	A3	11		26		16		25			70
	bj	100		70		30		110
		B1		B2		B3		B4			ai
	A1	4		14		11		18			30
71.	A2	3		17		1		10			130
	A3	9		16		11		18			120
	bj	50		70		30		160
		B1		B2		B3			B4			ai
	A1	14		9		12			4			150
73.	A2	12		15		19			16			70
	A3	15		19		15			12			210
	bj	140		50		100			160

§3. Метод потенциалов решения транспортной задачи

Вторым этапом решения транспортной задачи является проверка построенного плана на оптимальность и его улучшение (если он не оптимален). Эту задачу мы будем решать с помощью метода потенциалов. Применение метода потенциалов основано на следующей теореме

65

ui +v j ≤ cij

Теорема. Если опорный план X =			xij		транспортной задачи явля-
ется оптимальным,	то существуют				потенциалы поставщиков
ui , i =1,K, m и потребителей v j , j =1,K, n , удовлетворяющие условиям:
	ui +v j = cij при xij			> 0 ,
	ui +v j ≤ cij при xij			= 0 .
Равенства ui +v j	= cij для занятых клеток образуют систему с m+n

неизвестными ui и v j , а число уравнений этой системы равно m +n −1 (по числу занятых клеток невырожденного опорного плана). Так как число неизвестных системы на единицу больше числа уравнений, то одну из неизвестных можно задать произвольно, а остальные найти из системы.

Неравенства для свободных клеток используются для

проверки оптимальности опорного решения. Введем числа

ij = ui +v j −cij ,

которые называются оценками свободных клеток. Таким образом, со-

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

Проверим теперь оптимальность планов, построенных выше. Пример 4. Сначала рассмотрим начальный опорный план, постро-

енный методом минимального тарифа и методом Фогеля. Образуем у таблицы по одному дополнительному столбцу и строке, куда будем записывать потенциалы:

	B1	B2	B3	B4		ai	ui
A1	11	5	4	80	2	80	0
A2	1	4	5		9	170
	70	60	40
A3	9	8	7		10	150
			140	10
bj	70	60	180	90		400
v j

66

Так как одну из неизвестных можно задать произвольно, то, как правило, будем выбирать u1 = 0 . Далее, поскольку для первой строки определен потенциал u1 , находим потенциалы v j для ее занятых клеток по формуле

v j	= c1 j −u1 . В первой строке всего одна занятая клетка A1B4 , поэтому
v4	= 2 . В столбце B4 , помимо уже использованной, есть еще одна занятая

клетка A3 B4 , а так как тариф с34 =10 , то условие u3 +v4 = c34 u3 +2 =10 да-

ет u3 =8 .	Далее, переходя к клетке A3 B3 ,	получаем: u3 +v3 = c33 8 +v3 = 7 и
v3 = −1, а	из клетки A2 B3 следует, что	u2 +v3 = c23 u2 −1 = 5 , т.е. u2 = 6 .

Дальнейшие вычисления будем записывать более сокращенно:

A2 B1 u2 +v1 = c21 6 +v1 =1 v1 = −5 ;

A2 B2 u2 +v2 = c22 6 +v2 = 4 v2 = −2 .

Все потенциалы найдены. Теперь находим оценки для свободных клеток

11 = u1 +v1 −c11 = −16 < 0 ,	12 = u1 +v2 −c12 = −7 < 0,	13 = u1 +v3 −c13 = −5 < 0,
24 = u2 +v4 −c24 = −1 < 0,	31 = u3 +v1 −c31 = −6 < 0,	32 = u3 +v2 −c32 = −2 < 0.

Результат записываем в таблицу (где в свободных клетках в квадратике записаны оценки)

		B1				B2			B3			B4			ai			ui
A1		11				5			4			2			80			0
		−16				−7			−5			80
A2		70		1		60	4		40	5		9			170			6
												−1
A3		9				8			7				10		150			8
		−6				−2			140			10
bj		70				60			180			90			400
v j		−5				−2			−1			2
															0			0	0		80
Все оценки отрицательны, поэтому план															X =		70	60	40		0 оптима-
																	0	0	140
																					10

лен и zmin = z(X ) =1750.

Пример 5. Теперь проверим на оптимальность план перевозок, полученный методом северо-западного угла. Ясно, что в силу большей

67

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

	B1			B2			B3		B4	ai
A1	70	11	10			5	4		2	80
A2		1				4	5		9	170
			50				120
A3		9				8	7		10	150
							60		90
bj	70		60				180		90	400
полагаем	, что u1 =		0 , а далее				находим	последовательно
A1B1 u1 +v1 = c11 0 +v1 =11 v1 =11,
A1B2 u1 +v2 = c12 0 +v2 = 5 v2 = 5,
A2 B1 u2 +v2 = c22 u2 +5 = 4 u2 = −1,
A2 B3 u2 +v3 = c23 −1+v3 = 5 v3 = 6,
A3 B3 u3 +v3 = c33 u3 +6 = 7 u3 =1,
A3 B4 u3 +v4 = c34 1+v4 =10 v4 = 9.
Получаем также оценки для свободных клеток
13 = u1 +v3 −c13 = 2 > 0 ,							14 = u1 +v4 −c14 = 7 > 0,				21 = u2 +v1 −c21 = 9 > 0,
24 = u2 +v4 −c24 = −1 < 0,						31 = u3 +v1 −c31 = 3 > 0,				32 = u3 +v2 −c32 = −2 < 0.
Все результаты записываем в таблицу
	B1			B2			B3		B4	ai	ui
A1	70	11	10			5	4		2	80	0
							2		7
A2		1				4	5		9	170	−1
	9		50				120		−1
A3		9				8	7		10	150	1
	3			−2			60		90
bj	70		60				180		90	400
v j	11		5				6		9

68

Как видим, среди оценок есть положительные, поэтому опорный план

70		10	0	0
X =	0	50	120	0	не оптимален.
	0	0	60	90

Чтобы улучшить допустимое решение X транспортной задачи, нам потребуется понятие цикла. Напомним, что циклом называется последовательность клеток таблицы транспортной задачи, в которой две и только две соседние клетки расположены в одной строке или столбце. Цикл обычно изображают в виде замкнутой ломаной линии, соединяющей вершины цикла, расположенные в клетках таблицы.

Для построения нового опорного плана в таблице выбираем сво-

бодную клетку с максимальной положительной оценкой (клетка A2 B1 ) и

формируем цикл, одной из вершин которого является выбранная клетка, а остальные клетки занятые. Легко видеть, что это цикл, соединяющий клетки A1B1 , A1B2 , A2 B2 и A2 B1 . Кроме этого, сопоставим каждой верши-

не цикла знак и перевозку, при этом свободной клетке сопоставляем знак « + », а для остальных клеток знаки чередуются. Получим следующий цикл:

	70			10
		–	+
		+	–	50

Теперь сделаем перестановку по циклу, а именно: из всех вершин, отмеченных минусом, вычтем минимум из всех перевозок, означенных этим знаком, т.е. вычитаем = min(50,70) = 50 , а ко всем вершинам с « + »

прибавим .

Замечание. Если при нахождении плана минимум достигается в нескольких клетках, помеченным знаком «–», то одна из клеток становится свободной, а остальные считаются занятыми с нулевыми перевозками, так чтобы число занятых клеток оставалось равным m +n −1 .

69