Құ республ жə а ұрылы ликасы əңгір ха аграрлы ыс өн

103 
мəселелерді шешуде əмбебап құрал ретінде Р. Бэллманмен ойлап 
табылған. 
Берілген мəселенің шешімінің алгоритмін көрсету үшін ортақ 
ұзақтықты есептеу формуласын (3.4) келесідей түрге келтіреміз: 
,
,
,
→
. 
(3.13) 
Өрнек (3.13) берілген оңтайландыру мəселесінің мақсатты 
функциясы болып табылады жəне ол келесі үш мүшеден тұрады: 
 
бірінші мүше – бұл бірінші түрі жұмыстарының қосындысын 
анықтайтын сан; оның мəні жеке жұмыс аймақтарын алмастырудан 
өзгермейді; 
 
екінші мүше – бұл элементтерінің саны жеке жұмыс 
аймақтарының санына тең болатын жəне əрбір элементі барлық 
жұмыстардың, біріншісінен басқа, қосындысы арқылы анықталатын бір 
өлшемді матрица. Формулаға тек соңғы орында тұрған жеке жұмыс 
аймағына сəйкес келетін элемент кіреді; 
 
үшінші мүше – бірінші түрі жұмыстарының арасында қорлық 
байланыстардың созылуының қосындысы. Əрбір қорлық байланыстың 
созылуы жұмыстың қызып тұрған кезеңі мəнінен алдыңғы жеке жұмыс 
аймағындағы бірінші жұмыстың ұзақтығын мəнін алу арқылы анықталады.
Қорлық байланыстардың созылуының қосындысын анықтайтын 
элементтер 
өлшемді жəне бас диагоналінің элменттерінсіз 
матрицадан анықталады.
Динамикалық бағдарламалау əдісі бойынша жеке жұмыс аймақтарын 
игерудің 
оңтайлы 
кезектілігін 
анықтау 
алгоритмінің 
қадамдық 
сипаттамасын көрсетеміз. Алгоритмнің 1-ші қадамында бірінші бұтақталу 
жүзеге асады жəне (3.12) формуланың бірінші жəне екінші мүшелерінің 
қосындысы арқылы əрбір бұтақ үшін қосылған қосындыны бағалау 
жүргізіледі. Бағаланған бұтақтар саны жеке жұмыс аймақтарының санына 
тең болады.
2-ші қадамында барлық бағаланған бұтақтар көптігінен минималды 
бағалау өлшемі бойынша ең көрнекті бұтақ анықталады. Атап өтейік, алда 
бұтақтар бірден көп болуы мүмкін жəне бұл жағдайда олардың əрбіреуіне 
келесі қадамдарды орындау қажет болады.
3-ші қадамда сəйкес алдыңғы жеке жұмыс аймақтарын бекітуден 
тұратын барлық альтернативаларды қосу арқылы келешекті бұтақтардың 
бұтақталуы жүзеге асырылады.
Алынған альтернативаларды бағалауды анықтайтын қосылған 
қосынды (3.13) формуласының үшінші мүшесіне кіретін қорлық 

104 
байланыстардың бірінің созылуына сəйкес келетін мəнді қосу арқылы 
анықталатын болады.
4-ші қадамда соңғы бұтақтардың бар жоғы анықталады, яғни, барлық 
жеке жұмыстар аймағы бекітілген бұтақтар анықталады. Егер соңғы 
бұтақтар бар болатын болса, онда соңғы минималды бағадан жоғары 
бағаға ие барлық аралық бұтақтар келешексіз бұтақтар деп танылады жəне 
олардың ендігі бұтақталуы тоқтатылады.
5-ші қадамда келешекті аралық бұтақтардың бар жоғы анықталады. 
Егер осындай бұтақтар бар болса, онда 2-ші қадамға көшу жүргізіледі, ал 
кері жағдайда 6-шы қадамға.
6-шы қадамда алынған қосылған қосындылардың минималды мəніне 
ие соңғы бұтақтар анықталады, ал осы бұтақтарға əкелген сəйкес жолдар 
ізделіп жатқан жеке жұмыстар аймағынының оңтайлы кезектілігін 
анықтайды.
Мысал. Кесте 3.5-те көрсетілген жұмыс кестесі АҮИƏ сəйкес жеке 
жұмыс аймақтарын игерудің 1→2→3→4 кезектілігінен есептелген 
жұмыстарды ұйымдастырудың матрицасы берілген. Бастапқы матрица 
бойынша бір түрдегі (А түрі) жұмыстардың ұзақтығының қосындысы 
арқылы анықталатын (3.13) формуласының 1-ші мүшесінің мəнін 
анықтаймыз: 4 + 8 + 10 + 6 = 28. 
Енді бастапқы матрица бойынша (3.13) формуласының 2-ші мүшесін 
құрастырушылардың мəнін анықтаймыз. Соңғы орында бекітілген 1 жеке 
жұмыс аймағы үшін А түрінің жұмыстарын қоспағанда, барлық жұмыстар 
ұзақтығының қосындысы: 2 + 7 + 4 = 13.
Соңғы орында бекітілген 2 жеке жұмыс аймағы үшін А түрінің 
жұмыстарын қоспағанда, барлық жұмыстар ұзақтығының қосындысы: 5 + 
4 + 5 = 14.
Соңғы орында бекітілген 3 жеке жұмыс аймағы үшін А түрінің 
жұмыстарын қоспағанда, барлық жұмыстар ұзақтығының қосындысы: 2 + 
9 + 7 = 18.
Соңғы орында бекітілген 4 жеке жұмыс аймағы үшін А түрінің 
жұмыстарын қоспағанда, барлық жұмыстар ұзақтығының қосындысы: 3 + 
1 + 6 = 10. (3.13) фомуласының үшінші мүшесіне сəйкес келетін 
матрицаны қалып- 
тастыру 
үшін, (3.5) формуласы 
арқылы 
анықталған 
жеке 
жұмыстардыңқызып 
жүру кезеңінің барлық мүмкін болатын матрицаларын қалыптастыру қажет 
жəне одан алдыңғы жұмыс аймақтарында орындалып жатқан 1-ші түрдегі
жұмыстарының ұзақтығын алу қажет.
Осылайша алынған нəтижелер сурет 3.4-те көрсетілген.

105 
Кесте 3.5 Жұмыс аймақтарын үздіксіз игеру əдісі бойынша бастапқы 
кезектілікпен есептелген жұмыстар кестесі 
Жұмыс индексі 
Жұмыстың жеке аймағы 
1 2 3 4 
А 
0 4 4 12 
12 22 
30 36 
4 8 10 6
Б 
4 6 12 17 
22 24 
36 39 
2 5 2 3
В 
6 13 17 21 24 33 39 40 
7 4 9 1
Г 
13 17 
21 26 
33 40 
40 46 
4 5 7 
6 
Оңтайландыру нəтижесі сурет 3.5-те көрсетілген. 
Сурет 3.5-тің бірінші жолында 1-ші түрдегі жұмыстарының 
ұзақтығының қосындысы көрсетілген. Келесі жолда (3.13) формуласының 
екінші мүшесіне сəйкес қосындылар көрсетілген.
Үшінші жолда жоғарыда сипатталған алгоритмнің 1-ші қадамын 
орындауда алынған бұтақтарды бағалаудың нəтижелері көрсетілген. 
Алгоритмнің 2-ші қадамын қолдана отырып, 4-ші жұмыстар 
аймағындағы жұмыстардың аяқталуына сəйкес келетін бұтақ келешекті 
болып табылатынын анықтаймыз. Бұл келешекті бұтақтың бағасы 38-ге 
тең. 
Алгоритмнің 3-ші қадамын қолдана отырып, 1, 2 жəне 3 жұмыс 
аймақтарының алдыңғы орнына бекіту арқылы келешектегі бұтақтың 
дамуын жүзеге асырамыз. 
Жұмыстың 
қызған кезінің 
матрицасы 
Келесі 
- 
= 
Қорлық 
байланыстардың 
созылуы 
Келесі 
1 
2 
3 
4 
1 
2 
3 
4 
Алдыңғы
1 
4 4 7 
4 
Алдыңғы
1 
0 0 3 
2 
11 
8 12 
8 
2 
3 
0 4 
3 15 
11 
18 
10 3 5 1 
8 
4 6 6 6
6 
4 0 0 0
Сурет 3.4. Бір жұмыс түрінің қорлық байланыстарының созылу 
матрицасын қалыптастыру (асты сызылу арқылы ерекшеленген сандар 
қиын жұмыстарды анықтайды)

106 
Сурет 3.5. АҮИƏ оңтайландыру динамикасын мақсаттар «ағашында» 
көрсету 
Алынған альтернативалардың қосындысы алдыңғы бағаға сурет 3.4 
арқылы алдыңғы жəне келесі жеке жұмыстар аймағынан сəйкес 
реттіліктермен анықталатын қорлық байланыстардың созылу мəнін қосу 
арқылы анықталатын болады. Алынған альтернативалардың мəні сəйкес 
41, 42 жəне 46 уақыт бірлігіне тең. Алгоритмнің 4-ші жəне 5- ші 
қадамдарының негізінде жаңа альтернативалардың соңғы бұтақ болып 
табылмайтындығын анықтаймыз жəне 2-ші қадамға өтеміз, оның негізінде 
алынған бағалардың көптігінен (41, 42, 46, 41, 42, 46) келешектегілерін 
таңдап алып оларды дамытамыз.
Жоғарыда сипатталған алгоритмді қолданудың соңғы нəтижелері 
сурет 3.5-те көрсетілген. Берілген суреттеме арқылы оңтайландыру 
үдерісінің толық динамикасы жаңғыртылуы мүмкін. Оңтайландыру 
нəтижесінде жеке жұмыстар аймағын игерудің оңтайлы екі кезектілігі 
анықталды: сəйкесінше кесте 3.6 жəне кесте 3.7-де көрсетілген 4→1→3→2 
жəне 1→3→2→4. Айта кететін жай, есептеу қатынасында бұл мəселелер 
қиын болып саналады, бірақ бұл қосымша қорларды тартусыз құрылысты 
қысқартуға мүмкіндік беретін, төлеуге абзал «баға» болып табылады. Бұл 
мəселелерді есептеудегі қиындық есептеулер көлемінің бастапқы өлшемге 
тəуелді факториалды өсуімен байланысты.

жүктеу/скачать 1.57 Mb.

Достарыңызбен бөлісу: