8-Тақырып. Сызықтық бағдарламалаудың тасымалдау есебі Дәріс жоспары (1 сағат)
жүктеу/скачать 1,09 Mb.
|
‹ҐЄжЁп 8. ЊЏЋђ Є §
- Бұл бет үшін навигация:
- Қажеттіліктер
- Таяныш тіректі жоспарды оптималдыққа зерттеу. Потенциалдар әдісі.
5-кесте
Сонымен, А2 жолында минималды тариф 4-ке тең, ал келесісі содан кейін 5-ке тең, олардың арасындағы айырмашылық 5-4=1. Осы тәрізді В4 бағанасындағы минималды элементтер арасындағы айырмашылық 6-2=4. Бұл барлық айырмашылықтарды есептей келе, біз В4 бағанасының неғұрлым сәйкес келетінін көреміз. Бұл бағанада минималды тариф В4 бағанасымен А1 жолының қиылысындағы тор көзге жазылады. Сонымен бұл тор көзді толтыру қажет. Оны толтырып, біз В4 пунктінің тұтынушылығын қанағаттандырамыз. Сондықтан В4 бағанасын қарастырудан алып тастаймыз және пунктінің қоры 160-110=50 бірлікке тең деп есептейміз. Бұдан соң толтыру үшін келесі тор көзді анықтаймыз. Әрбір жол мен бағанадағы қалған екі минималды тарифтер арасындағы айырмашылықты қайтадан табамыз және оларды 5-кестеге екінші қосымша жол мен бағанаға жазамыз. Бұл кестеде көріп отырғандай, үлкен айырмашылық А1 жолына сәйкес келеді. Бұл жолдағы минималды тариф оның В3 бағанасымен қиылысындағы тор көзде жазылған. Содан кейін осы тор көзді толтырамыз. Оған 50 санын сыйдыра отырып, A1 пунктіндегі қорлар толықтай алынып тасталады, ал В3 пунктіндегі тұтынушылық 190-50=140 бірлікке тең. А1 жолының қарастырылуын алып тастаймыз және толтыру үшін жаңа тор көзді анықтаймыз. Итерациялық процессті жалғастыра отырып, оның соңынан В2 бағанасы мен А2 жолы, В1 бағанасы мен А2 жолы, В2 бағанасы мен А3 жолы, В3 бағанасы мен А3 жолының қиылысындагы тор көздерді толтырамыз. Нәтижесінде мынатіректі жоспарын аламыз. Сонымен жоспарда тасымалдаудың жалпы құны мынаған тең: Ережеге сәйкес, Фогель аппроксимациясы әдісін қолдану оптималды жоспарға жақын тірек жоспарын алуға мүмкіндік береді, не болмаса оптималды жоспарды алуға мүмкіндік береді. Таяныш жоспарды оптималдыққа зсрттеу үшін бірнеше әдістер жасалынған, бірақта неғұрлым жиі потенциал әдісі мен дифференциалды рента әдісі қолданылады. Таяныш тіректі жоспарды оптималдыққа зерттеу. Потенциалдар әдісі. Потенциал әдісімен көліктік тапсырманың оптималды жоспарын анықтаудың жалпы принципі сызықтық бағдарламалаудың симплексті әдісі мен тапсырмаларды шешу принципіне негізделеді, оның ішінде: ең бірінші көліктік тапсырманың тірек жоспарын табады, ал одан соң оның өзінше оптималды жоспарды алуға жақсартады. Көліктік тапсырманың тірек жоспарын анықтау үшін қарастырылған әдістердің бірін колданамыз. Бұл әдістер алынған жоспардағы n+m-1 бос емес тор көздерді табуға кепілдік береді, себебі олардың ішінде кейбіреулерінде нөл тұруы мүмкін. Алынған жоспар оптималды критериясына тексерілуі керек. Егер ∆ij ішінде бірнеше оң сан болатын болса, онда осы оң элементтердің ішінен ең үлкені таңдалынып, осы элемент тұрған клетка циклдың басы етіп тағайындалады. Цикл деп, төбелері жабық клеткаларда жататын баған немесе қатар бойынша сызылған сынық сызықтардан тұратын жабық немесе тұйық контурды айтады. Циклдің басы тұрған клеткаға «+» таңбасы қойылып, қалған төбелеріне кезектесіп «-», «+» таңбалары қойылады. «-» клеткалардың арасынан х ij-дің ең кішісі таңдалынып, осы санды «+» клеткаларға қосып, клеткалардан алып, жаңадан таяныш жоспар құрады. Құрылған таяныш жоспарды қайтадан потенциалдар әдісін пайдаланып, оптималдыққа зерттейміз. Теорема-1. Егер көліктік тапсырманың бірнеше тірек жоспары үшін келесідей реттер бар: i=l, m және j=l, n, онда барлық үшін – көліктік тапсырманың оптималды жоспарын анықтау үшін келесідей потенциалдар енгіземіз: – тұтынушылар потенциалы; – жабдықтаушылар потенциалы. Құрастырылған теорема көліктік тапсырманың шешімін табу алгоритмін құрастыруға мүмкіндік береді. Сондықтан, жоғарыда қарастырылған әдістердің бәрі көліктік тапсырманың оптимды жоспарымен табылған. Белгіленген және жөнелту пунктерінің әрқайсысы үшін мен (i =l, m; j=l, n) потенциалдары анықтайды. Бұл сандар теңдік жүйесінде анықталады: – көліктік тапсырманың шарт кестесіндегі толтырылған тор көздегі тарифтер. Сонымен толтырылған тор көздердің саны n+m-1 тең болса, онда (10) жүйесі n+m белгісіздермен n+m-1 теңдігін құрайды. Өйткені, белгісіздер саны теңдік санының бірлігіне жоғарылайды, белгісіздердің бірін туынды санға тең деп алуға болады, мысалы, a=0 және (10) теңдігін қалған белгісіздердің мәнін табуға болады. Содан соң, яғни барлық потенциалдар табылғаннан кейін, бос көздердің әрбіреуінде саны анықталады. Егер сандары арасында оң болмаса, онда табылған тірек жоспары оптималды болып табылады. Егер де кейбір бос тор көздері үшін болса, онда табылған тірек жоспары оптималды емес болып табылады. Егер ∆ij ішінде бірнеше оң сан болатын болса, онда осы оң элементтердің ішінен ең үлкені таңдалынып, осы элемент тұрған клетка циклдың басы етіп тағайындалады. Цикл деп, төбелері жабық клеткаларда жататын баған немесе қатар бойынша сызылған сынық сызықтардан тұратын жабық немесе тұйық контурды айтады. Циклдың басы тұрған клеткаға «+» таңбасы қойылып, калған төбелеріне кезектесіп «-», «+» таңбалары қойылады. «-» клеткалардың арасынан хij-дің ең кішісі таңдалынып, осы санды «+» клеткаларға қосып, клеткалардан алып, жаңадан таяныш жоспар құрады. Құрылған таяныш жоспарды қайтадан потенциалдар әдісін пайдаланып, оптималдыққа зерттейміз. Мынаны ескеру қажет, яғни қайта есептеу циклі бойынша өсімі кезінде бос емес тор көздердің саны өзгеріссіз қалады, дәлірек, яғни n+m-1 тең. Сонымен, егер минусты тор кезде хij екі бірдей сан (одан да көп) болса, онда бұл тор көздердің біреуі ғана босатылады, ал қалғандары бос емсс қалады (нөлдікпен койылган). Көліктік тапсырманың алынған жаңа тірек жоспары оптималдығына тексерілсді. Бұл үшін белгіленген және кету пунктері потенциалдары анықталады және барлық бос тор көздер үшін сандарын табады. Егер осы сандардың арасында оң сан болмаса, онда бұл оптималды жоспардың алынғандығын куәландырады. Егер де мұнда оң сандар болса, онда жаңа тірек жоспарына көшу қажет. Нәтижесінде, иттеракционды процестен соң қадамдардың соңғы санынан тапсырманың оптималды жоспары алынады. Жоғарыда айтылғандардан көліктік тапсырмалардың шешімдерін потенциалды әдістермен табу процесі өзіне келесі этаптардан тұрады: Тірек жоспарын табады. Сонымен бірге ондағы толтырылған тор көздердід саны n+m-1-ге тең болуы қажет. Белгілеу және жөнелту пунктеріне сәйкес және потенциалдарын табады. Әрбір бос тор көз үшін санын анықтайды. Егер сандарының арасында оң сан болса, онда көліктік тапсырманың оптималды жоспары алынады, егер де болмаса, онда жаңа тірек жоспарына ауысады. оң сандарының арасынан максималдарын таңдайды, оларды бос тор көздер үшін құрайды, қайта есептеу циклі өсімін жасап шығарады. Алынған тірек жоспарының оптималдылығын тексереді, яғни 2-ші этаптан бастап қайтадан қайталайды. Есеп-1. Көліктік тапсырма үшін келесідегідей мәліметтер 1-кестесінде берілген, оптималды жоспарды табу керек. 1-кесте
Шешімі. Алғашқыда С.Б.Е. әдісін пайдалана отырып тапсырманың тірек жоспарын табамыз. Бұл жоспар 1-кестеде жазылған. Табылған тірек жоспарының оптималдылығын тексереміз. Осыған байланысты жөнелту пунктерінің және белгілеу пунктерінің потенциалдарын табамыз. Потенциалдарды анықтау үшін 7 белгісізі бар 6 теңдіктер жүйесін аламыз. дей отырып, , , , , , табамыз. Әрбір бос тор көз үшін . , , , , санын шығарамыз. Табылған сандарды қоршаймыз және олардың әрбіреуін 2-кестесіндегі бос тор көздерге жазамыз. 2-кесте
жүктеу/скачать 1,09 Mb. Достарыңызбен бөлісу:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||