Iniţiere în programarea matematică

„Deoarece edificiul omenirii e înălţat de Preaînţeleptul Creator,
în lume nu se întâmplă nimic în ce nu s-ar vedea sensul unui
maxim sau minim… „

Leonhard Euler

În semestrul doi se predă cursul de metode de optimizare – un curs interesant atât din perspectiva teoretică, cât şi din cele practice şi informatice. Articolul se adresează, în primul rând, studenţilor.

Probleme de optimizare şi soluţii

Programarea matematică, numită în sens larg şi teoria optimizării, e ramura matematicii ce se ocupă de studierea problemelor de optimizare şi de elaborarea metodelor de soluţionare a lor. E strâns legată de teoria şi practica luării deciziilor şi are aplicaţii în cele mai variate domenii ale vieţii.

Ce se înţelege prin noţiunea de problemă de optimizare? Esenţa ei devine clară dacă reamintim că românescul optim provine de la latinescul „optimus” – superlativ al lui „bonus” (bun) – semnificând  nu altceva decât cel mai bun. O problemă de optimizare cere selectarea alcătuirea/construirea/găsirea celei mai bune variante dintr-o mulţime de alternative. În acest sens, natura ce ne înconjoară abundă în probleme de optimizare pe care le rezolvă prin nenumărate „experienţe”, uneori în decurs de milioane de ani.

Referindu-ne la activitatea umană, vom sublinia că însăşi natura omului presupune de la sine o tendinţă spre optim, spre perfecţiune, iar în artă – spre ideal, sublim şi armonie. Omul se străduieşte să creeze nu pur şi simplu obiecte uzuale, ci obiecte bune, foarte bune, desăvârşite, perfecte. În nenumărate situaţii el încearcă  să realizeze caracteristici optime – de profitabilitate, de rentabilitate, de volum, de eficienţă etc. Totuşi spre deosebire de natură, omul nu acţionează orbeşte,  făcând nenumărate experienţe în timp nelimitat. Homo Sapiens, pentru a realiza optimul, foloseşte capacităţile sale intelectuale: analizează, meditează, inventează, experimentează, modelează etc., operând de cele mai dese ori nu cu obiectul real (ce ar determina nenumărate cheltuieli, îndeosebi în economie), ci cu un careva model: machet, prototip, model matematic, desen etc. Caracteristica esenţială a activităţii umane în calea spre optim, spre perfecţiune constă în utilizarea unui model cu ajutorul căruia se verifică diferitele proprietăţi şi caracteristici ale obiectului (situaţiei, fenomenului, procesului, sistemului) real cu scopul de a le determina pe cele mai bune.

Problemele de optimizare pot fi interpretate/tratate şi ca modele matematice ale unor probleme reale care apar în variate domenii: economie, ştiinţă, medicină etc. Ele includ în sine modelul obiectului/procesului/fenomenului real – o consecutivitate de axiome, reguli, relaţii logice, algoritmi etc. – care reflectă proprietăţile, caracteristicile şi relaţiile existente între parametrii, mărimile constante şi variabile ale obiectului de optimizat, precum şi criteriul sau criteriile conform cărora se apreciază soluţiile admisibile ale problemei, dintre care şi se selectează cea optimă.

Problema construirii modelului matematic ţine de modelarea matematică (domeniu distinct) şi, mai puţin, de programarea matematică. Modelarea matematic[ elucidează dependenţa ce există între mărimile z, x1,…,xn, ale obiectului real şi, ca o relaţie de forma G(z, x1,…,xn)=0 (z şi G pot fi mărimi vectoriale), variabilele z,  x1,…,xn, fiind legate printr-o funcţie implicită. Adeseori variabila z poate fi scrisă şi ca funcţie explicită sub forma z=g(x1,…,xn).

În general, o problemă de optimizare se scrie formal (matematic) astfel:

f(x) –> max, xX,

şi se citeşte: de ales din mulţimea de soluţii admisibile X soluţia optimă x* cu cea mai mare valoare a funcţiei obiectiv f(x).

Problema de optimizare e numită problemă de programare matematică (program matematic) dacă are forma:

f(x) –> max,_____________ (1)

gi(x) ≤ 0, i=1,…,l,__________(2)

gi(x) = 0, i=l+1,…,m,_______ (3)

x ∈ D ⊆ Rn,______________ (4)

unde f(x) şi gi(x) sunt funcţii de vectorul x ∈ Rn.

Problema (1)-(4) se citeşte: dintre punctele x ∈ Rn care satisfac relaţiile (2)-(4) să se aleagă punctul optim x* pentru care funcţia obiectiv (1) are cea mai mare valoare fmax=f*=f(x*).

Relaţiile (2)–(4) se numesc restricţii ale problemei. Relaţiile (4) se mai numesc condiţii de admisibilitate sau restricţii directe.

Mulţimea de puncte x ∈ Rn care satisfac restricţiile (2)-(4) formează mulţimea de puncte (soluţii) admisibile şi, de regulă, se notează prin X. Aşadar, orice punct x X e numit punct admisibil (soluţie admisibilă). Punctele admisibile reprezintă variantele (alternativele) dintre care se alege cea mai bună. În calitate de criteriu de apreciere a variantelor serveşte funcţia obiectiv, cea mai mare valoare a ei realizându-se pe soluţia optimă.

Problema (1)-(4) se mai scrie şi sub forma:

maxx∈X f(x) = max{ f(x) | gi(x) ≤ 0, i=1,…,l}, gi(x) = 0, i=l+1,…,m}, x ∈ D Rn}.

Vom menţiona că orice problemă de determinare a valorii maxime a funcţiei f(x) poate fi scrisă ca problemă de determinare a valorii minime a funcţiei -f(x), deoarece maxx∈X f(x) = – minxX -f(x) pentru orice mulţime X.

Punctul x* X este punct de maxim global dacă

f(x*) f(x), __________(5)

pentru orice x∈ X.

Punctul x* X este punct de maxim local dacă există un ε > 0, astfel că se verifică (5) pentru orice x∈ X ∩ Vε(x*), unde Vε(x*) este un glob deschis de rază ε cu centrul în punctul x*, numit  ε-vecinătate a punctului x*.

Punctele de minim,
local şi global, se definesc în mod analogic, inversând doar sensul inegalităţii (5).

Punctele de maxim şi minim, global şi local, sunt numite: puncte sau soluţii optime, puncte sau soluţii de extrem.

Inegalităţile stricte în (5) definesc punctele de maxim (minim) strict.

Remarca 1. Orice punct de optim global este şi punct de optim local. Nu orice punct de optim local este şi punct de optim global.

Remarca 2. Dacă există un punct de optim global, atunci există cel puţin un punct de optim local. Evident, sunt probleme care au soluţii locale, dar nu au soluţii globale.

Maxima  f*=supxX f(x) e numită şi valoare a problemei (1)-(4) .

Pot exista următoarele situaţii:

I. f* < +∞  şi există x*∈ X pentru care f*=f(x*);

II. f* < +∞  şi nu există x*∈ X pentru care f*=f(x*);

III. f* =+∞.

Vom spune că problema (1)-(4)  are soluţie optimă dacă are loc situaţia I. Problema (1)–(4) nu are soluţie dacă X= ∅, sau dacă are loc una dintre situaţiile II, III. În situaţia II valoarea problemei nu se realizează, iar în situaţia III valoarea nu este mărginită.

Conform celor expuse, problemele de optimizare pot fi globale şi locale. O altă clasificare a lor se face în corespundere cu proprietăţile funcţiilor componente şi proprietăţile mulţimii D, deosebind probleme de optimizare: necondiţionată, liniară, pătratică, convexă, concavă, discretă, combinatorie etc. De regulă, tipul problemei cercetate se menţionează  de fiecare dată când  există necesitatea.

Termenul/denumirea de programare matematică a fost introdus de către George Dantzig în anii 40 ai secolului XX, referindu-se la modelele folosite de către americani pentru a micşora cheltuielile de război, folosind diverse programe de aprovizionare a armatei amerticane.

Metode de optimizare

Referindu-ne la metodele de soluţionare, vom menţiona că în programarea matematică nu există metode universale de soluţionare. În funcţie de tipul problemei cercetate se alege şi metoda de rezolvare, care poate fi: exactă sau aproximativă, analitică sau numerică, locală sau globală, deterministică sau stochastică, strict fundamentată sau euristică etc.

O clasă importantă de metode pe larg utilizate în practică o formează metodele iterative. Ele determină soluţia optimă x* sau aproximarea ei prin parcuregerea unui şir convergent (către x*) de aproximaţii: x0, x1, …, xk, … fiecare element al căruia se calculează în baza elementului (elementelor) precedent după o regulă prestabilită xk=F(xk-1), k=1,2,…,  în care: x0 este soluţia iniţială (de start); F – o funcţie dată, în general, sub forma unui set de reguli, procedee şi algoritmi, fiecare element al setului (la fel ca şi realizarea lui) fiind numit pas. Procesul de calcul al valorii xk=F(xk-1) se numeşte iteraţia k a metodei.

Există mai multe caracteristici ale metodelor iterative: viteza de convergenţă, complexitatea calculelor (numărul preconizat de operaţii aritmetice), volumul de memorie utilizat (atât operativă, cât şi externă), stabilitatea faţă de erorile de calcul, timpul (durata) calculelor etc. Caracteristicile pot fi atât apriorice, cât şi aposteriorice. Cele apriorice pot fi determinate înainte de calcularea elementului xk, iar cele aposteriorice se determină numai după calcularea elementului xk.

Totuşi evaluarea calităţii unei metode iterative cere elucidarea, în primul rând, a trei probleme de bază:

  1. verificarea dacă metoda este într-adevăr convergentă, adică verificarea relaţiei: limk–>∞ xk =x*.
  2. estimarea distanţei d(xk, x*) (dacă există o estimare apriorică, atunci, de regulă, poate fi indicat atât numărul de iteraţii k care trebuie efectuate pentru a atinge exactitatea dorită, cât şi numărul necesar de operaţii aritmetice);
  3. estimarea vitezei (ratei, ordinului) de convergenţă către zero a distanţei d(xk, x*) , ceea ce înseamnă indicarea, în general, a unei consecutivităţi βk convergente către zero pentru care are loc d(xk, x*) ≤ q βk, unde q este o constantă necunoscută. Această problemă prezintă interes numai în cazul în care este dificil a evalua distanţa d(xk, x*).

Astfel, procesul iterativ converge liniar (cu viteza unei progresii geometrice) dacă există q ∈ (0,1) şi k0, încît

d(xk+1, x*) ≤ q d(xk, x*)

pentru orice k ≥ k0. Viteza de convergenţă e supraliniară dacă

d(xk+1, x*)qk d(xk, x*)

unde limk–>∞ qk = +0.

Calitatea metodelor iterative se estimează şi prin viteza de convergenţă a şirului de valori f(x0), f(x1), …, f(xk),… ale funcţiei obiectiv către valoarea optimă f(x*). Se consideră că metoda iterativă e definită complet dacă e stabilit domeniul în care se satisfac condiţiile de convergenţă şi sunt stabilite condiţiile de oprire a procesului iterativ.

Condiţiile de oprire diferă de la metodă la metodă, dar, în general, rezidă în verificarea după fiecare iteraţie a unei inegalităţi de tipul:

d(xk+1, x*) ≤ ε1,

| f(xk+1) – f(xk) | ≤ ε2,

în care ε1, ε2 ≥ 0, sunt exactităţile cu care se determină soluţia problemei, numere oricît de mici, prestabilite la lansarea în execuţie a procesului iterativ. Satisfacerea inegalităţii serveşte ca indiciu de oprire a procesului de calcul.

Dacă mulţimea de soluţii admisibile X are un număr finit de elemente, atunci problema dată este o problemă de optimizare combinatorie. Soluţia ei se determină ipotetec într-un timp garantat finit (dependent de dimensiunea datelor problemei).

Timpul (numărul de iteraţii, de paşi, de operaţii folosit de metodă la rezolvarea problemei este numit complexitate temporală a metodei. Se spune că metoda (sau algoritmul) are complexitatea O(φ (L)), dacă există o constantă C > 0 astfel că timpul necesar la rezolvarea problemei cu dimensiunea L nu depăşeşte C φ(L), unde φ este funcţie numerică, iar
L
– numărul de simboluri necesare pentru codificarea datelor problemei (combinatorii) la introducerea lor în calculator. Dacă funcţia φ este polinomială în raport cu L, metoda are complexitate polinomială.

Dacă φ este exponenţială în raport cu L, metoda are complexitate exponenţială.

Sunt considerate eficiente metodele de complexitate polinomială.

La cercetarea şi rezolvarea problemelor de optimizare au o importanţă specifică construcţiile geometrice, datorită caracterului lor ilustrativ în context teoretic, cât şi practic.

Sursa: V. Ungureanu, Programarea Matematică, Chişinău, USM, 2001.

http://www.youtube.com/p/436C5B5CC27376F9?hl=en_US&fs=1

Anunțuri

2 comentarii la “Iniţiere în programarea matematică

  1. Pingback: Iniţiere în programarea matematică - Ziarul toateBlogurile.ro

  2. Pingback: Modele economico-matematice celebre « Valorile Vieţii

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