Transport masalasi. Chiziqli programmalashtirish masalasining kompyuter texnologiyalari yordamida yrchish
Transport masalasini yechish usullari
Download 125.98 Kb.
|
1 2
Bog'liqTRANSPORT MASALASI.CHIZIQLI PROGRAMMALASHTIRISH MASALASINING KOMPYUTER TEXNOLOGIYALARI YORDAMIDA YRCHISH
- Bu sahifa navigatsiya:
- Yuk tashish tayanch planni topish.
- Yuk tashish rejasini optimallashtirish. Qayta hisoblash sikli.
Transport masalasini yechish usullari.
Transport masalasini yechish simpleks usuldan foydalanilmaydi,aksincha jadvalda ma’lum bir amal bajariladi.
ПН – qabul punktlari ПО – jo’natish punktlari Yacheykalarda yozilgan 0 dan farqli lari basiz xisoblanadi, qolganlari esa mustaqil xisoblanadi. Transport masalasini yechishda shunday musbat qiymatlar topiladigi ularni basiz yacheykalariga qo’shishda quydagi natijalarni bersin. a. Qatorlardagi yuk tashish summasi jo’natish punktlaridagi yuk zaxirasiga teng bo’lsin. b. ustundagi yuk tashish summasi qabul qilish punktlarining so’rovlariga teng bo’lish kerak. v. umumi yuk tashish qiymati. Yuk tashish tayanch planni topish.Matematik dasturlash masalasining barcha usullari kabi transport masalasida yechim avvalo tayanch planni topishdan boshlanadi, lekin boshqa usulardan farqli o’laroq tayanch plan transport masalasida xar doim mavjud bo’ladi. Tayanch planni topishning ko’plab usulari mavjud. Ulardan biri shimoly g’arbiy burchak usuliI(taqsimlovchi usul). Misol uchun: jadvalda transport masalasi berilgan,uning tayanch yechimini toppish talab qilinsin.
Bazis yacheykalar soni ga teng. Topilgan yechim nafaqat mumkin bo’lgan reja, balki tayanch reja ham hisoblanadi, chunki basiz yuk tashishlar soni ga teng. Lekin, usbu yechim optimal? Yo’q, chunki ushbu plan ko’rinishida narx hisobga olinmagan. Tayanch yechim uchun Е=1018+827+53+830+100+812+76+820=1034 Endilikda ushbu tayanch yechimga yanada yaqinlashishga urinib ko’ramiz. Buning uchun, (1.1) yacheykadan 18 birlini (2.1) ga ko’chiramiz. Balansni buzilmaslik uchun (2.3) yacheykadan (1.3) ga 18 birlikni tushiramiz. Shundan so’ng bizda yangi plan Е=913bo’ladi.Biz18 birlik yukni yacheykadan yacheykaga ko’chirichda yuk tashish rejasi optimallashtirish mumkin. Yuk tashish rejasini optimallashtirish. Qayta hisoblash sikli.Oldingi misolda ba’ziyuk tashishlarni yopiq sikl bo’ylab ko’chirish orqali yuk tashish planini yaxshilashga urindik. Olaylik quydagi transport jadvali berilgan bo’lsin. Sikl – bu, shunday bir nechta kataklar to’plamini ular yopiq siniq chiziqlar orqali ulangan bo’ladi va har bir katakda 900 ga buriladi. Misolda 2 ta sikl ko’rsatilgan. Biri 4 kattalikli, ikkinchisi 8 kattalikli Ko’rinib turibtiki, har bir sikl juft kattalikka va strelkaga ega bo’ladi. Strelkalar esa siklni aylanish yo’nalishini ko’rsatadi. «+» belgi siklning kata qiymatga erishadigan nuqtasi. «-» belgi siklni minimal qiymatga erishadigan nuqtasi. Qandaydir yuk miqdorini boshqa yacheyga ko’chirish ostida siklning kata qiymatga erishadigan nuqtalarini kamaytirish va kichik qiymatli nuqtalarni oshirish kerak. Bunday almashtirish natijasida so’rovlar va zahiralar balansi o’zgarmaydi. Lekin yuk tashish summasi kamayishi yoki ko’payishi mumkin. Sikl summasi belgilangan sikl bo’yicha har birlik yukni ko’chirishda yuk tashish narxining oshishi deyiladi. Siklning summasi siklning yuqori nuqtalaridagi algebraic summasiga teng. “-“ belgilar va “+” belgilar alohida qo’shiladi. Masalan, narxi narxi . Sikl narxini deb belgilaymiz. Bir birlik yukni sikl bo’yicha ko’chirsak uning narxi ga o’zgaradi. Agar k birlik yukni ko’chirsak, sikl bo’yicha sikl narxi k ga o’zgaradi. Demak, yaxshilash uchun yuk birliklarini faqatgina manfiy qiymatga ega bo’lgan sikllarda ko’chirish mantiqqa mos keladi. Chunki, yuk tashishlar manfiy qiymatda bolmasligi lozim. Shunday sikllardan foydalanamizki, ulardagi manfiy qiymatlar bazis kataklarda yotadi. Agarda manfiy qiymatkli sikl qolmasa, bu jadvalni yanada optimallashtirish mumkin emas, chunki optimal yechim topilgan hisoblanadi. Qadamma-qadam yaxshilanish usuli asosi quyidagicha, shunday manfiy qiymat beruvchi sikllar topiladi va ularga yuk tashishlar ko’chirilish orqali yaxwilab boradi va bu hol manfiy qiymat qolmaguncha davom ettiriladi. Har bir qadamda 1 ta bazis o’zgaruvchi mustaqil o’zgaruvchiga almashtirilib boriladi. Bunday almashtish jarayonida bazis o’zgaruvchilar soni bo’lib o’zgarmay qoladi. Misol berilgan transport masalasini optimal qiymatga erishtirish lozim. Tarqatma usul orqali tayanch yechim topilgan: Е1=1022+79+625+523+618+720=796. Bazis o’zgaruvchilar soni . (2.4) kattakni egallab rejani yaxshilaymiz. Ushbu sikl narxi ga teng. Quyida yangi yaxshilangan reja: Download 125.98 Kb. Do'stlaringiz bilan baham: |
1 2
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling