5.5.5. Перехiд до нового допустимого базисного розв’язку

Перехiд до нового ДБР здiйснюється за такими спiввiдношеннями:

(5.20)

5.5.6. Схема методу потенціалiв

Попереднiми мiркуваннями обґрунтована послiдовнiсть крокiв методу потенціалів розв’язання транспортних задач.

Крок 0. Побудова початкового ДБР.

Побудувати початковий ДБР {} задачi (методом пiвнiчно-захiдного кута, методом мінімальної вартостi й т. ін.).

Нехай — множина пар iндексiв базисних змiнних початкового ДБР.

Крок 1. Обчислення вiдносних оцiнок небазисних змiнних.

За множиною побудувати систему рiвнянь:

+=;(i, j )  .

Знайти розв’язок {}i=1, …, m, {}j=1, …, n такої системи з точнiстю до доданка. Обчислити вiдноснi оцiнки :

=+–,(i, j ).

Крок 2. Перевiрка умови оптимальностi.

Якщо  0 для всiх (i, j), то припинити обчислення, поточне ДБР є розв’язком початкової задачi.

Крок 3. Вибiр небазисної змiнної, що вводиться у множину базисних

Обрати пару таку, що> 0 змiнну ввести в базис.

Крок 4. Вибiр базисної змiнної, що виводиться з множини базисних.

Для змiнної побудувати компенсаторний цикл. Видiлити множиниi. Обрати

Крок 5. Перехiд до нового ДБР.

Визначити новий ДБР за допомогою спiввiдношень:

Побудувати нову множину пар iндексiв базисних змiнних:

Покласти i перейти до кроку 1.

Продовжимо розв’язання задачi, початковий ДБР якої наведено в табл. 5.5.

Таблиця 5.5

	v1=2		v2=5		v3=2		v4=-1
Ü		2		5		3		0
u1=0	5		5						10
	-			Å	-1		-1
		3		4		1		4
u2=-1			20		0				20
	-2			-		Å	-6
		2		6		5		2
u3=3 Þ	х31				10		10		20
	+3	Å	2			-
	5 Ý		25		10		10

З табл. 5.5 бачимо, що, якщо значення (змінної, що вводиться до базису)збільшується на одиницю, для збереження допустимості розв’язку значення базисних змінних, що стоять на зламах -циклу, необхідно скоректувати таким чином: зменшити на одиницю,збільшити на одиницю,зменшити на одиницю,збільшити на одиницю і, нарешті,зменшити на одиницю. Цей процес позначений знакамиÅ та “–” у відповідних клітинах табл. 5.4. Введені зміни не порушують обмежень на обсяги виробництва та попит.

Змінна, що виводиться з базису, обирається зі змінних, що знаходяться на зламах циклу, значення яких зменшуються при збільшенні . Вони розташовуються в табл. 5.5 у клітинах, помічених знаком“–”. З табл. 5.5 випливає, що ,, – базисні змінні, які зменшуються зі зростанням . Змінною, що виводиться з базису, стає та, що має найменше значення, оскільки саме вона раніше за всіх досягне нуля, і будь-яке подальше зменшення робить її від’ємною. У цьому прикладі= 5,= 20,= 10,

Таким чином, за змінну, що вилучається, обирається змінна ; тоді значеннябуде дорівнювати 5, а змінні, що знаходяться на зламах циклу (базисні), відповідним чином коректуються (тобто кожна з них збільшується або зменшується на 5 одиниць залежно від знакаÅ або ”–”). Новий розв’язок наведено у табл. 5.6.

Таблиця 5.6

	2		5		3		0
		10						10
	3		4		1		4
		15		5				20
	2		6		5		2
5				5		10		20
5		25		10		10

Цей розв’язок має таку вартість:

z₁

Одержана вартість є відмінною від z₀ на 185 — 170 = 15 од. вартості, тобто на величину, приписану змінній = 5 і помножену на= 3.

Оптимальність нового базисного розв’язку з табл. 5.6 перевіряють обчисленням нових потенціалів та оцінок небазисних змінних (табл. 5.7). Небазисна змінна , що має максимальну додатну оцінку= 2, вводиться до складу базисних.

Таблиця 5.7

	v1=-1		v2=5		v3=2		v4=-1
		2		5		3		0
u1=0			10						10
	-3				-1		-1
		3		4		1		4
u2=-1			15		5				20
	-5			¾		Å	-6
		2		6		5		2
u3=3	5		x32		5		10		20
			+2	Å		¾
	5		25 Ý		10 ß		10

Замкнений цикл, що відповідає ,, показує, що з базису повинна бути вилучена змінна

У табл. 5.8 наведено новий базисний розв’язок з вартістю .

Таблиця 5.8

	v1=1		v2=5		v3=2		v4=1
		2		5		3		0
u1=0			10				х14		10
	-1			-	-1		+1	Å	Ü
		3		4		1		4
u2=-1			10		10				20
	-3						-6
		2		6		5		2
u3=1	5		5				10		20
				Å	-2			-
	5		25		10		10 ß

Оскільки , то розв’язок не оптимальний. Для змінної , що вводиться до базису, побудуємо компенсаторний цикл:. З компенсаторного циклу бачимо, що з базису може бути вилучена або змінна, або змінна(оскільки); зупинимося на останній. У результаті одержимо розв’язок, наведений у табл. 5.9.

Таблиця 5.9

	v1=1		v2=5		v3=2		v4=0
		2		5		3		0
u1=0			0				10		10
	-1				-1
		3		4		1		4
u2=-1			10		10				20
	-3						-5
		2		6		5		2
u3=1	5		15						20
					-2		-1
	5		25		10		10

Оскільки відносні оцінки всіх небазисних змінних у цьому розв’язку недодатні, одержаний розв’язок — оптимальний.

Оптимальний план перевезень наведено в табл. 5.10.

Таблиця 5.10

Пункт виробництва	Пункт споживання	Обсяг перевезення	Вартість перевезення
1	4	10	0
2	2	10	40
2	3	10	10
3	1	5	10
3	2	15	90
	Усього	50	150