Metoda grafică în programarea matematică

„Profesorul doar îţi deschide uşa.
De intrat trebuie să intri singur.”

Metoda grafică este prin esenţă o metodă mai mult ilustrativă. În programarea matematică se aplică, de regulă, la rezolvarea problemelor cu două variabile sau a celor care pot fi reduse la probleme cu două şi uneori cu trei variabile:

z = f(x,y) → max,
gi(x,y)≤0, i=1,…,l,
gi(x,y)=0, i=l+1,…,m.

Se construieşte în plan sistemul de coordonate şi domeniul M de soluţii ale sistemului de restricţii. Apoi se trasează câteva linii de nivel ale funcţiei obiectiv

L[α] = { (x,u) ∈ R2:  f(x,y) = α },

pentru câteva valori numerice distincte ale parametrului α, pentru a evidenţia direcţiile de minimizare şi maximizare. Determinarea soluţiei globale se reduce la găsirea nivelului maxim αmax (numărului αmax) pentru care linia de nivel respectivă mai are intersecţie cu domeniul M. Punctele din intersecţia ML[αmax] şi sunt cele de maxim global.

În sistemul Wolfram Mathematica procedeul poate fi realizat printr-un program simplu. În exemplul ce urmează se ilustrează aplicarea metodei grafice la rezolvarea următoarei probleme de programare liniară:

z = 2 x + 3 y → max,
2 x + 3 y ≤ 10,
-2 x + 3 y ≤ 6,
2 x + 4 y ≥ 8,
x ≥ 0, y ≥ 0.

De observat că la rezolvarea problemelor de programare liniară în planul de coordonate se mai trasează şi vectorul normal n (gradientul) la dreptele de nivel, care indică direcţiile de cea mai rapidă creştere şi descreştere a funcţiei obiectiv.

M = RegionPlot[2 x + y ≤ 10 && -2 x + 3 y ≤ 6 && 2 x + 4 y ≥ 8 && x ≥ 0 && y ≥ 0,
{x, -1, 6}, {y, -1, 5}, Axes → TrueAspectRatio → Automatic, PerformanceGoal →Quality„];

n = Graphics[Arrow[{{0, 0}, {2, 3}}]];

L[α_] := ContourPlot[2 x + 3 y ==α, {x, -1, 6}, {y, -1, 5}, ContourStyle → {Red, Dashed}]

Manipulate[Show[M, n, L[α]], {{α, 0, „z=2x+3y=”}, -4, 20, Appearance →Labeled„}]

Folosind manivela, se schimbă valoarea nivelului  α şi concomitent se obţine imaginea dreptei de nivel corepunzătoare (culoare roşie). Pentru a determina coordonatele punctului de maxim, rămâne să se rezolve sistemul de două ecuţaii cu două necunoscute,  corespunzător restricţiilor.

Programul poate fi modificat elementar pentru a ilustra aplicarea metodei grafice la rezolvarea altor probleme. Dacă domeniul  este definit şi prin ecuaţii se vor utiliza şi alte funcţii grafice ale sistemului Wolfram Mathematica.

Prezentăm şi un program care ilustrează aplicarea metodei grafice la rezolvarea unei probleme neliniare  cu trei variabile în cazul când domeniul  este definit de soluţiile unei ecuaţii neliniare:

f = x+y+z2+2(xy+xz+yz) → min,
x2 + y2 – z = 1

În acest caz domeniul M reprezintă un paraboloid de rotaţie, iar suprafeţele de nivel S[α] sunt nişte hiperboloizi. Mişcând manivela, obţinem o imagine clară referitoare la soluţia problemei şi anume că se realizează într-un singur punct. Punctul poate fi uşor determinat reducând prin metode substituţiei problema condiţionată la una necondiţionata. Pentru ultima se află punctul critic, care este şi de minim, egalând derivatele parţiale cu zero.

M = ContourPlot3D[x z2 + y z2 – z == 1, {x, -10, 10}, {y, -10, 10}, {z, -10, 10}];

S[α_] :=ContourPlot3D[x + y + z2 + 2 (x y + x z + y z) == α,
{x, -10,10}, {y, -10, 10}, {z, -10, 10}, ContourStyle → Red]

Manipulate[Show[M, S[α]], {{α, 0, „f=x+y+z2+2(xy+xz+yz)=”}, -50, 50, Appearance →Labeled„}]

Sistemul Wolfram Mathematica oferă posibilităţi avansate de rezolvare a poblemelor de optimizare. Aici l-am folosit doar pentru ilustrarea metodei grafice.

P.S. Pleacă pe drumul fără întoarcere un fost coleg de Facultate şi de serviciu, o persoană pentru care matematica a fost una din valorile vieţii… Adio Doriane… Lacrima noastră e şi demonstraţia neputinţei omului în faţa veşniciei…

 

Anunțuri

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s