Transport masalasini yechishning potentsiallar usuli

Transport masalasini yechishning potentsiallar usuli Reja: Berilgan masalani transport jadvaliga joylashtirish. iste'molchi va ta'minotchining potentsiallarini belgilash. Potentsiallar uchun tenglamalar tuzish. Yangi jadvalga utish uchun yopiq kontur tuzish mahsulotlarni taksimlash. Optimallik shartini tekshirish. Potentsiallar usuli erdami bilan boshlang'ich tayanch plandan boshlab, optimal yechimga yaqinrok bo'lgan yangi tayanch planlarga utib borib, chekli sondagi iteratsiyadan sung masalaning optimal yechimi topiladi. Xar bir iteratsiyada topilgan tayanch plan optimal plan ekanini tekshirish uchun xar bir ishlab chikaruvchi (Ai) va istemol qiluvchi (Bj) punktga uning potentsiali deb ataluvchi miqdor ui va vj mos kuyiladi. Bu potentsiallar shunday tanlanadiki, bunda o'zaro boglangan Ai va Bj punktlarga mos keluvchi potentsiallar yig'indisi sij ga teng bo'lishi kerak. Teorema. Agar X*=(xij*) plan transport masalasining optimal plani bulsa, u holda unga ui*+ vj*= cij, (xij*0), (1) ui*+ vj* cij, (xij*=0) (2) shartlarni kanoatlantiruvchi n+m ta ui* va vj* potentsiallar mos keladi. Potentsiallar usulining algoritmi kuyidagilardan iborat: yuqoridagi kurilgan usullarning biridan foydalanib, boshlang'ich plan topiladi. Topilgan planni optimal plan ekanligini tekshirish uchun potentsiallar sistemasi tuziladi. Buning uchun formuladan foydalanib, xar bir tuldirilgan katakcha uchun ko'rinishda potentsial tenglamalar tuziladi. Malumki, transport masalasining planidagi 0 dan farqli bo'lgan o'zgaruvchilar soni n+m-1 ta. Demak, potentsial tenglamalar sistemasi n+m ta nomalumli n+m-1 tenglamalar sistemasidan iborat bo'ladi. Bu sistemada nomalumlar soni tenglamalar sonidan ortik bo'lganligi sababli, potentsiallarning son qiymatini topish uchun ulardan ixtieriy bittasiga ixtieriy qiymat, soddalik uchun nol qiymat berib, kolganlarini birin- ketin topish mumkin. Faraz kilaylik, ui malum bulsin, u holda vj topiladi: vj =cij- ui Agar vj malum bulsa, u holda ui kuyidagicha topiladi: ui =cij- vj Barcha potentsiallarning son qiymatini aniklab bulgach, xamma bush kataklar uchun hisoblanadi. Agarda barcha i va j lar uchun urinli bulsa, topilgan boshlang'ich plan optimal plan bo'ladi. Agar i va j larning kamida bir qiymati uchun bulsa, boshlang'ich tayanch plan almashtiriladi. Buning uchun shartni kanoatlantiruvchi (l,k) katakcha tuldiriladi ( nomalum bazisga kiritiladi), = deb faraz qilib (l,k) katakchaga kiritiladi. Sungra soat strelkasi bo'yicha (l,k) katakchadan boshlab uchlari tuldirilgan kataklarga to'g'ri keluvchi to'g'ri burchakli yopiq (kontur bo'yicha) harakat qilib tuldirilgan katakchalarga kontur uchlariga tartib bilan (-) va (+) ishoralar kuyib boriladi. Natijada yopiq K kontur hosil bo'ladi: bu yerda , -(-) va (+) ishorali katakchalarni o'z ichiga oluvchi yarim konturlar. quyidagi formula orqali ning son qiymati topiladi. Yangi tayanch plan hisoblanadi: Topilgan yangi tayanch plan uchun yana qaytadan potentsiallar sistemasi topiladi va yangi planning optimal plan bo'lishlik sharti tekshiriladi. Agar yangi tayanch plan optimal plan bulmasa, u holda yana ...