Sarcini de programare convexe. Programare convexă

Un număr mare de situații economice practice, a cărui studiu este subiectul programării matematice sau nu poate fi redus la sarcini liniare (chiar și atunci când o astfel de linearizare este produsă într-o anumită etapă), încercând o considerație mai detaliată, mai duce la neliniaritate.

Cea mai obișnuită sarcină de programare neliniară poate fi formulată după cum urmează:

este necesar să se determine valorile variabilelor N X 1, X2, ..., X N, care satisfac ecuațiile sau inegalitățile formularului

i \u003d 1, 2, ..., m.

și să plătiți o țintă maximă (sau cel puțin)

f (x) \u003d f (x 1, x 2, ..., x n).(2.2)

Să presupunem că F și G sunt funcții specificate neliniare, B I sunt constante cunoscute. De obicei, se crede că toate sau cel puțin unele variabile ar trebui să fie ne-negative.

În cazul particular al programării liniare, se presupune că funcțiile f și g sunt liniare, adică.

Orice altă sarcină de programare matematică, altele decât aceasta, este considerată o sarcină neliniară.

În secțiunile relevante ale matematicii, au fost dezvoltate metode generale (clasice) pentru determinarea funcțiilor maximă și minime ale diferitelor tipuri. Cu toate acestea, o astfel de abordare generală a problemelor de rezolvare practic găsește o utilizare limitată pentru a obține rezultate numerice, deoarece duce la necesitatea de a rezolva sistemele neliniare de ecuații cu multe necunoscute și nu este potrivit pentru găsirea extremelor de margine. Prin urmare, în programarea matematică, metodele care pot servi ca algoritm sunt studiate în principal, adică procedura computațională cu o soluție numerică de sarcini speciale care au aplicații economice specifice. Specificăm unele dintre aceste sarcini.

Cele mai bine studiate sarcini cu limitări liniare și funcția de funcționare neliniară. Cu toate acestea, chiar și pentru aceste sarcini, metodele computaționale sunt dezvoltate numai în cazurile în care funcția țintă are anumite proprietăți. În special, de exemplu, funcția funcției poate fi reprezentată ca

În cazul în care funcția F J (x J) ar trebui, la rândul său, să fie supraimpozate unor limitări. Aceasta este așa-numita funcție separabilă. Într-un alt caz, funcția țintă poate fi înregistrată ca o sumă de funcții liniare și quadratice:

Sarcinile neliniare de acest tip sunt numite sarcini de programare quadratic. Pentru a găsi soluția optimă, valorile D IJ trebuie să fie supraimpozate unor limitări suplimentare.

Sarcinile cu constrângeri neliniare sunt mai dificile decât cu liniar. Pentru a obține o soluție optimă în aceste sarcini, cerințele ridicate rigide ar trebui prezentate funcțiilor G I și F. În particular, soluția optimă a problemei neliniare poate fi obținută dacă limitările G I, definite de inegalitățile neliniare, determină setul convex în spațiul variabilelor (vezi capitolul 1, § 3) și funcția funcției este a Funcția convexă netedă netedă sau concavă. În viitor, se va da o determinare strictă a funcțiilor convexe și concave. Aici este necesar să se indice că funcția convexității funcțiilor F asigură existența unui singur minim, iar proprietatea concavității F este doar una maximă F în regiunea specificată de restricții. În acest sens, sunt construite algoritmii pentru determinarea valorii optime a funcției funcției. În absența convexității sau a concurenței, se întâlnește soluția problemei programării matematice pentru prezența unor scăzute sau a înălțimilor locale, metodele clasice sunt aplicate constatării cărora în cazul general.

Luarea în considerare a acestei sarcini de clasă începe de obicei cu prezentarea. metodă de multiplicatori incerte lagrange. Pentru a face acest lucru, am pus asta / (x b ..., x ") și g (x b ... x ") - funcții continue, împreună cu propriile sale derivați parțiali, vom elimina condițiile pentru non-negativitatea variabilelor și vom formula următoarea sarcină pentru extremum condiționată:

Pentru a-și găsi decizia, introducem lagrange multiplicatori / = 1, t.și alcătuiesc așa-numitul funcția Lagrange.:

noi găsim și echivalează la zero derivații privați pe toate variabilele

după ce a primit sistemul p + T. Ecuații privind necunoscutul x b x n,

UI -,

Dacă funcția. f (x h ..., x ") La punctul are un extremum, atunci există un astfel de vector (0\u003e \u003d (Y, 0, ... y °.) că litera (a g (0), f (0)) este o soluție de sistem (2.23). În consecință, rezolvarea sistemului (2.23), obținem un punct în care funcția (2.20) poate avea un extremum. Mai mult, punctele găsite sunt investigate în același mod ca și atunci când se rezolvă problema extremumului necondiționat.

Astfel, metoda multiplicatorului Lagrange include următorii pași.

1. Funcționați funcția Lagrange.
2. Găsiți derivați privați Xj. și y, Din funcția de la Lagrange și le echivalează la zero.
3. Sistemul de rezolvare (2.23), găsiți puncte în care funcția țintă poate avea un extremum.
4. Printre punctele-solicitante pentru extremum să găsească astfel în care se realizează extremul și să calculeze valorile funcției f (x, ..., x ")la aceste puncte.

Metoda de mai sus este aplicabilă sarcinilor de programare convexe, adică La acestea în care funcția țintă este convexă (sau concavă) și zona de soluții admise determinate de limitări, de asemenea convexă.

Definiție 1.Funcţie f (X.,..., x n), Setați setul convex X numit convex dacă pentru orice puncte X, x 2 de Chill. Pentru orice număr X 0 x 1 inegalitate

Definiția 2.Funcţie/(*, h."), Setați pe un set convex X numit concav dacă pentru orice puncte H. X, X 2. de Chill. Pentru orice număr X 0 X.

Definiția 3.Multe soluții valide ale problemei programării convexe satisfac starea regularității dacă există cel puțin un punct XJ. deținută de zona soluțiilor admisibile pentru care g ^ xj) \u003db H I. = 1, t.

Teorema 1.Orice problemă locală extremum a programului convex este globală.

Definiție 4.Funcția Lagrange a sarcinilor de programare convexe este o funcție

unde u, - Lagrange multiplicator.

Definiție 5.Punct (X (0), T (0)) = (x, °, ..., x (', Y, 0,..., u " ) numit funcția Lagrange Point Point, în cazul în care un

Dăm două teoreme scurte care sunt auxiliare.

Teorema 2.Plan optim X (0)sarcini NP.- aceasta este

unde da) este o funcție diferențiabilă non-liniară care satisfac condiții

unde este funcția de gradient /

la punctul A "(0).

Dovezi.

Răspândiți funcția țintă într-o serie de Taylor în vecinătatea punctului X (())

unde OH - vectori mici X (0);

I este desemnarea normei (lungime) vectorului.

Din expresia (2.26) rezultă că, dacă orice valoare a coordonatelor vectorului X | 0)\u003e 0, atunci va fi cu siguranță zero derivat

, deoarece altfel coordonatele x K. poate sa,

cu valori fixe ale restului variabilelor, continuați să minimalizați funcția țintă, reducând valoarea x [0), dacă derivatul este mai mare decât zero sau în creștere xF. Dacă un derivat al mai puțin

zero. Dacă X | 0) \u003d 0, atunci ar trebui să fie în măsura în care

În caz contrar, ar fi posibil să se reducă valoarea f (x m), Prin creșterea 4 0) cu valoarea DH *, fără a schimba valorile variabilelor rămase. Prin urmare, pentru oricare dintre ele la Egalitatea se efectuează:

Teorema este dovedită.

Vom defini acum condițiile necesare și suficiente pentru existența punctului de șa din funcția Lagrange.

Teorema 3.La punctul (10 * și 0)), cu coordonatele non-negative a fost un punct de tăiere a unei funcții diferențiate L (x, y),condițiile trebuie îndeplinite:

Dovezi.

1) Necesitate. Lasa (x (0), y "(0)) - un punct sfat, adică:

Formula (2.29) este echivalentă cu expresia

Pe baza (2.29) și (2.30), condițiile (2.27) și (2.28) sunt îndeplinite. Nevoia este astfel dovedită.

2) Adecvare. Presupunem că sunt îndeplinite condițiile (2.27) și (2.28). Funcția de răspândire L (x, y) Într-o serie de Taylor în vecinătatea punctului

De la descompunere (2.31) și în condițiile (2.27) și (2.28) rezultă că

Ultimele două expresii sunt echivalente cu formula (2.29). Teorema este dovedită.

După teoremele oferite de teoreme, vom formula teorema aproape evidentă a Kuna-Takker.

Teorema 4 (Kuna - Takcker).Pentru problema programării convexe (2.20) - (2.21), setul de soluții permise are proprietatea regularității, punct X (0) \u003d (xj 0 *, ..., x '0)), x, - 0 \u003e\u003e 0, / \u003d 1, p. Este apoi planul optim și numai atunci când există un astfel de vector t \u003d (în 1 (0), ..., yi 0)), y / 0)\u003e 0, / \u003d 1, t, Ce punct (t (0), h 0\u003e) este un punct de șa de funcția Lagrange.

Dacă în problema programării convexe (2.20) - (2.21), funcția și limitările țintă sunt continuu diferențiate, atunci teoremul Kun poate fi suplimentat cu expresii analitice care determină condițiile necesare și suficiente pentru punctul (x (0 0 ), în I (L),) a fost un punct de șa din funcția Lagrange, adică. El a fost o problemă de rezolvare a programării convexe. Acestea sunt expresii (2.27) și (2.28). Ei satisfac sarcina de programare patratic. Pentru formularea finală, oferim mai multe definiții și o teoremă.

Definiția 6.O formă patrată față de variabila X [, ..., x " Funcția numerică a acestor variabile se numește:

Definiție 7.Forme patrate F. numit definit pozitiv / negativ dacă F (x)\u003e 0/ F (x) 0 pentru toate valorile variabilelor care constituie vector X.

Definiția 8.Forme patrate F. numit semedy pozitiv / negativ dacă F (x ")\u003e O / da ") x, iar, în plus, există un astfel de set de variabile - componenta vectorului X " ce F (x ") \u003d 0.

Teorema 5.Forma patratic este o funcție convexă / concavă dacă este pozitiv / negativ cu semedied.

Definiție9. Sarcina constând în minimizarea / maximizarea valorii funcției

cu restricții

în cazul în care - formularul patratic semifinanțat pozitiv / negativ, numit sarcina programării patrate (ZKP).

Pentru această sarcină, caracteristica Lagrange are forma:

Dacă funcția Lagrange are un punct de șa, atunci condițiile (2,27) sunt efectuate în acesta (2.28). Introducerea acum variabile suplimentare care transformă inegalitățile în egalitate (această tehnică este folosită și când rezolvați sarcinile LP), scriem aceste condiții în formular:

Pentru a găsi decizia SCP, este necesar să se determine soluția ne-negativă a sistemului de ecuații algebrice liniare (2.32). Această soluție poate fi găsită metoda de bază artificială, aplicată pentru a găsi valoarea minimă a funcției țintă artificială F \u003d ^ PJ, Variabile artificiale de baldachin. Metodă, kakiz-

se știe că numărul final de pași va găsi planul optim sau va stabili o insoluabilitate a sarcinii.

Deci, procesul de găsire a soluției SCP include următorii pași.

1. Funcționați funcția Lagrange.
2. Ca expresii (2.27), (2.28) înregistrează condițiile necesare și suficiente pentru existența punctului de șa din funcția Lagrange.
3. Folosind metoda de bază artificială, setați absența unui punct de șa pentru funcția Lagrange sau coordonați coordonatele acesteia.
4. Înregistrați soluția optimă a sarcinii inițiale și găsiți valoarea funcției țintă.

Luați în considerare elementar exemplu numeric (Nr. 1) din cartea I. L. Aculich "Programarea matematică în exemple și obiective". Conform planului de producție, întreprinderea ar trebui să producă 180 de produse. Ele pot fi făcute în două tehnologii. In productie H. Costurile 1 Costurile s-au ridicat la xF. + 4, freca., Și în fabricație x 2. Produsele 2 în modul în care sunt egale x +. 8x 2 freca. Determinați câte produse ar trebui să fie făcute pentru a minimiza costul ordinului.

Decizie. Minimizarea urmează următoarea funcție:

În condiții:

Funcția Lagrange în acest caz va arăta astfel:

Calculați derivații privați ai acestei funcții X, x 2, u și echivalează cu zero:

Transferat în prima și a doua ecuație w. Pe partea dreaptă și egalarea părților stângi, obținem după reduceri evidente:

Rezolvarea acestei ecuații împreună cu a treia ecuație a sistemului, vom găsi asta Acest punct este un solicitant pentru un extremum.

Folosind al doilea derivate private, nu este dificil să se arate că punctul găsit este o funcție minimă condiționată /

Sarcini similare cu cele considerate, în multe nominalizează practica economică. Adevăratele sarcini reale sunt, de obicei, un număr mare de variabile și restricții, ceea ce face imposibilă rezolvarea acestora fără utilizarea calculatorului. Cu toate acestea, eficacitatea utilizării software-ului standard este determinată de cunoașterea cercetătorului de substanțe prin transformările efectuate de computer. Îi ajută să navigheze în mod corect într-o varietate de metode oferite pentru a rezolva problemele de optimizare a metodelor, a procedurilor de calcul și a complexelor de software.

Pentru a asigura subiectul, ia în considerare consumul exemplu numeric (Nr. 2). Găsiți funcția maximă

În condiții:

Decizie. Funcția / este concavă deoarece este suma funcției liniare f \u003d 2x 2 + 4x kcare poate fi privită ca formă concavă și pavaratic / 2 = -H -2x1, care este definită negativ. Restricțiile conțin doar limitări liniare. Prin urmare, puteți utiliza schema Kuna Teorem - TakCker și SCC Solution.

1. Faceți o funcție de lagrange:

2. Scriu condițiile necesare și suficiente pentru existența punctului de șa a funcției L.

3. Introducem variabile non-negative suplimentare v B v2 la sistemul de inegalitate liniară. w, W 2, Contractarea inegalităților în egalitate. Obținem sistemul de ecuații:

În același timp, condițiile sunt îndeplinite:

Este necesar să se găsească soluția de bază a sistemului de ecuații (2.33) pentru a determina coordonatele punctului de șa din funcția Lagrange. În acest scop, folosim metoda de bază artificială. Minimizați funcția țintă artificială

unde Zi, Zi. - variabile artificiale, în condiții:

Aici, soluția evidentă de bază permisă este după cum urmează:

Caracteristică țintă F.exprimați prin variabile non-deconectare:

Finalizarea argumentelor, menționăm că se referă la zero la XJ (0) \u003d 1, \u003d 1 și alte variabile cu valori zero. Astfel, t (0) \u003d (1, 1) este planul optim al problemei sursei,

Curs 11.Programare convexă

Definiție 1. Z. adserve de programare convexă Se numește sarcină de programare neliniară, unde toate funcțiile sunt convexe.

Astfel, problema programării convexe este o problemă a minimizării condiționate, în care funcția țintă a convexului și zona admisibilă este un set convex format din sistemul de inegalități convexe. Prin urmare, afirmațiile obținute anterior în coloana de vapori 6 sunt valabile pentru problema programării convexe. În acest paragraf, concretizăm aceste rezultate generale și le aducem în formular mai convenabil pentru studiul și rezolvarea următoarei probleme de programare convexă:

(1)

, (2)

. (3)

Vom avea nevoie de construcții auxiliare în spațiu.
vectori
. Vector de la primul
Punct de component. Vom denota . Asa de,
.

Pentru problema (1) - (3) Definim un set

unde
.

Lemma. . Pentru problema programării convexe (1) - (3) multe de bază.

Dovezi. Alegeți vectori arbitrari
De la set și numărul
. Apoi există puncte și de ca. Înmulțiți aceste inegalități și
, în consecință, adăugați-le. Datorită convexității tuturor funcțiilor pe care le obținem

Din inegalitățile obținute și de umflarea setului .

Teorema 1. (Teorema coon-tacker în forma unei funcții de Lagrange Point Saddle a sarcinilor de programare convexe ) Să presupunem că, în problema programării convexe (1) - (3), sistemul (2) satisface starea ardezie față de a fost o soluție la problema (1) - (3), este necesar și suficient pentru a exista într-un vector non-negativ astfel încât
- Punctul Saddal al funcției Lagrange.

Dovezi. Deoarece adecvarea acestei condiții a fost deja dovedită pentru o problemă arbitrară de programare neliniară (a se vedea Teorema Introducere 2.6), rămâne să dovedească doar nevoia.

Necesitate. Lasa - Soluția de problemă (1) - (3). A pune
. Este evident că
, la fel de
,
și
.

Asigura-te ca
. Să presupunem urât. Aceasta înseamnă că există un punct
astfel încât
. Prin urmare, - un astfel de punct admisibil, valoarea funcției țintă în care este mai mică decât minimul. Avem o contradicție cu faptul că - Rezolvarea problemei programării convexe.

Asa de,
. Potrivit setului de lemma convex. În consecință, sunt efectuate toate cerințele Teoremei 8.2. Prin urmare, există nonsens

vector
Referință la punct A seta :

Asigurați-vă că toate coordonatele vectorului Nespus. Să presupunem urât. Să presupunem că există coordonate
. Fixați în vector Toate componentele, cu excepția cazurilor -Oh. Apoi, având în vedere că lucrarea
poate face un mare înțeles (datorită coordonatelor nelimitate ), obținem o contradicție cu inegalitatea (4).

Ușor de văzut asta cu oricare
Vectori
Porniți în multe . Apoi, de la (4) avem:

Să arătăm asta
. Să fie greșit. Atunci
. Prin urmare,
. Sub starea de ardezie există un vector
astfel încât
. prin urmare
. A obținut contradicție și înseamnă asta
.

Denota
. Să arătăm acel vector construit Este un vector de multiplicator de lagran. Este evident că
și de la (5) obțineți

Prin urmare, PLY.
urma

. (7)

Pe de altă parte, deoarece
(în măsura în care
) I.
, Am inegalitate

. De aici și de la (7) rezultă că la acest punct
Se efectuează condiția reticenței complementare:

. (8)

De la (6) și (8) avem

sau că același lucru

Apoi, lasa
. Atunci
. De aici și de la (8) avem inegalitate

Inegalități (9), (10) și înseamnă asta
- Punctul de șa din funcția Lagrange a problemei

programarea logo-ului. Ceea ce a fost necesar.

Înainte de a vă familiariza cu o altă opțiune a teoremei Kuna-Takker, prezentăm următoarea teoremă, care este un criteriu al unui minim condiționat în ceea ce privește conurile vectorilor de sprijin.

Teorema 2. Lasa - Convex și diferențiat pe
Funcție, set
convex. Apoi, pentru moment
a fost o funcție minimă condiționată Pe set
, este necesar și suficient pentru a include

. (11)

Dovada ar trebui să fie direct din teorema 6.5 și definiția conului
Suport vectori la punct A seta
.

Teorema 3. (Teorema rezervorului de coafon în formă diferențială pentru sarcina de programare convexă ) Lăsați sarcina de programare convexă în forma (1), (2), în cazul în care toate funcțiile
Continuă diferențiată, sistemul (2) satisface starea eșantionului. Apoi, pentru ca vectorul
a fost o soluție la problema (1), (2), este necesar și suficient pentru a exista într-un vector non-negativ Aceste condiții sunt îndeplinite

, (12)

Dovezi. Arătăm că condițiile (12) și (13) sunt echivalente cu includerea (11). Lăsați punctul
Aceasta este aceea
. Atunci
și
.

Lăsați acum
. Apoi, din teoremele 2 și 10.5 rezultă că existența unor astfel de factori este necesară și o condiție suficientă pentru extremum.
,
pentru care
. A pune
pentru toți
și să ajungă din ultima condiție de egalitate (12) și (13). Ceea ce a fost necesar.

În încheierea paragrafului, prezentăm formularea celor două teoreme Koon-Tacker pentru sarcina de

programarea Pon cu restricții liniare.

Teorema 4. Să presupunem că în problema programării convexe (1) - (3), sistemul de limitare (2) are forma

, b - dimensiunea vectorială
. Apoi, pentru vectorul nonnegativ a fost o soluție la această problemă, este necesar și suficient pentru a

a existat un vector non-negativ astfel încât
- Punctul de șa din funcția Lagrange a acestei sarcini.

Rețineți că, în acest caz, funcția Lagrange este vizualizată.

Teorema 5. Lăsați în problema programării convexe (1), (2) funcția țintă sistemul de restricție continuu, diferența (2) are forma
unde dimensiunea A - Matrix
, b - dimensiunea vectorială
. Apoi, pentru ca vectorul
a fost o soluție la problemă, este necesar și suficient pentru a exista într-un vector non-negativ aceste condiții sunt îndeplinite
,
.

Rețineți că, în teoremele 4 și 5, nu necesită punerea în aplicare a stării slater, astfel încât acestea nu sunt cazuri particulare de teoreme 1 și 3 și necesită o dovadă independentă.

Funcția specificată pe setul convex este numită convexă dacă pentru orice puncte și orice inegalitate este efectuată. O combinație liniară cu coeficienți non-negativi de convex pe funcțiile multiple convexe este o funcție convexă pe acest set. Lăsați funcțiile definite pe setul convex să fie convexe pe.

Împărțiți lucrul la rețelele sociale

Dacă acest loc de muncă nu vine în partea de jos a paginii există o listă de lucrări similare. De asemenea, puteți utiliza butonul de căutare.

Numărul de curs 12.

Programare convexă

O clasă largă de sarcini de programare matematică este asociată cu minimizarea funcțiilor convexe ale multor variabile definite pe setul convex. Astfel de sarcini se numesc sarcini de programare convexe (ZVP).

Sarcina programării matematice

(12.1)

se numește sarcină de programare convexă dacă toate funcțiile sunt funcții convexe.

Să trăim pe elementele analizei convexe - zona matematică, în care sunt studiate proprietățile seturilor convexe și funcțiilor convexe și care joacă un rol fundamental în teorie și metode de rezolvare a sarcinilor extreme.

Elemente de analiză convexă

Prezentăm câteva definiții și luăm în considerare exemple specifice de seturi convexe. Vom continua să ne ocupăm de caracteristicile definite pe seturile de spațiu euclidan finit-dimensionalE n.

Definiția 12.1. Multe tipuri

(12.2)

se numește puncte de conectare a segmentului și, și a indicat.

Evident, cândX. Coincide cu unul dintre capetele segmentului (), când - cu altul () și când - cu un anumit punct interior al segmentului.

Definiția 12.2. Mulți numițiconvex Dacă cu oricare două puncte și aparține segmentului de conectare.

Bulgeul setului înseamnă că de la apartenența și se pune rezultă că aparține tuturor.

Evident, în convexe tăiate, semi-simplicabile, drepte, cerc, triunghi, jumătate de plan și întregul plan.

Toate spațiul, evident, formează un set convex. Un set gol și un set constând dintr-un punct este convenabil să fie considerat convex.

Teorema 12.1. Forkshaw teorema.Lăsați matricea de dimensiune și setul vectorului. Inegalitatea este efectuată pentru toți în asta și numai dacă există un vector astfel încât.

D o k a și t e t e în aproximativ.Adecvare. Lăsați rapoartele și. Apoi, pentru orice vector va fi

Necesitate. Lăsați pentru toată lumea pe bună dreptate. Ia în considerare un con. Dacă teorema este dovedită. Să presupunem asta. Setul, prin definiție 12.2, convex și închis, prin urmare, în virtutea teoremei de separabilitate, există un vector astfel încât

(12.3)

pentru toți.

Deoarece toate, apoi de la (12.3) obținem asta pentru toți. Asa de. Pe de altă parte. Adică și din moment ce are loc pentru toată lumea, atunci

. (12.4)

Dar, prin urmare, de la (12,3) urmează

. (12.5)

Luând, de la (12.4) și (12.5) obținem o contradicție cu condițiile teoremei.

Cometariu. Prezentăm interpretarea geometrică a teoremei Farkash. Lasa

și. Conul este o combinație a tuturor vectorilor care formează colțuri non-luminoase cu fiecare dintre vectori. În figura 12.1, conul este umbrit de linii verticale, iar conul este orizontal. Semnificația geometrică a teoremei este după cum urmează. Pentru orice vector, unghiul dintre și a fost Unotica, este necesar și suficient pentru a aparține conului.

Figura 12.1.

Definiția 12.3. Funcția specificată pe setul convex este apelatăconvex Dacă inegalitatea este efectuată pentru orice puncte și orice

(12.6)

Funcția este numităstrict convexă Dacă pentru toată inegalitatea (12.6) se efectuează ca fiind strictă. Funcția este numităputernic convexă Dacă există un astfel de număr (constant de o bulgare puternică) că pentru toate și orice inegalitate

(12.7)

Fiecare funcție puternic convexă este strict convexă și chiar mai convexă, dar nu invers.

Un exemplu de funcție convexă este o funcție patrată cu o matrice definită pozitiv.

Teorema 12.2. O combinație liniară cu coeficienți non-negativi de convex pe funcții multiple convexe este o funcție convexă pe acest set.

D o k a și t e t e în aproximativ. Lăsați funcțiile definite pe setul convex să fie convexe pe. Arătăm că funcția

, (12.8)

unde convexă.

Pentru puncte arbitrare și de la orice număr pe care îl avem

În acest lanț de relații, prima inegalitate este valabilă, deoarece funcțiile sunt convexe. Rezultatul obținut arată că funcția determinată prin formula (12,8) este convexă pe set.

Teorema 12.3. Dacă este convex pe o multiplă convexă, atunci pentru orice puncte și orice numere, astfel încât inegalitatea Yensen este efectuată

. (12.9)

D O k a și t e l s t în O (prin inducție). Pentru inegalitate (12,9) evident. De fapt, dacă, atunci, adică (12.9) se efectuează ca egalitate. Să presupunem că (12,9) are loc, adică. Pentru o combinație convexă de puncte. Arătăm că atunci este adevărat și pentru combinația convexă de puncte ale setului, adică.

În același timp, dacă, în (12,9), egalitatea este evidentă. Dacă. Apoi, de la convexitatea și ipoteza inductivă urmează

Se spune că setul satisfacecondiție regulatăDacă există un punct pentru fiecare, adică.

(12.10)

Este ușor de arătat că condiția (12.10) este echivalentă cu o altă condiție numităstarea regularității Slatera.

Teorema 12.4. Dacă setul este efectuat pentru starea regularității(12.10), apoi setul În mod regulat în Salayer, și anume există un punct în care toate restricțiile sunt efectuate strict

. (12.11)

D o k a și t e t e în aproximativ. Permiteți condiția de regularitate (12.10). Selectați un punct care este o combinație convexă de puncte și, prin urmare, aparținând. Apoi, cu oricare dintre ele

acestea. . În acest lanț de relații, prima inegalitate este adevărată datorită inegalității lui Jensen, iar al doilea este de cel puțin un membru al sumei, și anume strict mai puțin. Aceste inegalități arată că starea regularității slabeului are condiția luată în considerare.

Să dăm fără dovadă următoarea proprietate importantă a funcțiilor convexe.

Funcția convexă definită pe setul convex este continuă în fiecare punct interior al acestui set și are un derivat în fiecare punct interior în orice direcție.

O proprietate importantă a funcțiilor diferențiate convexe, pe care le vom folosi adesea, stabilește următoarea teoremă.

Teorema 12.5. Funcția care diferențiază pe setul convex este convexă dacă și numai atunci când se efectuează inegalitatea pentru oricare și aparține

. (12.12)

D o k a și t e t e în aproximativ.Necesitate . Să fie convexă. Apoi, pentru orice și, () și toate astfel încât inegalitatea este adevărată

din

Întorcându-se la limita ultimei inegalități, obținem

Adecvare . Să presupunem că starea este acum satisfăcută (12.12) pentru orice două puncte ale setului. Apoi, pentru un punct cu apartenența, inegalitățile echitabile

Înmulțirea primei inegalități, a doua și plierea inegalităților obținute, avem

sau, având în vedere ceea ce avem

cei, că funcția convexă pe set.

Luați în considerare o serie de proprietăți extreme ale funcțiilor convexe pe un set convex, jucând un rol semnificativ la rezolvarea problemei de a găsi un punct de setare convex, în care funcția convexă definită de valoarea minimă :.

Teorema 12.6. Orice punct al unei funcții minime locale pe un set convex este un punct minim global.

D o k a și t e t e în aproximativ. Lăsați - punctul funcției minime locale. Apoi, prin definirea punctului unui minim local, există un anumit cartier al acestui punct astfel încât să se efectueze inegalitatea

. (12.13)

Să presupunem că nu este un punct al funcției minime globale, adică există un punct astfel încât. Luați în considerare punctele de vedere.

acestea. . Dar acest lucru este contrar condiției care - punctul minim local, deoarece cu un punct suficient de mic este situat în vecinătate, unde există (12,13).

În consecință, punctul minim global este activat.

Teorema 12.7. Setul de puncte minime ale funcției convexe pe setul convex este un set convex.

D o k a și t e t e în aproximativ. Fie setul de puncte minime ale funcției convexe pe setul convex, adică.

Alegeți două puncte și. Deoarece ambele - setul convex, apoi pentru orice

și datorită convexității funcției pe care le avem

Adică În plus, deoarece - valoarea minimă a funcției, atunci. Și, adică, adică . În consecință, setul convex.

Teorema 12.8. Funcția strict convexă pe setul convex atinge minimum nu mai mult de un punct.

D o k a și t e t e în aproximativ. Să presupunem - Funcția strict convexă pe setul convex, adică. Pentru oricine și toate inegalitățile stricte

Fie \u003d.

Să presupunem că există un punct, astfel încât

Apoi, pentru orice moment aparține setului și în virtutea convexității stricte a funcției va fi

acestea. . Acest lucru este contrar condiției care este un punct minim. În consecință, punctul este singurul.

Lucrări de testare

1. Dați sarcina de programare convexă.

2. Dați definiția unui set convex.

3. Formularea teoremei Forkash.

4. Dați o interpretare geometrică a teoremei Farkash.

5. Dați definiția convexului, o funcție strict convexă și puternic convexă pe setul convex.

6. Dați exemple de funcții convexe.

7. CUVINTE CONDIȚIILE DE COABILITATE A setului.

8. Cuvânt Condiția regularității în ardezie, seturi.

9. Dați starea convexității necesare și suficiente a funcției., Diferenţialpe un set convex .

10. Calculați proprietățile principale ale extreme ale funcțiilor convexe pe un set convex.

Pagina 131.

Permiteți-i să primească sistemul de inegalități ale formularului

(4.3) și funcția

Z \u003d f (x 1, x 2, ..., x n), (4.4)

mai mult, toate funcțiile sunt convexe pe unele set convexe M, iar funcția Z este fie convexă pe setul M, fie concavă.

Problema programării convexe este găsirea unei astfel de soluții la sistemul de limitare (4.3), în care funcția țintă Z atinge valoarea minimă sau funcția concavă Z atinge valoarea maximă. (Problemele non-negativității variabilelor pot fi luate în considerare în (4.3)).

Datorită proprietăților de 3 0, orice problemă de programare liniară este un caz special al unei sarcini de programare convexă. În cazul general, sarcinile de programare convexe sunt sarcini de programare neliniare. Selectarea sarcinilor de programare convexă către o clasă specială este explicată prin proprietățile extreme ale funcțiilor convexe: orice funcție convexă minimă locală (funcția maximă maximă concavă) este atât globală; În plus, datorită proprietăților 2 0, funcția Convex (Concave) specificată pe un set limitat închis ajunge pe acest set de un maxim global și un minim global. De aici rezultă asta dacă funcția țintă Z este strict convexă (strict concavă) și dacă zona de soluții ale sistemului limită nu este goală și este limitată, atunci problema programării convexe are întotdeauna o singură soluție.

Funcția F (x) \u003d F (x 1, x 2, ..., x N) numită separabelno.Dacă poate fi reprezentată ca suma funcțiilor, fiecare dintre ele depinde doar de o variabilă, adică. în cazul în care un

(Este posibil ca F I (x I) \u003d 0 pentru unii i).

Să presupunem că sistemul de limitare (4.3) și funcția țintă (4.4) sunt date în sarcina de programare convexă (4.3), iar funcția Z Z și toate limitările sunt separabile. Apoi, sarcina este:

Găsiți o funcție minimă convexă (maximă - concavă)

cu restricții

Ideea unei metode de aproximare liniară din bucăți este că toate f I și toate sunt înlocuite cu linii sparte constând din tăieturi drepte. În acest caz, sarcina inițială de programare convexă se înlocuiește cu o sarcină nouă, aproximativă, care este o sarcină de programare liniară. Această sarcină este de obicei rezolvată prin metoda simplăxă, iar soluția sa este o soluție aproximativă a problemei inițiale a programării convexe.

Figura 12. Soluția problemei de programare convexă prin armonizare liniară din bucăți

Pentru a construi o sarcină aproximativă, luați în considerare o armonizare liniară din bucăți a funcției unei variabile H (X) specificată pe segment. Am rupe acest segment pe punctele R Puncte X 0

Ecuația liniei întrerupte între punctele (x k; h k k) și (x k + 1; h k + 1) are forma (ecuația directă de-a lungul a două puncte). Dacă fiecare dintre relațiile din această egalitate este de a desemna, atunci vom obține:

Rețineți că fiecare există un singur sens în sensul satisfăcător (4.7). Desemnarea pe care o puteți rescrie (4.7) în formularul:

[Ecuațiile (4.8) se numesc segmente parametrice.

Dacă H (X) \u003d 0, atunci al doilea dintre aceste ecuații se referă la identitatea 0 \u003d 0, iar prima ia formularul (4.1) - ecuația segmentului care se află pe axa Abscisa].

Astfel, pentru orice ecuație lolorală, puteți scrie în formularul:

mai mult decât atât, doar două valori sunt întotdeauna diferite de zero (dacă X este secțiunea Interioară K-Ho a partiției) sau una (dacă x coincide cu capătul segmentului).

Revenind la problema programării convexe cu funcții separabile, observăm că în primul rând (în funcție de sistemul limită) trebuie să determinați intervalul de modificare a fiecărei variabile x j. Apoi, fiecare interval este împărțit în părți de x jk și folosind formule (4.9) o armonizare liniară din bucăți pentru funcții f j și. După aceasta, este posibil ca sarcina inițială (4.6) să înregistreze o sarcină aproximativă:

Găsiți o funcție maximă

cu restricții (4.10)

Deoarece problema aproximativă (4.10) este o sarcină liniară de programare, care este de obicei rezolvată de metoda simplă, condițiile de definiție sunt scrise separat de alte restricții.

Diferența dintre sarcina obținută (4.10) din problema obișnuită de programare liniară este că pentru fiecare X J, nu există mai mult de două non-zero adiacente și, înseamnă că două cu același J și non-emergente K nu sunt luate ca variabile principale. De asemenea, menționăm că, pentru condițiile de non-permisiuni ale variabilelor termenilor F J (x J) și (dacă există), nu este necesar să se efectueze o aproximare liniară din bucăți.

Acest capitol acoperă doar câteva metode de optimizare utilizate de manageri pentru a face soluții eficiente în întreprinderi. Cu toate acestea, tehnicile descrise permit înțelegerea principiului de bază al utilizării aparatului matematic din economie, ceea ce face posibilă alegerea dintr-o varietate de opțiuni alternative optime pentru acest caz sau situații.