Navch._posibnuk_Ivaschyk

	30	0	0	170
xопорн. = 110		40	0	0	.
	0	85	90	0

Сумарна вартість перевезення всього вантажу при цьому буде:

Z=2·30+1·170+3·110+7·40+9·85+3·90=60+170+330+280+765+270=1875. ♦

Після побудови початкового опорного плану кожним з методів у таблиці має бути заповнено (m+n-1) клітинок, тому що ранг матриці системи обмежень транспортної задачі рівний r=m+n-1, де m – кількість постачальників, n – кількість споживачів. Заповнені клітинки називаються базисними, а незаповнені – вільними. Якщо кількість базисних клітинок рівна (m+n-1), то такий план називається невиродженим. Якщо кількість заповнених клітинок менша (m+n-1), то план називається виродженим. Тоді необхідно заповнити відповідну кількість порожніх (небазисних) клітинок, записуючи в них «нульове перевезення», і ці клітинки вважати базисними. Коли ж кількість заповнених клітинок перевищує (m+n-1), то початковий опорний план побудовано неправильно і він не є опорним.

Для того, щоб з’ясувати, який метод знаходження початкового опорного плану транспортної задачі є ефективнішим, порівняємо загальні вартості перевезення за опорними планами, знайденими кожним з методів. Бачимо, що меншу вартість отримаємо за методом найменшої вартості (Z=1875) і значно більшу вартість перевезення (Z=2675) всього вантажу дає діагональний метод побудови початкового опорного плану. Як бачимо, ефективнішим методом побудови початкового опорного плану транспортної задачі є метод найменшої вартості.

4.3.Метод потенціалів

4.3.1.Критерій оптимальності опорного плану за методом потенціалів

Ми вже знаємо методи знаходження початкових опорних планів транспортної задачі, але чи ці опорні плани є оптимальними, тобто такими, що дають найменшу загальну вартість перевезення всього вантажу від постачальників до споживачів, ми не знаємо. Опорний план перевіряють на оптимальність за допомогою потенціалів. Відповідно до кожного постачальника Аi ставимо потенціал ui, а кожному споживачеві Вj – vj.

141

Критерій оптимальності опорного плану транспортної задачі:

якщо для деякого опорного плану (хij) транспортної задачі існують такі числа-потенціапи ui та vj, що для базисних

клітинок			виконуються рівності ui+vj=сij, а для			небазисних
клітинок				виконуються нерівності ui+vj ≤сij		для всіх
i =		;	j =		, то такий опорний план є оптимальним.
	1, m			1, n

Потенціали опорного плану визначаються із системи ui+vj=сij, які записують для всіх заповнених клітинок таблиці транспортної задачі. За допомогою розрахованих потенціалів перевіряють умову оптимальності ui+vj ≤сij для незаповнених клітинок таблиці. Якщо хоча б для однієї небазисної клітинки ця умова не виконується, тобто ui+vj>сij, то поточний план не є оптимальним і потрібно перейти до нового опорного плану.

4.3.1. Цикли перерахунку транспортної задачі

Перехід від одного опорного плану до іншого виконують заповненням небазисної клітинки, для якої порушена умова оптимальності. Якщо окреслених клітинок кілька, то для заповнення вибирають таку, що має найбільше порушення, тобто max{ ij = (ui + v j ) −cij }. Для вибраної порожньої клітинки будують

цикл перерахунку.

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

Перерозподіл продукції в межах циклу здійснюють за такими правилами:

а) кожній вершині циклу приписують певний знак, причому незаповненій клітинці знак «+», а всім іншим по черзі знаки «–» та

«+»;

б) у порожню клітинку заносять найменше з чисел, що стоять у клітинках зі знаком «–». Одночасно це число додають до відповідних чисел, що стоять у клітинках зі знаком «+» і віднімають від чисел, що розміщені у клітинках зі знаком «–».

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

142

отримаємо новий опорний план транспортної задачі, який знову перевіряємо на оптимальність. Якщо розв’язок оптимальний, то обчислюємо мінімальне значення цільової функції (мінімальну вартість перевезення всього вантажу), а якщо неоптимальний, то знову будуємо цикл перерахунку і з допомогою зсуву по циклу переходимо до нового опорного плану. Процес повторюють до тих пір, доки не отримаємо оптимального розв’язку транспортної задачі.

Значення базисних клітинок, які не брали участі в циклі перерахунку, в новій таблиці залишаються без змін.

Якщо на деякому кроці потреби співпадають із запасами, то в потребах ставимо дійсний нуль, а в запасах – фіктивний (нуль з крапкою – О). Тоді одразу будується повна система рівнянь для знаходження значень потенціалів (див. прикл. 4.5).

У задачах з виродженим планом часто зсув стосовно циклу треба робити на 0. Тоді при переході до наступної таблиці значення базисних клітинок, що брали участь в циклі перерахунку, не змінилося. Тільки цей «базисний нуль» переводять у небазисну клітинку, для якої по суті робили цикл перерахунку, а клітинка, в якій знаходився цей 0, стає вільною.

Зобразимо можливі види циклів:

*

*

*

*

*

Розглянемо алгоритм методу потенціалів на прикладі.

Приклад 4.3. Знайти оптимальний план перевезення однорідного вантажу від постачальників А1, А2, А3, А4 з запасами а1=90, а2=85, а3=125, а4=І05 до споживачів В1, В2, В3 з потребами в цьому вантажі

143

b1=110, b2=155, b3=140, який забезпечить мінімальну вартість
перевезення вантажу, якщо відома вартість перевезення одиниці
вантажу від постачальників до споживачів:
						3	6	2
						1	5	7
			c	=						.
			ij			9	7	8
						4	3	5
♦Розв’язування.
Початковий опорний план задачі знайдемо з допомогою
діагонального методу (північно-західного кута).
Перевіримо, чи транспортна задача є закритою. Обчислимо:
4								3
∑ai = 90	+85 +125 +105 = 405;						∑bj =110 +155 +140 = 405.
i=1								j=1
	4	3
Оскільки ∑ai = ∑bj , то описана транспортна задача є закритого
типу.	i=1	j=1
Побудуємо початковий опорний план транспортної задачі
діагональним методом:
Постачальники	Споживачі		B1				B2					B3		ui
	Потреби		110				155					140
	Запаси
			3				6	(1)			2	+	(6)
A1	90		–		90					–			*	u1=0
			1				5				7		–
A2	85													u2=–2
			+		20		–		65				–
			9				7				8
A3	125													u3=0
					–		+		90			–	35
A4	105		4				3	(1)			5			u4=–3
					–					–			105
	vj		v1=3				v2=7					v3=8
						144

	90	0	0
	20	65	0
xопорн. =	0	90	35	.
	0	0	105

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

Z1=3·90+1·20+5·65+7·90+8·35+5·105=270+20+325+630+280+525=2050

грошових одиниць.

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

Перевіримо, чи описаний опорний план є оптимальним. Для базиснихклітинокповиннівиконуватисьрівностіui+vj=сij. Запишемоїх:

v1 +u1 = 3,

u

= 0,

u1 = 0,

1

= 3,

v1 = 3 −u1 = 3 −0 = 3,

v1

v1

+u2

=1,

u

2

=1−v

=1−3 = −2,

u2 − 2,

+u2

= 5,

v

1

= 5 −(−2) = 7,

v

= 7,

v2

= 5 −u

2

2

v2 +u3

= 7,

2

= 7 −v2 = 7 −7 = 0,

= 0,

+u

= 8,

u3

u3

v

v

= 8 −u

= 8 −0 = 8,

v

= 8,

3

3

v3 +u4 = 5.

3

3

3

u4 = 5 −v3 = 5 −8 = −3.

u4 −3.

Ми маємо систему 6 рівнянь з 7 невідомими. Ця система має безліч розв’язків. Візьмемо одну з невідомих рівну будь-якому числу, наприклад, u1=0, і знайдемо всі інші потенціали. Знайдені значення потенціалів запишемо в таблицю. Тепер здійснимо перевірку другої умови критерію оптимальності транспортної задачі, а саме: чи виконуються для небазисних (незаповнених) клітинок нерівності

ui+vj ≤сij.

Для	клітинки (A1B2 ) :	v2 +u1 ≤ 6		7 + 0 > 6	нерівність	не	виконується
Для	клітинки (A1B3 ) :	v3 +u1 ≤ 2		8 + 0 > 2	нерівність	не	виконується
Для	клітинки (A2 B3 ) :	v3 +u2 ≤ 7		8 + (−2) ≤ 7
Для	клітинки (A3 B1 ) :	v1 +u3 ≤ 9		3 + 0 ≤ 9
Для	клітинки (A4 B1 ) :	v1 +u4	≤ 4	3 + (−3) ≤ 4
Для	клітинки (A4 B2 ) :	v2 +u4	≤ 3	7 + (−3) > 3	нерівність	не	виконується

145

Маємо три клітинки (А1В2), (А1В3) та (А4B2), для яких не
виконуються нерівності ui+vj ≤сij, а це означає, що опорний план не є
оптимальним. В клітинках (А1В2), (А1В3) та (А4B2) ставимо зірочки (*)
і в правому верхньому кутку клітинки записуємо в дужках різницю
між сумою потенціалів і вартістю перевезення одиниці вантажу
окреслених клітинок та вибираємо клітинку, для якої ця різниця
найбільша, зокрема клітинку (A1B3). Для цієї клітинки будуємо цикл
перерахунку на величину θ1 =min(90;65;35)=35, тобто до чисел, які є у
додатних вершинах, додаємо 35,				а від чисел, які знаходяться у
від’ємних вершинах, віднімаємо 35:
90		+ *		55				35
–
+	–			55			30
20	65
	+	– 35
	90						125
a) до перерахунку						б) після перерахунку
Всі інші клітинки таблиці переписуємо без змін.
Постачальники	Споживачі	B1				B2	B3	ui
	Потреби	110				155	140
	Запаси
		3		6		(1)	2
A1	90	–	55			*	+	u1=0
		1					35
A2	85			5			7	u2=–2
		+	55		–	30
		9		7			8
A3	125							u3=0
						125
		4	(2)	3		(7)	5
A4	105		*		+		–	u4=3
						*	105
	vj	v1=3			v2=7		v3=2
			146

Ми отримали новий опорний план:

	55	0	35
	55	30	0
xопорн. =	0	125	35	.
	0	0	105

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

Z2=3·55+2·35+1·55+5·30+7·125+5·105=1840.

Перевіряємо план на оптимальність: знову записуємо систему рівнянь, знаходимо всі потенціали, заносимо їх значення в таблицю і дивимось, чи виконуються нерівності ui+vj ≤сij для небазисних клітинок. Є ще три клітинки, зокрема (A1B2), (A4B1) та (A4B2), для яких ці нерівності не виконуються. Будуємо цикл перерахунку на величину θ2 =min(55;30;105)=30 для клітинки (A4B2), тому що різниця між сумою потенціалів і вартістю перевезення одиниці вантажу для неї найбільша (7). Переходимо до наступної таблиці:

Постачальники	Споживачі		B1		B2	B3	ui
	Потреби		110		155	140
	Запаси
		3 +		6	2
A1	90					–	u1=0
			25	5	*	65
A2	85	1			7		u2=–2
			85
		9		7	8	(1)
A3	125		(1)				u3=7
			*		125
		4		3
A4	105		(2)		5		u4=3
			–		30	+
			*			75
	vj		v1=3		v2=0	v3=2
			147

Новий опорний план:					25	0	65
					85	0	0
	x		=						.
	опорн.				0	125	0
					0	30	75
Вартість перевезення при описаному опорному плані буде:
Z3 =3·25+2·65+1·85+7·125+3·30+5·75=1630.
Ще є небазисні клітинки (A3B1), (A3B3) та (A4B1), для яких не
виконуються нерівності ui+vj ≤сij. Тому будуємо цикл перерахунку
на величину θ3 =min(25;75)=25 для клітинки (A4B1), оскільки різниця
між сумою потенціалів і вартістю перевезення одиниці вантажу для
неї рівна 2 (найбільша). Отримаємо таблицю:
Постачальники	Споживачі	B1				B2			B3	ui
	Потреби	110				155			140
	Запаси
A1	3					6			2
	90								90	u1=0
						5
A2	1								7
	85			85						u2=0
	9					7			8
A3	125					–			+	u3=7
						125
A4	4					3			5
	105			25		+	30		–	u4=3
									50
	vj	v1=1				v2=0			v3=2
Ми отримали новий опорний план:

			0	0	90
			85	0	0
x	=						.
опорн.			0	125	0
			25	30	50

148

При цьому загальна вартість перевезення становить

Z4=2·90+1·85+7·125+4·25+3·30+5·50=1580.

Оскільки в клітинці (А3В3) ще порушується друга умова критерію оптимальності транспортної задачі, а саме u3+v3>с33 (7+2>9), то для цієї клітинки робимо цикл перерахунку на величину (θ 4=min(125;50)=50. В результаті отримали:

Постачальники	Споживачі	B1	B2	B3	ui
	Потреби	110	155	140
	Запаси
A1	3	6		2	u1=0
	90			90
A2	1	5		7	u2=–2
	85	85
A3	9	7		8	u3=6
	125		75	50
A4	4	3		5	u4=2
	105	25	80
	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, використавши для визначення початкового опорного плану задачі метод найменшої вартості.

149

♦ Розв’язування.
Використаємо метод найменшої вартості і заповнимо початкову
таблицю транспортної задачі:
Постачальники		Споживачі		B1				B2			B3	ui
		Потреби		110				155			140
		Запаси
				3				6			2
	A1	90										u1=0
							¯		¯		90
	A2	85		1				5			7	u2=-2
						85			¯		¯
				9				7			8
	A3	125		–		25		+	50		50	u3=6
	A4
		105		4				3			5	u4=2
				+			¯	–			¯
				*				105
		vj		v1=3				v2=1			v3=2
Кількість базисних клітинок рівна 6 і ранг r=4+3–1=6, значить
отриманий опорний план невироджений:
							0	0	90
							85	0	0
				x	=						.
				опорн.			25	50	50
							0	105	0
При такому плані загальна вартість перевезення вантажу від
постачальників до споживачів становитиме:
	Z1=2·90+1·85+9·25+7·50+8·50+3·105=1555.
За базисними клітинками знаходимо всі потенціали і їх значення
заносимо в таблицю. Перевіряємо, чи описаний опорний план є
оптимальним.
Оскільки в клітинці (А4В1) порушується умова оптимальності
ui+vj ≤сij,	то	для	неї	робимо				цикл	перерахунку			на	величину
θ =min(25;105)=25 і переходимо до нової таблиці:

150