Differentsial rentalar usuli (Brudno usuli)

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