9-Maruza. Chiziqli dasturning transport masalasi

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 emas , 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.