Крок 3.

3.1.Якщо невикресленим залишається рівно один рядок або один стовпчик, то закінчити обчислення.

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

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

3.4. В інших випадках обчислити нові значення штрафів для невикреслених рядків і стовпчиків і перейти до кроку 2 (рядки та стовпчики з нульовими значеннями обсягу виробництва та попиту не слід використовувати при обчисленні цих штрафів).

Знайдемо ДБР задачі, умову якої наведено в наступній таблиці, за допомогою наближеного методу Фогеля.

Нижче наведено таблицю, що містить перший набір штрафів для рядків та стовпчиків. Оскільки рядок 3 має найбільший штраф (=3) та с₃₁=2 є найменшим коефіцієнтом вартості, то змінній х₃₁ приписуємо значення 5. Викреслюємо стовпчик 1.

	1		2		3		4			Штрафи рядків
		2		5		3		1
1									10	1
		3		4		1		4
2									20	2
		2		6		5		5
3	5								20	3
	5		25		10		10
Штрафи стовпчиків	0		1		2		3

Наступна таблиця вміщує новий набір штрафів, одержаний після викреслювання стовпчика 1.

	1			2		3		4				Штрафи рядків
			2		5		3		1
1										10		2
		3			4		1		4
2						10				20			3
		2			6		5		5
3	5									20	15	0
	5			25		10		10
Штрафи стовпчиків	¾			1		2		3

У цій таблиці другий рядок та третій стовпець мають найбільший штраф. Оберемо рядок 2. При цьому с₂₃=1 є найменшим коефіцієнтом вартості в рядку. Змінній х₂₃ приписуємо значення 10 і викреслюємо стовпчик 3.

	1		2		3		4				Штрафи рядків
		2		5		3		1
1							10		10		4
		3		4		1		4
2					10				20	10	0
		2		6		5		5
3	5								20	15	1
	5		25		10		10
Штрафи стовпчиків	¾		1		¾		3

Рядок 1 є рядком з найбільшим штрафом. Елемент х₁₄ є елементом з найменшою вартістю. Тому приписуємо йому значення 10. Обмеження виконується по рядку і по стовпчику, тобто викреслити можна або рядок, або стовпчик.

Викреслюємо стовпчик 4.

Оскільки невикресленим залишається лише один стовпчик 2, то далі шукаємо значення базисних змінних методом найменшої вартості.

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

У результаті одержуємо такий базисний розв’язок:

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

Базисні змінні набувають значень: х₁₂=0, х₁₄=10, х₂₂=10, х₂₃=10, х₃₁=5, х₃₂=15. Сумарні витрати складають: 0*5+10*1+10*4+10*1+5*2+15*6=160.

5.5.3. Знаходження змінної, що вводиться до базису

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

Нехай ТЗЛП задано у векторній формі:

(5.10)

(5.11)

(5.12)

Вибір змінної, що вводиться до базису, залежить від значень компонент вектора відносних оцінок, який у "звичайному" модифікованому симплекс-методі визначається так:

(5.13)

де – вектор оцінок обмежень (двоїстих змінних).

Вектор визначається таким чином:

Тобто є розв’язком такої системи лінійних рівнянь:

Після транспонування одержимо:

(5.14)

Розглянемо тепер модифікований симплекс-метод, який застосуємо до ТЗЛП.

Подамо вектор оцінок обмежень (5.11) ЗЛП (5.10) – (5.12) у вигляді , де пiдвекторвідповідаєm першим обмеженням, пов’язаним з виробниками, а пiдвектор –n - останнім обмеженням, пов’язаним зі споживачами. Побудуємо для задачі (5.10) – (5.12) систему (5.14), записану за рівняннями:

=, (i, j) , (5.15)

де – множина пар індексів базисних змінних.

З урахуванням структури векторів = із системи (5.15) одержуємо:

+=; (i, j) . (5.16)

Система (5.16) має m+n змінних і m+n—1 рівнянь.

У системі обмежень ТЗЛП одне з обмежень "зайве ". Відкинути його – це означає надати відповідній йому двоїстій змінній довільного значення (найпростіше прирівняти до нуля). Оскільки зайвим можна вважати будь-яке з рівнянь, то значення "нуль" можна надати будь-якій зі змінних або . Нехай=0. Після цього система (5.16) перетворюється у систему з m+n—1 рівнянь із m+n—1 змінними.

Нехай ,,,– розв’язок системи (5.16). Тоді, враховуючи (5.13), можемо визначити відносні оцінкинебазисних змінних:

=+–. (5.17)

Якщо всі £ 0, то задане ДБР оптимальне, якщо >0, то треба переходити до наступного ДБР.

Величини іназиваютьсяпотенціалами.

Побудуємо систему (5.16) за початковим ДБР задачі, одержаним методом північно-західного кута (див. табл. 5.3). Рівняння, пов’язані з базисними змінними, матимуть вигляд:

Поклавши = 0, одержимо значення потенціалів:

=2, =5, =–1, =2, =3, =–1.

Відповідно до (5.18) оцінки для небазисних змінних визначаються такимчином:

Оскільки =max{} за небазисними змінними , то зміннаобирається як змінна, що вводиться до базису (табл. 5.4).

Таблиця 5.4

	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

Рівняння +=, використовувані для знаходження потенціалів, мають настільки просту структуру, що насправді їх не треба записувати в явному вигляді. Звичайно набагато простіше визначати потенціали безпосередньо з транспортної таблиці, помітивши, щорядкаi і стовпчикаj в сумі дають, якщо на перетині рядкаi та стовпчика j знаходиться базисна змінна . Визначивши, можна обчислитидля всіх небазисних змінних, додаючирядкар до стовпчикаq і потім віднімаючи величину , що стоїть на перетині рядкар та стовпчика q.

Далі величини будемо вказувати впівденно-західному куті кожного небазисного елемента.