Динамикалық программаластыру – бұл көп этапты амалдарға қолданылатын оптимизация әдістерінің ерекше түрі. Бұл әдіс арқылы шешім табу процессі көп этапты, демек уақыт пен еңбекті көп талап етеді. Бұл мақалада осы процессті Excell электронды кестесінің көмегімен оңай әрі тез есептеудің бір үлгісі баяндалады.
Сонымен, қандайда бір М ресурстарды К кәсіпорындарға П1, П2, …, Пк бөліп беру керек болатын көпэтапты мәселе берілсін. Әрбір кәсіпорын өзіне бөлінген х ресурсқа байланысты кіріс әкеледі. Бұл кіріс қандайда бір функциясымен анықталады.
Жалпы қосынды кіріс максимал болуы үшін М ресурстарды кәсіпорындарға қалай бөлу керек? (Бұл мәселені 1 жыл үшін қарастырамыз).
Мәселені біз ойша мынандай қадамдарға бөлуімізге болады(өйткені мәселенің қойылуында қадамдарға бөлініп көрсетілмеген). Бірінші қадам ретінде П1 кәсіпорынға ресурстан бөліп беру, екінші қадам – П2 кәсіп орынға ресурстан бөліп беру,т.с.с.
Біздің мәселемізде басқарылатын жүйе – бұл бөлініп берілетін S ресурстар (М-бұл жалпы барлық ресурс).S жүйесінің жағдайы әрбір қадам алдында әлі бөлінбеген ресурстар қорымен анықталады.
Бұл мәселедегі “қадамдық басқарулар” кәсіпорындарға бөлінетін х1, х2, …, хn ресурстар мөлшері.
Оптимал басқаруды, яғни
W=(xi)mах
функциясын (кірісті) максималдайтын х1, х2, …, х1 мәндерін табу керек [1].
Алдымен бұл есепті жалпы формула түрінде шешіп, одан соң нақты мәндері үшін шешіп көреміз.
Әрбір i–ші(i=1… к) қадам үшін “шарты оптимал ұтысты” табайық.(“шартты” деп i-ші қадамның ұтысы өзінен алдыңғы қадамдарға байланысты өзгеруін айтып отармыз). Шартты оптимал ұтысты Wi (S) арқылы белгілейік, сәйкесінше шартты қадамдық басқаруды xi(S) арқылы белгілейік.
Оптимизациялауды соңғы k-шы қадамнан бастайық. Айталық, бұл қадамға алдыңғыларына бөліп беруден қалған S ресурспен келдік. Демек, қалған S ресурстың барлығын соңғы Пк кәсіп орынға саламыз (береміз). Сондықтан k-шы қадамдағы шартты оптимал басқару: соңғы кәсіпорынға қолда қалған S ресурстың барлығын беру болады, яғни
хm(S)=S
Ал шартты оптимал ұтыс
Wm(S)=m(S)
Қалған ресурс S-ң (Пк-ға берілген)мөлшерін шамалап, әртүрлі мәндер беріп, сәйкес хk(S)-пен Wk(S)-ті табамыз. Сонымен соңғы қадам оптимизацияланды.
Енді, алдынғы (k-1)-ші қадамға өтеміз. Айталық бұл қадамға бөлініп бергеннен қалған S ресурс қорымен келдік.
Wk-1 (S)арқылы соңғы 2 қадамдағы шартты оптимал ұтысты белгілейік:
(k-1)-ші және k-шы қадамдағы. Егер(k-1)кәсіпорынға х ресурс берсек, онда соңғы k қадамға S-х ресурс қалады. 2 қадамның ұтысы мынаған тең:
(1)
осы ұтысты максималдайтын х (ресурс)мәнін табу керек:
Wk-1 (S)=mах тах –белгісі бұл х мәндерінің ішінен ең үлкені x=s алдынады дегенді білдіреді.(Ең үлкенінің өзі S тен үлкен болмайды).
Осылайша , (k-2)-ші, (k-3)-ші, т.с.с. қадамдарды оптимизациялаймыз. Жалпы әрбір i-қадам үшін осы i-ден бастап соңына дейінгі барлық қадамдар үшін шартты оптимал ұтысты мына формула арқылы табамыз:
Wi(S)=тах
бұған сәйкес бұл формуланы максималдайдын х мәні үшін шарты оптимал басқару xi(S) табылады.
Осылай жалғастырып 1-қадамдағы П1 кәсіп орынға дейін жетеміз. Бұл жерде S-ке шамалар әртүрлі мәндер берудің қажеті жоқ; бірінші қадамда ресурс қоры М-ге тең екендігін анық білеміз:
W*= W1 (M)=тах
Cонымен, максимал ұтыс (кіріс)табылады. Енді тек әр қадам үшін берілген “кеңестерді оқу”керек. (әрқадам да S-ң әртүрлі шамаланған мәндерді үшін шартты оптимал басқару , шартты оптимал Wi(S)ұтыс табылған еді) (4)формуласын максимумға жеткізетін х мәні бұл 1-қадамдағы оптимал шешім х1* болып табылады. (яғни ресурс мөлшері)Бұл ресурсты 1-ші кәсіпорынға берген соң қараймызда М-х1 ресурс қалады . S=M-x1 мәні үшін кеңестерді оқи отырып, 2-ші кәсіп орынға ресурстардың мүмкін болған оптимал мөлшерін береміз: х2*=x2(M-x1*)
Әрі қарай соңына дейін осылай жалғасады.
Ал енді нақты мәндер үшін шешеміз. Бастапқы ресурс қоры М=10(бірлік) Осы қоры 5 кәсіп орынға барынша оптимал түрде бөліп беру керек. (k=5).
Оңай болуы үшін ресурстар тек бүтін мәнді бөлінуі мүмкін деп алайық.
кірісі функцияның мәндері кестеде көрсетілген [2].
| x | |||||
| 1
2 3 4 5 6 7 8
|
0,5
1,0 1,4 2,0 2,5 2,8 3,0 3,0 |
0,1
0,5 1,2 1,8 2,5 2,9 3,5 3,5
|
0,6
1,1 1,2 1,4 1,6 1,7 1,8 1,8
|
0,3
0,6 1,3 1,4 1,5 1,5 1,5 1,5 |
1,0
1,2 1,3 1,3 1,3 1,3 1,3 1,3 |
Әрбір бағанда х ресурсының қандайда бір мәніне бастап, кірістің өсуі тоқтайды.
(Шындығында , кәсіпорын ресурстардың белгілі бір мөлшерін ғана игере алады).
Алдымен, әр кәсіпорынға қатысты х ресурс берілген кездегі кіріс функцияларының мәндерін Excell парағының жоғарғы жағына енгізіп қоямыз(1-суретте В3:G13 ұяшықтар диапозонында берілген).
Келесі істейтініміз бұл – қадамдар бойыша шартты оптимизациялау, яғни әр қадамда (і кәсіпорынға) бөлінуі мүмкін S ресурстың барлық мәндері үшін шартты оптимал ұтыстарды Wi(S) және оған сәйкес шартты оптимал басқаруларды Хі(S) табамыз.
Сурет 1. Бастапқы берілгендерді енгізу
Бұл процесс 5 қадамнан тұрады. Бізге белгілі процесс соңғы қадамнан бастап, кері қарай жүреді. Демек, і=5 қадамды, яғни 5-ші кәсіпорынды қарастырамыз. Бұл қадамды оптимизациялаудың қажеті жоқ, өйткені соңғы кәсіпорынға алдыңғыларға бөлініп берілген ресурстың қалған бөлігі түгел беріледі. Сондықтан, f5(x) мәндерін шартты оптимизациялау нәтижелері кестесіне көшіріп жазып қоямыз. fi(x) кіріс функциясының мәндері өзгерген кезде бұл кестенің мәні автоматты жаңарып отыру үшін формула арқылы енгіземіз.
Сурет 2. Қадамдар бойынша шартты оптимизациялау нәтижелері
Қалған 4 қадамды оптимизациялауға тура келеді. Демек, 2-суретте көрсетілген кестенің қалған қатар жұптарын толтыру үшін қосымша кестелерден пайдаланамыз. Олар төменде көрсетілген.
| S= | 10 | S= | 9 | S= | 8 | ||||||||||||
| х | 7-х | f4(x) | W5(7-x) | f4(x)+ W5(7-x) | х | 7-х | f4(x) | W5(7-x) | f4(x)+ W5(7-x) | х | 7-х | f4(x) | W5(7-x) | f4(x)+ W5(7-x) | |||
| 10 | 0 | 1,5 | 0 | 1,5 | 9 | 0 | 1,5 | 0 | 1,5 | 8 | 0 | 1,5 | 0 | 1,5 | |||
| 9 | 1 | 1,5 | 1 | 2,5 | 8 | 1 | 1,5 | 1 | 2,5 | 7 | 1 | 1,5 | 1 | 2,5 | |||
| 8 | 2 | 1,5 | 1,2 | 2,7 | 7 | 2 | 1,5 | 1,2 | 2,7 | 6 | 2 | 1,5 | 1,2 | 2,7 | |||
| 7 | 3 | 1,5 | 1,3 | 2,8 | 6 | 3 | 1,5 | 1,3 | 2,8 | 5 | 3 | 1,5 | 1,3 | 2,8 | |||
| 6 | 4 | 1,5 | 1,3 | 2,8 | 5 | 4 | 1,5 | 1,3 | 2,8 | 4 | 4 | 1,4 | 1,3 | 2,7 | |||
| 5 | 5 | 1,5 | 1,3 | 2,8 | 4 | 5 | 1,4 | 1,3 | 2,7 | 3 | 5 | 1,3 | 1,3 | 2,6 | |||
| 4 | 6 | 1,4 | 1,3 | 2,7 | 3 | 6 | 1,3 | 1,3 | 2,6 | 2 | 6 | 0,6 | 1,3 | 1,9 | |||
| 3 | 7 | 1,3 | 1,3 | 2,6 | 2 | 7 | 0,6 | 1,3 | 1,9 | 1 | 7 | 0,3 | 1,3 | 1,6 | |||
| 2 | 8 | 0,6 | 1,3 | 1,9 | 1 | 8 | 0,3 | 1,3 | 1,6 | 0 | 8 | 0 | 1,3 | 1,3 | |||
| 1 | 9 | 0,3 | 1,3 | 1,6 | 0 | 9 | 0 | 1,3 | 1,3 | ||||||||
| 0 | 10 | 0 | 1,3 | 1,3 | |||||||||||||
| S= | 7 | S= | 6 | S= | 5 | ||||||||||||
| х | 7-х | f4(x) | W5(7-x) | f4(x)+W5(7-x) | х | 7-х | f4(x) | W5 (7-x) | f4(x)
+W5(7-x) |
х | 7-х | f4(x) | W5(7-x) | f4(x)+
W5(7-x) |
|||
| 7 | 0 | 1,5 | 0 | 1,5 | 6 | 0 | 1,5 | 0 | 1,5 | 5 | 0 | 1,5 | 0 | 1,5 | |||
| 6 | 1 | 1,5 | 1 | 2,5 | 5 | 1 | 1,5 | 1 | 2,5 | 4 | 1 | 1,4 | 1 | 2,4 | |||
| 5 | 2 | 1,5 | 1,2 | 2,7 | 4 | 2 | 1,4 | 1,2 | 2,6 | 3 | 2 | 1,3 | 1,2 | 2,5 | |||
| 4 | 3 | 1,4 | 1,3 | 2,7 | 3 | 3 | 1,3 | 1,3 | 2,6 | 2 | 3 | 0,6 | 1,3 | 1,9 | |||
| 3 | 4 | 1,3 | 1,3 | 2,6 | 2 | 4 | 0,6 | 1,3 | 1,9 | 1 | 4 | 0,3 | 1,3 | 1,6 | |||
| 2 | 5 | 0,6 | 1,3 | 1,9 | 1 | 5 | 0,3 | 1,3 | 1,6 | 0 | 5 | 0 | 1,3 | 1,3 | |||
| 1 | 6 | 0,3 | 1,3 | 1,6 | 0 | 6 | 0 | 1,3 | 1,3 | ||||||||
| 0 | 7 | 0 | 1,3 | 1,3 | |||||||||||||
| S= | 4 | S= | 3 | S= | 2 | ||||||||||||
| х | 7-х | f4(x) | W5(7-x) | f4(x)+ W5(7-x) | х | 7-х | f4(x) | W5(7-x) | f4(x)+ W5(7-x) | х | 7-х | f4(x) | W5 (7-x) | f4(x)+ W5(7-x) | |||
| 4 | 0 | 1,4 | 0 | 1,4 | 3 | 0 | 1,3 | 0 | 1,3 | 2 | 0 | 0,6 | 0 | 0,6 | |||
| 3 | 1 | 1,3 | 1 | 2,3 | 2 | 1 | 0,6 | 1 | 1,6 | 1 | 1 | 0,3 | 1 | 1,3 | |||
| 2 | 2 | 0,6 | 1,2 | 1,8 | 1 | 2 | 0,3 | 1,2 | 1,5 | 0 | 2 | 0 | 1,2 | 1,2 | |||
| 1 | 3 | 0,3 | 1,3 | 1,6 | 0 | 3 | 0 | 1,3 | 1,3 | ||||||||
| 0 | 4 | 0 | 1,3 | 1,3 | |||||||||||||
| S= | 1 | ||||
| х | 7-х | f4(x) | W5(7-x) | f4(x)+ W5(7-x) | |
| 1 | 0 | 0,3 | 0 | 0,3 | |
| 0 | 1 | 0 | 1 | 1 |
Кестеде көрініп тұрғанындай бұл кәсіпорынға бөлінуі мүмкін болған ресурс мәндері(S=10, 9, 8, …1) үшін жеке-жеке кесте толтырылады. Кестені толтыру ережесі мынадай:
х өрісіне бөлінген ресурс мәнінен бастап кему ретімен 0-ге дейін жазылып шығады;
7-х өрісіне бөлінген ресурстан (х өрісіндегі) қалған бөлігі жазылады;
fi(x) – өрісіне х өрісіндегі мәндерге сәйкес fi(x) кіріс функциясының сәйкес мәндері жазылады;
өрісіне 7-х өрісіндегі мәндерге сәйкес алдыңғы қадамның шартты оптимал Wі+1(7-x) ұтыс мәндері жазылады. Бұл мәндер 2-суретте көрсетілген кестеден алынады;
fі(x)+ Wі+1(7-x) өрісіне осы қадамның шартты ұтыс мәндері жазылады: Wі(x)= fі(x)+Wі(7-x), яғни толтырылып қойылған алдыңғы екі өрістің қосындысы жазылады;
Осылайша, 10 кесте толтырылып шыққан соң, әр кесте бойынша Wі(x)-ң максимал мәндерін және оған сәйкес х өрісінің мәнін 2-суретте көрсетілген кестеге енгізіп шығамыз (Сурет 3).
Сурет 3. Шартты оптимизациялау нәтижелері кестесінің толтырылуы
Енді 3-ші қадамға келдік. Бұл қадамда да 4-ші қадам үшін орындалған әрекеттер қайталанады, яғни S=10, 9, 8, …1 мәндері үшін шартты ұтысты анықтайтын 10 кесте құрылып, солардың ішінен шартты ұтыстардың максимал мәндері мен оған сәйкес ресурс мәні 3-суретте көрсетілген кестеге енгізіледі. Бұл процесс 2-қадам үшін де қайталанады. Тек 1-ші қадамға келгенде ғана кестелер құрудың қажеті жоқ.
Байқалғандай, бұл процессті қолмен жүргізсек өте көп уақыт және еңбекті талап етеді. Ал Excell электронды кестесінде формулалар мен функцияларды пайдалану арқылы бұл процессті бірнеше есе жеңілдетуге және кететін уақытты азайтуға болады. Олай болса, бұл көпэтапты мәселені шешу үшін Excell-де қолданылған формулалар мен функцияларды қарастырамыз [3].
|
|
|
Сурет 4. Көпэтапты мәселе шешімінің Excell-де автоматтандырылған көрінісі
Әр қадамда, яғни әр кәсіпорын (1-шісіне басқа) үшін бөлінуі мүмкін S=10, 9, …, 1 ресурстар үшін құрылатын кестелердің (4-суреттегі Кестелер-3) автомат толтырылуы үшін пайдаланылған формула мен функциялар төменде келтірілген.
| S= | 2 | ||||
| Х | 7-х | f4(x) | W5(7-x) | =СЦЕПИТЬ (D33;»+»;E33) | |
| =B$32-C34 | 0 | =ВПР(B34;$B$6:$G$13;$V$4+1) | 0 | =D34+E34 | |
| =B$32-C35 | 1 | =ВПР(B35;$B$6:$G$13;$V$4+1) | =ГПР(C35;$D$18:$M$28;$V$5) | =D35+E35 | |
| =B$32-C36 | 2 | =ВПР(B36;$B$6:$G$13;$V$4+1) | =ГПР(C36;$D$18:$M$28;$V$5) | =D36+E36 |
Ал 4-суреттегі 4-кесте 3-кестелердегі шартты ұтыстардың Wi(S ) максималдарын және соған сәйкес оптимал басқаруды Xi(S) анықтау үшін құрылған. Анықтауды автоматтандыру үшін пайдаланылған функциялар төменде келтірілді.
Дайындалған бұл электронды кесте параған осы күйінде 5 және одан кем қадамнан тұратын көпэтапты мәселелер үшін қолдануға болады. Ол үшін кіріс функцияларының мәндерін енгізіп шығу қажет (Кесте-1). Бұдан соң әр қадам үшін (і=5-ші қадамнан басқа) мына әрекеттер орындалады:
- Қадам реті қатарына оптимизацияланатын қадам реті енгізіледі.
- Wі(S) -ң кестедегі позициясы қатарына 2-кестедегі Wі(S) мәндері жазылған қатар реті енгізіледі. Мысалы W3(S) үшін, ол кестенің 7-ші қатарында орналасқан, 7 санын енгіземіз.
- Бұдан соң 4-кестеде пайда болған мәндерді (бұл оптимал ұтыс және басқару мәндері) 2-кестенің сәйкес қатарларына көшіріп қоямыз(бұл қатарлар толтырылмаған күйде болады).
Осылайша 2-кесте толтырылған соң сол мәндердің ішінен жалпы максимал ұтысты беретін мәндерді таңдау ғана қалады.
Пайдаланылған әдебиеттер:
- Е.С.Вентцель «Исcледование операций», «Советское радио», М., 1964
- Беллман Р. «Динамическое программирование», М., И, 1960
- В.Долженков, Юлий Колесников «Microsoft Excel-2002», Санкт-Петербург, 2003