Курстық ЖҰмыс тақырыбы: «Мақсат функциясы және математикалық программалау есебінің шектемелері»
Динамикалық программалау есебін пайдаланып
жүктеу/скачать 0,83 Mb.
|
stud.kz-71884
| 2.3. Динамикалық программалау есебін пайдаланып
есептің мәнін шығару Бүтін сандық программалау есептерінің бірі болып табылатын, ізделінетін есептің экстремалдық шешімін кейбір белгілі сандар жиынтығын алмастыруын сипаттау арқылы алынатын есеп үлкен қызығушылық танытады. Бұл есептер комбинаторлық типті есептер деген атқа ие болды. Бүтін сандық типтің сызықтық есебін қию əдісімен шешу барысында міндетті түрде олардың кемшіліктеріне көңіл аудару керек, себебі практикалық есептің шешімін алуға мүмкіндік бермейтін жағдайды туғызуы мүмкін. Біріншіден, бұл бірнеше рет бағаларды тізбектеп дəлдеу əдісінің қолданылуымен жəне осымен байланысты есептеу қателіктерімен; екіншіден, формуласы бойынша қосымша сызықтық шектеулерді құрумен түсіндіріледі, мұндағы қателіктер мəні. Мұндай кемшіліктер варианттардың тізбектелген талдауы əдісінде кездеспейді. Варианттардың тізбектелген талдауы əдісінің схемасына Р.Беллман атымен байланысқан динамикалық программалау əдісі; Литтл, Суин, Карел [1] аттарымен байланысқан буындар мен шекаралар əдістері жатады. Варианттарды тізбектеп талдау əдісінің қию əдісінен айырмашылығы, бұл əдіс сызықтық программалау аппаратын мүлдем пайдаланбайды жəне есептеу қателіктерін жібермейді. Динамикалық программалау əдісі — бұл басқарудың жіберуші дискретті жиынымен берілген математикалық программалау есептерінің тиімді шешімін жылдам табуға мүмкіндік беретін құрал, яғни əр түрлі шешімдерді алып келетін, беталыстың əр түрлі варианттарының кейбір көрсеткіштерінің арасынан ең жақсысын таңдап алу керек. Осы тəріздес кез келген есептің шешімін мүмкін болатын барлық варианттарды теру жолымен жəне олардың арасынан ең жақсысын таңдау арқылы алуға болады. Бірақ мұндай теру қиындық туғызуы мүмкін. Мұндай жағдайда тиімді шешімді қабылдау процесі қадамдарға бөлініп, динамикалық программалау əдісімен зерттелуіне мүмкіндік алады. Динамикалық программалау əдісін пайдаланып жалпы түрде есептің шешімін қарастырайық [2]. Айталық, тиімдеу процесі n қадамға бөлінсін делік. Əрбір қадамда екі типті айнымалыларды анықтау қажет — s жағдай айнымалысын жəне x басқару айнымалысын. s айнымалысы жиынның берілген k-қадамда қандай жағдайларда болатын мүмкіндігін анықтайды. s айымалысына байланысты осы қадамда кейбір айнымалысымен сипатталатын басқаруды пайдалануға болады. х басқаруын k-қадамда пайдалану кейбір нəтижесін береді жəне жүйені кейбір жаңа жағдайына ауыстырады. Сонымен, жүйе ауысқан жағдайы берілген s жағдайымен таңдалынған басқаруына байланысты деп жəне жүйе s жағдайына қандай жолмен ауысқанына байланысты емес деп болжаймыз. k-шы қадамда əрбір мүмкін болатын жағдай үшін мүмкін болатын барлық басқарулар ішінен тиімді басқаруы таңдалынады, оның k-шы мен n-ші қадамдар аралығында алынатын нəтижесі тиімді болу керек. Ары қарай k-қадамды жүзеге асыру нəтижесінде белгілі бір кіріс немесе ұтыс қамтамасыз етіледі деп санаймыз, ол s жүйесінің алғашқы жағдайы мен таңдалынған басқаруына байланысты жəне тең болады. Сонымен, біз екі шартты тұжырымдадық, ол шарттарды қарастырылатын динамикалық программалау есебі қанағаттандыру қажет. Əдетте бірінші шартты — салдары жоқ шарт, ал екіншісін — есептің мақсаттық функциясының аддитивті шарты деп атайды. Бірінші шарттың динамикалық программалау есебі үшін орындалуы Беллманның тиімді принципін тұжырымдауға мүмкіндік береді. Мұны орындамай тұрып, басқарудың тиімді стратегиясына анықтама берейік. Басқарудың тиімді стратегиясы деп басқарулар жиынтығын түсінуге болады. Тиімдеу принципі. Шартты тиімдеу, немесе шартты тиімді басқару, деп аталатын есепті шешудің бірінші кезеңінде Беллман функциясы мен соңынан басталатын əрбір қадамдағы барлық мүмкін болатын жағдайлар үшін тиімді басқарулар ізделінеді. Жоғарыдағыны практикалық жүзінде іске асыру үшін тиімділеу принципінің математикалық тұжырымын беру қажет. Ол үшін кейбір қосымша белгілеулерді енгіземіз. -пенен басқарудың тиімді стратегиясы іске асыра отырып, жүйенің алғашқы жағдайынан соңғы жағдайына көшкендегі n қадамдарынан алынған ең үлкен кірісті белгілейік, ал -пенен қалған n-k қадамдарындағы басқарудың тиімді стратегиясын іске асыра отырып, жүйенің кез келген жағдайынан соңғы жағдайына көшуде алынған ең үлкен кірісті белгілейік. Сонда (1) Соңғы көрсетілген өрнек тиімді принципті математикалық жазуды көрсетеді жəне Беллманның негізгі функционалдық теңдеуі, немесе рекурренттік сəйкестік, деп аталынады. Берілген теңдеуді пайдаланып, динамикалық программалау есебінің шешімін табамыз. Берілген процесті толығырақ қарастырайық. (1) рекурренттік сəйкестігінде k=n-1 деп алып, келесі функционалдық теңдеуді аламыз: (2) Бұл теңдеуде белгілі деп санаймыз. (2)-теңдеуді пайдаланып жəне жүйенің (n-1)- қадамындағы мүмкін болатын жіберілетін жағдайларын қарастыру арқылы шартты тиімді шешімді табамыз жəне (2)-функцияның сəйкес келетін мəндерін табамыз Сонымен, n-шы қадамда жүйенің (n-1)-қадамынан кейінгі кез келген жіберілетін жағдайы ескерілген шартты тиімді басқаруды табамыз. Енді k=n-2 болғандағы функционалдық теңдеуді қарастыруға көшеміз: Барлық жіберілетін мəндерге арналған мəнін табу үшін жəне білу қажет. Мұндағы мəндері анықталған. Кейбір мəндері мен сəйкес келетін жіберілетін жиындар көмегімен үшін есептеулерді жүргізу қажет. Осы есептеулер əрбір үшін шартты тиімді басқаруды анықтауға мүмкіндік береді. Алдында таңдалынған басқарулармен бірге осындай əрбір басқарулар соңғы қадамда кірістің соңғы екі қадамындағы ең көп мəнін қамтамасыз етеді. Жоғарыда сипатталған итерациялық процесті тізбектеп іске асыру арқылы бірінші қадамға да жетеміз. Осы қадамда жүйе қандай жағдайда болатыны белгілі. Сондықтан да жүйенің жіберілетін жағдайларын жобалаудың енді қажеті жоқ, тек қана басқарудың шартты тиімділігінде ескерілген ең жақсы болып табылатын басқаруды таңдау ғана қалады. n-нен біріншіге дейінгі барлық қадамдар үшін Беллман функциясы жəне сəйкес келетін тиімді басқарулар табылғаннан кейін, шартсыз тиімдеу деп аталатын есеп шешімінің екінші кезеңі жүргізіледі. Бірінші (k=1) қадамдағы жүйе жағдайы белгілі ( — алғашқы жағдайы) екендігін пайдаланып, барлық n қадамдар үшін тиімді шешімді табуға болады жəне де нəтиже беретін бірінші қадамдағы тиімді басқаруды. Осы басқаруды қолданғаннан кейін жүйе кейбір жаңа жағдайына көшеді, осыған сүйеніп, шартты тиімдеу кезеңіндегі нəтижелерді пайдалану арқылы, екінші қадамдағы тиімді басқаруды табуға болады жəне ары қарай тағы сол сияқты n- қадамға дейін. Осы жалпы схеманы түсіндіру үшін, есептің мазмұны жағдай айнымалысын таңдауды жəне əр түрлі типтерді басқаруды талап ететін есептің шешімін қарастырайық. Есептің қойлымы. Транспорттық тор n буындардан тұрады, олардың кейбірі магистральдармен байланысқан. Əрбір магистраль бойынша жол құны белгілі жəне схемада белгіленген. 1-пунктіден n-пунктіге дейінгі жол жүрудің тиімді маршрутын анықтау қажет. Берілген есепті шешу жалпы жағдайда үлкен көлемді есептеулермен түйіндескен. Айталық, тор 10 буыннан (қалалардан) тұрсын делік жəне олар бір-бірімен магистральдар арқылы байланыссын делік (сур. қара). 1-сур. Торлар схемасы i пунктінен j пунктіне дейінгі жол жүру құны tij тең, жəне осы матрицаның элементтері схемаға енгізілген (сур.). 1-пунктінен 10-пунктіге дейінгі жол жүрудің тиімді маршрутын анықтау қажет. Берілген есепте шектеу бар — схемада көрсетілген магистральдар бойынша тек қана солдан оңға қарай ғана қозғалыс жасауға болады, яғни, мысалы, 7-пунктіге түссек, онда біз тек қана 10-шыға ғана көшуге құқығымыз бар жəне 5 немесе 6-ға орала алмаймыз. Бұл (берілген схеманың ерекшеліктер жиынтығымен) бізге əрбір 10 пунктілерді 4 белдеудің біреуіне жатқызуға болады дегенді білдіреді. Пункт k-шы белдеуге тиісті деп айтайық, егер де одан нақты k қадам арқылы соңғы (10-шы) пунктіге жететін болсақ, яғни нақты k-1 аралық пунктісіне кіру арқылы. Сонымен, 7, 8 жəне 9 пунктілері бірінші белдеуге, 5 жəне 6 — екінші белдеуге, 2, 3 жəне 4 — үшінші белдеуге жəне 1 — төртінші белдеуге тиісті болады. k-шы белдеудегі қалалардан соңғы пунктіге дейінгі тиімді маршруттарды k-қадамда табатын боламыз. Сонымен, тиімділікті процестің соңынан жүргізетін боламыз, яғни, k-қадамға жеткеннен кейін, k-белдеудің нақты қай қаласына түсетінімізді біз біле алмаймыз. Сондықтан, əрбір осы қалалар үшін соңғы пунктіге дейінгі тиімді маршрутты табу қажет. k-белдеудегі қалалардан 10 пунктіге дейінгі жол жүрудің мүмкін болатын ең аз құны, тек қана осы белдеудің қай қалаларына тап болатынымызға байланысты болады. k-белдеуге тиісті s қаласының нөмірі, k-қадамдағы берілген жүйенің жағдай айнымалысы деп аталынады. (k-1)-белдеуге тиісті қаланың нөмірі k-қадамдағы басқару айнымалысы болып табылады. есебінің k-қадамының шешіміндегі Беллман функциясы деп, s қаласынан соңғы пунктіге дейінгі жол жүрудің мүмкін болатын ең аз құнын атаймыз. Бірінші қадам (k=1) үшін бұл өлшемді іздеу қиын емес — бұл 1-белдеудің қалаларынан соңғы пунктіге дейінгі жол жүру құны: I-кезең. Шартты тиімділеу 1-қадам. k=1.
Келесі қадамдар үшін жол құны екі қосылғыштың қосындысынан k-белдеуді s қаласынан (k-1)- белдеуді J қаласына дейінгі жол құны жəне J қаласынан соңғы пунктіге дейінгі мүмкіндігінше аз болатын жол құнынан тұрады, яғни 2-қадам. k=2.
Сонымен, берілген қадамдағы барлық мүмкін болатын басқаруларды теру арқылы, соңғы пунктіге дейінгі ең аз жол құнын табуға болады. 3-қадам. k=3.
s пунктісінен соңғы пунктіге дейінгі қозғалыстың тиімді бағыты болып табылатын кейбір J* мəнінде баға минимумына қол жеткізіледі. Төртінші қадамда біз 4-белдеуге тап боламыз жəне жүйенің жағдайы анықталған s=1 түрінде болады. 1-пунктіден 10-пунктіге орын ауыстыру барысында аз мөлшерде шығындалу Беллман функциясы арқылы көрініс табады. k-қадамда кейбір J басқаруын таңдау, (k-1)-қадамдағы жүйе жағдайын анықталған түрге əкелетінін ескере отырып, керісінше, ретпенен барлық қадамдар нəтижесін көру арқылы, тиімді маршрутты табуға болады. 4-қадам. k=4.
II-кезең. Шартсыз тиімділеу 1-пунктен 10-пунктіге дейінгі мүмкін болатын ең аз жол құны тең. Осы жол құнына қол жеткіземіз, егер де 1-пунктіден 3-пунктіге жіберілетін болса. Оған түскеннен кейін, алдындағы кестеде көрсетіліп тұрғандай, 6-пунктіге қозғалып, содан 7-пунктіге жəне осыдан соңғы пунктіге қозғалу қажет, яғни тиімді маршрут түрінде болады. жүктеу/скачать 0,83 Mb. Достарыңызбен бөлісу:
|