Динамикалық бағдарламалау түсініктері
1. Динамикалық бағдарламалау түсініктері
Сызықтық және бейсызықтық бағдарламалау есептерінде экономикалық үдеріс көбіне статикалық, яғни уақыттан тәуелсіз деп қарастырылады. Сондықтан тиімді шешім жоспарлаудың бір ғана кезеңіне қатысты анықталады. Мұндай есептер бір кезеңдік немесе бір қадамдық деп аталады.
Ал динамикалық бағдарламалау есептерінде экономикалық үдеріс уақытқа тәуелді және бірнеше кезеңнен тұрады. Осыған байланысты әр кезең үшін тиімді шешімдер табылып, сол шешімдер негізінде бүкіл үдерістің тиімді дамуы (оптималды ұласуы) қалыптастырылады. Сондықтан мұндай есептер көп кезеңді немесе көп қадамды деп аталады.
Басқару ұғымы
Экономикалық үдеріс басқарылатын деп аталады, егер оның дамуына ықпал ету мүмкін болса. Әрбір кезеңде үдеріс барысына әсер ететін шешімдер жиынтығы басқару деп аталады.
Көп кезеңді үдерісті жоспарлау кезінде жеке кезеңдердегі шешімдер тұтас үдерістің талаптарына сәйкес келетіндей етіп таңдалады. Мысалы, T уақыт кезеңі (шаруашылық жылдары) бойы кәсіпорындар жүйесінің қызметі жоспарлансын. Период басында бөлінетін негізгі қаржы жүйенің бастапқы жағдайын, ал период соңындағы жағдай қорытынды күйін сипаттайды. Мақсат: T периодының соңында жүйенің қосынды кірісін максималдау.
Егер t-шы жылдың басында i-ші кәсіпорынға бөлінетін қаржыны басқарушы шама деп алсақ, онда әр кезең үшін бөліністерден басқару векторы құралады. Демек, қосынды кіріс кезеңдер бойынша таңдалатын басқарулар жиынтығына тәуелді болады.
Есептің қойылымы
Әрбір кезеңдегі басқаруды жүйенің қосынды кірісі максималды болатындай етіп таңдау қажет. Бұл — динамикалық бағдарламалаудың типтік мақсаттық қойылымы.
2. Динамикалық бағдарламалаудың жалпы есебі
Басқарылатын физикалық (немесе экономикалық) жүйе бастапқы жағдайынан уақыт өте келе ақырғы жағдайына жеткізіледі. Жағдайлардың өзгеру үдерісі белгілі бір сандық көрсеткішпен (мақсат функционалымен) сипатталады. Үдерісті осы көрсеткіш оптималды мән қабылдайтындай етіп ұйымдастыру керек.
Мүмкін болатын басқарулар жиынын U деп белгілейік. Онда есептің мәні: жүйені бастапқы жағдайынан ақырғы жағдайына мақсаттық көрсеткіш оптималды мәнге жететіндей етіп жеткізетін басқаруды анықтау.
Нәтиже
Жалпы түрде динамикалық бағдарламалау — көп қадамды жүйеде басқаруды таңдаудың құрылымды әдісі: мақсат функциясын кезеңдер бойынша есептеп, ең тиімді траекторияны табуға мүмкіндік береді.
3. Тиімді басқаруды кезеңдер бойынша құру қағидасы (функционалдық теңдеулер әдісі)
3.1 Кезеңдеп жоспарлау және «ақырынан бастау» идеясы
Динамикалық бағдарламалау көп қадамды үдерісті кезең-кезеңімен жоспарлайды және әр қадамды болашақ салдарын ескере отырып тиімді етеді. Кез келген көп қадамды үдерісте соңғы k-ші қадам бар; бұл қадамда шешім қабылдау келешектен тәуелсіз болады, себебі келешек қадамдар жоқ. Сондықтан соңғы қадам үшін ең тиімді басқару бірден таңдалады.
Соңғы қадам жоспарланғаннан кейін одан алдыңғы (k−1)-қадам қарастырылады, кейін (k−2)-қадам және т.с.с. Ақырында бастапқы жағдайға келеміз. Яғни динамикалық бағдарламалау логикасы ақырғы жағдайдан бастап бастапқы жағдайға қарай құрылады.
Шартты тиімді басқару
Егер қандай да бір қадамдағы жүйе жағдайы алдын ала нақты белгісіз болса, сол қадамдағы ықтимал жағдайлардың бірнеше нұсқасы қарастырылады. Соңғы қадамда әрбір мүмкін жағдай үшін табылған тиімді шешім шартты тиімді басқару деп аталады. Кейін бұл шартты нәтижелер алдыңғы қадамдарды есептеу үшін қолданылады.
Бірінші қадамда жағдайдың көп нұсқасы қарастырылмайды, себебі бастапқы жағдай біреу ғана. Сол бастапқы жағдай үшін келесі қадамдардағы шартты тиімді шешімдерді ескере отырып, тиімді басқару тікелей анықталады. Нәтижесінде бүкіл үдеріс үшін ізделінетін тиімді басқару алынады.
3.2 Беллман қағидасы және функционалдық теңдеулер
Р. Беллман көрсеткендей, көп кезеңді үдерістің тиімді шешімін табу көбіне функционалдық теңдеуді шешуге келтіріледі.
Екі кәсіпорынға қаржы бөлу мысалы
x мөлшеріндегі қаржы екі кәсіпорынды дамытуға жұмсалсын. Біріншісіне y, екіншісіне x−y бөлінсін. Сонда кірістер тиісінше g(y) және h(x−y) болады. Мақсат — жалпы кіріс J максималды болатындай етіп бөлуді таңдау: J = g(y) + h(x−y).
Егер g және h функциялары үздіксіз болса, мақсат функциясының максимумы бар болады. Айта кету керек: кірістің өлшем бірлігі қаржының өлшем бірлігінен өзгеше болуы мүмкін (мысалы, үнемделген машина-сағат, еңбек шығынының азаюы және т.б.).
Екі кезеңді үдерісте бірінші кезеңнен кейін қалған қаржының мөлшері кіріс алу нәтижесінде өзгеруі мүмкін деп ұйғарайық: бөлінген қаржы белгілі бір заңдылықпен «қайта есептеліп», келесі кезеңге өтеді. Сонда екінші кезең үшін де дәл осындай бөлу қайталанып, толық кіріс бірінші және екінші кезең нәтижелерінің қосындысы ретінде қарастырылады.
Негізгі қорытынды (рекурсия)
N кезеңнен тұратын үдерісте толық кірістің максималды мәні тек N және бастапқы ресурс x шамасына тәуелді болады. Осы тәуелділік кезеңдер бойынша рекурентті қатынастар (функционалдық теңдеулер) арқылы өрнектеледі.
Функционалдық теңдеулер әдісінің маңызды нәтижесі: N өлшемді күрделі есеп көбіне N тізбектен тұратын бір өлшемді есептерге жіктеледі. Бұл — динамикалық бағдарламалаудың есептеу тұрғысынан ең күшті артықшылықтарының бірі.
Белгілердің мағынасы (интерпретация)
- f
- Үдеріс мақсаты (кіріс, пайда және т.б.).
- N
- Кезеңдер (қадамдар) саны.
- x
- Жүйе жағдайын сипаттайтын ресурс/шама (N-қадамдағы күй параметрі).
- u
- Басқарушы айнымалы (таңдалатын шешім).
- max нәтижесі
- Тиімділік қағидасы бойынша алынған оптималды мән.
- 0…x аралығы
- Кезеңдегі ресурс бөлінісінің мүмкін шекаралары (типтік шектеу).
Қорытынды
Шешімдер бірінен соң бірі қабылданатын көп кезеңді үдерісте «кезеңнен-кезеңге» және «жағдайдан-жағдайға» өту функционалдық теңдеулермен өрнектеледі және Р. Беллманның тиімділік қағидасына негізделеді.
Әдебиеттер
- Беллман Р. Динамическое программирование. — М.: ИЛ, 1960.
- Вентцель Е.С. Исследование операций. — М.: Советское радио, 1972.
- Кузнецов Ю.Н., Кузибов В.И., Волощенко А.Б. Математическое программирование. — М.: Высшая школа, 1976.
- Робертс С. Динамическое программирование в процессах химической технологии и методы управления. — М.: Мир, 1965.
- Хедли Дж. Нелинейное и динамическое программирование. — М.: Мир, 1967.