Схема методу потенціал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
Ь
u1=0
	-			Е	-1		-1
u2=-1
	-2			-		Е	-6
u3=3 Ю	х31
	+3	Е				-
	5 Э

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

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

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

Таблиця 5.6

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

z₁

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

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

Таблиця 5.7

	v1=-1	v2=5	v3=2	v4=-1
u1=0
	-3				-1		-1
u2=-1		15
	-5			ѕ		Е	-6
u3=3		x32
			+2	Е		ѕ
		25 Э	10 Я

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

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

Таблиця 5.8

	v1=1	v2=5	v3=2	v4=1
u1=0				х14
	-1			-	-1		+1	Е	Ь
u2=-1
	-3						-6
u3=1
				Е	-2			-
				10 Я

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

Таблиця 5.9

	v1=1	v2=5	v3=2	v4=0
u1=0
	-1				-1
u2=-1
	-3						-5
u3=1
					-2		-1

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

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

Таблиця 5.10