8-Тақырып. Сызықтық бағдарламалаудың тасымалдау есебі Дәріс жоспары (1 сағат)
жүктеу/скачать 1,09 Mb.
|
| 2. Алғашқы тірек жоспарын құру.
Сызықтық бағдарламалау есебінің кез-келгені үшін транспорпық есептің оптималдық жоспары тірек жоспары болып табылады. Транспорттық есептің тірек жоспарын анықтау үшін транспорт есебінің үлестіру әдістері қолданылады. Олар: Солтүстік-батыс әдісі. Минимал элемент әдісі немесе кестедегі ең кіші элемент бойынша. Фогель аппроксимациясы әдісі. Сызықтық бағдарламалаудың есебін симплексті әдіспен шешкен сияқты, транспорттық есептің оптималдық жоспар анықтамасын оның қандай да бір тірек жоспарын табудан бастайды. Бұл әдістердің мәні, тірек жоспарын мұнда n+m-1 қадамынан соң, есептер шарттары кестесінің әрбірінде «бос емес» деп аталатын бір тор көзбен толтырудан табылады. Бос тор көздердің бірін толтыру белгілі пунктердің біреуінің жүкке деген қажеттілігін не толықтай қанағаттандырады, не болмаса жүру пунктердің біреуінің жүкті тасымалдауын толықтай қанағаттандырады. Бірінші жағдайда нақты қадамдағы толтырылған тор көзі бар бағананы қарастырудан уақытты алып тастайды және шарттар кестесінде алғашқы қадамын қарастырғанда бір бағанасы кем, бірақ жөнелту пунктерінің бірінде жүк қорлары сәйкес өзгертілген және реттік саны бірдей есеппен қарастырылады. Екінші жағдайда толтырылған тор көзі бар жолды қарастырудан уақытша алып тастайды және шарттар кестесі сан жағынан өзгермеген бағаналарды, сонымен қатар бір жолы кем белгілеу пунктінде жүкке деген қажеттілігі сәйкес өзгертілген, толтырылған тор көзі бар бағанада болады деп есептеледі. n+m-2 жоғары қадамдарда белгіленгеннен кейін бір жөнелту пунктіменен және белгіленген пунктімен жасалынған тапсырма алады. Мұнда тек бір ғана тор көз бос қалады, ал қалған жүру пунктерінің қорлары қалған белгілеу пунктерінің кажеттілігіне тең болады. Бұл жағдайда сонымен бірге не бағананы, не жолды (екеуінің біреуін) қарастырудан алып тастайды. Демек, не сәйкес жүру пунктінің қорлары, не берілген белгілеу пунктінің қажеттілігі 0-ге тең болып есептеледі. Бұл 0-ді келесі толтырылатын тор көзге жазады. Жоғарыда айтылған шарттар соңғысының оптималдылығы мен оптималды жоспарын тексеру үшін алғашқы болып табылатын тірек жоспарының компоненттері тұрған n+m-1-ді алуға кепілдік береді. жүктеу/скачать 1,09 Mb. Достарыңызбен бөлісу:
|