Умк по инженерному проектированию

Солтүстік батыс бұрыш әдіснде әрбір қадам сұранысында қалған жіберуші пункттердің біріншісі, бірінші қалған қабылдаушы пункттерді қанағаттандырады. Қабылдаушы пунктті таңдап алу мен жіберуді және жүк тасымалдау тарифіне сүйене отырып, толықрақ айтсақ ең кіші тарифке жауап беретін әрбір қадамда бір тордан таңду керек, жіберу пунктті мен қабылдау пунктін таңдап алынған торға сәкес келтірейік. Ең кіші элемент әдісінің мағынасы минималды тарифтен тұратын торды таңдауда. Бұл әдіс жүк тасымал есебінің тиімді әдісн табуға көмектесетінің жүкті тасудың жалпы бағасы оны жоспар бойынша тасыған бағасынан аз, берілген есепті солтүстік батыс бұрыш әдісімен табамыз. Сондықтан жүк тасымадау есебінің тірек жоспрын минималды элементтер әдісімен тапқан дұрыс болады.

Анықтама. Жүк тасымалы туралы есептің шарты жазылған кестенің цикілі деп, мына шарттарды қанағаттандыратын қисық сызықты деп аталады. Оның төбесі кестенің толтырылған торында орналасуы тиіс.

Оның қабырғалары кестенің жолының және бағанасының басында орналасады. Циклдың әрбір төбесінен екі қабырға ғана шығады, біреуі горизонтал, ал екіншісі вертикал орналасады.

Егер, цикл құрайтын қисықтың қабырғалары бір – бірімен қиылысатын болса, онда ол оның төбесі деп есептелінеді. Егер тірек жоспары дұрыс құрылған болса, онда әрбір бос торға сәйкес келетін бір ғана цикл сызуға болады.

Таңдап алған бос тор үшін цикл құрғаннан кейін ғана тірек жоспарына көшу қажет, ол үшін циклдің басында орналасқан торлардың арасында жүктің мөлшері бір – бірімен ауысудың нәтижесінде ауысу қажет. Бұл өзгерту мынадай ережеге сүйеніп іске асырылады.

1. Циклдің ішінде орналасқан торларға таңба қосылады дәлірек айтқанда бос торға + ал, басқа торларға - пен + таңбалары кезекпен қосылады.

2. Таңбасы қосылған торлардағы x_ij сандарының арасынан ең кішісі таңдап алынады, осы таңдап алынған санды + таңбасы бар торларға қосады, ал - таңбасы бар сандардан осы санды алып тастайды. Нәтижесінде бос болған тор бос емес торға айналады. Ал таңбасы бар торлардың ішіндегі ең кіші сан орналасқан тор бос тор деп есептелінеді.

Торлардағы жүктің орын ауыстыруы жүк тасымалдау есебінің тірек жоспарын анықтауға көмектеседі.

Жоғарыда айтылғанан жүк тасымалдау есебінің потенциялдар әдісімен шешкенде манандай этаптардан тұратынын көреміз:

1. 
   Тірек жоспарын табу. Толтырылған торлардың саны n+m-1 ге тең болу керек.
   
2. 
   мен жүкті тасу мен қабылдау потенциялдарын табады.
   
   
   жүктеу 9,53 Mb.
   
   Достарыңызбен бөлісу: