Transport masalasining optimal yechimini topishning potentsiallar usuli

Transport masalasining optimal yechimini topishning potentsiallar usuli Reja: Boshlang'ich tayanch yechimning optimallik sharti teoremasi. Potentsiallar usuli algoritmi. Misol. Ochiq modeli transport masalasi Misol. Teorema: Agar transport masalasining X*=(x*ij) yechimi optimal bo'lsa, unga quyidagi shartlarni qanoatlantiruvchi m+n-ta sonlar sistemasi mos keladi: X*ij 0 lar uchun U*i + V*j = Cij X*ij = 0 lar uchun U*i + V*j Cij i=1,2,…,m; j=1,2,…,n. U*i va V*j sonlar mos ravishda «ta'minotchi va iste'molchilarning potentsiallari» deyiladi. Bu teoremaga ko'ra boshlang'ich tayanch yechim optimal bo'lishi uchun quyidagi ikki shart bajarilishi kerak: a) har bir band katak uchun mos potentsiallar yig'indisi shu katakdagi yo'l xarajati qiymatiga teng bo'lishi kerak: U*i + V*j = Cij (6) b) har bir bo'sh katak uchun mos potentsiallar yig'indisi shu katakdagi yo'l xarajati qiymatidan katta bo'lmasligi kerak: U*i + V*j Cij (7) Agar kamida bitta bo'sh katak uchun (7) shart bajarilmasa, ko'rilayotgan yechim optimal bo'lmaydi va bu yechimni bazisga (7) shart buzilgan katakdagi nomalumni kiritish bilan yaxshilash mumkin. Shunday qilib, navbatdagi tayanch yechimni optimallikka tekshirish uchun avval (6) shart yordamida potentsiallar sistemasi ko'riladi va so'ngra (7) shartning bajarilishi tekshiriladi. Potentsiallar usulining algoritmi 1. Boshlang'ich tayanch yechimni qurish; 2. (6) shart asosida potentsiallar sistemasini qurish; bunda m+n-1 ta band katak uchun m+n-ta chiziqli tenglama hosil bo'ladi. Nomalumlar soni tenglamalar sonidan bitta ortiq bo'lgani uchun bitta nomalum erkli bo'lib unga ixtiyoriy qiymat, masalan nol qiymati berilib qolganlari mos tenglamalardan topiladi; 3. Bo'sh kataklar uchun (7) shart tekshiriladi; a) bu shart barcha bo'sh kataklar uchun bajarilsa, yechim optimal bo'ladi va yechish jarayoni tugaydi; b) aks holda yechim optimal bo'lmaydi va keyingi yechimga o'tishga kirishiladi; 4. Keyingi yechimga o'tish uchun (7) shart buzilgan kataklarning o'ng past burchagiga tij = Ui + Vj - Cij qiymatlar yozib chiqiladi va bu qiymatlarning eng kattasi mos kelgan katakka «+» ishora qo'yiladi. «+» ishora qo'yilgan katakdan boshlab band kataklar orqali sikl quriladi, yani uchlari band kataklarda yotgan yopiq ko'pburchak hosil qilinadi. Bu ko'pburchakning uchlariga bo'sh katakdagi «+» dan ixtiyoriy yo'nalishda «-» va «+» ishoralari qo'yib chiqiladi. «-» ishorali kataklardagi yuk birliklaridan eng kami tanlanadi va shu miqdor barcha «-» ishorali kataklardan ayirilib, «+» ishorali kataklarga qo'shiladi, natijada yangi tayanch yechim hosil bo'ladi. Bu jarayon chekli sonda qaytarilgandan so'ng albatta optimal yechim hosil bo'ladi. Bu algoritmni quyidagi misolda batafsil ko'rib chiqamiz: Misol: 1- bosqich 2- bosqich Optimal yechim hosil bo'ldi: X11 = 100; X22 = 200; X23= 50; X35 = 200 X41 = 100; X43 = 50; X44 = 100; ...