Тармақтар және шектер» әдісінің жалпы схемасы

Дискретті програмалау есебін шешуде кең қолданылатын әдістердің бірі тармақтар және шектерәдісі болып табылады. БСПЕ шешудін бұл әдісін шешудің бұл әдісін 1960 ж. Лэнг және Дойг ұсынды, ал оның «екінші ре туылуы» 1963ж. Литтл, Мурти, Суини және Кэрелдің коммивояжер есебін шешуге арналған жұмыстың шығуына байланысты болды.

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

Алгоритм итераивті болып табылады, және әрбір итерацияда D жиынының ішкі жиынында жұмс жүргізіледі. Бұл ішкі жиынды ағымды деп атаймыз және оны D(q) орқылы белгілейміз, мұндағы q — итерация индексі. Бірінші итерацияның басында ағымды жиын ретінде барлық D (D(1) =D) жиыны алынады, және ол үшін кейбір әдіспен maxf(x)<^(Dw)^ мақсат функциясы үшін жоғарғы бағаның мәні есептелінеді.

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

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

Жалпы жағдайда динамикалық программалау есебі келесі түрде құрылады.

Берілген S физикалық жүйесі Sо бастапқы жағдайда тұрсын және басқарылатын болсын. Қандай да бірдей басқаруы арқылы берілген жүйе бастапқы Sо жағдайдан соңғы Sn жағдайға өтеді. Осыдан әр бір U жүргізілетін басқарудың сапасы W(U) функциясының сәйкес мәнімен сипатталады. Есеп u U мүмкін басқарулар жиынының ішінен W(U) функциясы экстремалды W(U) мәнін қабылдайтын u U шешімін табудан тұрады.

Динамикалық программалаудың жалпы есебінің экономикалық интерпретациясын келесі мысалдардан көреміз.

1 есеп. Өзінің тиімді жұмысын жүзеге асыру үшін өндірістік бірлестіктер қолданылатын жабдықтарды мезгілмен ауыстырып отыру керек. Ол ауыстыруда қолданылатын жабдықтын өнімділігі, жөндеуге кететін шығыннан алынатын және ауыстыратын бағасы ескеріледі. Ағымды бес жылдықтын басында өндірісте жаңа жабдық орналатылған деп алайық. Осы жабдықтың өндірісте қолданылған уақытпен тәуелділігі, саны мен қатар жабдықты жөндеуге кеткен шығынның пайдалану уақытынан тәуелділігі кесте түрінде беріледі. Жаңа жабдықты алуға және орнатуға кеткен шығын 40 мың тенгені құрайды және алмастырылған жабдықты шығарып тастайтынын біле отырып бес жылдық ішінде берілген аралықта уақыт аралығында жалпы пайда үлкен болатындай жабдықты алмастыру жоспарын құру қажет. Бұл есепті динамикалық программалау есебі ретінде карастыруға болады, S жүйесі ретіндежабдық кіреді. Бұл жүйенің жағдайы жабдықты қолдану уақытымен (оның жолымен) анықталады, яғни жалғыз параметрмен сипатталады. Басқару ретінде әрбір жылдың басында қолданылатын жабдықты сақтау және ауыстыру шешімі кіреді.

2 есеп. Өнеркәсіпте дайындалатын жоғарғы сұранысқа ие өнімді шығару көлемін ұлғайту үшін А мың тенге көлемінде капитал салымдары бөлінген 1 – ші өнеркәсіпте көрсетілген қаржының ішінен Х мың тенгені пайдалану f (x) мәнімен анықталатын өнім шығарудың өсуін қамтамасыз етеді. Капитал салымдарын өнеркәсіптердің арасында өнім шығарудың максималды көбеюін қамтамасыз ететіндей етіп бөлу қажет. Бұл есепті көпқадамды ретінде қарастыруға болады, егер қаржыны салу тиімділігінен бір өнеркәсіпте, екі өнеркәсіпте т.с.с n өнеркәсіпте зерттесе.

2. Р.Беллман принципі бойынша динамикалық программалау есебінің алгоритмі Кейбір белгілеулер еніземіз және арық қарай болжауға көшеміз. S жүйесінің k-шы қадамдағы (k = 1,и) жағдайын S жүйесін бастапқыдан соңғысына өтуді қамтамасыз ететін u_k басқаруын жүргізу нәтижесінде алынған x^(k) сандар жиынтығымен анықталады деп есептейік. S жүйесі өткен жағдай берілген жағдайдан және таңдалынған басқарудан тәуелді және S жүйесі бұл жағдайға қалай өткенінен тәуелсіз деп есептейміз.

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

Есеп басқарудың тиімді стратегиясын, яғни жүзеге асыру нәтижесінде S жүйесі n қадамда бастапқы жағдайдан кейінгісіне өтетін W(u) пайда функциясының ең үлкен жиынтығы.

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

20 суретте Р.Беллманның оптималдық принципі көрсетілген.