9-Maruza. Chiziqli dasturning transport masalasi

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 90⁰ 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 nu

qtalarini 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