ПӘннің ОҚУ-Әдістемелік кешені «Технологиялық процесстерді оңтайландыру әдістері»
жүктеу/скачать 5,43 Mb.
|
21ad3594-56e4-11e5-884b-f6d299da70eeУМК новое по МОТП каз (умм)
| Ең кіші элемент әдісі.
Солтүстік батыс бұрыш әдіснде әрбір қадам сұранысында қалған жіберуші пункттердің біріншісі, бірінші қалған қабылдаушы пункттерді қанағаттандырады. Қабылдаушы пунктті таңдап алу мен жіберуді және жүк тасымалдау тарифіне сүйене отырып, толықрақ айтсақ ең кіші тарифке жауап беретін әрбір қадамда бір тордан таңду керек, жіберу пунктті мен қабылдау пунктін таңдап алынған торға сәкес келтірейік. Ең кіші элемент әдісінің мағынасы минималды тарифтен тұратын торды таңдауда. Бұл әдіс жүк тасымал есебінің тиімді әдісн табуға көмектесетінің жүкті тасудың жалпы бағасы оны жоспар бойынша тасыған бағасынан аз, берілген есепті солтүстік батыс бұрыш әдісімен табамыз. Сондықтан жүк тасымадау есебінің тірек жоспрын минималды элементтер әдісімен тапқан дұрыс болады. Анықтама. Жүк тасымалы туралы есептің шарты жазылған кестенің цикілі деп, мына шарттарды қанағаттандыратын қисық сызықты деп аталады. Оның төбесі кестенің толтырылған торында орналасуы тиіс. Оның қабырғалары кестенің жолының және бағанасының басында орналасады. Циклдың әрбір төбесінен екі қабырға ғана шығады, біреуі горизонтал, ал екіншісі вертикал орналасады. Егер, цикл құрайтын қисықтың қабырғалары бір – бірімен қиылысатын болса, онда ол оның төбесі деп есептелінеді. Егер тірек жоспары дұрыс құрылған болса, онда әрбір бос торға сәйкес келетін бір ғана цикл сызуға болады. Таңдап алған бос тор үшін цикл құрғаннан кейін ғана тірек жоспарына көшу қажет, ол үшін циклдің басында орналасқан торлардың арасында жүктің мөлшері бір – бірімен ауысудың нәтижесінде ауысу қажет. Бұл өзгерту мынадай ережеге сүйеніп іске асырылады. 1. Циклдің ішінде орналасқан торларға таңба қосылады дәлірек айтқанда бос торға + ал, басқа торларға - пен + таңбалары кезекпен қосылады. 2. Таңбасы қосылған торлардағы xij сандарының арасынан ең кішісі таңдап алынады, осы таңдап алынған санды + таңбасы бар торларға қосады, ал - таңбасы бар сандардан осы санды алып тастайды. Нәтижесінде бос болған тор бос емес торға айналады. Ал таңбасы бар торлардың ішіндегі ең кіші сан орналасқан тор бос тор деп есептелінеді. Торлардағы жүктің орын ауыстыруы жүк тасымалдау есебінің тірек жоспарын анықтауға көмектеседі. Жоғарыда көрсетілген бір трек жоспарынан екінші трек жоспарына ауысу қайтасанау цикылындағы жылжуы деп аталады. қайтасанау цикылында жылжуы болғанда оның бос емес торлары өзгермейді, n+m-1-ге тең болады. Егер минусы бар торлардың екі бірдей сан болса, онда тордың біреу ғана босатылады, ал қалғандарын бос емес қылып қалдырады. Алынған жаңа трек жоспарын тиімділікке тексереміз. Ол үшін жіберуші пункт пен қабылдаушы пунктті  барлық бос торлар үшін табамыз. Егер осылардың арасында оң сан болмаса, онда ол тиімді жоспардың табылғанын көрсетеді. Ал егер олардың арасында оң сан болса, онда жаңа тиімді жоспаға көшеміз. Инерцияналды процестерден кейін соңғы санның қадамынан кейін есептің тиімді жоспары алынады.
Жоғарыда айтылғанан жүк тасымалдау есебінің потенциялдар әдісімен шешкенде манандай этаптардан тұратынын көреміз: Тірек жоспарын табу. Толтырылған торлардың саны n+m-1 ге тең болу керек.  мен жүкті тасу мен қабылдау потенциялдарын табады.
жүктеу/скачать 5,43 Mb. Достарыңызбен бөлісу:
|