11.1 Динамикалық программалау есебінің жалпы қойылуы
Динамикалық программалау – шешімді қабылдау үрдісі бірнеше кезеңдерге бөлінуі мүмкін амалдарға бейімделген оңтайландыру әдістері. Мұндай амалдар көпқадамды деп аталады.
Динамикалық программалау есепті бірнеше кезеңге декомпозициялау (бөлу) арқылы тиімді шешімін табуға мүмкіндік береді. Бұл декомпозициялау әр түрлі принциптер бойынша жүзеге асырылады. Кейбір есептерде уақыт аралығы бойынша, ал басқаларында – басқару нысаны бойынша жүзеге асырылады. Оңтайлылық – есепті кезеңдерге бөлудің негізін құрайтын динамикалық программалаудың іргелі принципі болып табылады.
Осындай тәсіл өлшемділігі бойынша үлкен бір есепті кіші мөлшерлі көптеген есептерге әкеледі. Бұл есептеу көлемін едәуір қысқартады және басқару шешімдерін қабылдау үрдісін тездетеді. Динамсикалық программалаудағы есептеу бір ішкі есептің тиімді шешімі келесі есеп үшін бастапқы мәліметтер ретінде пайдаланылатындығымен рекуррентті болып келеді.
Егер
сызықтық программалау модельдерін
экономикада күрделі жағдайлардағы
үлкен масштабтағы жоспарлардың шешімдерін
қабылдау үшін пайдаланатын болса, онда
динамикалық программалау модельдерін
кіші масштабтағы есептерді шығару үшін,
мысалы, қорларды толықтыру мезгілін
және толықтыратын қорлардың өлшемін
анықтайтын қорларды басқару ережесін
дайындау кезінде; өндірістің күнтізбелік
жоспарлау принципін дайындау және
өнімге сұраныстың тұрақты болмаған
жағдайында оны бос болмайтындай
бірқалыпты ету кезінде; мүмкін болатын
жаңа бағыттар арасында жетіспейтін
қаржыны бөліп, оларды пайдалану кезінде;
күрделі құралдарды ағымдық және
түпкілікті жөндеуге және қажет болған
жағдайда оларды ауыстыру үшін күнтізбелік
жоспар жасау кезінде, әуе шабуылына
қарсы қорғаныстың бірнеше жолағын
ұшақтар тобымен басып алу кезінде,
аппаратураны тексеру барысында
қолданылатын тесттердің тізбегі және
т.б. пайдаланылады. Кейбір амалдар
(жоғарыда келтірілген) қадамдарға
бөлінеді; осындай бөлулердің кейбіреуі
жасанды түрде жүзеге асырылады. Айталық,
ракетаның мақсатына жетуі үшін үрдісті
шартты түрде кезеңдерге бөлуге болады,
олардың әрқайсысы қандай да бір
уақытын алады.
Нақты жұмыс атқаратын үлкен экономикалық жүйелерде күнделікті микроэкономикалық шешімдерді қабылдау талап етіледі. Динамикалық программалау модельдері адамдардың аз араласуымен стандарттық тәсілдің негізінде осындай шешімдерді қабылдау мүмкіндігімен құнды. Егер осындай шешімдерді жеке қарастырған кезде маңыздылығы аз болса, онда оларды жалпы алғанда пайда түсіруге өте көп әсер етуі мүмкін.
Енді динамикалық программалау есебінің жалпы қойылуын қарастырайық.
Басқарылатын
үрдісті (мысалы, қаражаттарды өндірістерге
бөлу, ресурстарды бірнеше жыл пайдалану,
құрал-жабдықтарды ауыстыру, қорларды
толықтыру және т.т. кезіндегі экономикалық
үрдіс) қарастырайық. Басқару нәтижесінде
жүйе (басқару нысаны)
бастапқы жағдайдан
жағдайға көшеді. Айталық, басқаруды
қадамға бөлуге болсын, яғни шешім
біртіндеп әрбір қадамда қабылданады,
ал
жүйесін бастапқы жағдайдан соңғы
жағдайға көшіретін басқару
қадамдық басқару жиынтығын береді.
арқылы
-шы
(
)
қадамдағы басқаруды белгілейміз.
айнымалылары кейбір шектеулерді
қанағаттандырады және осы мағынада
жарамды
(
– сан,
-өлшемді
кеңістіктегі нүкте, сапалы белгі болуы
мүмкін) деп аталады.
–
жүйесін
жағдайдан
жағдайына көшіретін басқару болсын.
арқылы
-шы
басқарудан кейінгі жүйенің жағдайын
белгілейік.
жағдайлар тізбегін аламыз:
...
...
Қарастырылайын деп отырған басқарылатын амалдың тиімділік көрсеткіші – мақсат функция – бастапқы жағдайдан және басқарудан тәуелді болады:
. (9.1)
Бірнеше тұжырымдаманы келтірейік.
1. Жүйенің жағдайы -шы қадамның соңында тек қана алдыңғы жағдайынан тәуелді болады және -шы қадамдағы басқарудан (алдыңғы жағдайлар мен басқарулардан тәуелсіз) тәуелді болады. Бұл қойылып отырған талап «кейінгі әсердің болмауы» деп аталады. Алынған тұжырымдаманы жағдайлар теңдеуі деп аталатын теңдеу түрінде жазуға болады:
,
. (9.2)
2. (9.1) мақсат функциясы әрбір қадамда тиімділік көрсеткішінен аддитивті болып табылады.
Бірнеше
айнымалылардан тұратын функцияның
мәнін тек қана бір
айнымалысынан тұратын қандай да бір
функцияларының қосындысы ретінде
қарастыруға болатын функция аддитивті
функция
деп аталады.
-шы
қадамдағы тиімділік көрсеткішін
,
(9.3)
арқылы белгілейміз. Сонда
. (9.4)
Динамикалық программалау есебі былай қойылады:
1. оңтайландыру есебі басқаруды қадамды үрдіс ретінде түсіндіріледі;
2. мақсат функциясы әрбір қадамдағы мақсат функциялардың қосындысына тең болады;
3. -шы қадамдағы басқаруды таңдау осы қадамның жағдайынан тәуелді, алдындағы қадамдарға әсер етпейді (кері байланыс жоқ);
4. басқарудың -шы қадамынан кейінгі жағдайы тек қана алдындағы жағдайынан және -шы қадамдағы басқарудан (кейінгі әсердің болмауы) тәуелді болады;
5. басқару әрбір қадамда тек қана басқарушы айнымалылардың ақырлы санынан, ал жағдайы – параметрлердің ақырлы санынан тәуелді болады.