Differentsial rentalar usuli (Brudno usuli)

Differentsial rentalar usuli (Brudno usuli)
Rus olimi A.L.Lure 1959 yilda transport masalasini echish uchun optimal echimga shartli optimal echimlar ¸rdami bilan yaqinlashish usulini yaratdi. A.L.Brudno bu usulni modifitsirlab (o’zgartirib), uni differentsial rentalar usuli deb ataydi. Differentsial rentalar usuli va shartli optimal echimlar bilan yaqinlashish usulining g’oyasi bir xil bo’lishiga qaramay, ular bir-biridan farq qiladi. Ular orasidagi asosiy farq shundan iboratki, differentsial rentalar usuli elektron hisoblash mashinasida qo’llanish uchun qulay bo’lib, shartli optimal rejalar ¸rdami bilan yaqinlashish usuliga nisbatan ikki marta kam vaqt talab qiladi.

Ma’lumki, transport masalasini potentsiallar usuli bilan echishda eng avval ishlab chiqarilgan hamma mahsulot to’la taqsimlanadi, ya’ni bazis reja topiladi. So’ngra topilgan bazis reja optimal rejaga ketma ket yaqinlashtirilib boriladi. Differentsial rentalar usulida esa dastlab mahsulotning bir qismi taqsimlana-

di, lekin taqsimlangan mahsulot optimal rejaning qismini tashkil qiladi. Echish jara¸ni mahsulot to’la taqsimlanguncha davaom ettiriladi.

Differentsial rentalar usulining algoritmini ko’rishdan avval ba’zi qo’shimcha tushunchalar bilan tanishchamiz.

Faraz qilaylik, X=(x_ij) bazis echimga shunday ikki o’lchovli (nxm) jadval mos kelsinki, unda har bir x_ij bazis o’zgaruvchi joylashgan katakchaga belgi (kvadratcha) qo’yilgan bo’lsin.

1-ta’rif. Agar belgi o’zining ustunida (qatorida) yagona bo’lsa, u tartiblanuvchi deb ataladi. Berilgan jadvaldagi belgilarning har birini quyidagi algoritm yordamida tartiblash mumkin bo’lsa, bu belgilar sistemasi tartiblanuvchi deb ataladi.

Belgilarni tartiblash uchun transport jadvalining birinchi ustunidan boshlab tartib bilan barcha ustunlar qarab chiqiladi va belgilarga 1 nomerdan boshlab tartib nomerlar qo’yiladi. Qarala¸tgan ustunda (qatorda) yagona nomerlanmagan belgi qatnashsa unga navbatdagi tartib nomeri qo’yiladi, aks holda bu ustundagi (qatordagi) belgilar vaqtincha nomerlanmay o’tkazib yuboriladi. Belgilar ustunlar bo’yicha nomerlanib bo’lmagan holda 1-qatordan boshlab nomerlanish tatibi davom ettiriladi. Shunday qilib, belgilarning hammasi nomerlanguncha ketma-ket ustun va qator bo’ylab belgilar qarab chiqiladi.

Lemma. Ikki o’lchovli (nxm) jadvaldagi belgilar sistemasi tartiblanuvchi bo’lishi uchun bu jadvalning ixti¸riy (n'xm') qismidagi belgilar soni n'+m'-1 ta bo’lishi zarur va etarlidir.

Zarurligi. Faraz qilaylik, belgilar sistemasi tartiblanuvchi bo’lsin. U holda berilgan (nxm) jadvalning ixti¸riy (n'xm') qismi kamida bitta nomerlanuvchi belgini o’z ichiga olishini isbot qilish mumkin. (n'xm') jadvalda bitta ham nomerlanuvchi belgi bo’lmasin deylik. U holda bu jadvalning har bir ustun va qatorida kamida ikitadan belgi joylashgan bo’ladi, ya’ni (n'xm') jadvaldagi belgilar sistemasi ham tartiblanuvchi bo’lmaydi. Demak, bunday zidlikda (nxm) jadvaldagi belgilar sistemasi ham tartiblanuvchi bo’lmaydi, chunki tartiblanuvchi belgilar sistemasini o’z ichiga olgan jadvalning ixti¸riy qismidagi belgilar sistemasi ham tartiblanuvchi bo’lishi kerak.

Etarliligi. Faraz qilaylik, (nxm) jadvalning ixti¸riy (n'xm') qismi kamida bitta nomerlanuvchi belgini o’z ichiga olsin. Bu holda (n'xm') jadvaldagi hamma belgilarni va demak, (nxm) jadvaldagi belgilarni birin-ketin nomerlash mumkin bo’ladi.

Transport masalasini differentsial rentalar usuli bilan echish uchun masalaning berilganlarini ushbu jadvalga joylashtiramiz

bi ai	b1		b2		...		bn
a1	^c11	1	^c12		...	^c1n
	^x11
a2	^c21		^c22	2	...	^c2n
			^x22
...	...		...		...		...
am	^cm1		^cm2		...		^cmn	n
							^xmn

So’ngra quyidagi ishlarni amalga oshiramiz.

1. 
   Har bir j, ( j  1, n)
   

uchun

min c_ij=c_kj (5.24)

i

topiladi va (k,j) katakchaning yuqori o’ng burchagiga belgi (kvadratcha) kiritiladi. Agarda j-ustunda (5.24) shartni qanoatlantiruvchi c_ij lar bittadan ko’p bo’lsa, u holda ulardan faqat bittasiga mos keluvchi katakchaga belgi kiritiladi.

2. 
   Yuqoridagi algoritm bo’yicha belgilar nomerlanadi.
   
3. 
   Birinchi nomerli belgidan boshlab, tartib bilan har bir belgi joylashgan (k,l) katakchaga mahsulot taqsimlanadi
   

X_kl=min (a_k,b_l)
Agar b_lk bo’lsa, x_kl=b_l bo’ladi va a_k ning qiymati a_k-b_l ga o’zgaradi. Agarda a_kl bo’lsa,

x_kl=a_k bo’lib, b_l ning qiymati b_l-a_k ga o’zgaradi.

4. 
   Har bir j-ustun uchun
   

 _ x ,
m


b
t (t )

j ij

i1

(5.27)

ya’ni j-iste’mol qiluvchi punktga keltirilgan mahsulotlar yig’indisi topiladi, bu erda t-tsiklning nomeri.

5. 
   Ustun xarakteristikasi (y.x.) topiladi. Agar j-ustun uchun
   

b

j

j
^t  b

bo’lsa, ya’ni j-punktning mahsulotga bo’lgan talabi qondirilmagan bo’lsa, u holda jadvaldagi ustun xarakteristikasi (y.x.) ni ifodalovchi qatorda j-ustun uchun (-) ishora qo’yiladi.

6. 
   Qator xarakteristikasi (q.x) topiladi buning uchun belgilarni teskari tartibda bir marta qarab chiqib, minus ishorali ustundagi belgi joylashgan qatorga minus ishora qo’yiladi.
   

Agar belgi minus ishorali i-qatorda joylashgan bo’lib, bu belgi joylashgan (i,j) katakchadagi x_ij>0 bo’lsa, j-ustunga ham minus ishora qo’yiladi. Hamma belgilarni bir marta qarab chiqqandan so’ng qolgan qator va ustunlarga plyus ishora qo’yiladi.

7. 
   Har bir minus ishorali j-ustun uchun differentsial renta
   

  min c^  c^[]
j _i ij ij

topiladi, bu erda c^ - plyus ishorali qatordagi transport xarajatlarini va c^[] - belgisi bor katakchadagi

ij ij

transport xarajatini ko’rsatadi.

8. 
   min  _j i
   

  _k

shartni qanoatlantiruvchi k-ustundagi minimal xarajat joylashgan (l,k)

katakchaga qo’shimcha belgi kiritiladi. So’ngra yangi tsiklga o’tiladi. Yangi tsiklga o’tish uchun yana jadval tuziladi. Yangi jadvalga a_i, b_j lar va musbat ishorali qatordagi c_ij lar oldingi jadvaldan o’zgarmasdan ko’chirildi. Minus ishorali qatordagi transport xarajatlari (c_ij) ga _k qo’shiladi, ya’ni

(c_ij )'  c_ij   _k .

Yangi jadvalga belgilar nomersiz ko’chiriladi. Agar birorta j-ustunda ikkita belgi joylashgan bo’lib ulardan biri musbat qatorda, ikkinchisi esa minus ishorali qatorda ¸tsa, minus ishorali belgi yangi jadvalga ko’chirilmaydi.

Yangi tsikl belgilarni nomerlashdan boshlanadi va yuqoridagi 2-8 punktlarda qilingan ishlar yana qaytadan takrorlanadi. Bunday takrorlanish masalaning optimal echimi topilguncha, ya’ni

 b

j j
barcha j lar uchun b ^t

yoziladi.

Faraz qilaylik,

tenglik bajarilguncha davom etadi. So’ngra masalaning optimal echimi

x*₁₁, x*₂₁, ..., x*_mn

masalaning optimal echimi bo’lsin, u holda bu echimdagi umumiy transport xarajatlari quyidagiga teng bo’ladi:
Y_min=c₁₁x*₁₁+c₂₁x*₂₁+...+c_mnx*_mn

bi ai	200			200			100			100			250				q.X.
100	10			7			4			1	4		4				+
										100
250	2	1	7			10			6			11				+
	200
200	8			5	2	3		3	2			2		5	-
				200			0					0
300	11			8			12			16			13				+
b1j	200			200			0			100			0
U.X.	+			-			-			+			-
 j				2			1						2				 min^=1

Misol. Differentsial rentalar usuli bilan quyidagi masalani echamiz. I.

II.

bi ai	200			200			100				100			250				q.X.
100	10			7			4		5		1	3		4				-
							0				100
250	2	1	7 3			10				6			11				+
	200
200	9			6	2	4		6		3			3		4	-
				200			0						0
300	11			8			12				16			13				+
b2j	200			200			0				100			0
U.X.	+			-			-				-			-
 j				1			6				5			8				 min^=1

III.

bi ai	200		200					100				100			250				q.X.
100	11		8					5		4		2	2	5				-
								0				100
250	2	1	7	5		10					6			11				-
	200		50
200	10		7		6		5		7		4			4		3	-
			0					0							200
300	11		8					12				16			13				+
b3j	200		50					0				100			200
U.X.	-		-					-				-			-
 j	9		1					7				14			9				 min^=1

3. 
   
   

bi ai	200		200			100		100				250			q.X.
100	12		9			6	4	3		2		6			-
						0		100
250	3	1	8	5	11			7			12			+
	200		0
200	1		8			6	6	5				5	3		-
						0						200
300	11		8	4	12			16			13			+
			200
b4j	200		200			0		100				200
U.X.	+		+			-		-				-
 j						5		4				7			 min^=4

V.

bi ai	200			200					100				100						250					q.X.
100	16			13					10	6		7			7		10					-
									100				0
250	3	1	8		5		11				7			8		12					-
	200			0									50
200	15			12					10	3		9						9		2			-
									0									200
300	11			8		4		12				16						13					+
				200
b5j	200			200					100				50						200
U.X.	-			+					-				-						-
 j	8								2				9						4					 min^=2

VI.

bi ai	200		200			100				100			250			q.X.
100	18		15			12		7		9	8		12			+
						0				50
250	5	1	10			13				9	4		14			+
	200									50
200	17		14			12		5		11			11	3		-
						0							200
300	11		8	2	12		6		16			13			+
			200			100
b6j	200		200			100				100			200
U.X.	+		+			+				+			-
 j													1			 min^=1

VII.

bi ai	200		200		100		100		250			q.X.
100	18		15		12	6	9	7	12	8
					0		50		50
250	5	1	10		13		9	3	14
	200						50
200	18		15		13		12		12	4
									200
300	11		8	2	12	5	16		13
			200		100
b7j	200		200		100		100		250
U.X.

Shunday qilib, VII tsiklda optimal echim topildi. Masalaning javobini ¸zish uchun topilgan optimal rejani dastlabki jadvalga joylashtiramiz:

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

Optimal reja

x₁₄=50, x₁₅=50, x₁₅= 0 x₂₁=200, x₂₄=50, x₃₅=200,

x₄₂=200, x₄₃=100, Y_min=150+450+650+2200+2200+8200+12100=4150