Курстық ЖҰмыс тақырыбы: «Мақсат функциясы және математикалық программалау есебінің шектемелері»
ІІ. Мақсат функциясы және математикалық программалау
жүктеу/скачать 0,83 Mb.
|
stud.kz-71884
| ІІ. Мақсат функциясы және математикалық программалау
есебінің шектемелері 2.1.Динамикалық бағдарламалаудың жалпы есебі және мақсат функциясы Математикалық бағдарламалау есептерінің кез келгенінде айнымалыларға қойылған шектеулерге сәйкес мақсатты функцияның экстремумын табу қажет. Осыған дейін мақсатты функция мен шектеулері сызықтық болып келген есептер қарастырылды. Ал нақты есептерде сызықтық емес тәуелділіктер көптеп кездесетіндіктен сызықтық емес бағдарламалау теориясының жасалу қажеттігі туды. Қазіргі кезде сызықтық емес бағдарламалау есептері жылдам дамып келеді. Математикалық бағдарламалау есептерінің мақсатты функциясы мен шектеулері сызықтық емес болса, онда ондай есептер сызықтық емес бағдарламалау есептері деп аталады. Басқарылатын физикалық жүйе бастапқы жағдайынан уақыт өте келе ақырғы жағдайына келтіріледі. Жағдайлардың өзгеріс үдерісімен сандық белгі байланысты. Үдерісті осы сандық белгі тиімді (оптималды) мәнін қабылдайтындай етіп ұйымдастыру қажет. Мүмкін болатын басқарулар жиынын деп белгілейміз. Онда есеп былай қойылады: жүйесін бастапқы жағдайынан, ақырғы жағдайына белгі тиімді мәнін қабылдайтындай етіп келтіретін, басқаруын анықтау керек. Математикалық түрде , , , . Динамикалық бағдарламалау көп қадамды үдерісті кезеңдермен жоспарлайтындықтан, үдерістің тұтас дамуын ескере отырып, әрбір қадамын келешекті ескере отырып тиімді етеді. Әрбір үдерістің соңғы k-ші қадамы бар, онда шешімді қабылдау келешектен тәуелсіз. Осы себепті бұл қадамда ең үлкен әсер басқару қабылданады. Бұл қадамды жоспарлап алып, оның алдынғы (k-1)-қадам тіркеледі, ал оған өз кезегінде (k-2)-қадам тіркеледі т.с.с. Ақырында бастапқы жағдайына келеді. Динамикалық бағдарламалау осылайша ақырынан бастапқы жағдайға оралатындай болып түзіледі. k-ші қадамды жоспарлау үшін жүйенің (k-1)-ші қадамындағы жағдайын білу керек. Егер жүйенің (k-1)-ші қадамындағы жағдайы белгісіз болса, үдерістің сипатында, осы қадамдағы жағдайына мүмкін болатындай әр түрлі болжамдар жасалады. Соңғы k-ші қадамда әрбір болжамға тиісті тиімді басқару анықталады. Мұндай тиімді басқару шартты тиімді делінеді. k қадамды үдеріс жоспарланады. Жүйенің (k-1)-ші қадамдағы мүмкін болатын жағдайларды делік. Соңғы қадамда олардың әрқайсысына шартты тиімді басқаруларын табамыз. Осылайша k-ші қадамы жоспарланады. Шындығында, соңғы қадам алдында жүйе қандай жағдайда болмасын, алдын ала белгілі соңғы қадамда қандай басқару қабылданатыны. Дәл осылайша (k-1)-ші қадамда да шартты тиімді қадам басқаруы k-ші қадамдағы шартты тиімді қортындыда жүйенің бастапқы жағдайына келеміз. Басқа қадамдарға қарағанда жүйенің бірінші қадамда мүмкін болатын жағдайлар қарастырылмайды, себебі бастапқы жағдай біреу ғана, екінші қадамдағы шартты тиімді басқарулар ескеріле отырып , тиімді басқару бірден анықталады. -ден -ға дейін өтіп, тұтас үдерістің ізделініп отырған тиімді басқаруы алынады. Р.Беллманның [1] көрсетуіндей, көп кезеңді үдерістің тиімді шешімін табу функционалдық теңдеудің шешімін табуға келтіріледі. Шамасы х қаржы екі түрлі кәсіпорнын дамытуға жұмсалады делік. Егер бірінші кәсіпорнына у, екіншісіне х-у қаржы бөлінсе, онда кіріс тиісінше g(y) және h(x-y)-ті құрасын. Жалпы кіріс J максималды болатындай етіп қаржыны бөлу қажет. Қойылған есеп мақсат функциясының максималды мәнін табуға келтіріледі. , , (1) Егер g және h функциялары мәндерінде үздіксіз болса, мақсат функциясының максималды мәні барлық уақытта бар екендігі белгілі. Сонымен max бір кезеңді үдерістегі мүмкін болатын максималды кірісті анықтайды. Кірістің бірлік өлшемі қаржының бірлік өлшемінен өзгеше болуы да мүмкін. Мысалы х теңге болса, g(y) адам-сағат мөлшері, машина қолданғанда үнемделген нәтижесі болуы да мүмкін. Екі кезеңді үдерісті қарастырайық. Бастапқы қаржы у кіріс g(y)-ті алуға жұмсалған шығыннан соң шамасына дейін кемиді , сол сияқты (х-у)-те һ(х-у) кірісінен соң b(x-y)-ке дейін кемиді делік. Онда бір кезеңді үдерістен соң қалған қаржы үшін бөлісті қайта жалғастырамыз , , . Бұл бөліс нәтижесіндегі кіріс , онда толық кіріс . Демек, максималды толық кіріс осы функцияның және айнымалылары бойынша алынатын максимумынан турады . , . N кезеңнен тұратын үдерісте операция N рет қайталанады, толық кіріс функциясы былай анықталады , (2) мұндағы бірінші, екінші, ... , (N-1)-ші кезеңдерде әрі қарай бөлініске түсетін шамалар келесі қатынастармен анықталады: , ; , ; ........................................ (3) , , . Есепті кезеңдерге бөліп, тиімділік қағидасымен N кезеңді үдерісте шешеміз. N кезеңді үдерістегі толық кірістің максималды мәні тек N-нен және бастапқы х шамасынан тәуелді болатындықтан деп аламыз. Онда бір кезеңді үдерісте . (4) Екі кезеңдік үдерісте алғашқыдан қалған шамасын тиімді етіп бөлу қажет. Демек тиімді таңдалғандағы кіріс , ал екі кезеңді үдеріс үшін толық кіріс және функцияларын байланыстыратын (5) рекурентті қатынасымен өрнектеледі.Осылайша тұжырымдай отырып, N кезеңді үдеріс үшін негізгі функцио-налдық теңдеуді аламыз: , (6) Мұнда әрбір кезең есептеулерінде мен бірге -те анықталады. Сонымен динамикалық бағдарламалау есебін функционалдық теңдеулер әдісімен шешкенде N өлшемді есепті N тізбектен тұратын бір өлшемді есептерге келтіреміз. Динамикалық бағдарламалауда үдеріс соңғы жағдайдан бастапқы жағдайына қарай өрбитіндіктен, бұған тән дискретті үдерісті өрнектейтін функционалдық теңдеу: , (7) f-үдеріс мақсаты (кіріс, пайда т.б); N-кезеңдер саны; х-айнымалы, жүйенің N-ші қадамдағы сипаттаушысы; - белгінің нәтижелік мәні, тиімділік қағидасымен алынған; - басқарушы айнымалы, нәтижелік белгінің мәні тәуелді болатын; - белгінің шамасы; N-ші кезеңде алынған, 0 мен х аралығында; - нәтижелік белгінің тиімді мәні жағдайынан бастап қалған N-1 кезеңдерден өткеннен соңғы. N-ші кезеңдегі тиімді басқару делік. Онда жүйенің (N-1)-ші кезеңдегі жағдайының функционалдық теңдеуі: , (8) , себебі шамасын N-ші кезеңде таңдауға байланысты бастапқы х шамасы -ге дейін кеміген. Заводтағы станоктардың тозуын есептей отырып, жұмыс істеуін қарастыру. Заводта екі түрлі бұйымды өңдейтін s станок бар. Бірінші бұйым x станокта өңделеді және одан түсетін жылдық пайда f (x) , ал (s- x) станокта екінші бұйым өңделеді, одан g(s- x) пайда түседі. f және g функциялары үзіліссіз және түрлері белгілі. Бірінші бұйымды өңдейтін станоктардың бір жылдан соң 20%-і, ал екінші бұйымды өңдейтін станоктардың 10%-і амортизацияланады. Алғашқы үш жылда кәсіпорынға максималды пайда түсіретін станоктардың санын анықтау керек. F1(s) -бірінші жылы алынатын максималды пайданы белгілейміз, яғни (1) (1) теңдеуінің оң жағын былай түсінуге болады. Бірінші бұйымды өңдейтін станоктың саны (x) , ол 0 ден s - ке дейінгі интервалда өзгеруі мүмкін, ал әрбір x үшін f(x)+ g(s-x) қосындысын есептеуге болады: Алынған мәндердің арасынан максималды мәні таңдалып алынады. Екінші жылдың басында бірінші бұйымды өңдейтін x станоктан 0.8x, ал екінші өңдейтін (s-x) станоктан 9,0(s-x) станок қалады. Екі түрлі бұйымды өңдейтін станоктың жалпы саны екінші жылдың басында мынадай болады: 0,8x+0,9(s-x)=0,9-0,1x Кәсіпорынның екінші жылы алатын максималды пайдасын F1(0,9s-0.1x) деп, ал алғашқы екі жылда алатын пайдасын F2(s) деп белгілейміз. Сонда F2(s)=max[f(x)+g(s-x)+F1(0,9s-0,1x)] (2) (2) теңдеу F1 (бірінші жылғы максималды пайда) мен (екі жылғы максималды пайда) функцияларын байланыстырады. Егер F3(s) деп үш жылда алынатын максималды пайда шамасын белгілесек, онда F2 және F3 функцияларының арасындағы байланыс келесі теңдеумен өрнектеледі: F3(s)=max[f(x)+g(s-x)+F2(0,9s-0,1x)] (3) (1)-(3) теңдеулері функциональды деп аталады. F және g функциялары берілгендіктен F3(s) шамасын тауып, әр жылдағы қажетті станоктарды анықтауға болады. Берілген есепті F1,F2,F3 табатын үш есепке бөлуге болады. Есепті шешу процесі үш сатыдан немесе адымнан тұрады. Жалпы жағдайда n жылда алынатын максималды пайданы табуға болады, оның теңдеуі Fn(s)=max[f(x)+g(s-x)+Fn-1(0,9s-0,1x)] Жоғарыда қарастырылған станокты жұмыс істеткізу есебінде бір айнымалы қолданылды. Динамикалық программалау модельдерінде бірнеше айнымалысы бар модельдер де кездеседі. Айнымалының санының өсуі шешілу варианттарының өсуіне әкеліп соғады. Ол кезде өлшемділік проблемасы тууы мүмкін, себебі ондай есептерді ЭЕМ (оперативтік жадысының шектеулігіне байланысты) шешу қиындайды. жүктеу/скачать 0,83 Mb. Достарыңызбен бөлісу:
|