PROGRAMI KONVEKS, një pjesë e programimit matematik që studion problemin e maksimizimit të funksionit objektiv konkav f(x) të argumentit vektor x = (x 1, ..., x n), duke plotësuar kufizimet g i (x) ≥ 0, x Є X, i = 1, ..., m, ku g i janë funksione konkave, X është një grup konveks. Një pikë x që plotëson këto kufizime quhet e pranueshme. Rezultati kryesor i teorisë së programimit konveks është teorema e pikës së shalës: në mënyrë që pika e pranueshme x* e një problemi programimi konveks të jetë optimale, është e nevojshme (në kushte mjaft të gjera) dhe e mjaftueshme për ekzistencën e vektorit y. * = (y* 1, ..., y m *) me komponentë jonegativë y* të tillë që pika (x*, y*) të jetë një pikë shale për funksionin Lagranzh
problemet e programimit konveks, domethënë për çdo x Є X dhe y me komponentë jonegativë, pabarazitë plotësohen
Një numër metodash programimi konveks mbështeten në teoremën e pikës së shalës, në të cilën funksioni φ(y 1 , ..., y m) = max x Є X L(x, y) minimizohet për y i ≥ 0, i = 1, . .., m, ose pika e shalës gjendet drejtpërdrejt dhe në vend të funksionit Lagranzh, ndonjëherë përdoren disa nga modifikimet e tij. Një qasje tjetër për zgjidhjen e problemit të programimit konveks shoqërohet me kërkimin e drejtimeve të mundshme të lëvizjes së një pike të pranueshme x, të cilat nuk rrjedhin nga grupi i pikave të pranueshme dhe kur lëvizin përgjatë së cilës funksioni objektiv rritet. Kjo qasje zbatohet përmes një sekuence përsëritjesh. Në çdo përsëritje, llogaritet drejtimi i mundshëm që del nga pika tjetër, pas së cilës bëhet një zhvendosje në këtë drejtim me një distancë të caktuar në pikën tjetër. Ekzistojnë metoda për zgjidhjen e problemeve të programimit konveks që janë përshtatur posaçërisht për rastin kur funksioni objektiv është jolinear dhe kufizimet janë lineare. Në mënyrë tipike, metodat e programimit konveks kërkojnë një numër të pafund përsëritjesh për të përcaktuar me saktësi pikën optimale. Përjashtim bëjnë problemet e programimit kuadratik (funksioni objektiv është shuma e një funksioni kuadratik dhe linear konkav, kufizimet janë lineare) dhe programimi linear (funksioni objektiv dhe kufizimet janë lineare), për të cilat kryesisht përdoren metoda të fundme. Shumë metoda të programimit konveks llogaritës zbatohen si programe kompjuterike; Ekzistojnë gjithashtu paketa softuerike që mbulojnë problemet e programimit linear dhe programimit konveks. Shihni gjithashtu Kërkimin e Operacioneve.
Lit.: Golshtein E. G. Programimi konveks. Elementet e teorisë. M., 1970; Zangwill U. I. Programim jolinear. Qasje e unifikuar. M., 1973.
Shqyrtimi i kësaj klase problemesh zakonisht fillon me një deklaratë Metoda e Lagranzhit të shumëzuesve të papërcaktuar. Për ta bërë këtë, le të supozojmë se/(x b..., X") dhe g(x b ..., X")- Funksionet e vazhdueshme së bashku me derivatet e tyre të pjesshëm, le të heqim tani për tani kushtet e jonegativitetit të ndryshoreve dhe të formulojmë problemin e mëposhtëm për një ekstrem të kushtëzuar:
Për të gjetur zgjidhjen e saj, ne prezantojmë Shumëzuesit e Lagranzhit / = 1, T dhe krijojnë të ashtuquajturat Funksioni i Lagranzhit:
le të gjejmë dhe barazojmë me zero derivatet e tij të pjesshme në lidhje me të gjitha variablat
pasi ka marrë sistemin p + t ekuacionet për të panjohurat x b x p,
Ui-,Up-
Nëse funksioni f(x h ..., X") në pikën 
ka një ekstrem, atëherë ekziston një vektor i tillë Y (0> = (y, 0 ,..., y°) se pika (A r(0) , F (0)) është zgjidhje e sistemit (2.23). Rrjedhimisht, duke zgjidhur sistemin (2.23), marrim pikat në të cilat funksioni (2.20) mund të ketë një ekstrem. Më pas, pikat e gjetura shqyrtohen në të njëjtën mënyrë si kur zgjidhet problemi i një ekstremi të pakushtëzuar.
Kështu, metoda e shumëzuesit Lagrange përfshin kryerjen e hapave të mëposhtëm.
- 1. Hartoni funksionin Lagranzh.
- 2. Gjeni derivatet e pjesshme në lidhje me Xj Dhe y, nga funksioni Lagranzh dhe barazojini ato me zero.
- 3. Sistemi i zgjidhjes (2.23), gjeni pikat në të cilat funksioni objektiv mund të ketë një ekstrem.
- 4. Ndër pikat që janë kandidate për ekstremin, gjeni ato në të cilat arrihet ekstremi dhe llogaritni vlerat e funksionit. f(x, ..., X") në këto pika.
Metoda e paraqitur është e zbatueshme për problemet e programimit konveks, d.m.th. ndaj atyre në të cilat funksioni objektiv është konveks (ose konkav) dhe rajoni i zgjidhjeve të realizueshme, i përcaktuar nga kufizimet, është gjithashtu konveks.
Përkufizimi 1. Funksioni f(x,..., x n), të përcaktuara në një grup konveks X, quhet konveks nëse për ndonjë pikë X, X 2 nga Hee për çdo numër X, 0 X 1 vlen pabarazia
Përkufizimi 2. Funksioni/(*, X„), e përcaktuar në një grup konveks X, quhet konkave nëse për ndonjë pikë X X, X 2 nga Hee për çdo numër X, 0 X
Përkufizimi 3. Grupi i zgjidhjeve të realizueshme për një problem programimi konveks plotëson kushtin e rregullsisë nëse ka të paktën një pikë Xj, që i përkasin rajonit të zgjidhjeve të realizueshme për të cilat g^XJ) =b h i = 1, T.
Teorema 1.Çdo ekstrem lokal i një problemi programimi konveks është global.
Përkufizimi 4. Funksioni Lagranzh i një problemi programimi konveks është funksioni
ku y është shumëzuesi i Lagranzhit.
Përkufizimi 5. Pika (X(0) , T(0)) = (x,°,..., X (',y, 0,..., y” ) thirrur pika e shalës së funksionit të Lagranzhit, Nëse
Le të paraqesim dy teorema të shkurtra që janë të një natyre ndihmëse.
Teorema 2. Plani optimal X (0) detyrat NP- Kjo
ku DA) është një funksion jolinear i diferencueshëm që plotëson kushtet
ku është gradienti i funksionit /
në pikën A" (0).
Dëshmi.
Le ta zgjerojmë funksionin objektiv në një seri Taylor në afërsi të pikës X (())
Ku Oh- vektor i rritjeve të vogla X (0) ;
I - përcaktimi i normës (gjatësisë) së vektorit.
Nga shprehja (2.26) del se nëse ndonjë vlerë e koordinatës vektoriale x| 0) > 0, atëherë derivati do të jetë domosdoshmërisht i barabartë me zero
, pasi ndryshe përgjatë koordinatës x k Mund,
me vlera fikse të variablave të mbetur, vazhdoni të minimizoni funksionin objektiv, duke ulur vlerën e x[0) nëse derivati është më i madh se zero, ose duke u rritur xf nëse derivati është më i vogël
zero. Nëse x| 0) = 0, atëherë duhet të jetë 
sepse
përndryshe ju mund të zvogëloni vlerën f (X m), duke u rritur 4 0) me shumën Dx*, pa ndryshuar vlerat e variablave të tjerë. Prandaj, për çdo për të barazia vlen:
Teorema është vërtetuar.
Le të përcaktojmë tani kushtet e nevojshme dhe të mjaftueshme për ekzistencën e një pike shale të funksionit Lagranzh.
Teorema 3. Kështu që pika (A 10 *, I 0)) me koordinata jo negative është një pikë shalë e funksionit të diferencueshëm L (X, Y), duhet të plotësohen kushtet e mëposhtme:
Dëshmi.
1) Domosdoshmëri. Le të jetë (X (0), Y" (0)) një pikë shale, d.m.th.:
Formula (2.29) është ekuivalente me shprehjen
Bazuar në (2.29) dhe (2.30), kushtet (2.27) dhe (2.28) janë plotësuar. Kështu është vërtetuar domosdoshmëria.
- 2) Përshtatshmëria. Le të supozojmë se kushtet (2.27) dhe (2.28) janë përmbushur. Le të zgjerojmë funksionin L(X, Y) në një seri Taylor në afërsi të një pike
Nga zgjerimi (2.31) dhe duke marrë parasysh kushtet (2.27) dhe (2.28) rezulton se
Dy shprehjet e fundit janë ekuivalente me formulën (2.29). Teorema është vërtetuar.
Pas teoremave të mësipërme, ne formulojmë teoremën tashmë praktikisht të dukshme Kuhn-Tucker.
Teorema 4 (Kuhn - Tucker). Për problemin e programimit konveks (2.20) - (2.21), grupi i zgjidhjeve të pranueshme të të cilave ka vetinë e rregullsisë, pikën X (0) =(xj 0 *,..., x’ 0)), x,- 0> >0, / = 1, Pështë një plan optimal nëse dhe vetëm nëse ekziston një vektor i tillë T = (y 1 (0),..., yi 0)), V/ 0) > 0, / = 1, T, se pika (T (0), H 0>) është një pikë shalë e funksionit Lagranzh.
Nëse në problemin e programimit konveks (2.20) - (2.21) funksioni objektiv dhe kufizimet janë vazhdimisht të diferencueshëm, atëherë teorema Kuhn-Tucker mund të plotësohet me shprehje analitike që përcaktojnë kushtet e nevojshme dhe të mjaftueshme për pikën (X (0), Y i(l), ) ishte pika e shalës së funksionit të Lagranzhit, d.m.th. ishte një zgjidhje për problemin e programimit konveks. Këto janë shprehjet (2.27) dhe (2.28). Ata janë të kënaqur me problemin e programimit kuadratik. Për formulimin përfundimtar të tij, ne paraqesim disa përkufizime dhe një teoremë.
Përkufizimi 6. Forma kuadratike në lidhje me ndryshoret X[, ..., X" quhet funksion numerik i këtyre variablave, që ka formën:
Përkufizimi 7. Forma kuadratike F quhet e caktuar pozitive/negative nëse F(X) > 0/F(X) 0 për të gjitha vlerat e variablave që përbëjnë vektorin X.
Përkufizimi 8. Forma kuadratike F quhet gjysmëpërcaktuar pozitiv/negativ nëse F(X") > O / PO") X, dhe, përveç kësaj, ekziston një grup i tillë variablash - një komponent i vektorit X",Çfarë F(X") = 0.
Teorema 5. Një formë kuadratike është një funksion konveks/konkav nëse është gjysmëpërcaktuar pozitiv/negativ.
Përkufizimi 9. Detyra e minimizimit/maksimizimit të vlerës së një funksioni
nën kufizime
ku quhet një formë kuadratike gjysmëpërcaktuar pozitive/negative, e quajtur problemi i programimit kuadratik(ZKP).
Për këtë problem, funksioni Lagranzh ka formën:
Nëse funksioni Lagranzh ka një pikë shale, atëherë kushtet (2.27), (2.28) janë të kënaqura. Tani duke prezantuar variabla shtesë që i kthejnë pabarazitë në barazi (kjo teknikë përdoret gjithashtu gjatë zgjidhjes së problemeve LP), ne i shkruajmë këto kushte në formën:
Për të gjetur një zgjidhje për ZKP, është e nevojshme të përcaktohet një zgjidhje jo negative për sistemin e ekuacioneve algjebrike lineare (2.32). Një zgjidhje e tillë mund të gjendet metoda e bazës artificiale, aplikohet për të gjetur vlerën minimale të funksionit objektiv artificial F = ^Pj, ku janë variabla artificialë. Metoda, si -
Dihet se në një numër të kufizuar hapash do të gjejë planin optimal ose do të vendosë pazgjidhshmërinë e problemit.
Pra, procesi i gjetjes së një zgjidhjeje për KPK përfshin hapat e mëposhtëm.
- 1. Hartoni funksionin Lagranzh.
- 2. Në formën e shprehjeve (2.27), (2.28) shënojmë kushtet e nevojshme dhe të mjaftueshme për ekzistencën e një pike shale të funksionit Lagranzh.
- 3. Duke përdorur metodën e bazës artificiale, konstatohet mungesa e një pike shale për funksionin Lagranzh ose gjenden koordinatat e tij.
- 4. Shkruani zgjidhjen optimale të problemit origjinal dhe gjeni vlerën e funksionit objektiv.
Le të konsiderojmë elementare shembull numerik(Nr. 1) nga libri i I. L. Akulich "Programimi matematikor në shembuj dhe problema". Sipas planit të prodhimit, ndërmarrja duhet të prodhojë 180 produkte. Ato mund të prodhohen duke përdorur dy teknologji. Në prodhim X të produkteve duke përdorur metodën e 1-rë, kostot ishin xf+4x, fshij., dhe gjatë prodhimit x 2 produktet në mënyrën e dytë janë të barabarta x + 8 x 2 fshij. Përcaktoni sa produkte duhet të prodhohen duke përdorur secilën metodë për të minimizuar koston e porosisë.
Zgjidhje. Funksioni i mëposhtëm duhet të minimizohet:
në kushte: 
Funksioni Lagrange në këtë rast do të duket kështu:
Le të llogarisim derivatet e pjesshme të këtij funksioni në lidhje me X, x 2, y dhe vendosini ato të barabarta me zero: 
Vazhdimi në ekuacionin e parë dhe të dytë në në anën e djathtë dhe duke barazuar anët e majta, marrim pas shkurtesave të dukshme:
Duke zgjidhur këtë ekuacion së bashku me ekuacionin e tretë të sistemit, gjejmë se 
Kjo pikë është një kandidat për ekstremin.
Duke përdorur derivatet e dytë të pjesshëm, është e lehtë të tregohet se pika e gjetur është minimumi i kushtëzuar i funksionit /
Probleme të ngjashme me atë të shqyrtuar paraqiten në shumë mënyra nga praktika ekonomike. Vërtetë, problemet reale përmbajnë, si rregull, një numër të madh variablash dhe kufizimesh, gjë që e bën të pamundur zgjidhjen e tyre pa përdorimin e një kompjuteri. Sidoqoftë, efektiviteti i përdorimit të softuerit të standardizuar përcaktohet nga njohuritë e studiuesit për thelbin e transformimeve të kryera nga kompjuteri. Kjo e ndihmon atë të lundrojë saktë në shumëllojshmërinë e metodave, procedurave llogaritëse dhe sistemeve softuerike të propozuara për zgjidhjen e problemeve të optimizimit.
Për të konsoliduar temën, le të shqyrtojmë një tjetër shembull numerik(Nr. 2). Gjeni vlerën maksimale të një funksioni
në kushte:
Zgjidhje. Funksioni / është konkav sepse është shuma e një funksioni linear f = 2х 2 + 4х ъ e cila mund të konsiderohet si konkave, dhe kuadratike në formë / 2 = -x -2x1, e cila është e përcaktuar negative. Kufizimet përmbajnë vetëm kufizime lineare. Prandaj, ne mund të përdorim teoremën Kuhn-Tucker dhe skemën e zgjidhjes ZKP.
1. Le të kompozojmë funksionin Lagranzh:
2. Le të shkruajmë kushtet e nevojshme dhe të mjaftueshme për ekzistencën e një pike shale të funksionit L.
3. Le të futim ndryshore shtesë jo negative v b V2 në sistemin e pabarazive lineare, w, w 2, duke i kthyer pabarazitë në barazi. Ne marrim një sistem ekuacionesh:
Në këtë rast, sigurisht që plotësohen kushtet e mëposhtme:
Është e nevojshme të gjendet një zgjidhje bazë për sistemin e ekuacioneve (2.33) për të përcaktuar koordinatat e pikës së shalës së funksionit Lagranzh. Për këtë qëllim, ne do të përdorim metodën e bazës artificiale. Minimizimi i një funksioni objektiv artificial
Ku Zi, Zi- variabla artificialë, në kushtet e mëposhtme:
Këtu zgjidhja e dukshme themelore e realizueshme duket si kjo:
Funksioni i synuar F Le ta shprehim atë në terma të variablave jo bazë:
Duke përfunduar arsyetimin tonë, vërejmë se shkon në zero kur Xj (0) = 1, = 1 dhe variablat e tjerë kanë vlera zero. Kështu, T (0) = (1, 1) është plani optimal për problemin origjinal,
(Dokument)
n1.doc
Programim konveks. Teorema Kuhn-Tucker. Kushtet e Kuhn-Tucker
Në kushte
(1.3)
Ku janë funksionet 
supozohet se janë konveks.
Nëse 
dhe janë funksione konkave, atëherë kemi një problem maksimizimi 
nën kufizime 
Dhe 
Le të hartojmë funksionin Lagrange për këtë problem:
Një pikë quhet pikë shalë e funksionit (1.4) nëse pika është pika minimale e funksionit 
, dhe pika është pika maksimale e funksionit. Me fjalë të tjera, për një pikë shale për të gjithë 
Dhe 
lidhja qëndron
(1.5)
Teorema 1 (teorema Kuhn-Tucker). Le të ketë të paktën një pikë 
, per cilin 
. Pastaj një kusht i domosdoshëm dhe i mjaftueshëm për optimalitetin e vektorit 
, që i përket fushës së zgjidhjeve të realizueshme të problemit (1.1)-(1.5), është ekzistenca e një vektori të tillë 
që është për të gjithë dhe 
pabarazitë (1.5) qëndrojnë
Le ta pranojmë këtë teoremë pa prova.
Teorema Kuhn-Tucker quhet edhe teorema e pikës së shalës.
Nëse 
Dhe 
janë funksione të diferencueshme, atëherë pabarazitë në (1.5) janë ekuivalente me kushtet e mëposhtme lokale Kuhn-Tucker:
Këto shprehje nënkuptojnë që vlerat e derivateve merren në pikë 
.
1.2. Programim kuadratik. Metoda Barankin-Dorfman.
Një rast i veçantë i një problemi programimi konveks është një problem programimi kuadratik. Problemi kryesor në programimin kuadratik është minimizimi i funksionit Z, i cili është shuma e një funksioni linear dhe një funksioni kuadratik:
Nën kufizimet lineare
Matrica D supozohet të jetë e caktuar simetrike dhe jo negative. Në këtë rast, funksioni (2.1) do të jetë konveks.
Për problemën (2.1) - (2.3), le të hartojmë kushtet lokale Kuhn-Tucker (1.6) - (1.7), të cilat janë kushte të nevojshme dhe të mjaftueshme për optimalitetin e zgjidhjes së problemit (2.1) - (2.3).
Funksioni Lagranzh në këtë rast ka formën:
Le të gjejmë derivatet e pjesshme të këtij funksioni:
Le të shënojmë
Duke marrë parasysh këto shënime dhe marrëdhënie (2.4) dhe (2.5), kushtet Kuhn-Tucker (1.6) - (1.7) marrin formën e mëposhtme
Barazimet (2.6) dhe (2.7) formojnë një sistem N=n+m ekuacionesh lineare me 2N=2(n+m) të panjohura: .
Pra, në përputhje me teoremën Kuhn-Tucker, zgjidhja 
problemi (2.1) – (2.3) i programimit kuadratik është optimal nëse dhe vetëm nëse, së bashku me zgjidhjen 
ka zgjidhje 
Dhe 
e tillë që është një zgjidhje e sistemit (2.6) – (2.8) që i nënshtrohet barazisë (2.9).
Kushti (2.9) për problemin (2.1) - (2.3) është i barabartë me përmbushjen e kushtit
Ekzistojnë disa metoda për zgjidhjen e një problemi të programimit kuadratik. Le të shqyrtojmë një prej tyre - metodën Barankin-Dorfman.
Me këtë metodë, së pari sistemi i ekuacioneve (2.6) – (2.7) reduktohet në formën:
Ku 
(ndryshoret bazë) dhe 
(ndryshoret e lira) janë elementë të ndryshëm të disa ndërrimit të variablave, dhe të gjitha 
janë numra jonegativë (i=1,2,…,N).
Më pas nga sistemi (2.11) gjendet zgjidhja fillestare e referencës
Sistemet (2.6) – (2.8), dhe komponentët vektorë 
e rregulluar në rregull.
Nëse për zgjidhje 
plotësohet kushti (2.10), atëherë problemi (2.1) – (2.3) zgjidhet dhe zgjidhja optimale e tij është 
gjendet nga komponentët përkatës të vektorit .
Nëse kushti (2.10) nuk plotësohet, atëherë përpilohet tabela e mëposhtme për të kaluar në një zgjidhje tjetër referuese (Tabela 2.1). Pjesa kryesore e kësaj tabele përfshin rreshta për të gjitha variablat, të renditura sipas radhës. Për variablat bazë, elementët e rreshtit merren nga sistemi (2.11), dhe për ndryshoret e lira - nga marrëdhëniet
Parametrat e pjesës shtesë të tabelës 2.1 janë si më poshtë:
A) 
gjenden nga formula 
Ku 
- një vektor i përbërë nga elementë të kolonës së katërt të pjesës kryesore të tabelës;
B) për ato s për të cilat 
, llogariten parametrat e mbetur: 
(elementet e kolonave përkatëse që japin minimumin 
, e shënuar me një yll), 
.
Kolona që korrespondon me negativin më të vogël 
, caktohet si kolonë zgjidhëse, rreshti me elementin e shënuar me yll në këtë kolonë është rresht zgjidhës dhe vetë ky element është element zgjidhës dhe me ndihmën e tyre kryhet transformimi i thjeshtë i tabelës 2.1.
ku:
Si rezultat, merret një zgjidhje e re referencë e sistemit (2.6) - (2.8). Ky proces vazhdon derisa të plotësohet kushti (2.10). Nëse gjithçka 
, A 
, më pas zgjidhet një zgjidhje tjetër si fillestare.
1.3 Një shembull i zgjidhjes së një problemi duke përdorur metodën Barankin-Dorfman
Minimizo funksionin
Me kufizime:
; 
.
Zgjidhje
Ne gjejmë zgjidhjen fillestare të mbështetjes së sistemit (2.12). Në këtë rast, vlera e funksionit objektiv është e barabartë me .
Atëherë kushti (2.10) nuk është i plotësuar dhe, për rrjedhojë, zgjidhja nuk është optimale.
Le të përpilojmë tabelën 2.2 për të kaluar në një zgjidhje të re referimi të sistemit (2.12) - (2.13). Le të plotësojmë pjesën kryesore të kësaj tabele duke përdorur sistemin (2.12).
A) për pjesën shtesë të tabelës gjejmë:
B) për pozitive 
Dhe 
Le të llogarisim parametrat e mbetur:
Kolona e katërt, e cila korrespondon me negativin më të vogël 
, caktojmë një kolonë zgjidhëse, një rresht me elementin 3 të kësaj kolone si rresht zgjidhës dhe vetë elementin 3 si element zgjidhës dhe me ndihmën e tyre kryejmë një transformim simplex të tabelës 2.2.
Si rezultat, marrim tabelën 2.3 që përmban një zgjidhje të re referimi.
Për këtë zgjidhje
Prandaj, ne plotësojmë pjesën shtesë të tabelës 2.3 në të njëjtën mënyrë siç u bë në rastin e mëparshëm, për të kaluar në një zgjidhje të re referimi të sistemit (2.12) - (2.13).
Duke i nënshtruar tabelës 2.3 një transformimi simplex me një element rezolucioni prej 13.30, marrim një tabelë tjetër me një zgjidhje referimi për të cilën 
.
Kështu, u gjet zgjidhja optimale 
, në të cilin funksioni objektiv Z i këtij problemi është minimizuar. ku 
1.4 Detyrë individuale: zgjidhja e problemit duke përdorur metodën Barankin-Dorfman
;
Zgjidhje
Nga relacionet (2.6) - (2.7) marrim sistemin e mëposhtëm të ekuacioneve:
Pas transformimeve të thjeshta, ne e sjellim këtë sistem në formën:
(2.14)
Nga ku, duke marrë parasysh jonegativitetin
Gjetja e zgjidhjes bazë fillestare 
sistemet (2.14). Në këtë rast, vlera e funksionit objektiv është e barabartë me 
.
Meqenëse , atëherë kushti (2.10) nuk është i plotësuar dhe, për rrjedhojë, zgjidhja nuk është optimale.
Le të përpilojmë tabelën 2.4 për të kaluar në një zgjidhje të re bazë të sistemit (2.14) - (2.15).
Tabela 2.4
| 1 | -  | -  | -  |
||||
| | 0 | -1 | 0 | 0 |
|||
| | 0 | 0 | -1 | 0 |
|||
 | 4 | 1 | -2 | 0 |
|||
| | 0 | 0 | 0 | -1 |
|||
 | 2 | 4 * | -6 | -2 |
|||
 | 4 | 2 | 0 | -1 |
|||
 | 32 | ||||||
 | 12 | -10 | -4 |
||||
 | 4 | ||||||
 | 1/2 | Tabela 2.5 | 0 | 0 | -1 |
||
| | 0 | -1 | 0 | 0 |
|||
| | 3 | -1/2 | 3 * | 0 |
|||
| | 110,25 | ||||||
| | -2,5 | 9 | -2 |
||||
| | -3 |
Leksioni 11.Programim konveks
Përkufizimi 1. Z problem programimi konveks quhet problem programimi jolinear ku të gjithë funksionet janë konveks.
Kështu, problemi i programimit konveks është një problem minimizimi i kufizuar, ku funksioni objektiv është konveks dhe rajoni i realizueshëm është një grup konveks i formuar nga një sistem pabarazish konvekse. Prandaj, deklaratat e marra më parë në seksionin 6 janë të vlefshme për problemin e programimit konveks. Në këtë seksion do të specifikojmë këto rezultate të përgjithshme dhe do t'i vendosim në një formë më të përshtatshme për të studiuar dhe zgjidhur problemin e mëposhtëm të programimit konveks:
(1)
,
(2)
.
(3)
Do të na duhen disa ndërtime ndihmëse në hapësirë 
vektorët 
. Vektori i të parës 
komponent pikë 
do të shënojmë me 
. Kështu që, 
.
Për problemin (1) – (3) përcaktojmë bashkësinë
Ku 
.
Lemë
.
Për problemin e programimit konveks (1) - (3)
një tufë me
në mënyrë konvekse.
Dëshmi.
Le të zgjedhim vektorë arbitrarë 
nga shumë 
dhe numri 
. Pastaj ka pika 
Dhe 
nga
të tilla si . Le t'i shumëzojmë këto pabarazi me 
Dhe 
, respektivisht, dhe mblidhini ato. Për shkak të konveksitetit të të gjitha funksioneve, marrim
Nga pabarazitë e fituara del se bashkësia është konveks 
.
Teorema 1.
(Teorema Kuhn-Tucker në formën e pikës së shalës së funksionit të Lagranzhit të një problemi programimi konveks
) Lëreni problemin e programimit konveks (1) – (3) sistemi (2) të plotësojë kushtin Slater në lidhje me 
ishte një zgjidhje për problemin (1) - (3), është e nevojshme dhe e mjaftueshme që të ketë një vektor jo negativ 
sikurse 
– pika e shalës së funksionit Lagranzh.
Dëshmi. Meqenëse mjaftueshmëria e këtij kushti është vërtetuar tashmë për një problem arbitrar programimi jolinear (shih Teoremën 2.6 në hyrje), mbetet vetëm të vërtetohet domosdoshmëria.
Domosdoshmëri.
Le
– zgjidhja e problemit (1) – (3). Le të vendosim 
. Është e qartë se 
, sepse
,
Dhe
.
Le të sigurohemi që 
. Le të supozojmë të kundërtën. Kjo do të thotë se ka një pikë 
sikurse 
. Prandaj, 
– një pikë e tillë e pranueshme, vlera e funksionit objektiv në të cilën është më e vogël se minimumi. Kemi një kontradiktë me faktin se
– zgjidhja e një problemi programimi konveks.
Kështu që, 
. Sipas lemës, grupi 
konveks. Rrjedhimisht, të gjitha kërkesat e teoremës 8.2 janë përmbushur. Prandaj ka një jo-zero
vektoriale 
referencë në pikë 
per shume 
:
Le të verifikojmë më tej se të gjitha koordinatat e vektorit 
nuk janë pozitive. Le të supozojmë të kundërtën. Le të ketë një koordinatë 
. Le të rregullojmë vektorin 
të gjithë komponentët përveç 
-Uh. Pastaj, duke pasur parasysh se produkti 
mund të marrë vlera arbitrare të mëdha (për shkak të pakufizimit nga lart të koordinatës 
), marrim një kontradiktë me pabarazinë (4).
Është e lehtë të shihet se për çdo 
vektorët 
të përfshira në komplet 
. Pastaj nga (4) kemi:
Le ta tregojmë atë 
. Le të mos jetë kështu. Pastaj 
. Prandaj, 
. Sipas gjendjes së Slater, ekziston një vektor 
sikurse 
. Kjo është arsyeja pse 
. Kontradikta që rezulton do të thotë se 
.
Le të shënojmë 
. Le të tregojmë se vektori i ndërtuar 
paraqet vektorin e dëshiruar të shumëzuesve të Lagranzhit. Është e qartë se 
dhe nga (5) marrim
Prandaj, në
duhet
.
(7)
Nga ana tjetër, që nga 
(sepse 
) Dhe 
, marrim pabarazinë
. Nga këtu dhe nga (7) rrjedh se në pikën 
plotësohet kushti i jongurtësisë plotësuese:
.
(8)
Nga (6) dhe (8) kemi
ose, çfarë është e njëjta,
Tjetra, le 
. Pastaj 
. Nga këtu dhe nga (8) marrim pabarazinë
Pabarazitë (9), (10) nënkuptojnë se 
është pika e shalës së funksionit të Lagranzhit të problemit konveks.
logo programimi. Kjo është ajo që kërkohej.
Përpara se të njihemi me një version tjetër të teoremës Kuhn-Tucker, ne paraqesim teoremën e mëposhtme, e cila është një kriter minimal i kushtëzuar përsa i përket koneve vektoriale mbështetëse.
Teorema 2.
Le 
– konveks dhe i diferencueshëm në 
funksion, grup 
konveks. Pastaj për të vënë një pikë
ishte minimumi i kushtëzuar i funksionit 
në një set 
, është e nevojshme dhe e mjaftueshme që të ndodhë përfshirja
.
(11)
Prova rrjedh drejtpërdrejt nga teorema 6.5 dhe përkufizimi i konit 
vektorët mbështetës në një pikë 
per shume
.
Teorema
3.
(Teorema Kuhn-Tucker në formë diferenciale për një problem programimi konveks
) Le të jepet një problem programimi konveks në formën (1), (2), ku të gjitha funksionet 
janë vazhdimisht të diferencueshëm, sistemi (2) plotëson kushtin Slater. Pastaj me qëllim për vektorin 
ishte një zgjidhje për problemin (1), (2), është e nevojshme dhe e mjaftueshme që të ketë një vektor jo negativ 
të tilla që të plotësohen kushtet
,
(12)
.
Dëshmi.
Le të tregojmë se kushtet (12) dhe (13) janë ekuivalente me përfshirjen (11). Lëreni pikën 
eshte ajo 
. Pastaj 
Dhe 
.
Lëreni tani 
. Pastaj nga teorema 2 dhe 10.5 rrjedh se një kusht i domosdoshëm dhe i mjaftueshëm për një ekstrem është ekzistenca e faktorëve të tillë 
,
, per cilin 
. Le të vendosim 
per te gjithe 
dhe nga barazia e fundit marrim kushtet (12) dhe (13). Kjo është ajo që kërkohej.
Për të përfunduar këtë pjesë, ne paraqesim formulimet e dy teoremave Kuhn-Tucker për problemin e llogaritjes
programim konveks me kufizime lineare.
Teorema 4.
Lere ne problemin e programimit konveks (1) – (3) sistemi i kufizimeve (2) te kete formen 
, b – vektori i dimensionit 
. Pastaj në mënyrë për një vektor jo negativ
ishte një zgjidhje e problemit, është e nevojshme dhe e mjaftueshme në mënyrë që
kishte një vektor jo negativ
sikurse
është pika e shalës së funksionit të Lagranzhit të këtij problemi.
Vini re se në këtë rast funksioni Lagranzh ka formën .
Teorema
5.
Lëreni problemin e programimit konveks (1), (2) funksionin objektiv
është vazhdimisht i diferencueshëm, sistemi i kufizimeve (2) ka formën 
, ku A është matrica e dimensionit 
, b – vektori i dimensionit 
.
Pastaj me qëllim për vektorin 
ishte një zgjidhje e problemit, është e nevojshme dhe e mjaftueshme që të ekzistojë një vektor jo negativ
të tilla që të plotësohen kushtet
,
.
Vini re se teorema 4 dhe 5 nuk kërkojnë përmbushjen e kushtit Slater, prandaj ato nuk janë raste të veçanta të teoremave 1 dhe 3 dhe kërkojnë prova të pavarura.
Le të na jepet një sistem pabarazish të formës
(4.3) dhe funksionin
Z = f (x 1 , x 2 , …, x n), (4.4)
Për më tepër, të gjithë funksionet janë konveks në një grup konveks M, dhe funksioni Z është ose konveks në grupin M ose konkav.
Problemi i programimit konveks është gjetja e një zgjidhjeje për sistemin e kufizimeve (4.3) në të cilin funksioni objektiv Z arrin një vlerë minimale, ose funksioni konkav Z arrin një vlerë maksimale. (Kushtet për mosnegativitetin e variablave mund të konsiderohen të përfshira në sistemin (4.3)).
Për shkak të vetive 3 0, çdo problem i programimit linear është një rast i veçantë i një problemi programimi konveks. Në përgjithësi, problemet e programimit konveks janë probleme programimi jolineare. Ndarja e problemeve të programimit konveks në një klasë të veçantë shpjegohet nga vetitë ekstremale të funksioneve konveks: çdo minimum lokal i një funksioni konveks (maksimumi lokal i një funksioni konkav) është gjithashtu global; përveç kësaj, në funksion të vetive 2 0, një funksion konveks (konkav) i përcaktuar në një grup të kufizuar të mbyllur arrin një maksimum global dhe një minimum global në këtë grup. Nga kjo rezulton se nëse funksioni objektiv Z është rreptësisht konveks (rreptësisht konkav) dhe nëse fusha e zgjidhjes së sistemit të kufizimit nuk është bosh dhe e kufizuar, atëherë problemi i programimit konveks ka gjithmonë një zgjidhje unike.
Funksioni F(X) = F(x 1, x 2, …, x n) thirret të ndashme, nëse mund të paraqitet si një shumë funksionesh, secila prej të cilave varet vetëm nga një ndryshore, d.m.th. Nëse
(është e mundur që F i (x i) = 0 për disa i).
Le të jepet problemi i programimit konveks nga një sistem kufizimesh (4.3) dhe një funksion objektiv (4.4), dhe funksioni objektiv Z dhe të gjitha kufizimet janë të ndashëm. Atëherë problemi duket si ky:
Gjeni minimumin e një funksioni konveks (maksimumi i një konkave).
nën kufizime
Ideja e metodës së përafrimit linear pjesë-pjesë është që të gjitha fi dhe të gjitha të zëvendësohen nga vija të thyera të përbëra nga segmente të drejta. Në këtë rast, problemi origjinal i programimit konveks zëvendësohet nga një problem i ri, i përafërt, i cili është një problem programimi linear. Ky problem zakonisht zgjidhet duke përdorur metodën simplex, dhe zgjidhja e tij është një zgjidhje e përafërt e problemit origjinal të programimit konveks.
Figura 12. Zgjidhja e problemit të programimit konveks duke përdorur metodën e përafrimit linear pjesë-pjesë
Për të ndërtuar një problem të përafërt, merrni parasysh një përafrim linear pjesë-pjesë të një funksioni të një ndryshoreje h(x) të përcaktuar në interval. Le ta ndajmë këtë segment në r pjesë me pika x 0 Ekuacioni për seksionin e vijës së thyer ndërmjet pikave (x k ; h k) dhe (x k+1 ; h k+1) ka formën (ekuacioni i një drejtëze të bazuar në dy pika). Nëse secilën nga relacionet në këtë barazi e shënojmë me: Vini re se për secilën ka një vlerë unike që plotëson kushtet (4.7). Pasi të kemi shënuar, mund ta rishkruajmë (4.7) në formën: [Ekuacionet (4.8) quhen ekuacione parametrike të segmentit. Nëse h(x) = 0, atëherë e dyta nga këto ekuacione bëhet identiteti 0 = 0, dhe i pari merr formën (4.1) - ekuacioni i segmentit që shtrihet në boshtin e abshisës]. Kështu, për cilindo, ekuacioni i vijës së thyer mund të shkruhet si: Për më tepër, vetëm dy vlera janë gjithmonë të ndryshme nga zero (nëse x është pika e brendshme e segmentit k-të të ndarjes) ose një (nëse x përkon me fundin e segmentit). Duke iu rikthyer problemit të programimit konveks me funksione të ndashme, vërejmë se para së gjithash (në varësi të sistemit të kufizimeve) është e nevojshme të përcaktohet intervali i ndryshimit të secilës ndryshore x j. Më pas secili prej këtij intervali ndahet në pjesë me pika x jk dhe duke përdorur formulat (4.9) ndërtohet një përafrim linear pjesë-pjesë për funksionet f j dhe. Pas kësaj, ne mund të shkruajmë një problem të përafërt për problemin origjinal (4.6): Gjeni maksimumin e një funksioni nën kufizime (4.10) Meqenëse problema e përafërt (4.10) është një problem i programimit linear, i cili zakonisht zgjidhet duke përdorur metodën simplex, kushtet për mos-negativitetin e variablave shkruhen veçmas nga kufizimet e tjera. Dallimi midis problemit që rezulton (4.10) dhe problemit të zakonshëm të programimit linear është se për çdo x j nuk ka më shumë se dy fqinjë jozero dhe, për rrjedhojë, dy me të njëjtën j dhe k jo fqinje nuk mund të merren si variablat kryesore. Vini re gjithashtu se për kushtet e jonegativitetit të termave të ndryshores f j (x j) dhe (nëse ka) përafrimi linear pjesë-pjesë, natyrisht, nuk është i nevojshëm. Ky kapitull shqyrtoi vetëm disa nga metodat e optimizimit të përdorura nga menaxherët për të marrë vendime efektive në ndërmarrje. Sidoqoftë, teknikat e përshkruara bëjnë të mundur kuptimin e parimit bazë të përdorimit të aparateve matematikore në ekonomi, i cili ju lejon të zgjidhni nga shumë opsione alternative atë optimale për një rast ose situatë specifike të caktuar.
