Optimaliteti është një kusht i domosdoshëm. Suksesi: kushte të nevojshme dhe të mjaftueshme

Le të marrim kushtet e optimalitetit që duhet të plotësojë sekuenca e dëshiruar e kontrollit. Për këtë qëllim, ne e interpretojmë problemin e formuluar më sipër si problem programimi matematik.

Le të paraqesim kriterin (4.2) si një funksion të caktuar të kontrollit të dëshiruar

Këtu poshtë Dhe dhe £ kuptohen si sekuenca, të shkruara për definicion në formën e vektorëve të zgjeruar me dimensione (N+l)m Dhe (N+l)r përkatësisht. Varësia e funksionit të gjendjes përfundimtare J nga Dhe dhe të nënkuptuar dhe manifestohet përmes ekuacionit (4.1). Formalisht, problemi i optimizimit konsiston në gjetjen e një vektori të tillë midis atyre të realizueshëm Dhe, e cila minimizon kriterin . Dhe kjo është - detyrë normale programimi matematik. Kushti i domosdoshëm për optimizëm në një problem të tillë reduktohet në përmbushjen e kushtit të mosnegativitetit të derivatit në pikën e dëshiruar. Dhe në çdo drejtim të pranueshëm, d.m.th.

Në vijim, shënimi përdoret për të treguar gradientin e funksionit skalar J(s) me argument vektorial Dhe, llogaritur në pikën u = a. Nën gradient , siç dihet nënkuptojmë një vektor (kolona) të përbërë nga derivatet e parë të pjesshëm të funksionit / mbi të gjitha argumentet e vektorit Dhe. NË në këtë rast mund të përfaqësohet si më poshtë:

ku nga ana tjetër tregon gradientin e funksionit J sipas një vektori të veçantë .

Le të shpjegojmë tani termin drejtim i vlefshëm. Me drejtim të pranueshëm nënkuptohet një vektor i cili, kur i shtohet vektorit Dhe, nuk do të çojë në shkelje të kufizimeve origjinale të kontrollit për ndonjë vlerë arbitrare të vogël të modulit të vetë vektorit. Me fjalë të tjera, konsiderohet i vlefshëm nëse plotësohet kushti, ku nën U grupi i të gjitha grupeve të pranueshme është i ngjeshur , dhe është mjaft i vogël numër jo negativ. Le të theksojmë gjithashtu se kur shkruajmë disa derivate të pjesshëm, natyrshëm do të supozojmë, pa përcaktuar në mënyrë specifike, se ato ekzistojnë.

Kushti i optimalitetit i paraqitur këtu është i vështirë për t'u punuar për shkak të faktit se ai përdor një vektor kontrolli të zgjeruar Dhe, zakonisht ka një dimension shumë të madh. Le ta transformojmë këtë gjendje në më shumë pamje e thjeshtë. Për këtë qëllim, midis grupit të vektorëve të pranueshëm, ne konsiderojmë vetëm ata që kanë përbërës jo zero në vetëm një të vetme. i momenti. Me fjalë të tjera, ne do të kërkojmë për të gjithë , dhe në . Pastaj kushti i optimalitetit merr një formë më të thjeshtë, domethënë,

për të gjitha të vlefshme d.m.th., plotësimi i kushtit

Meqenëse relacioni (4.4) është i vlefshëm për çdo moment , Në vend të një kushti optimaliteti, marrim një grup të tërë kushtesh optimaliteti të formës (4.4). Përparësitë e këtyre kushteve janë se secila prej tyre përfshin vetëm një vektor të kontrollit të dimensionit T.

Kuptimi fizik secili prej kushteve (4.4) është që ndryshimi i kriterit të terminalit (4.2) për shkak të ndryshimit të kontrollit në i Momenti i th, i llogaritur në lidhje me kontrollin optimal, është një sasi jo negative.

Kushtet e optimizmit (4.4) nuk janë ende të lidhura në mënyrë eksplicite me origjinalin modeli matematik. Le ta vendosim këtë lidhje. Për këtë qëllim, ne do të zbulojmë derivatet , duke e lidhur këtë të fundit me ekuacionin (4.1). Së pari tregojmë se si mund të llogaritet derivati për çdo kontroll Dhe dhe çdo indinjatë. Për ta bërë këtë, ne dallojmë funksionin J = F(x N + l) përgjatë vektorit duke marrë parasysh lidhjen (4.1). Mund të shkruajmë zinxhirin e mëposhtëm të marrëdhënieve:

Këtu, ne shënojmë matricat e derivateve të pjesshëm të një funksioni në lidhje me argumentet e tij dhe, përkatësisht. Për më tepër, këto matrica formohen sipas rregullit të mëposhtëm: secila kolonë e matricës paraqet gradientin e komponentit përkatës të funksionit vektor në lidhje me argumentin vektor. Prezantimi zyrtar i shënimit

marrim një shprehje më kompakte për derivatin

Ne tani gjithashtu prezantojmë zyrtarisht në konsideratë sa vijon funksion skalar:

që në thelb është produkt me pika vektor i përcaktuar në përputhje me relacionin e përsëritjes (4.5), dhe vektor , duke qenë anën e djathtë ekuacioni origjinal (4.1). Funksioni N i i përcaktuar sipas (4.7) quhet Hamiltonian. Le të theksojmë se në rast i përgjithshëm Hamiltoniani është funksion i rastësishëm, pasi varet nga shqetësimi. Siç do të shohim më vonë, Hamiltonian është një ndërtim i përshtatshëm për formimin e kushteve të optimalitetit dhe zbatimin e llojeve të ndryshme. metodat numerike optimizimi. Le të fillojmë me kushtet e optimalitetit. Nuk është e vështirë të përcaktohet se derivatet e pjesshme të Hamiltonian kanë formën e mëposhtme në argumentet e tyre:

Duke marrë parasysh këtë, ekuacionet origjinale të lëvizjes (4.1), si dhe relacionet (4.5) që përcaktojnë vektorin, mund të reduktohen në sa vijon formë kanonike:

Ekuacioni për një vektor zakonisht quhet i konjuguar në lidhje me ekuacioni origjinal për vektor . Prandaj, vetë vektori, sistemi i kënaqshëm (4.8), do të quhet vektor i konjuguar. Për ta përcaktuar atë me një kontroll të njohur, është e nevojshme, siç vijon nga sistemi (4.8), së pari të përcaktohet trajektorja e lëvizjes në kohë të drejtpërdrejtë për një të dhënë. gjendje fillestare. Dhe vetëm pas kësaj, në kohë të kundërt, gjeni vektorin e konjuguar, duke marrë parasysh trajektoren e gjetur dhe gjendjen kufitare të vendosur në vektor, duhet pasur parasysh gjithashtu se për shkak të pranisë së një shqetësimi të rastësishëm në të djathtë anët e ekuacioneve të sistemit (4.8), vektori i konjuguar në rastin e përgjithshëm është gjithashtu i rastësishëm.

Nëse tani i kthehemi shprehjes (4.6), atëherë duke përdorur konceptin e një Hamiltoniani mund të shkruhet në formën

Duke marrë parasysh që, si rregull, operacionet e diferencimit dhe pritshmëria matematikore janë komutative, dhe, për rrjedhojë, barazia vlen

kushtet e nevojshme optimaliteti (4.4) përfundimisht mund të paraqitet në formën sistemin e ardhshëm pabarazitë:

të cilat duhet të plotësohen për të gjitha të vlefshme .

Kështu, kushtet e nevojshme të optimalitetit në problemin e kontrollit të sistemit të programimit (4.1) për të arritur kriterin minimal (4.2) konsistojnë në përmbushjen e sistemit të pabarazive (4.10), i cili duhet të zbulohet duke marrë parasysh sistemin origjinal të ekuacioneve ( 4.1) dhe sistemi i konjuguar i ekuacioneve (4.5) ose, çfarë është i njëjtë, sistemi (4.8).

Në rastin e përgjithshëm, përdorimi i drejtpërdrejtë i këtyre kushteve për të zgjidhur problemin e programimit të kontrollit optimal është i vështirë. Kjo për shkak të jokonstruktivitetit të vetë kushteve (4.10), gjë që manifestohet në faktin se është e vështirë të përdoret fare sistemi i pabarazive për të gjetur zgjidhjen optimale. Vështirësitë rëndohen, nga njëra anë, nga prania në këto pabarazi të funksionimit të pritshmërisë matematikore (mesatarja statistikore mbi të gjithë faktorët e rastësishëm) dhe, nga ana tjetër, nga nevoja që çdo zbatim specifik të zgjidhë problemin e vlerës kufitare. për sistemin e ekuacioneve (4.1) dhe (4.5). Në këtë rast, kontrolli optimal në çdo zbatim duhet të çojë në përmbushjen e të dy kushteve kufitare "në të majtë" në momenti i fillimit për sistemin (4.1), dhe kushtin kufitar "në të djathtë" në momentin përfundimtar për sistemin (4.5).

Duhet theksuar edhe një herë se relacioni (4.6) është i vlefshëm për çdo kontroll fiks (jo domosdoshmërisht optimal). Prandaj, mund të përdoret me sukses në marrjen e kontrollit optimal duke përdorur metodat e optimizimit numerik, pasi lejon, me një kontroll fiks, duke përdorur një llogaritje, fillimisht duke përdorur ekuacionin (4.1), dhe më pas duke përdorur ekuacionin (4.6), të përcaktohen menjëherë të gjithë përbërësit e vektori i gradientit në një zbatim specifik. Përdorimi i relacionit (4.6) së bashku me (4.1) dhe (4.5) për llogaritjen e komponentëve të gradientit do të quhet metoda e sistemeve të konjuguara për hir të shumëfishimit.

Le të diskutojmë tani rastet e veçanta më të zakonshme kur kushtet e nevojshme të optimalitetit mund të sillen në një formë më konstruktive.

1. Nuk ka kufizime në kontroll. Në këtë rast, çdo vektor përcakton drejtimet e pranueshme, duke përfshirë vektorët me të njëjtat vlera absolute, por me shenja të kundërta. Kjo do të thotë se kushtet (4.10) mund të plotësohen vetëm në formën e barazive strikte

Duhet theksuar se ne vijmë edhe në këtë rast kur kufizimet në kontrolle, edhe pse ekzistojnë, kryhen automatikisht.

Zgjidhja e problemit të programimit në këtë rast zbret në përdorimin e kushtit (4.11) në çdo hap kontrolli për të identifikuar strukturën e kontrollit dhe zgjidhjen pasuese të sistemit (4.8) me strukturën e gjetur.

2. Nuk ka shqetësime të rastësishme, . Ky rast korrespondon me kontrollin e një sistemi determinist. Formalisht, funksionimi i pritshmërisë matematikore është lënë jashtë kudo dhe kushtet e nevojshme të optimalitetit (4.40) marrin formën

ku Hamiltoniani dhe vektorët , janë përcaktues dhe përcaktohen duke përdorur relacionet e mëposhtme:

Të gjitha vështirësitë e zgjidhjes së problemit duke përdorur kushte optimale, të diskutuara më herët kur merren parasysh sistemi stokastik, ruhen edhe këtu. Thjeshtimi i vetëm është se, siç është treguar tashmë, funksionimi i pritshmërisë matematikore mungon për shkak të mungesës së vetë faktorëve të rastit.

3. Grupi i kontrolleve të pranueshme është konveks dhe Hamiltoniani është një funksion konveks. Para së gjithash, vërejmë se secili prej kushteve (4.10) në rastin e përgjithshëm mund të interpretohet si një kusht i domosdoshëm për pritshmërinë minimale matematikore të Hamiltonian në lidhje me vektorin e kontrollit. . Më pas, mund të tregojmë se nëse Hamiltoniani është konveks, funksioni gjithashtu do të jetë konveks . Dhe dihet se në rastin e konveksitetit të funksionit të minimizuar në një grup konveks, minimumi është unik dhe për këtë arsye kushtet e nevojshme të optimalitetit do të jenë njëkohësisht të mjaftueshme. Duke marrë parasysh këtë, çdo kusht i sistemit (4.10) në rastin në shqyrtim rezulton të jetë i barabartë me kushtin për arritjen e kontrollit optimal. pritje matematikore Hamiltoniani i vlerës së tij minimale të kontrollit. Me fjalë të tjera, në vend të (4.10) mund të shkruajmë

ku , tregon çdo kontroll të pranueshëm , a përmes - kontrolli optimal i dëshiruar.

Natyrisht, kombinimet e rasteve të veçanta të diskutuara dhe, në përputhje me rrethanat, kushtet e optimalitetit janë të mundshme. Kështu, për shembull, në rastin determinist, d.m.th. në mungesë të shqetësimeve

(), dhe kur Hamiltoniani është konveks, kushtet e nevojshme të optimalitetit marrin formën

Vini re se nëse, kur futni shënimin (4.6), vektori përcaktohet si derivat i funksionit terminal në lidhje me shenjën e kundërt, d.m.th. në formën

atëherë, për shkak të ndryshimit të shenjës së vektorit në kushtet e optimalitetit (4.10), edhe shenja e pabarazisë ndryshon në të kundërtën, dhe si rrjedhojë, në kushtet e optimalitetit (4.12), (4.13) operacioni minimal është zëvendësohet nga një operacion maksimal. Në rastin përcaktues, në vend të (4.13) kemi

Kushti i fundit i optimalitetit në literaturë zakonisht referohet si parimi maksimal i i për sistemet e kontrollit diskrete përcaktues, ose shkurtimisht si parimi i maksimumit përcaktues diskret. Për analogji, kushti (4.13) mund të quhet një parim minimal përcaktues diskret, dhe kushti i optimalitetit (4.12) mund të quhet një parim minimal stokastik diskret.

Sipas diskrete parimi stokastik minimumi (4.12) programi optimal i kontrollit sistem diskret(4.1) në kushte konveksiteti siguron pritjen minimale matematikore të Hamiltonian në çdo hap kontrolli. Më vonë do të shohim se parimi minimal (maksimumi) për problemet me kohë të vazhdueshmeështë e vlefshme pavarësisht nga supozimet për konveksitetin e Hamiltonianit. Megjithatë, për problemet diskrete, këto supozime rezultojnë të jenë thelbësore.

Le të tregojmë tani se në problemin e kontrollit të sistemit diskret (4.1) për të minimizuar kriterin integroterminal (4.3)

ruhen kushtet e optimalitetit që rezultojnë (4.10) ose, përkatësisht, (4.11), (4.12). Megjithatë, në vend të marrëdhënieve (4.7) dhe (4.5) që përcaktojnë vektorin Hamiltonian dhe të konjuguar plotësojnë ekuacionet e mëposhtme:

Sepse për të gjithë , pastaj Hamiltonian deri në komponent përkon me Hamiltonian në (4.14). Prandaj, shprehja për derivatin , pjesëmarrjes në kushtet e optimalitetit mund t'i jepet e njëjta formë (4.9):

përkundër faktit se Hamiltoniani tani përkufizohet sipas (4.14) në vend të (4.7). Dhe kjo do të thotë se kushtet për optimalitet në formë do të mbeten të pandryshuara.

Le të marrim kushtet e optimalitetit që duhet të plotësojë sekuenca e dëshiruar e kontrollit. Për këtë qëllim, ne e interpretojmë problemin e formuluar më sipër si një problem programimi matematikor.

Le të paraqesim kriterin (4.2) si një funksion të caktuar të kontrollit të dëshiruar

Këtu poshtë Dhe dhe £ kuptohen si sekuenca, të shkruara për definicion në formën e vektorëve të zgjeruar me dimensione (N+l)m Dhe (N+l)r përkatësisht. Varësia e funksionit të gjendjes përfundimtare J nga Dhe dhe të nënkuptuar dhe manifestohet përmes ekuacionit (4.1). Formalisht, problemi i optimizimit konsiston në gjetjen e një vektori të tillë midis atyre të realizueshëm Dhe, e cila minimizon kriterin . Dhe ky është një problem i zakonshëm i programimit matematik. Kushti i domosdoshëm për optimizëm në një problem të tillë reduktohet në përmbushjen e kushtit të mosnegativitetit të derivatit në pikën e dëshiruar. Dhe në çdo drejtim të pranueshëm, d.m.th.

Në vijim, shënimi përdoret për të treguar gradientin e funksionit skalar J(s) me argument vektorial Dhe, llogaritur në pikën u = a. Nën gradient , siç dihet nënkuptojmë një vektor (kolona) të përbërë nga derivatet e parë të pjesshëm të funksionit / mbi të gjitha argumentet e vektorit Dhe. Në këtë rast, ajo mund të përfaqësohet si më poshtë:

ku nga ana tjetër tregon gradientin e funksionit J sipas një vektori të veçantë .

Le të shpjegojmë tani termin drejtim i vlefshëm. Me drejtim të pranueshëm nënkuptohet një vektor i cili, kur i shtohet vektorit Dhe, nuk do të çojë në shkelje të kufizimeve origjinale të kontrollit për ndonjë vlerë arbitrare të vogël të modulit të vetë vektorit. Me fjalë të tjera, konsiderohet i vlefshëm nëse plotësohet kushti, ku nën U grupi i të gjitha grupeve të pranueshme është i ngjeshur , a është një numër mjaft i vogël jo negativ. Vëmë re gjithashtu se kur shkruajmë disa derivate të pjesshëm, natyrshëm do të supozojmë, pa përcaktuar në mënyrë specifike, se ato ekzistojnë.

Kushti i optimalitetit i paraqitur këtu është i vështirë për t'u punuar për shkak të faktit se ai përdor një vektor kontrolli të zgjeruar Dhe, zakonisht ka një dimension shumë të madh. Le ta transformojmë këtë gjendje në një formë më të thjeshtë. Për këtë qëllim, midis grupit të vektorëve të pranueshëm, ne konsiderojmë vetëm ata që kanë përbërës jo zero në vetëm një të vetme. i momenti. Me fjalë të tjera, ne do të kërkojmë për të gjithë , dhe në . Pastaj kushti i optimalitetit merr një formë më të thjeshtë, domethënë,

për të gjitha të vlefshme d.m.th., plotësimi i kushtit

Kuptimi fizik i secilit prej kushteve (4.4) është se ndryshimi i kriterit terminal (4.2) për shkak të ndryshimit të kontrollit në i Momenti i th, i llogaritur në lidhje me kontrollin optimal, është një sasi jo negative.

Kushtet e optimalitetit (4.4) nuk janë ende të lidhura në mënyrë eksplicite me modelin matematikor origjinal. Le ta vendosim këtë lidhje. Për këtë qëllim, ne do të zbulojmë derivatet , duke e lidhur këtë të fundit me ekuacionin (4.1). Së pari tregojmë se si mund të llogaritet derivati për çdo kontroll Dhe dhe çdo indinjatë. Për ta bërë këtë, ne dallojmë funksionin J = F(x N + l) përgjatë vektorit duke marrë parasysh lidhjen (4.1). Mund të shkruajmë zinxhirin e mëposhtëm të marrëdhënieve:

marrim një shprehje më kompakte për derivatin

Ne tani gjithashtu prezantojmë zyrtarisht në konsideratë funksionin skalar të mëposhtëm:

i cili është në thelb prodhimi skalar i vektorit, i përcaktuar në përputhje me relacionin e përsëritjes (4.5) dhe vektorit , e cila është ana e djathtë e ekuacionit origjinal (4.1). Funksioni N i i përcaktuar sipas (4.7) quhet Hamiltonian. Theksojmë se në rastin e përgjithshëm Hamiltoniani është një funksion i rastësishëm, pasi varet nga shqetësimi. Siç do të shohim më vonë, Hamiltoniani është një ndërtim i përshtatshëm për formimin e kushteve të optimalitetit dhe zbatimin e metodave të ndryshme të optimizimit numerik. Le të fillojmë me kushtet e optimalitetit. Nuk është e vështirë të përcaktohet se derivatet e pjesshme të Hamiltonian kanë formën e mëposhtme në argumentet e tyre:

Duke marrë parasysh këtë, ekuacionet origjinale të lëvizjes (4.1), si dhe relacionet (4.5) që përcaktojnë vektorin, mund të reduktohen në formën kanonike të mëposhtme:

Ekuacioni për një vektor zakonisht quhet i konjuguar në lidhje me ekuacionin origjinal për vektorin . Prandaj, vetë vektori, sistemi i kënaqshëm (4.8), do të quhet vektor i konjuguar. Për ta përcaktuar atë me një kontroll të njohur, është e nevojshme, siç vijon nga sistemi (4.8), së pari të përcaktohet trajektorja e lëvizjes në kohë direkte për një gjendje fillestare të caktuar. Dhe vetëm pas kësaj, në kohë të kundërt, gjeni vektorin e konjuguar, duke marrë parasysh trajektoren e gjetur dhe gjendjen kufitare të vendosur në vektor, duhet pasur parasysh gjithashtu se për shkak të pranisë së një shqetësimi të rastësishëm në të djathtë anët e ekuacioneve të sistemit (4.8), vektori i konjuguar në rastin e përgjithshëm është gjithashtu i rastësishëm.

Nëse tani i kthehemi shprehjes (4.6), atëherë duke përdorur konceptin e një Hamiltoniani mund të shkruhet në formën

Duke marrë parasysh që, si rregull, operacionet e diferencimit dhe pritshmëria matematikore janë komutative, dhe, për rrjedhojë, barazia vlen

Kushtet e nevojshme të optimalitetit (4.4) në fund paraqiten në formën e sistemit të mëposhtëm të pabarazive:

të cilat duhet të plotësohen për të gjitha të vlefshme .

Në rastin e përgjithshëm, përdorimi i drejtpërdrejtë i këtyre kushteve për të zgjidhur problemin e programimit të kontrollit optimal është i vështirë. Kjo për shkak të jokonstruktivitetit të vetë kushteve (4.10), gjë që manifestohet në faktin se është e vështirë të përdoret fare sistemi i pabarazive për të gjetur zgjidhjen optimale. Vështirësitë rëndohen, nga njëra anë, nga prania në këto pabarazi të funksionimit të pritshmërisë matematikore (mesatarja statistikore mbi të gjithë faktorët e rastësishëm) dhe, nga ana tjetër, nga nevoja që çdo zbatim specifik të zgjidhë problemin e vlerës kufitare. për sistemin e ekuacioneve (4.1) dhe (4.5). Në këtë rast, kontrolli optimal në çdo zbatim duhet të çojë në përmbushjen e kushtit kufitar "në të majtë" në momentin fillestar për sistemin (4.1) dhe kushtit kufitar "në të djathtë" në momentin përfundimtar për sistemin (4.5. ).

Le të diskutojmë tani rastet e veçanta më të zakonshme kur kushtet e nevojshme të optimalitetit mund të sillen në një formë më konstruktive.

Duhet theksuar se ne vijmë edhe në këtë rast kur kufizimet në kontrolle, edhe pse ekzistojnë, kryhen automatikisht.

ku Hamiltoniani dhe vektorët , janë përcaktues dhe përcaktohen duke përdorur relacionet e mëposhtme:

Të gjitha vështirësitë e zgjidhjes së problemit duke përdorur kushtet e optimalitetit, të diskutuara më herët kur shqyrtohet një sistem stokastik, mbeten këtu. Thjeshtimi i vetëm është se, siç është treguar tashmë, funksionimi i pritshmërisë matematikore mungon për shkak të mungesës së vetë faktorëve të rastit.

3. Grupi i kontrolleve të pranueshme është konveks dhe Hamiltoniani është një funksion konveks. Para së gjithash, vërejmë se secili prej kushteve (4.10) në rastin e përgjithshëm mund të interpretohet si një kusht i domosdoshëm për pritshmërinë minimale matematikore të Hamiltonian në lidhje me vektorin e kontrollit. . Më pas, mund të tregojmë se nëse Hamiltoniani është konveks, funksioni gjithashtu do të jetë konveks . Dhe dihet se në rastin e konveksitetit të funksionit të minimizuar në një grup konveks, minimumi është unik dhe për këtë arsye kushtet e nevojshme të optimalitetit do të jenë njëkohësisht të mjaftueshme. Duke marrë parasysh këtë, çdo kusht i sistemit (4.10) në rastin në shqyrtim rezulton të jetë i barabartë me kushtin që pritshmëria matematikore e Hamiltonian të arrijë vlerën e tij minimale të kontrollit nën kontrollin optimal. Me fjalë të tjera, në vend të (4.10) mund të shkruajmë

ku , tregon çdo kontroll të pranueshëm , a përmes - kontrolli optimal i dëshiruar.

(), dhe kur Hamiltoniani është konveks, kushtet e nevojshme të optimalitetit marrin formën

Kushtet e optimizmit

Kur studion çdo lloj problemi optimizimi vend i rëndësishëm ka të bëjë me çështjen e kushtet e optimalitetit ose, siç thonë ata, kushte ekstreme. Ekziston një kusht jashtëzakonisht i rëndësishëm për optimizëm, ᴛ.ᴇ. kushtet që duhet të plotësojë një pikë që është zgjidhje e problemit, dhe kushte të mjaftueshme optimaliteti, ᴛ.ᴇ. kushtet nga të cilat rrjedh se pikë e dhënëështë zgjidhja e problemit.

Shënime:

1. Nëse një funksion ka vetinë e unimodalitetit, atëherë minimumi lokal është automatikisht një minimum global.

2. Nëse funksioni nuk është unimodal, atëherë mund të ketë disa optima lokale, dhe minimumi global mund të përcaktohet duke gjetur të gjitha optimat lokale dhe duke zgjedhur më të voglin prej tyre.

Teorema 4.1.(një kusht jashtëzakonisht i rëndësishëm për një minimum të rendit të parë): Le të jetë funksioni ¦ i diferencueshëm në pikën . Nëse është një zgjidhje lokale për problemin (4.1), atëherë

(4.5)

ku është gradienti i funksionit.

Pika X* zakonisht quhet kushti i kënaqshëm (4.5). pikë e palëvizshme funksionet ose problemet (4.1). Është e qartë se pikë e palëvizshme nuk duhet të jetë një zgjidhje, ᴛ.ᴇ. (4.5) nuk është një kusht i mjaftueshëm për optimizëm. Pika të tilla janë të dyshimta për të qenë optimale.

Shembulli 4.1. Konsideroni, për shembull, funksionin f(x) = x 3 (Fig. 4.4). Ky funksion plotëson kushtin jashtëzakonisht të rëndësishëm të optimalitetit, megjithatë, ai nuk ka as një maksimum dhe as një minimum në X* = 0, ᴛ.ᴇ. dhe periudha X* – pikë e palëvizshme.

Nëse një pikë e palëvizshme nuk korrespondon me optimumin lokal (minimum ose maksimal), atëherë është pika e lakimit ose pikë shale. Për të bërë dallimin midis rasteve kur një pikë e palëvizshme korrespondon me një minimum lokal, një maksimum lokal ose një pikë lakimi, është jashtëzakonisht e rëndësishme të ndërtohen kushte të mjaftueshme optimale.

x*x

Oriz. 4.6. Grafiku i një funksioni që ka një pikë lakimi

Teorema 4.2.(një kusht jashtëzakonisht i rëndësishëm për një minimum të rendit të dytë): Le të jetë funksioni ¦ dy herë i diferencueshëm në pikën . Në rast X* është një zgjidhje lokale për problemin (4.1), atëherë matrica është e përcaktuar jo negative, ᴛ.ᴇ.

h E n, (4.6)

Ku është hesian i funksionit ¦ në pikën .

Kushti i mjaftueshëm për optimalitetin lokal përmban një forcim karakteristik të kërkesave në matricë.

Teorema 4.3.(kusht i mjaftueshëm për një minimum të rendit të dytë): Le të jetë funksioni ¦ dy herë i diferencueshëm në pikën . Le të supozojmë se , dhe matrica është pozitive e përcaktuar, ᴛ.ᴇ.

, h E n, h≠ 0. (4.7)

Pastaj X* – zgjidhje strikte lokale e problemit (4.1). Për funksionin argument numerik (n= 1) kushtet (4.6) dhe (4.7) nënkuptojnë se derivati i dytë si sasi skalare jo negative dhe pozitive, respektivisht.

Pra, për funksionin ¦ argumenti numerik nuk është një garanci për praninë e një optimumi nëse plotësohen kushtet − minimale; − maksimale.

Në mënyrë që një pikë e palëvizshme të jetë një pikë ekstreme, është jashtëzakonisht e rëndësishme që të plotësohen kushte të mjaftueshme ekstremi lokal. Një kusht i mjaftueshëm është teorema e mëposhtme.

Teorema 4.4. Lëreni në pikën X* Së pari ( n−1) derivatet e funksionit zhduken, dhe derivati n e rendit është e ndryshme nga zero:

1) Në rast n− i rastësishëm, atëherë X* – pika e përkuljes;

2) Në rast n− madje, atëherë X* – pika optimale lokale.

Përveç kësaj:

A) nëse ky derivat është pozitiv, atëherë X* – pikë minimale lokale;

b) nëse ky derivat është negativ, atëherë X* – pika e maksimumit lokal.

Për të zbatuar këtë teoremë 4.4 në funksion f(x) = x 3 (shembulli 4.1), le të llogarisim:

Meqenëse rendi i derivatit të parë jozero është 3 ( numër tek), pikë X= 0 është pika e lakimit.

Shembulli 4.2. Konsideroni një funksion të përcaktuar në të gjithë bosht real dhe të përcaktojë pika njëjës:

Kushtet e optimizmit - koncepti dhe llojet. Klasifikimi dhe veçoritë e kategorisë "Kushtet e Optimalitetit" 2017, 2018.

Ekzistojnë dy lloje të kushteve optimale të zgjidhjes: të nevojshme dhe të mjaftueshme.

Kushtet e nevojshme për optimizëm.

Formulimi i përgjithshëm i kushteve të nevojshme: nëse thënia A gjithmonë nënkupton deklaratën B, atëherë B është e nevojshme për A.

Në lidhje me problemin e optimizimit: nga pohimi A (është elementi më i mirë i grupit D) ndjek deklaratën B ( - elementi më i mirë i kompletit L, në pronësi D dhe duke formuar zonën përreth
) (Fig. 1.7).

Kështu papërmirësueshmëria lokale (
- elementi më i mirë ndër elementët e pranueshëm të lagjes së tij) është e nevojshme kusht për
ishte zgjidhja optimale. Me fjalë të tjera, në mënyrë që tëX  D , është e nevojshme qëX  ishte zgjidhja optimale në setL, në pronësiD dhe duke formuar një fqinjësi të pikësX  . Si rregull, shumë L zgjidhet në mënyrë që kriteri dhe kufizimet e problemit origjinal të përkojnë saktësisht me kriteret dhe kufizimet e problemit të thjeshtuar ndihmës, për të cilin zgjidhja mund të identifikohet duke përdorur ekuacione të caktuara. Në këtë rast, ekuacionet që identifikojnë një zgjidhje të papërmirësueshme në nivel lokal rezultojnë të jenë kushte të nevojshme për optimalitetin e problemit origjinal. Në mënyrë tipike, një problem i thjeshtuar ndërtohet duke linearizuar atë origjinal në afërsi të zgjidhjes optimale të dëshiruar.

Kushtet e mjaftueshme për optimalitet.

Formulimi i përgjithshëm i kushteve të mjaftueshme: nëse pohimi A rrjedh gjithmonë nga pohimi B, atëherë B është i mjaftueshëm për A. Në lidhje me problemin e optimizimit nga pohimi B (zgjidhja
është më i miri në set V, duke përfshirë shumë D, dhe
i takon D) ndjek gjithmonë deklaratën A (
- elementi më i mirë i kompletit D) (Fig. 1.8)).

Kështu, papërmirësimi në mbulesën e grupit D, së bashku me përkatësinë ndaj D, është kusht i mjaftueshëm për
ishte zgjidhja optimale e dëshiruar.

Me fjalë të tjera, në mënyrë që tëX  ishte zgjidhja optimale në setD , mjaftueshëm për tëX  ishte zgjidhja optimale në setV , duke përfshirë shumëD , dhe u përkiste shumëD .

Përdorimi i kushteve të mjaftueshme është i këshillueshëm për grupe komplekse zgjidhjesh të pranueshme D, gjë që e bën të vështirë zgjidhjen e problemit, por grupin e zgjeruar V rezulton të jetë shumë më e thjeshtë.

Për shembull, grupi D, i paraqitur në Fig. Këshillohet që 1.8 të zëvendësohet me zonën V, e cila është një drejtkëndësh që përfshin zonën D dhe mund të përshkruhet nga kufizime autonome të formës

(shih Fig. 1.8)

2. Përcaktimi i maksimumit të një funksioni të një ndryshoreje.

2.1. Deklarata e problemit. Metodat për zgjidhjen e problemeve të optimizimit.

Në këtë rast, ka vetëm një variabël në kriterin e optimalitetit. Mund t'i vendosen vetëm kufizime autonome dhe deklarata e problemit merr formën:

(2.1)

(2.2)

Në përputhje me teoremën e Weierstrasse, çdo funksion
, e vazhdueshme në një grup të mbyllur dhe të kufizuar (
), arrin vlerat më të larta dhe më të ulëta mbi të. Funksioni
konveks në
, nëse ka në këtë grup maksimumi i vetëm. Një funksion konveks ka vetinë që nëse përmes dy pikave që i përkasin vizatojmë një vijë të drejtë (me koordinata Dhe
), atëherë çdo pikë e ndërmjetme e kësaj linje nuk do ta kalojë vlerën e funksionit në të njëjtën kohë X(Fig.2.1 ) . Për një funksion konveks shprehja është e vlefshme:

Nëse funksioni nuk është konveks (jo-unimodal), atëherë ai do të ketë disa pika maksimale, dhe vlera e funksionit në këto pika do të jetë e ndryshme (Fig. 2.2)

Në këtë rast, pika që korrespondon me vlerën më të madhe të funksionit (pika
në figurë) quhet pikën maksimale globale, dhe pikat e mbetura (
,,
,) – maksimumi lokal i funksionit.

Të gjitha metodat e zgjidhjes problemet e optimizimit, duke përfshirë metodat për përcaktimin e maksimumit të një funksioni të një ndryshoreje ndahen në:

Analitike, bazuar në kushte optimale të nevojshme ose të mjaftueshme, dhe kushte të mjaftueshme zbatohen vetëm në rastin e zonave komplekse me vlera të pranueshme.D.

Numerike, të cilat janë një procedurë llogaritëse që siguron përsosje sekuenciale të zgjidhjes nga një përafrim fillestar i caktuar në një maksimum me një gabim të caktuar të lejueshëm.

2.2. Metoda analitike për zgjidhjen e problemit. Kushtet për maksimumin e një funksioni të një ndryshoreje.

Le
- funksion i vazhdueshëm dhe dy herë i diferencueshëm në
uX 0 është pika e maksimumit të pritur të funksionit. Në mënyrë që funksioni të arrijë max për X 0, është e nevojshme që për çdo tjetër X, në mënyrë arbitrare afër X 0, d.m.th.
, relacioni (2.3) ishte i kënaqur

Le të shpërbëhemi
në një seri Taylor në afërsi të pikës X 0

Për të vogla  X, termat që përmbajnë rritje të fuqive më të mëdha se një mund të neglizhohen dhe më pas nga (2.4) vijon:

Duke zëvendësuar (2.5) në (2.3) më në fund marrim kusht i nevojshëm maksimumi i një funksioni të një ndryshoreje:

(2.6)

Kur përdorni këtë kusht, mund të ndodhin dy opsione:

1.
- pikë e brendshme diapazoni i vlerave të lejueshme (Fig. 2.3). Në këtë rast shenja  X nuk është përcaktuar dhe për të plotësuar kushtin (2.6) është e nevojshme

(2.7)

Në këtë rast, shenja e diferencës (2.3) përcaktohet nga shenja e termit të parë të hedhur poshtë të serisë Taylor, d.m.th. shenjë
. Prandaj, kushti i nevojshëm max (2.7) plotësohet nga kushti

(2.8)

2.
- pika kufitare e intervalit
. Në këtë rast shenja  X definohet (Fig. 2.4) dhe për llogaritjet do të përdorim shprehjen (2.6).

Fig.2.3. X * X * X

Le të formulojmë rregullat për zbatimin e kushteve të nevojshme për maksimumin e një funksioni të një ndryshoreje.

Shembull. Përcaktoni maksimumin e një funksioni
në

A)
, b)
, V)
;

a) X 0 = 0.6, pika e brendshme e segmentit
Prandaj, shenja e ΔX nuk është e përcaktuar dhe është e nevojshme të kontrollohet përmbushja e kushtit (2.8).