Құ республ жə а ұрылы ликасы əңгір ха аграрлы ыс өн
Бұтақтар жəне шекаралар əдісі
жүктеу/скачать 1.57 Mb. Pdf көрінісі
|
| Бұтақтар жəне шекаралар əдісі.
Комбинаторлы оңтайландырудыың басқа кең тараған əдісі 1960 жылы Лэнд жəне Дойг ойлап тапқан бұтақтар жəне шекаралар əдісі болып табылады. Бұл əдісте альтернативті нұсқаларды комбинаторлы іріктеп алумен байланысты мəселелерді шешуде əмбебап құрал болып саналады. Берілген əдісті қорларды үздіксіз қолдану əдісінде жеке жұмыс 107 аймақтарының оңтайлы кезектілігін анықтау мəселесіне қолдануды сипаттайық. Кесте 3.6 Жұмыс аймақтарын үздіксіз игеру əдісі бойынша 4→1→3→2 тиімді кезегінде есептелген жұмыстар кестесі Кесте 3.7 Жұмыс аймақтарын үздіксіз игеру əдісі бойынша 1→3→2→4 тиімді кезегінде есептелген жұмыстар кестесі Сонымен қатар, алдыңғы алгоритмдегі сияқты тиімділік өлшемі жұмыстар кешенінің ұзақтығының минимумына қол жеткізу болып табылады. Бұтақталу алгоритмі екі əдісте де бірдей. Бұтақтар мен шекаралар əдісінің динамикалық бағдарламалау əдісінен басты айырмашылығы бұтақтардың дамуының келешектілігін бағалау тəсілінде. Егер динамикалық бағдарламалау əдісінде бағалау, былайша айтқанда, көбейтілген нəтиже тəсілімен жүргізілсе, бұтақтар мен шекаралар əдісінде соңғысынан басқа, əрбір бұтақ үшін келесі барлық альтернативті нұсқалар үшін ұзақтықтың мүмкін болатын шекті минимумы анықталады. Бағалау матрицасының құралуын жəне бұл матрицалардың ұзақтығының шекті мүмкін болатын минимумын анықтау əдісінің мəнін кесте 3.8-де көрсетілген жұмыстарды бастапқы ұйымдастыруды оңтайландыру мысалында қарастырайық. Бағалау матрицаларын құрудағы негізгі элемент екі көрші жұмыстар үшін жеке жұмыс аймақтарын игерудің тиімді кезектілігін анықтайтын 108 жəне жұпты матрица (кесте 3.9) құратын Джонсон алгоритмін қолдану болып табылады. Алгоритмнің вербалды (сөздік) сипаттамасы орындалуы бастапқы матрицаны тиімді матрицаға өзгертуге мүмкіндік беретін келесі қадамдарды орындауға келтіріледі. 1-ші қадам. Бастапқы матрицадан ұзақтығы ең төмен элемент анықталады. 2-ші қадам. Егер бұл элемент сол бағанда болса, онда тиімі матрицада бұл жол шеткі жоғарғы жаққа орын ауыстырылады, ал кері жағдайда, шеткі төменгі жаққа орын ауыстырылады. Орын ауыстырылған жол екі матрицаның да қарастырылуынан алынып тасталынады. Кесте 3.8 Қорларды үздіксіз игеру əдісі бойынша бастапқы кезекте есептелген жұмыстар кестесі 3-ші қадам. Егер бастапқы матрицада орын ауыстырылмаған жолдар қалған болса, онда 1-ші қадамға қайтып келу жүргізіледі, кері жағдайда, алгоритм жұмысы тоқтатылады. Жұп матрицаларды тиімділендіру нəтижелерінен əр түрлі жұпты матрицаларда сəйкес жеке жұмыс аймақтарын игерудің тиімді кезектілігі сəйкес келмейтіні көрініп тұр. Мысалға, А—Б жұпты оңтайландырылған матрицасына сəйкес бірінші болып 2-ші жеке жұмыс аймағы игерілуі, ал Б—В матрицасына сəйкес бірінші болып 1-ші жеке жұмыс аймағы игерілуі тиісті. Бұл объективті қарама-қайшылық тек Джонсон алгоритмін қолданумен шектелуге мүмкіндік бермейді. Алайда, берілген алгоритм жазудың мүмкін болатын минималды кезеңін есептеуге жəне ол бойынша барлық жұмыс кешенінің ұзақтығының мүмкін болатын шекті минимумын анықтауға мүмкіндік береді. Мысалға, А—Б жұпты оңтайландырылған матрицасына сəйкес минималды мүмкін болатын жұмыстың қызған шағының кезеңі белгілі, ол 18-ге тең, Б—В жұпты оңтайландырылған матрицасы үшін минималды мүмкін болатын жұмыстың қызған шағының кезеңі белгілі, ол 2-ге тең, ал В—Г оңтайландырылған матрицасы үшін 6-ға тең минималды мүмкін болатын жұмыстың қызған шағы белгілі. Осылайша, барлық жұмыс кешенінің шекті мүмкін болатын ұзақтығы ((3.1) формуласына сəйкес) минималды мүмкін болатын жұмыстың қызған 109 шағының кезеңінің қосындысымен жəне соңғы түрдегі жұмыстарының барлық ұзақтығының қосындысы арқылы анықталады ол 38 бірлікке тең. Кесте 3.10-да екі бағалау матрицаларын көрсетілген. Сол жақ матрица 1-ші жеке жұмыс аймағынан басталатын барлық нұсқаларды бағалау үшін құрылған. Оң жақ матрица 1-ші жеке жұмыс аймағынан жəне одан кейінгі 4-ші жеке жұмыс аймағынан басталатын барлық нұсқаларды бағалау үшін құрылған. Кесте 3.9 Джонсон алгоритмі бойынша бастапқы матрицаларды тиімді матрицаларға қайта құру Бастапқы матрицалар жұбы Оңтайландырылған матрицалар жұбы Бағалау динамикасы осындай, төмен тұрған деңгейлердің барлық нұсқаларының бағасы төмендемеуі керек. Бағалау матрицаларын құру алгоритмі келесі қадамдарға келтіріледі. 1-ші қадам. Бағалау матрицасына кіретін жұпты матрицалар, жұмыстар ұзақтығымен жұмыс айтақтарын кезекте бекітумен анықталатын ретте толтырылады. Кесте 3.10 Бағалау матрицалары жүктеу/скачать 1.57 Mb. Достарыңызбен бөлісу:
|