Transport masalasini optimal rejasini topish

Transport masalasini optimal rejasini topish Reja: 1. Transport masalasini optimal rejasini topish 2. Muvozanatsiz (ochiq) transport masalasi Transport masalasini optimal rejasini topish Transport masalasining optimal rejasini topish usullari ichida eng qulay bo'lgani potentsiallar usuli hisoblanadi.Bu usul rejani ketma ket yaxshilash usuli bo'lib, u transport masalasining xususiyatlarini hisobga oladi. Potentsiallar usulida optimal rejani topish uchun avvalo biror usul bilan boshlang'ich bazis reja quriladi. Transport masalasi yechimining har bir qadami ikkita bosqichdan iborat. Birinchi bosqichda biror usul bilan topilgan X boshlang'ich bazis rejaning optimalligi tekshiriladi. Buning uchun potentsiallar sistemasi: -ishlab chiqarish potentsiallari -istemol potentsiallari aniqlanadi. Transport xarajatlari matritsasi dagi tekshirilayotgan X reja bazis komponentlariga mos elementlar belgilab olinadi (* bilan). Shunday elementlar soni (mQn-1) ta va ular uchun tengliklar bajariladi. Bu tengliklar sistemasida (nQm-1) ta tenglama bo'lib (mQn) ta nomalum bor, yani tenglamalar sonidan nomalumlar soni bittaga ortiq. Bunday sistema cheksiz ko'p yechimga ega. Berilgan reja uchun sistemaning ixtiyoriy yechimi o'rinli bo'lib uning birorta yechimini topish uchun potentsiallardan biriga ixtiyoriy qiymat beramiz, (masalan, 0) qolganlarini sistema tenglamalari yordamida topamiz. Shartlar vektorlari baholari matritsasini quramiz. Rejaning bazis komponentlariga mos baholar 0 ga teng qolganlari ixtiyoriy ishorali. Agar hamma baholar musbatmas bo'lsa , tekshirilayotgan reja optimal bo'ladi. Agar ularning ichida hech bo'lmaganda bittasi musbat bo'lsa ham, X reja optimal emas. Bu holda ikkinchi bosqichga o'tiladi. Ikkinchi bosqich avvalgi rejadan ko'ra maqsad funksiyasiga kichikroq qiymat beradigan yangi rejani qurish bilan xarakterlanadi. X rejaning yangi rejaga kiritiladigan o'zgaruvchisi, yani eng katta bahoga ega o'zgaruvchi tanlanadi. Bazisga kiradigan o'zgaruvchini shu yo'l bialn tanlab oldik. Endi bazisdan chiqariladigan o'zgaruvchini tanlash uchun rejaning musbat elementlaridan kiritiladigan o'zgaruvchida yopiladigan zanjir tuzamiz. Buni yuqorida aytib o'tilgan «o'chirish usuli» dan foydalanib topish mumkin. Buning uchun zanjirni tartib bilan nomerlaymiz. Toq nomerdagi qiymatlarni oshiramiz, juft nomerdagilarini kamaytiramiz. Zanjirdagi juft nomerda turgan ishorali elementlar ichidan eng kichik qiymatni tanlab olamiz. Shuni juft nomerdagilardan ayiramiz, toq nomerdagilarga qo'shamiz. Ana shu eng kichik qiymat to'g'ri kelgan o'zgaruvchi bazisdan chiqariladi. Shundan so'ng yangi bazis rejasi tuziladi, undagi zanjirga kirmagan elementlar o'zgarishsiz qoladi, zanjir elementlari yuqorida aytilgandek o'zgaradi. Yangi bazis reja transport masalasining bazis rejasi ekanligini va unda maqsad funksiyasining qiymati avvalgisidan ko'ra kamayganligini tekshirish qiyin emas. Nihoyat chekli sondagi qadamlardan so'ng optimal reja topiladi. Yangi bazis rejani tuzishda, bazisdan birdaniga bir necha o'zgaruvchi yo'qotilishiga to'g'ri keladi, yani 0 dan farqli elementlar soni (mQn-1) dan kam bo'ladi. Bunday reja xos reja deyiladi. Amalda bunday xos transport masalalari tez-tez uchrab turadi. Xos holida bazis komponentlari musbat son bo'lishidan tashqari ...