Telekommunikatsiya texnologiyalari davlat toshkent axborot texnologiyalari universiteti nukis filiali

3.1. Ba`zi transport masalalarni potentsiallar usuli bilan yechish.

3.1.1.-Misol. Yuqoridagi shimoliy-g`arbiy burchak usuli bilan echilgan guruch masalasining yechimini optimallikka potentsiallar usuli bilan tekshiraylik.

Band kataklar uchun potentsiallarni aniqlaymiz.
u₁ +v₁ = 5  u1 ⁼0
u1 +v2 = 6  u2 =−3
_u2 +_v2 = ₃  ⇒ u1=0 v₁ =5
u2 +v3 =11_ v₂ ⁼6
v₃ =14
Endi barcha bo`sh kataklar uchun yordamchi tarifni (soxta tarifni) c<sup>1</sup><sub>ke</sub> = u<sub>k</sub> + v<sub>e</sub> tenglik orqali aniqlaymiz:
c131 = u1 + v3 = 0 +14 =14
c<sub>21</sub> = u<sub>2</sub> + v<sub>1</sub> = −3+ 5 = 2
Endi har bir bo`sh kataklar uchun tariflar farqini aniqlaylik
^SS1321 ==CC1321−−CC13121¹ ==87−−142==5−6
bularning ichida manfiy bor, demak yechim optimal emas. Bu yechimni optimallashtirish uchun quyidagicha ish qilamiz:
Endi barcha manfiy S_ke larning ichida eng kichigini belgilab, uni qutb deb, ataymiz va qutbni «+» deb, keyingi uchini «-» deb, ularni navbat bilan almashtirib, uchlari band kataklarda yotuvchi tsikl yopiq siniq chiziq quramiz (chizmadagi kabi).
Endi barcha «-» ishorali kataklar ichidagi yuklardan eng kichik miqdorini aniqlab, o`sha miqdordagi yukni barchak «-» kataklardan olib, «+» ishorali kataklardagi yuklarga qo`shamiz.
Natijada yangi reja paydo bo`ladi <sup></sup><sub></sub>0<sup>20</sup>; <sup>;</sup> 30<sup>5;</sup>; <sup>15</sup>0 <sup></sup><sub></sub>. Hosil bo`lgan rejani dastlabki
reja sifatida qarab, barcha yuqoridagi tadbirlarni takrorlaymiz va optimallikka tekshiramiz. Agar optimallik sharti bajarilmasa, bu jarayonni yana takrorlaymiz va hokazo.

		v1		v2		v3
	bj ai	20		35		15
u1	40	20	5	5	6	8 15
u2	30	0	7	30	3	11 0

Band kataklar uchun potentsiallarni aniqlaymiz.
u1 =0
u1 +v1 = 5 
u1 +v2 = 6 v1 =5
uu1₂ ++vv3₂ ==8⇒ u1 = 0 desak, vv32 ==86
3 u2 =−6+3=−3
Shunday qilib, band kataklarning potentsiallari: u₁ = 0; v₁ = 5 u₂ =−3; v₂ = 6 v₃ = 8
Endi barcha bo`sh kataklar uchun yordamchi tarifni (soxta tarifni) C<sub>ke</sub><sup>1</sup> <sub>=</sub>U<sub>k</sub> +V<sub>e</sub> tenglik orqali aniqlaymiz.
c<sup>1</sup><sub>21</sub> =u<sub>2</sub> +v<sub>1</sub> =−3+5=2
Endi har bir bo`sh katak uchun tariflar farqini aniqlaymiz.
ske =cke −c1ke =cke −(uk +ve)
SS ₂₁23 ==117 −−25==56⇒ _optimal. bularning ichida manfiy yo`q, demak yechim
Demak, optimal reja Χ ={20;5;15;0;30;0} ёки Х = <sub></sub><sup></sup>0<sup>20</sup>30<sup>5 15</sup>0 <sup></sup><sub>
</sub>
f <sub>=</sub> 5<sub>⋅</sub>20 <sub>+</sub> 5<sub>⋅</sub>6 <sub>+</sub> 30<sub>⋅</sub>3 <sub>=</sub>100 <sub>+</sub> 30 <sub>+</sub> 90 <sub>+</sub>120 <sub>=</sub> 340 so`m ketgan harajat.
2-misol.

30 60 0 0 _
Χ = 40 0 0 30^_
_1 0 0 0 0 _
Band kataklar uchun potentsiallarni aniqlaymiz. v1 = 2
uuu12 ===00 vv32 ==11
1
3 v4 =1
u1 +v1 =2 u1 = 0 u1 +v2 =1 v1 = 2; v2 =1
uu22 ++vv14 ==21 uv42 ==12−−uv21 ==12 − 2 = 0  ⇒ u1=0 desak,
u₃ ⁺v₁ ⁼3^ u₃ = 3−v₁ = 3− 2 =1 u₃ ⁺v₃ ⁼2 v₃ = 2 −u₃ = 2 −1=1
Endi bo`sh kataklar uchun yordamchi narxlarni (soxta narxlarni) hisoblaymiz.
c<sub>13</sub><sup>1</sup> = u<sub>1</sub> + v<sub>3</sub> = 0 +1=1 c141 = u1 + v4 =1 c<sup>1</sup><sub>22</sub> = u<sub>2</sub> + v<sub>2</sub> = 0 +1=1 c123 = u2 + v3 =1
c<sub>32</sub><sup>1</sup> = u<sub>3</sub> + v<sub>2</sub> =1+1= 2 c<sub>34</sub><sup>1</sup> = u<sub>3</sub> + v<sub>4</sub> =1+1= 2
Endi har bir bo`sh katak uchun tariflar farqini xisoblaymiz . s₁₃ =3−1=2 s₁₄ =2−1=1 s22 =3−1=2 s₂₃ =3−1=2 s₃₂ =3−2=1
s₃₄ =1−2=−1
S₃₄=-1 manfiy chiqdi, demak reja optimal emas. Uni optimallashtirish kerak.
Shuning uchun S₃₄ ni ya`ni (3:4) ni qutb boshi deb yopiq tsikl quramiz.

b_j a_i 80 60 40 30

90 2 1 3 2

30 60 0 0 70 2 3 3 1

50 0 0 20
30 3 3 2 1
0 0 40 10

30 60 0 0 _
Χ = 50 0 0 20_ _0 0 40 10_
Yana band kataklar uchun potentsiallarni tekshiramiz.
u1 + v1 =2c131 = u1 + v3 = 0 + 2 = 2s13 = 3 − 2 =1
uu12 ++vv21 ==12 uu1 = 0; vv12 ==21 cc141122 == 00++11==11 ss1422 ==23 −−11==12 uu₃2 ++vv₃4 ==12⇒ u32 == 00;; vv34 ==12cc311123 == 00++22 == 22ss3123 ==33−− 22==11
u3 + v4 =1c321 = 0 +1=1s32 = 3 −1= 2
manfiy yo`q, demak reja optimal (yechim optimal)
30 60 0 0 <sub></sub>
Χ <sub>=</sub> 50 0 0 20<sup></sup><sub></sub> bo`lar ekan.
_0 0 40 10_
Demak transport uchun ketgan xarajat
f ₌60₊60₊100₊20₊80₊10₌330 so`m bo`ladi.

§4. Transport masalasini yechishning Venger usuli.

Venger usuli, transport masalalarini yechishning juda keng tarqalgan usullaridan biri hisoblanadi. Dastlab, venger usulining asosiy g`oyalarini transport masalasining yakka holda hisoblangan, tanlash masalasi yoki masalani yechish misolida ko`rib chiqamiz, keyin bu usulni hohlagan transport masalasi uchun umumlashtiramiz.

4.1. Tanlash masalasi uchun Venger usuli.

Masalaning qo`yilishi: n turli ishlar va har biri hohlagan ishini bajara oladigan mexanizmlar bor deylik. A<sub>1</sub> ishini bajarishdagi B<sub>1</sub> mexanizmining unimdorligini bilan belgilaymiz.
Mexanizmlarni ishlarga shunday qilib joylashtirish kerak, ularni ishlatishdan (foydalanadigan) umumiy effekt maksimal bo`lishi kerak. Bunday masala tanlash masalasi deb ataladi.
Tanlash masalasi quydagi ko`rinishda yoziladi
 
c11 c12 . . . c1n 
 
c21 c22 . . . c2n
C = <sub> </sub> matritsadan, elementlarning
<sup></sup>. . . . . . . . .<sup></sup>
 
 
cn1 cn2 . . . cnn
n
shunday ketma-ketligini tanlash kerak, bunda ∑C<sub>kik</sub> summasi maksimal bo`lishi
k=1 kerak va bunda har bir C qator va ustunlardan faqat bir element tanlangan bo`lishi kerak.
Quyidagi tushinchalarni kiritamiz:

1. 
   C matritsaning nulinchi elementlarni mustaqil nollar deb ataladi, agar hoxlagan uchun, ularning kesilishida elementi joylashgan qator va ustun boshqa nollarga ega bo`lmasa.
   
2. 
   C va D ikki to`g`ri burchakli matritsalar ekvivalentli ( ) deb ataladi, agar barcha uchun bo`lsa. Ekvivalent matritsalar bilan aniqlanadigan tanlash masalalari ekvivalentli hisoblanadi.
   
3. 
   Ajiratilgan qator yoki ustunda joylashgan elementlar ajiratilgan elementlar deb ataladi.
   

4.2. Venger usuli algoritmini ta`riflash.

Algoritm, oldingi bosqichdan va (n-2) ko`p bo`lmagan ketma-ket o`tkaziladigan iteratsiyalardan iborat. Har bir iteratsiya, mustaqil nollarning maksimal sonlarini tanlash va o`tkazilgan avvalgi iteratsiya natijasida olingan matritsaning ekvivalentl o`zgarishlari bilan bog`liq. Iteratsiyaning yakunlovchi natijasi mustaqil nollar sonining birga ko`payishi bo`ladi.
Mustaqil nollar sonining miqdori n-ga teng bo`lganda tanlash masalasi (muammosi) echilgan hisoblanadi, optimal variant esa oxirgi matritsadagi mustaqil nollar pozitsiyasi bilan aniqlanadi.
Oldingi bosqich. j ustundan maksimal element qidiriladi va bu ustunning barcha elementlari ketma-ket maksimaldan olinadi. Bu operatsiya matritsaning barcha ustunlariga ishlanadi. Natijada, har bir ustunda kamida bitta noldan bor, teskari emas (neotritsatel`n_ыy) elementlarga ega matritsa faydo bo`ladi. Olingan matritsaning j–chi qatorini ko`rib chiqamiz va uning har bir elementidan shu qatorning minimal elementini olib chiqamiz. ni 1–dan n–gacha o`zgartib teskari emas elementlarga ega matritsani olamiz, uning har bir qator va ustunida kamida bitta nol mavjud. Birinchi ustundagi nolni yulduzcha bilan belgilaymiz.
Keyin ikkinchi ustunni ko`rib chiqamiz, agar yulduzchali nol yo`q qatorda nol bor bo`lsa, unda uni yulduzcha bilan belgilaymiz.
matritsaning barcha ustunlarini birma-bir ko`rib chiqamiz.
matritsaning yulduzcha bilan belgilangan nollari tuzilishi bo`yicha mustaqil hisoblanadi. Shu bilan oldingi bosqich yakunlanadi.
(k+1) – li iteratsiya. k – li matritsa o`tkazilgan va natijada matritsa olingan deylik. Agar matritsada yulduzchali nollar soni n bo`lsa, unda yechish jarayoni yakunlanadi. Agar yulduzchali nollar soni n – dan kam bo`lsa, unda (k+1) – li iteratsiyaga o`tamiz.
Har bir iteratsiya birinchi bosqichdan boshlanib ikkinchisi bilan tamomlanadi. Ularning orasida bir necha juft bosqich o`tkazilishi mumkin: uchunchi – birinchi. “+” belgili iteratsiya boshlanishdan oldin, yulduzchali nollar bor matritsaning ustunlari belgilanadi.