Transport masalasini yechishning takribiy usullari

Transport masalasini yechishning takribiy usullari Reja: Transport masalsining takribiy usullari to'g'risida ma'lumot. Fogel usuli algoritmi. Fogel usulida misol yechish namunasi. Ikki marta afzallik usuli algoritmi. Ikki marta afzallik usuli bilan echilgan misol. Delta ( ) usul algoritmi. Delta usuli bilan echilgan misol. Takribiy usullar hosil bo'lgan yechimning optimalligiga kafolat bermaydi. Ammo ular matritsa o'lchami juda katta bo'lganda yoki qo'l ostida EHM bo'lmaganda juda qo'l keladi. Quyida shu usullarning bazi birlarining algoritmlarini keltiramiz. Fogel usuli algoritmi. 1. ma'lumotlarni tayyorlash. Transport masalasi shartlarining odatda keltiriladigan matritsa ifodasiga qo'shimcha ikkita ustun va ikkita satr kiritiladi. 2. Har bir ustun va satr bo'yicha shu ustun va satrdagi eng kichik qiymatlar o'rtasidagi ayirma topiladi va u qo'shimcha 1-ustun va 1-satrning mos kataklariga yozib chiqiladi. 3. Qo'shimcha 1-ustun va 1-satrdagi ayirmalar qiymatlaridan eng kattasi aniqlanadi va unga (*) belgi qo'yiladi. 4. Eng katta ayirmani ustun yoki satrning (* li) eng kichik transport xarajatli katagiga maksimal taqsimot miqdori yoziladi. 5. Qo'shimcha 2-ustun va 2-satrga shu ustun va shu satrdagi ortiqcha sig'im va quvvatlar yoziladi. Agar ortiqcha sig'im va quvvatlarning qiymati hamma ustun va satr kataklarida nolga teng bo'lsa, yechim olingan bo'ladi, aks holda hisoblashni yana 1-bosqichdan boshlash kerak. Keyingi bosqichlarda band kataklar eng kichik qiymatlar orasidagi farqli hisoblashda ishtirok etmaydi. Misol: I-bosqich: II -bosqich. II -bosqich. IV -bosqich. V -bosqich. VI -bosqich. F = 2*15 + 1*22 + 3*11 + 6*2 + 8*1 + 7*16 = 30 + 22 + 33 + 12 + 8 + 112 = 217 (pul birligi). Ikki marta afzallik usuli. Usul algoritmi. 1. Transport masalasining sharti berilgan matritsa jadvalining birlik mahsulotga bo'ladigan transport xarajatlarining qiymatlari ustunlar va satrlar bo'yicha ko'rib chiqiladi. Bu qiymatlarga (*) belgi qo'yiladi. 2. Bazi bir kataklar ikkitadan (*) belgiga ega bo'lib qoladi. Shunga ko'ra taqsimot avval ikkita (*) li kataklarda, ular tugagach, bitta (*) li kataklarda, keyin esa belgisiz kataklarning eng kichik elementli kataklariga maksimal taqsimotni kiritish bilan quvvatlar tugaguncha amalga oshiriladi. Misol. F = 2 * 11 + 2 * 4 + 1 * 22 + 6 * 2 + 8 * 12 + 7 *16 = 22+8+22+12+96+112 = 272 (pul birligi). Delta usuli. Usul algoritmi. 1. Trasport masalasi matritsasining standart jadvaliga yordamchi uchta ustun va ikkita satr chiziladi. 2. Har bir katakning chap tomoniga shu katak transport xarajati ele-mentidan ustundagi eng kichik qiymatga teng element ayirmasi (Δ i,j) yoziladi. 3. Har bir ustun bo'yicha Δi,j=0 bo'lgan katakka mos ta'minotchida mavjud quvvatlarning miqdoriga qaramasdan, shu ustun talabini ...