2. Transport masalasining optimal yechimini topish uchun potensiallar usuli

katakchadan boshlab harakat qilib, to’ldirilgan katakchalarga tartib bilan (-) va (+) ishoralari qo’yilib boriladi. Natijada yopiq kontur hosil bo’ladi

bu yerda – (-) va (+) ishorali katakchalarni o’z ichiga oluvchi yarim konturlar.
Quyidagi formula orqali ning son qiymati topiladi.
(19)
4. Yangi bazis reja hisoblanadi:

Yangi bazis rejadagi to’ldirilgan katakchalar soni ta bo’lganligi uchun (19) shartni qanoatlantiruvchi katakchalar birdan ortiq bo’lsa, ulardan bittasini bo’sh katakchaga aylantirib, qolgan katakchalardagi taqsimotni 0 ga teng deb qabul qilinadi. Topilgan yangi bazis reja uchun yana qaytadan potensiallar sistemasi topiladi va yangi rejaning optimal reja bo’lishlik sharti tekshiriladi. Agar yangi bazis reja optimal reja bo’lmasa, u holda yana qaytadan 3, 4 punktlarda qilingan ishlar takrorlanadi. Jarayon optimal yechim topilguncha, ya’ni barcha bo’sh katakchalar uchun

shart bajarilguncha takrorlanadi.

Misol. Berilgan transport masalasini potensiallar usuli bilan yeching.
1-jadval.

	200		200			100			100			250
100	10		7			4		1			4				0
					8		9			11			5
250	2 100+9		7 150-9			10		6			11				-8
							-5			-2			-12
200	8		5 50+			3 100			2 50-			2					-10
		-8												-3
300	11		8			12		16 50			13 250					4
		3		11			5
	10		15			13			12			9					=50

1. Boshlang’ich bazis rejani «shimoliy-g’arb burchak» usuli bilan topamiz.

2. Har bir to’ldirilgan katakcha uchun potensial tenglama tuzib, quyidagi sistemani hosil qilamiz:

Bu sistemadagi noma’lumlar soni tenglamalar sonidan bittaga ko’p. Shuning uchun ixtiyoriy bir potensialni (masalan, ni) 0 ga teng deb qabul qilib, qolganlarini birin- ketin topish mumkin.

3. Har bir bo’sh katakcha uchun

ni hisoblab uni bo’sh katakchaning pastki o’ng burchagiga yozamiz:

bo’lganligi sababli (1,4) katakchaga (yoki (4,2) katakchaga) son kiritamiz va (1,1), (2,1), (2,2),(3,2), (3,4) katakchalarni o’z ichiga oluvchi yopiq kontorini tuzamiz.

bu yerda (1,1), (2,2), (3,4) va (2,1), (3,2)
4. ning son qiymatini topamiz.
.
Yangi bazis rejani aniqlaymiz va ularni jadvalga joylashtiramiz.
2-jadval.

	200		200			100		100		250
100	10 50-		7			4		1 50+		4		0
				8			9				-6
250	2 150+		7 100-9			10		6		11		-8
							-10		-13		-21
200	8		5 100			3 100		2		2		-10
		-8							-11		-14
300	11		8			12		16 50-		13 250		15
		14			22
	10		15			13		1		-2		=50

Yuqoridagi usul bilan potensiallar sistemasini tuzib va uni yechib ekanini topamiz.

Barcha bo’sh kataklar uchun ni hisoblab chiqamiz.
2-jadvaldan ko’rinadiki,
Shuning uchun (4.2) katakcha ni kiritib, jadvalda ko’rsatilgan yopiq konturni tuzamiz va ekanini aniqlaymiz.
So’ngra (5.23) formula orqali yangi bazis rejani topib jadvalga joylashtiramiz va yuqoridagi ishlarni takrorlaymiz.
3-jadval.

	200			200			100		100				250
100	10 0-			7			4		1 100			4			0
					8			9						16
250	2 200+			7 50-			10		6			11			-8
								-5		-13				1
200	8		5 100			3 100			2			2			-10
		-8									-11			8
300	11			8 50+			12		16				13 250-		-7
	10			15			13		1				20		=0

4-jadval.

	200			200			100				100			250
100	10			7		4				1 100				4 0				0
		-16			-8			-7
250	2 200			7 50			10				6			11				8
									-5				3			1
200	8			5 100-			3 100				2				2				6
			-8									5					8
300	11			8 50+			12				16				13 250-				9
			-8						-6			-6
	-6			-1			-3				1			4				=100

5-jadval.

	200			200				100				100			250
100	10			7			4				1 100-				4 0+		0
		-16			-8				1
250	2 200			7 50-				10				6			11		8
										3				3		1
200	8			5			3 100				2				2 100		-2
			-16			-8							-3
300	11			8 150+			12 2				16				13 150-		9
			-8										-6
	-6			-1				5				1			4		=50

6-jadval.

	200			200				100				100				250
100	10			7				4				1 50			4 50			0
		-13				-8				1
250	2 200			7				10				6 50			11			5
						-11				0							-2
200	8			5			3 100-					2				2 100+			-2
			-13		-8									-3
300	11			8 100			12				16				13 100-			9
			-5						2				-6
	-3			-1				5				1				4			=100

7-jadval.

	200			200		100				100			250
100	10			7		4				1 50			4 50-					0
			-13		-6			1
250	2 200			7		10				6 50		11					5
					-1			0							-2
200	8			5		3 0-				2				2 200+					-2
		-11			-8						-3
300	11			8 200		12 100				16				13				7
		-7									-8					-2
	-3			1		5				1			4					=0

8-jadval.

	200			200		100		100				250
100	10			7		4 0		1 50				4 50					0
			-13		-7
250	2 200			7		10		6 50			11					5
					-2		-1							-2
200	8			5		3		2				2 200					-2
		-11			-7		-1		-3
300	11			8 200		12 100		16					13				8
		-6								-7					-1
	-3			0		4		1				4

8-jadvalda keltirilgan reja optimal yechim bo’ladi, chunki barcha bo’sh katakchalar uchun

Shunday qilib, sakkizinchi siklda quyidagi optimal yechimga ega bo’ldik: