11.2 Тиімділік принципі. Беллман теңдеуі

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

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

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

Динамикалық программалау есебінде енгізілген жаңа белгілеулер үлкен ақпараттық жүктемені қамтиды, сондықтан оларды толық және дәл меңгеру керек.

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

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

-ші қадамды қарастырайық: жүйенің -ші қадамының басындағы жағдайы, – соңғы жағдайы, – -ші қадамдағы басқару, ал – -ші қадамдағы мақсат функция (ұтыс).

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

арқылы соңғы қадамның басына жүйесі еркін алынған жағдайында, ал соңғы қадамда басқару тиімді болатындай мақсат функцияның максимумын -ші қадамдағы тиімділік көрсеткішін белгілейміз.

– -ші қадамдағы мақсат функциясының шартты максимумы деп аталады:

. (9.5)

Максимизациялау барлық жарамды басқаруы бойынша жүргізіледі.

мәнінде алынатын шешімі де жағдайынан тәуелді және -ші қадамдағы шартты тиімді басқару деп аталады да, – арқылы белгіленеді.

-ші қадамдағы шартты тиімді ұтыс

еркін алынғандағы басқару мен жағдайындағы -ші қадамдағы мақсат функцияның мәні

9.1-сурет

(9.5) теңдеуі бойынша төңіректік оңтайландырудың бірөлшемді есебін шығарып барлық мүмкін болатын жағдайы үшін және екі функцияны табамыз.

Енді екіқадамды есепті қарастырайық: -ші қадамға -ші қадамды қосамыз (9.1-сурет).

Кез келген жағдайы, еркін алынған басқаруы және -ші қадамдағы тиімді басқару үшін соңғы екі қадамдағы мақсат функциясының мәні мынаған тең:

. (9.6)

Тиімділік принципіне сәйкес кез келген жағдайы үшін шешім соңғы -қадамда тиімді басқарумен бірге соңғы екі қадамда мақсат функция максимум мәнді қабылдайтындай шешімді таңдау керек. Демек, (9.6) өрнегінің барлық жарамды басқаруы бойынша максимумын табу керек. Осы қосындының максимумы жағдайынан тәуелді, арқылы белгіленеді және соңғы екі қадамдағы тиімді басқарудағы мақсат функцияның шартты максимумы деп аталады.

. (9.7)

(9.7) қатынасындағы фигуралық жақшадағы өрнек мәнін болғанда (9.2) жағдай теңдеуінен

табуға болатындықтан және функциясындағы орнына қоюға болатындықтан тек қана және мәндерінен тәуелді болады.

(9.7) теңдеуіне сәйкес тек қана бір айнымалы бойынша максимизациялау нәтижесінде қайтадан екі функция алынады:

және .

Әрі қарай үш қадамды есеп қарастырылады: соңғы екі қадамға -ші қадам қосылады және т.т.

арқылы -шы қадамның басына жүйе жағдайында болатын шарт орындалғанда -шы қадамнан бастап соңына дейінгі -ші қадамдағы тиімді басқарудағы мақсат функциясының шартты максимумын белгілейміз.

Бұл функция мына түрде анықталады:

.

Сонда

.

... ...

9.2-сурет

-шы қадамдағы еркін алынған басқаруда және келесі қадамдағы тиімді басқаруда соңғы қадамдағы мақсат функция (9.2-сурет) мына түрде есептеледі:

.

Тиімділік принципіне сәйкес осы қосындының максимум шартынан таңдалынады:

, . (9.8)

(9.8) максимумды қабылдайтын -шы қадамдағы басқаруы арқылы белгіленеді және -шы қадамдағы шартты тиімді басқару болып табылады ((9.8) теңдеуінің оң жағына -ның орнына жағдайлар теңдеуінен алынған өрнегін қоямыз).

(9.8) теңдеуі Беллман теңдеуі деп аталады. Бұл рекуррентті қатынас функцияның келесі мәндерін біле отырып алдыңғы мәндерін табуға мүмкіндік береді. Егер (9.5) теңдеуінен мәнін анықтауға болса, онда болғанда барлық мүмкін болатын мәндері үшін максимизациялау есебін шығарып (9.8) теңдеуінен үшін өрнекті және сәйкес мәнін табуға болады.

(9.5) және (9.8) теңдеулерін шығару үрдісі шартты оңтайландыру деп аталады (бұл жерде «кері сұлба» қарастырылады, яғни соңғы қадамнан бастап шығарылады, -ші қадаммен 1-ші қадамның орындарын алмастыруға болады, онда «тура сұлба» алынады).

Шартты оңтайландыру нәтижесінде екі тізбек алынады:

, , ..., ,

соңғы, соңғы екі, ..., -ші қадамдардағы мақсат функциялардың шартты максимумдары, және

, , ..., ,

-ші, -ші, ..., 1-ші қадамдардағы шартты тиімді басқарулар.

Осы тізбектерді пайдалана отырып және мәндеріндегі динамикалық программалау есептерінің шешімін табуға болады. 1-ші қадамның басында жүйе жағдайында, яғни шарты орындалған жағдайда анықтама бойынша – қадамдағы мақсат функцияның шартты максимумы, яғни

.

Осыдан кейін шартты тиімді басқаруды және (9.2) жағдайлар теңдеуінің тізбегін пайдаланған дұрыс.

Бекітілген мәнінде мәнін аламыз. (9.2) теңдеуінен –табамыз және осы өрнекті шартты тиімді басқару тізбегіне қоямыз:

және т.т. (мұндағы арқылы -шы қадамда тиімді басқару таңдалынған кездегі -шы қадамнан кейінгі жүйенің жағдайы белгіленген):

... ,

– жағдайлар теңдеуінің пайдаланылатынын, – шартты тиімді басқару тізбегінің пайдаланылатынын білдіреді.

Динамикалық программалау есебінің тиімді шешімін аламыз:

.

9.1-мысал.

Өнеркәсіп арасында инвестицияларды бөлу есебі.

Өнеркәсіптік бірлестік төрт өндірістік кәсіпорыннан тұрады. Бастапқы қаражат – шартты бірлікті құрайды. Әрбір өнеркәсіпке бөлінетін қаражат 1 шартты бірлікке еселі болып келеді. -шы өнеркәсіпке бөлінген қаражат жылдың соңында пайда береді. функциялары 9.1-кестеде берілген. Бұл жерде мына мәселелерді ескеру қажет:

1. пайдасы басқа кәсіпорындарға бөлінген инвестициялардан тәуелсіз;

2. әрбір кәсіпорыннан түсетін пайда бірдей шартты бірлікпен беріледі;

3. жалпы пайда әрбір кәсіпорыннан түскен пайдалардың қосындысына тең.

Барлық кәсіпорындардағы жалпы пайданы максимизациялайтындай кәсіпорындардың арасында инвестицияны үлестіруді табу талап етіледі.

9.1-кесте.

1	20	18	25	30
2	34	29	41	52
3	46	45	52	76
4	53	62	74	90
5	55	78	82	104
6	60	90	88	116
7	60	98	90	125

Шығарылуы. арқылы -шы кәсіпорынға бөлінген қаражатты белгілейміз.

Жалпы қосынды:

(9.9)

айнымалысы келесі шектеулерді қанағаттандырады:

, , (9.10)

(9.10) шектеулер жүйесін қанағаттандыратын және (9.9) функция максимум мәнді қабылдайтындай , , , айнымалыларын табу керек.

қаражатын үлестіруді шешу үрдісін төрт қадамды ретінде қарастыруға болады. Қадам нөмірі кәсіпорын нөмірімен бірдей болады. , , , айнымалыларын таңдау – сәйкес І, ІІ, ІІІ, ІV-қадамдарды басқару. үлестіру үрдісінің соңғы жағдайы, барлық инвестицияны кәсіпорындарға бөліп беру қажет болғандықтан оның мәні нөлге тең, . Үлестіру сұлбасы 9.3-суретте келтірілген.

_

9.3-сурет

Берілген есеп үшін (9.2) жағдай теңдеуі мына түрде жазылады:

, (9.11)

мұндағы – жағдай параметрі, -шы қадамнан кейін қалған инвестиция мөлшері, яғни қалған кәсіпорындарға үлестірілетін инвестиция саны.

функциясын қарастырамыз. – егер -шы, -ші, ..., 4-ші кәсіпорындар арасында қаражаты тиімді үлестірілсе, онда осы кәсіпорындардан алынған шартты тиімді пайда. -шы қадамдағы жарамды басқару (не -шы кәсіпорынға ештеңе бермейміз, , не -шы қадамдағы бар қаражаттан артық емес қаражат береміз) шартын қанағаттандырады.

(9.5) және (9.8) теңдеулері мына түрде жазылады:

, (а)

(ә)

(б)

(в)

Әрбір қадамның шартты оңтайландыруын (9.3-сурет) жүргізе отырып жазылған теңдеулерді біртіндеп шығарамыз.

ІV-қадам. 9.1-кестеде пайдасы монотонды өседі, сондықтан ІV қадамда қалған қаражаттың барлығын 4-ші кәсіпорынға жұмсаған дұрыс. Бұл жерде мүмкін болатын мәндері үшін мына қатынасты аламыз:

және .

ІІІ-қадам. ІІІ қадамға қалған (яғни және таңдағаннан кейін) қаражатқа қатысты барлық ұсыныстарды қарастырамыз. – 0, 1, 2, 3, 4, 5, 6, 7 мәндерін қабылдауы мүмкін (мысалы, , егер барлық қаражат 1-ші және 2-ші кәсіпорындарға жұмсалса; , егер 1-ші және 2-ші кәсіпорындарға ештеңе берілмесе, және т.т.). Осыған байланысты таңдаймыз, – анықтаймыз және қосындысының мәнін бекітілген мәнінде әр түрлі үшін салыстырамыз. Әрбір үшін осы мәндердің ішіндегі ең үлкені – қаражатын 3-ші және 4-ші кәсіпорындарға тиімді үлестіргенде алынатын шартты тиімді пайда. мәніндегі оңтайландыру 9.2-кестеде берілген. Әрбір мәні үшін және сәйкес 5-ші және 6-шы бағандарда көрсетілген.

ІІ-қадам. үшін (б) теңдеуіне сәйкес шартты оңтайландыру 9.2-кестеде келтірілген. Мүмкін болатын барлық мәні үшін және мәндері сәйкес 8-ші және 9-шы бағанда келтірілген; 7-ші бағандағы бірінші қосылғыштар – мәндері 9.1-кестеден, ал екінші қосылғыштар мәнінде 9.2-кестенің 5-ші бағанынан алынған.

І-қадам. Шартты оңтайландырудың І-қадамында кестенің мәніне сәйкес бөлімді толтырса жеткілікті. үшін болғандағы шартты оңтайландыру ((в) теңдеуі) 9.2-кестеде келтірілген. Егер болса, онда , төрт кәсіпорыннан алынған пайда; қалған үш кәсіпорынның арасында тиімді үлестірілген жағдайда мәніне тең болады ( мәні мәнінде 9.2-кестенің 9-шы бағанынан алынған). Егер болса, онда . қалған үш кәсіпорынның арасында тиімді үлестірілген жағдайдағы жалпы пайда мәніне тең болады ( мәні 9.1-кестеден, мәні 9.2-кестенің 9-шы бағанынан алынған). Осылайша

болғанда, және ;

болғанда, және ;

болғанда, және ;

болғанда, және ;

болғанда, және ;

болғанда, және .

Алынған нәтижелерді салыстыра отырып, мәнінде .

(9.11) теңдеуді пайдаланып мәнін аламыз, ал 9.2-кесте бойынша 9-бағаннан мәнін табамыз.

, 9.2-кесте бойынша 6-бағаннан ;

, , яғни .

1-ші кәсіпорынға 1 ш.б.; 2-ші кәсіпорынға 1 ш.б.; 3-ші кәсіпорынға 2 ш.б..; 4-ші кәсіпорынға 3 ш.б. қаражат бөлінген кезде жалпы пайданың максимумы – 155 ш.б. тең.

Жауабы. 1-ші кәсіпорынға 1 ш.б.; 2-ші кәсіпорынға 1 ш.б.; 3-ші кәсіпорынға 2 ш.б..; 4-ші кәсіпорынға 3 ш.б. көлеміндегі инвестицияларды үлестірген кезде жалпы пайданың максимумы – 155 ш.б. тең болады.

9.2-кесте

1	2	3	4	5	6	7	8	9	10	11	12
0	0	0	0	0	0	0	0	0	0	0	0
1	0 1	1 0	0+1=1 25+0=25	25	0	0+25=25 18+0=18	25	0	0+25=25 20+0=20	25	0
2	0 1 2	2 1 0	0+52=52 25+30=55 41+0=41	55	1	0+55=55 18+25=43 29+0=29	55	0	0+55=55 20+25=45 34+0=34	55	0
3	0 1 2 3	3 2 1 0	0+76=76 25+52=77 41+30=71 52+0=52	77	1	0+77=77 18+55=73 29+25=54 45+0=45	77	0	0+77=77 20+55=75 34+25=59 46+0=46	77	0
4	0 1 2 3 4	4 3 2 1 0	0+90=90 25+76=101 41+52=93 52+30=82 74+0=74	101	1	0+101=101 18+77=95 29+55=84 45+25=70 62+0=62	101	0	0+101=101 20+77=97 34+55=89 46+25=71 53+0=53	101	0
5	0 1 2 3 4 5	5 4 3 2 1 0	0+104=104 25+90=115 41+76=117 52+52=104 74+30=104 82+0=82	117	2	0+117=117 18+101=119 29+77=106 45+55=100 62+25=87 78+0=78	119	1	0+119=119 20+101=121 34+77=111 46+55=101 53+25=78 55+0=55	121	1
6	0 1 2 3 4 5 6	6 5 4 3 2 1 0	0+116=116 25+104=129 41+90=131 52+76=128 74+52=116 82+30=110 88+0=88	131	2	0+131=131 18+117=135 29+101=130 45+77=122 62+55=117 78+25=103 90+0=90	135	1	0+135=135 20+119=139 34+101=135 46+77=123 53+55=108 55+25=80 60+0=60	139	1
7	0 1 2 3 4 5 6 7	7 6 5 4 3 2 1 0	0+125=125 25+116=141 41+104=145 52+90=142 74+76=150 82+52=134 88+30=118 90+0=90	150	4	0+150=150 18+131=149 29+117=146 45+101=146 62+77=139 78+55=133 90+25=115 98+0=98	150	0	0+150=150 20+135=155 34+119=153 46+101=147 53+77=130 55+55=110+60+25=85 60+0=60	155	1

Ескертулер.

1. Төртөлшемді 9.1-мысалда шартты экстремумды анықтау есебі төрт бірөлшемді есепті шешуге келтірілді: әрбір қадамда бір айнымалысы анықталды.

2. Шығарылған 9.1-мысалды талдау нәтижесінде функцияның берілу түрі мен тәсілі динамикалық программалау әдісіне ешқандай әсер етпейтінін көрдік: кестемен берілді, сондықтан, шамасы да, шамасы да 9.2-кестеде келтірілген дискретті мәндерді қабылдады.

3. Іріктеу әдісі динамикалық программалау мен осы есепке ұқсас дискретті есептердің арасындағы балама болып табылады. Шартты оңтайландырудың кезеңінде қолайлы емес нұсқаларды жазбай тастап кетуге болатындықтан динамикалық программалау әдісі «жақсы әдіс» болып табылады.

4. жағдайы мен қадам санының өзгерген мәндері үшін де осы әдісті пайдалануға болатынын әдістің жетістігі ретінде қарастыруға болады.

5. Өлшемділігі артқан кезде есептеу барысында техникалық қиындықтардың пайда болуын осы әдістің кемшілігі ретінде қарауға болады. Егер әрбір басқару айнымалысынан, ал жағдайы параметрінен тәуелді болса, онда әрбір қадамда оңтайландырудың -өлшемді есебі пайда болады.

12-лекция.Ойындар теориясы