Transport masalasining dastlabki rejasini topish usullari

Transport masalasining dastlabki rejasini topish usullari Reja: 1. «Shimoliy-g'arbiy burchak» qoidasi (usuli). 2. Eng kam (minimal) xarajatlar usuli 3. Potentsiallar usuli. 4. Bazi transport masalalarni potentsiallar usuli bilan yechish 1. «Shimoliy-g'arbiy burchak» qoidasi (usuli). Transport masalasining yechimini yani optimal rejasini topish uchun dastlab biror reja topiladi. Bunday rejani topish usullaridan biri «Shimoliy-g'arbiy burchak» qoidasidir. Bu qoida quyidagicha ifodalanadi. Aytaylik, transport masalasi jadval ko'rinishda berilgan bo'lsin (1-jadval). Maqsad va lar kesishuvidagi kataklardagi mahsulot miqdorini aniqlashdan iborat. Kataklarni to'ldirishni jadvalning shimoliy-g'arbiy burchagidan, yani va kesishgan katakdan boshlaymiz. Bu katakka mos keluvchi mahsulot (yuk) miqdori a1 ga teng bo'lib, talab esa b1 miqdordan iborat. Bu katakka a1 va b1 dan qaysi biri kichik bo'lsa, shuni joylashtiramiz, yani Agar a1 b1 bo'lsa, demak, katakka a1 , agar b1 a1 bo'lsa esa katakka b1 ni yozamiz. Ravshanki, a1 b1 bo'lgan holda, 1- satrdagi boshqa barcha kataklarga 0 miqdoridagi yuk mos keladi, chunki, mavjud yukning barchasi b1 iste'molchiga yuborildi. Agar b1 a1 bo'lsa, 1- ustundagi barcha kataklarga 0 miqdor mos keladi, chunki mavjud talab 1-katakdayoq to'la qondirildi. Shunday qilib, birinchi qadamda 1- satr yoki 1- ustun kataklarining barchasi to'ldiriladi. Ikkinchi qadam sifatida 2-katakni to'ldirishga o'tamiz. Ravshanki, agar a1 b1 bo'lsa, bu katak A2 va V1 kesishgan katak bo'ladi. Agar b1 a1 bo'lsa, bu katak A1 va V2 kesishgan katak bo'ladi. Bu katakni ham avvalgi katak singari to'ldiramiz. Biroq, bu katakni to'ldirishda 1-katakka tushirilgan yukni inobatga olamiz, yani, agar a1 b1 bo'lsa, 1-ustundagi 2- katakka ni joylashtiramiz Agar b1 a1 bo'lsa, 1- yo'ldagi 2- katakka ni joylashtiramiz va bu jarayon barcha katak to'lguncha davom ettiriladi. 1-Misol. Yuqoridagi shakar masalasini ko'raylik. 1-katakka x11=min80; 30=30 ni yozamiz. Shundan so'ng, birinchi ustundagi barcha kataklarga 0 yozamiz. So'ng A1 punktda 80-30=50 birlik mahsulot qolganini inobatga olib, keyingi katakni, yani 1-yo'l, 2-ustundagi katakni to'ldiramiz: X12=min 50; 10 =10 Ikkinchi ustunning ham qolgan kataklariga 0 lar yozamiz, kataklarni shu usulda to'ldiramiz. X13=min40; 90=40 X23=min25; 50=25 X33=min35; 25=25 Shunday qilib, quyidagi tayanch rejaga ega bo'ldik: X=30; 10; 40; 0; 0; 0; 25; 0; 0; 0; 25; 10. Aniqlangan tayanch rejaga mos keluvchi xarajat f=304+103+404+252+257=535 so'm bo'lar ekan. 2-misol. (Guruch masalasi). Transport masalasidagi guruchlarni do'konlarga yetkazish masalasini ko'raylik. Transport uchun ketgan eng kam xarajat f=520+620+315+115=430 so'm 2. Eng kam (minimal) xarajatlar usuli Shimoliy-g'arbiy usul bilan tayanch rejani topish jarayonida tashish xarajatlari larni etiborga olmadik. Shu sababdan topilgan reja optimal rejadan ancha uzoq bo'lishi mumkin. Bu esa optimal rejani topishni qiyinlashtiradi. Agar tayanch rejani ...