Transport masalasi. Chiziqli programmalashtirish masalasining kompyuter texnologiyalari yordamida yrchish

Transport masalasini yechish usullari.
Transport masalasini yechish simpleks usuldan foydalanilmaydi,aksincha jadvalda ma’lum bir amal bajariladi.

ПН ПО	B1	B2	…	Bn	Запасы ai
A1	c11	c12	…	c1n	a1
A2	c21	c22	…	c2n	a2
…	…	…	…	…	…
Am	cm1	cm2	…	cmn	am
Заявки bj	b1	b2	…	bn

ПН – 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.

ПН ПО	B1	B2	B3	B4	B5	Запасы ai
A1	10 18	8 27	5 3	6	9	48
A2	6	7	8 30	6	5	30
A3	8	7	10 9	8 12	7 6	27
A4	7	5	4	6	8 20	20
Заявки bj	18	27	42	12	26	125

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
Е=1018+827+53+830+100+812+76+820=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 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 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:
Е₁=1022+79+625+523+618+720=796.
Bazis o’zgaruvchilar soni . (2.4) kattakni egallab rejani yaxshilaymiz. Ushbu sikl narxi ga teng.

Quyida yangi yaxshilangan reja: