Білім беру бағдарламасының атауы мен шифры mo 2645 Оптимизация әдістері Оқу жылы / семестр 2020- 2021/ 5
жүктеу/скачать 2,3 Mb.
|
- Бұл бет үшін навигация:
- Мысал
- Тақырып 3. Дөңес программалау
- Тақырып 4. Сызықтық емес программалау
- Бір өлшемді тиімділеу. Экстремумға арналған есептер
- Теорема (Вейерштрасс теоремасы).
- Іздеу әдістері
| бастапқы тірек шешімін табу
Есептің алғашқы берілгендері кестесі берілсін. Бастапқы тірек шешімін «солтүстік –батыс» ережесі бойынша табайық..
Кестені солжақты жоғарғы бұрышынан бастап, жол бойымен оңға қарай немесе баған бойымен төмен қарай қозғалып толтырайық.. (1,1) торына a1 мен b1 сандарының кіші мәнiн жазамыз, демек x11 = min{ a1 , b1}. Егер a1> b1 болса, онда x11 = b1 сонымен бірінші баған «жабылады», яғни бірінші тұтынушының қажеттілігі қанағаттандырылды. Бірінші баған бойымен әрі қарай қозғаламыз. Көршілес (1,2) торына a1 – b1 мен b2 мәндерінен кішісін жазамыз: x12 = min{ a1 – b1 , b2}. Егер b1 > a1 болса, онда дәл сол сияқты бірінші жол «жабылады». Енді көршілес (2,1) торын тлтырамыз. Оған b1 – a1 мен a2 мәндерінің кішісі жазылады: x21 = min{ a2, b1 – a1}. Дәл осылай қозғалысты кейбір қадамда ap ресурстары мен bq қажеттіліктері таусылғанынша жалғастырамыз. Мысал А және В қоймаларда сәйкес және т жағармай бар. Тізбекті итерацияларды құру Бастапқы тірек шешімін табудан кейін, жаңа, бір бірін жақсартатын тірек шешімдерін құруға кірісеміз: ол үшін потенциалдар әдісін қолданайық.. Сонымен бастапқы тірек шешімі құрылғаннан кейін барлық айнымалылары екі топқа бөлінген: xkl - базистық, және xpq – бос. Бағаның сызықтық функциясы бос айнымалылары арқылы былай өрнектеледі: L= (1) Бос айнымалылардың коэффициенттерін табу мақсатында әр қоймаға кейбір мәнін сәйкестендірейік. Тақырып 3. Дөңес программалау Сағат саны 1. Дөңес талдам элементтері. дөңес функциялар. әлді дөңес функциялар. Тегіс функциялар дөңестігінің критериийлері. Тегіс функциялардың әлді дөңестігінің критерийлері. Дөңес функциялар қасиеттері. Глобал минимум туралы теорема. Тиімділік критерийі. Математикалық програмалау теориясының негіздері. Дөңес программалаудағы Лагранж қағидасы. Лагранж функциясы. Қайқы нүкте. Қайқы нүкте туралы негіқгі лемма. Глобал минимум туралы негізгі теорема. КунТаккер теоремалары. Слейтер шарты. Дөңес программалаудағы түйіндестік. Тақырып 4. Сызықтық емес программалау Мәселенің қойылуы. Тиімділіктің қажетті шарттары. Сызықтық емес программалау есебін шығару алгоритмі. Тақырып 5. Ақырлы өлшемді кеңестіктегі минимумдаудың сандық әдістері Бір айнымалы функцияны минимумдау әдістері. Кесіндіні қақ бөлу әдісі. Алтын қима әдісі. Тиімді іздестіру.сандық тізбектің қасиеті туралы лемма. Градиенттік әдіс. Градиент проекциясы туралы теорема. Ньютон әдісі. Айыптық функциялар әдісі. Лагранж көбейткіштер әдісі. Бір өлшемді тиімділеу. Экстремумға арналған есептер Тиімділеудің бірөлшемді есептері жалпы жағдайда келесі түрде тұжырымдалады: жиынында берілген мақсатты функциясының ең кіші (ең үлкен) мәндерін табу және мақсатты функция экстремумдық мәнді қабылдағандағы жобалау параметрінің мәнін анықтау. Қойылған есептің шешімінің бар болуы келесі теоремадан шығады: Теорема (Вейерштрасс теоремасы). кесіндісінде үздіксіз кез келген функциясы осы кесіндіде ең кіші және ең үлкен мәнді қабылдайды, яғни кесіндісінде кез келген үшін теңсіздігі орындалатындай және нүктелері бар болады. Бұл теорема шешімнің жалғыздығын дәлелдемейді. Берілген кесіндіде экстремумдық мәнге тең бірнеше нүктелер болуы мүмкін. Дербес жағдайда, мұндайға периодтық функцияларды жатқызуға болады. Тиімділеу әдістерін мақсатты функциялардың әртүрлі класстары үшін қарастырамыз. Қарапайым ретінде кесіндісінде дифференциалданатын функциясы болып табылады. функциясы аналитикалық тәуелділік түрінде берілген және оның туындысы үшін айқын өрнек табылады. Мұндай функциялардың экстремумдарын жоғары математика курсындағы дифференциалдық есептеулер әдісімен табуға болады. функциясының ең кіші және ең үлкен мәндері кесіндісінің шеткі нүктелерінде немесе минимум және максимум нүктелерінде болуы мүмкін. Соңғы нүктелер кризистік болуы міндетті, яғни туындысы осы нүктелерде нөлге айналуы керек – бұл экстремумның қажетті шарты. Бұдан функциясының кесіндесіндегі ең кіші және ең үлкен мәндерін анықтау үшін, оның берілген кесіндідегі барлық кризистік нүктелеріндегі және шеткі нүктелеріндегі мәндерін есептеп, алынған мәндерді салыстыру керек. Олардың ішіндегі ең кіші және ең үлкендері ізделінді мәндер болады. Мысал. функциясының кесіндісіндегі ең кіші және ең үлкен мәндерін табыңдар. Шешуі. туындысын есептеймыз: Оны нөлге теңестіріп, кризистік нүктелерін табамыз: нүктесі қарастырылған кесіндіге тиісті емес, сондықтан талдауға үш нүктені қалдырамыз: Функцияның осы нүктелердегі мәндерін есептейміз: Алынған шамаларды салыстыра отрып, функциясының ең кіші мәні нүктесінде, ал ең үлкен мәні нүктесінде болатынын анықтаймыз, яғни: күрделі функцияның туындылары үшін сызықтық емес теңдеулерді шешудің сандық әдістерін пайдалану қажет. Мақсатты функцияның туындысын есептеуге негізделген әдіс оны аналитикалық түрде болуын қалайды. Басқадай жағдайларда кестелік түрде берілген мақсатты функция аргументтің кейбір дискретті мәндерінде есептелуі мүмкін, мұндайда іздеудің әртүрлі әдістері пайдаланылады. Олар мақсатты функцияны жекелей нүктелерде есептеуге және олардың ішінен ең үлкен және ең кіші мәндерді таңдауға негізделген. Берілген есепті шешудің бірқатар алгоритмдері бар. Олардың кейбірін қарастырайық.
Берілген кесіндіде бір минимум бар болсын делік. Есепті іздеу әдісімен шешу үрдісі жобалы параметрді өзгертумен интервалды тізбектей сығудан тұрады. Интервалды анықталмаған интервал деп атайды. Тиімділеу үрдісінің бастапқысында оның ұзындығы -ға тең, ал соңында ол берілген мәнінен кіші болуы керек, яғни жобалы параметрдің тиімді мәні анықталмаған интервалда жатуы керек – кесінді мұндағы . Анықталған интервалды сығудың ең қарапайым тәсілі болып, оны тең бөліктерге бөлуден тұрады, кейін бөліну нүктелерінде мақсатты функцияның мәндерін есептеу керек. Айталық -қарапайым кесінділер саны, бөлу қадамы. мақсатты функцияның түйіндердегі мәндерін есептейміз. Алынған мәндерін салыстыра отырып, олардың ішінен ең кіші мәнін табамыз. санын мақсатты функцияның кесіндісіндегі ең кіші мәні ретінде жуықтап алуға болады. үздіксіз функциясы үшін мәні минимумға жақындауы, нүктелер санына байланысты яғни бөліну нүктелерінің саны өскен сайын минимумды анықтаудағы өсімше нөлге ұмтылады. Тиімді параметрді анықтау тәсілі мақсатты функцияның унимодалдық қасиетін пайдалану болып табылады. Ал бұл, анықталмаған интеравалды сығу үрдісін құруға мүмкіндік береді. Айталық барлық унимодалды функциялар мәндерінің ішінен түйіндерінде ең кішісі болып болсын. Сондықтан жобалы параметрдің тиімді мәні кесіндісінде жатады. Егер интервалдың өлшемі берілген өсімшені қанағаттандыру үшін жеткілікті болмаса, яғни онда оны жаңа бөлу жолымен төмендетуге болады. Тиімділеу үрдісі анықталмаған интервалдың берілген өлшемге жеткенінше жалғастырылады. Мысал. Анықталмаған интервалдың бастапқы ұзындығы болсын. Оны 100 рет кеміту керек. Ол үшін интервалды 200 бөлікке бөлу арқылы жетуге болады. мақсатты функцияның мәндерін есептеп, оның минималды мәнін табамыз. Мұндай ізделінді анықталмаған интервал кесіндісі болып табылады. Бұны басқаша тәсілмен есептейік. Алдымен кесіндісін 20 бөлікке бөлеміз және ұзындығы -ге тең анықталмаған интервалды табамыз, сонымен қатар біз нүктелерінде мақсатты функцияның мәндерін есептейміз. Алынған кесіндісін тағы 20 бөлікке бөле отырып, ұзындығы 0,01 болатын ізделінді интервалды аламыз және ( және нүктелерінде мәні табылған) нүктелерінде мақсатты функцияның мәндерін есептейміз. Сонымен, тиімділеу үрдісінің екінші жағдайында мақсатты функцияның 40 есептемесі жүргізілді, яғни бөліктерге бөлу тиімді есептеуді жүзеге асыруға мүмкіндік береді. Анықталмаған интервалды сығуды және түйіндерді таңда әртүрлі тәсілдерді пайдаланып, тиімді шешімді іздеудің арнайы әдістері бар: кесіндіні жартыға бөлу әдісі, алтын қима әдісі және т.б.
жүктеу/скачать 2,3 Mb. Достарыңызбен бөлісу:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||