Navch._posibnuk_Ivaschyk

Постачальники	Споживачі		B1	B2	B3
	Потреби		110	155	ui
	Запаси				140
			3	6	2
A1
		90			u1=0
					90
A2			1	5	7
		85	85		u2=–2
A3			9	7	8
		125		75	u3=6
					50
A4			4	3	5
		105	25	80	u4=2
	vj		v1=2	v2=1	v3=2
Обчислюємо значення всіх потенціалів. І оскільки для всіх
небазисних клітинок цієї таблиці виконуються нерівності ui+vj ≤сij, то
це означає, що ми отримали оптимальний план перевезення вантажу:

			0	0	90
			85	0	0
x	=						.
опт.			0	75	50
			25	80	0

Мінімальна вартість перевезення вантажу:

Zmin=2·90+1·85+7·75+8·50+4·25+2·80=1530 грошових одиниць. ♦

Ми використали обидва методи знаходження початкового опорного плану транспортної задачі і бачимо, що найбільш ефективним є метод найменшої вартості, тому що він вже на першому кроці (при заповненні початкової таблиці) дає значно краще значення цільової функції транспортної задачі (меншу вартість перевезення всього вантажу від постачальників до споживачів), ніж діагональний метод. Крім того, для знаходження оптимального плану перевезення вантажу робимо меншу кількість циклів перерахунку (один) в прикладі 4.4, де використовували метод найменшої вартості, ніж в прикладі 4.3, де застосовували діагональний метод і циклів перерахунку було чотири. Тому рекомендуємо при знаходженні

151

початкового опорного плану транспортної задачі використовувати метод найменшої вартості.

4.4. Відкрита транспортна задача

Відомо, що транспортна задача, для якої сума запасів постачальників не дорівнює сумі потреб споживачів, тобто

m	n
∑ai ≠ ∑bj , називається відкритою. Якщо під час розв’язання
i=1	j=1

транспортної задачі з’ясувалося, що транспортна задача відкрита, то її необхідно звести до закритого типу, оскільки ми можемо знайти оптимальний план тільки транспортної задачі закритого типу. У разі перевищення попиту над запасами, вводимо фіктивного

n	m
постачальника Аф=Аm+1 з запасом am+1 = ∑bj	− ∑ai ,	якщо ж запаси
j=1	i=1
постачальників перевищують потреби споживачів, то			вводимо
	m	n
фіктивного споживача Вф=Вn+1 з потребою bn+1 = ∑ai		− ∑bj	. Вартість
	i=1	j=1

перевезення одиниці продукції від фіктивного постачальника чи до фіктивного споживача вважається рівною нулю, оскільки насправді цей вантаж перевозитись не буде і це не вплине на значення цільової функції.

Слід звернути увагу на те, що при побудові початкового опорного плану транспортної задачі методом найменшої вартості клітинки з нульовими вартостями перевезення одиниці вантажу потрібно заповнювати в останню чергу.

Приклад 4.5. Знайти оптимальний план транспортної задачі,

якщо: ai =( 60;	85; 30;	45 );				bj =(115; 85;			40 );
				7	4	6
				6	2	3
	c	=						.
	ij			4	5	1
					3	8
♦ Розв’язування.			11
Перевіримо, чи транспортна задача є закритою.
4	= 60 +85 +30 + 40							3	+85 + 40 = 240.
Обчислимо: ∑ai					=	220; ∑bi =115
i =1								j =1

152

m	n
Оскільки ∑ai ≠ ∑bj , то задача відкрита. Приведемо її до закритого
i=1	j=1
типу. Враховуючи те, що потреби перевищують запаси, то вводимо
							n	m
фіктивного постачальника Аф з запасами aф = ∑bj − ∑ai = 240 − 220									= 20
						j=1		i=1
і вартістю перевезення одиниці вантажу від нього сij=0.
Побудуємо початковий опорний план транспортної задачі
методом найменшої вартості:
Постачальники	Споживачі	B1			B2		B3	ui
	Потреби	115			85		40
	Запаси
		7 +		4		6
A1	60		50		(1)		–	u1=0
		6		2	*	3		10
A2	85						+	u2=–3
					–
		4		5	85	1		0
A3	30							u3=–5
		11		3		8		30
A4					(6)			(2)
	45	–	45		+ *			u4=4
								*
Aф	20	0		0		0		u5=–7
			20
	vj	v1=7			v2=5		v3=6
Ми отримали початковий опорний план транспортної задачі:

		50	0	10
		0	85	0
x	=	0	0	30	.
опорн.			0	0
	45
		20	0	0

153

Вартість перевезення за окресленим опорним планом буде:

Z1=7·50+6·10+2·85+l·30+11·45+0·20=1105.

Перевіримо, чи цей план вироджений. Кількість заповнених (базисних) клітинок має бути рівна рангу r=5+3–1=7, а в нас базисних клітинок 6, тому план перевезення вантажу вироджений. Отже, в одній з небазисних (незаповнених) клітинок ставимо «нульове перевезення» (базисний нуль) і вважаємо цю клітинку базисною, а яку саме клітинку треба нам взяти, визначимо при знаходженні потенціалів.

Для базисних клітинок повинні виконуватись рівності ui+vj=cij. Запишемо ці нерівності, візьмемо одну з невідомих рівну будь-якому числу, наприклад, u1=0, і знаходимо всі інші потенціали:

v1 +u1 = 7,					u = 0,
					1
	+u1		= 6,		v1 = 7 −u1 = 7 −0 = 7,
v3						= 6 −u1 = 6 −0 = 6,
v2 +u2			= 2,
					v3
	+u3		=1,		v2 +u2 = 2,
v3						=1−v =1−6 = −5,
					u
	+u		=11,		3	3
v					u	=11−v =11−7 =	4,
1		4	= 0.
v1 +u5					4	1
					u5 = 0 −v1 = 0 −7 = −7.

Ми маємо значення всіх потенціалів, крім u2 та v2. Запишемо значення знайдених потенціалів в початкову таблицю транспортної задачі і далі визначаємо, в якій небазисній клітинці нам треба записати «базисний» нуль. З небазисних клітинок другого рядочка і другого стовпчика (для них не можемо обчислити значення потенціалів), де вже є порахований один з потенціалів, вибираємо ту, де найменша вартість перевезення одиниці вантажу (крім нульової вартості). В нашому випадку – це клітинка (А2В3). Записуємо в ній 0 та вважаємо її базисною. Записуємо для неї рівняння v3+u2=3, яке дописуємо до системи і далі знаходимо всі потенціали:

u1 = 0, v1 = 7, v3 = 6, v3 +u2 = 3, v2 + u2 = 2, u3 = −5, u4 = 4, u5 = −7.

u1 = 0, v1 = 7, v3 = 6, u2 = 3 − v3 = 3 − 6 = −3, v2 = 2 −u2 = 2 − (−3) = 5,

u3 = −5, u4 = 4, u5 = −7.

154

Знайдені значення потенціалів запишемо в таблицю.
Перевіримо, чи даний опорний план є оптимальним, зокрема чи
виконуються	для небазисних		(незаповнених) клітинок нерівності:
ui + v j ≤ cij .
Маємо три клітинки (А1В2), (А4В2) та (А4В3), для яких не
виконуються ці нерівності, а це означає, що опорний план не є
оптимальним. В цих клітинках ставимо зірочки і в правому
верхньому кутку клітинки записуємо в дужках різницю між сумою
потенціалів окреслених клітинок і вартістю перевезення одиниці
вантажу та	вибираємо клітинку,			для якої		ця різниця найбільша
(клітинку (А4В2)). Для цієї клітинки будуємо цикл перерахунку на
величину θ1 =min(10;85;45)=10, тобто до чисел, які є у додатних
вершинах, додаємо 10, а від чисел, які знаходяться у від’ємних
вершинах, віднімаємо 10. Всі інші клітинки таблиці переписуємо без
змін.
Постачальники	Споживачі	B1			B2	B3	ui
	Потреби	115			85	40
	Запаси
A1	7			4		6
	60		60				u1=0
	6			2		3
			(4)		–
A2	85		*			+	u2=3
					75	10
A3	4	+ (4)		5		1	u3=1
	30		*			–
						30
A4	11			3		8
	45	–	35		+ 10		u4=4
	0			0		0
Aф
	20		20				u5=–7
	vj	v1=7			v2=–1	v3=0
			155

Ми отримали новий опорний план:
					60		0	0
					0		75	10
	x		=		0		0	30	.
	опорн.						10
				35				0
					20		0	0
Вартість перевезення при опорному плані буде:
Z2=7·60+2·75+3·10+1·30+11·35+3·10+0·20=1045.
Перевіряємо описаний план на оптимальність: знову записуємо
систему рівнянь, знаходимо всі потенціали, заносимо їх значення в
таблицю і дивимось, чи виконуються								нерівності ui + v j ≤ cij			для
небазисних клітинок. Є ще дві клітинки – (А2В1) та (А3В1), для яких ці
нерівності не виконуються. Будуємо цикл перерахунку на величину
θ2 =min(75; 30; 35)=30 для клітинки (А3В1), тому що різниця між
сумою потенціалів і вартістю перевезення одиниці вантажу для обох
клітинок однакова (4) і немає суттєвого значення, яку з клітинок
взяти. Переходимо до наступної таблиці:
Постачальники	Споживачі	B1					B2			B3
	Потреби									ui
	Запаси	115					85			40
A1	7					4			6	u1=0
	60			60
	6					2			3
A2		+	(4)				–
	85			*						u2=3
								45		40
						5
A3	4								1
	30			30						u3=–3
	11					3			8
A4
	45	–			5		+	40		u4=4
Aф	0					0			0	u5=–7
	20			20
	vj	v1=7					v2=–1			v3=0
					156

	Новий опорний план:
										60	0	0
										0	45	40
						x		=		30	0	0	.
						опорн.					40
									5			0
										20	0	0
	Вартість перевезення вантажу при цьому буде:
		Z3 =7·60+2·45+3·40+4·30+11·5+3·40+0·20=925.
	Ще є одна клітинка (А2В1), для якої не виконуються нерівності
ui	+ v j ≤ cij .		Тому		будуємо					цикл		перерахунку			на	величину
θ3 =min(45;5)=5 для цієї клітинки. Отримаємо таку таблицю:
	Постачальники		Споживачі				B1				B2			B3	ui
			Потреби				115				85			40
			Запаси
						7				4			6
	A1			60											u1=0
									60
	A2			85		6				2			3		u2=–1
										5		40		40
	A3			30		4				5			1		u3=–3
									30
	A4			45		11				3			8		u4=0
												45
						0				0			0
	Aф			20											u5=–7
									20
			vj				v1=7				v2=3			v3=4
	Знову обчислюємо всі потенціали і записуємо їх значення в
таблицю.		Для		всіх		небазисних					клітинок			останньої		таблиці
										157

виконуються нерівності ui			+ v j			≤ cij , а це означає,					що ми отримали
оптимальний план перевезення вантажу:
						60	0	0
						5	40	40
		x		=		30	0	0	.
		опт.					45
					0			0
						20	0	0
Мінімальна вартість перевезення всіх вантажів від
постачальників до споживачів становить:
Zmin =7·60+6·5+2·40+3·30+4·30+3·45+0·20=905 грошових одиниць.
При цьому споживач В1 не отримає 20 одиниць вантажу,
оскільки п’ятий постачальник фіктивний і вантажу насправді немає. ♦
Неєдиніcть оптимального плану транспортної задачі.
Коли ми отримуємо оптимальний план транспортної задачі,
постає логічне запитання: чи єдиний такий оптимальний план?
Розглянемо останню таблицю транспортної задачі прикладу 4.5.
Постачальники	Споживачі			B1			B2			B3	ui
	Потреби		115				85			40
	Запаси
A1		7					4		6
		60			60						u1=0
		6					2		3
A2			+							–	u2=–1
		85				5		40
										40
A3		4		–			5		1	+
		30			30						u3=–3
		11					3		8
A4
		45						45			u4=0
Aф		0					0		0
		20			20						u5=–7
	vj	v1=7					v2=3			v3=4
						158

Ми бачимо, що для однієї з небазисних клітинок цієї таблиці,
зокрема А3В3,	умова оптимальності опорного плану виконується як
строга рівність: u3 + v3			= c33 ;		−3 + 4 =1.
Виконаємо		для	цієї			клітинки				цикл	перерахунку	на
θ =min(30;40)=30. В результаті отримаємо нову таблицю і новий план
перевезення вантажу:
Постачальники	Споживачі			B1				B2		B3	ui
	Потреби			115				85		40
	Запаси
			7					4		6
A1		60									u1=0
						60
			6					2		3
A2		85									u2=–1
						35			40
											10
A3		30	4					5		1	u3=–3
			11					3		8	30
A4		45									u4=0
									45
Aф		20	0					0		0	u5=–7
						20
	vj		v1=7					v2=3		v3=4
Бачимо, що в таблиці виконуються умови критерію
оптимальності транспортної задачі, а тому отриманий план теж
оптимальний:
							60	0	0
							35	40	10
			x		=		0	0	30
			опт.					45
						0			0
							20	0	0
і сумарна вартість перевезення вантажу співпадає з мінімальною
вартістю, яку отримали з попередньої таблиці:

159

Zmin =7·60+6·35+2·40+3·10+1·30+3·45+0·20=905.

Отже, ми маємо два оптимальні плани однієї транспортної задачі. Проте з геометричної інтерпретації задач лінійного програмування ми знаємо, що якщо цільова функція досягає свого екстремального (максимального чи мінімального) значення в двох вершинах многогранника допустимих розв’язків, то вона набуває такого ж значення в кожній точці відрізка, що сполучає ці дві вершини. Значить транспортна задача теж повинна мати безліч оптимальних планів. Якщо розглянути останню таблицю, то бачимо, що для клітинки А3В1 умова оптимальності виконується як строга рівність і цикли для цієї клітинки, і клітинки А3В3 попередньої таблиці здійснюються на одне і те ж значення параметру θ =30. Перерозподіл вантажу в розмірі θ одиниць стосовно кожного із циклів залишає незмінними умови оптимальності. Визначимо межі зміни параметру θ з останньої таблиці:

0 ≤ θ ≤ min( 35; 30 ) = 30.

Отже, множина всіх оптимальних планів транспортної задачі, що розглядається, має вигляд:

		60	0	0
		35 −θ	40
				10 +θ
x	=	0	0	30 −θ .
опт.		0	45	0
		20	0	0

Проте, якщо врахувати цілочисельність параметру θ , то множина оптимальних планів звузиться.

4.5.Економічні задачі, що зводяться до задач транспортного типу

4.5.1.Однопродуктова задача поточного перспективного планування

Найпростішими моделями галузевого планування є моделі оптимізації поточних і перспективних планових розрахунків виробництва та постачання однорідної продукції.

Розглянемо однопродуктову модель поточного галузевого планування. У поточному періоді необхідно визначити оптимальний варіант закріплення споживачів за постачальниками таким чином,

160