Metoda simplex

Metoda Simplex, numită şi algoritm simplex, a fost propusa de George Bernard Dantzig în 1947. Este una dintre cele mai populare metode de rezolvare a problemelor de programare liniară. Metoda se aplică asupra problemei în forma standard, ceea ce, potrivit teoremei despre echivalenţa formelor, nu afectează universalitatea metodei. Denumirea provine de la noţiunea de simplex şi a fost sugerată de T.S. Motzkin. Revista Computing in Science and Engineering (vol. 2, no. 1, 2000) a inclus algoritmul în primii 10 algoritmi de top ai secolului XX.

Care sunt premisele metodei?

Să reamintim că:

  • domeniul X de soluţii admisibile ale problemei de programare liniară este mulţime poliedrală cu un număr finit de vârfuri;
  • dacă problema de programare liniară  are valoare finită, atunci ea se atinge şi într-un vârf al mulţimii de soluţii admisibile;
  • fiecărui vârf al mulţimii poliedrale X îi corespunde o soluţie admisibilă de bază a sistemului de restricţii ale problemei iniţiale;
  • metoda Gauss-Jordan şi transformările simplex permit să se efectueze trecerea de la o soluţie admisibilă de bază (de la un vârf) la altă soluţie admisibilă de bază (la alt vârf). Rămâne doar să se clarifice cum să se efectueze trecerea, ca de la o soluţie la alta să crească valoarea funcţiei obiectiv.

Ideea de bază a metodei simplex constă în parcurgerea orientată a vârfurilor mulţimii poliedrale de soluţii admisibile cu scopul de a afla vârful în care valoarea funcţiei obiectiv este maximă.

Să considerăm problema de programare liniară în formă standard:

z=z(x)= c1x1 + c2x2 + … + cnxn → max,_________(1)
______i1x1 + a­i2x2 + … + ainxn = bi, i=1,…,m,___(2)
______xj ≥ 0, j=1,…,n.________________________

Metoda Gauss-Jordan. Interpretări geometrice. Aplicaţii

Metoda Gauss-Jordan este în primul rând o metodă de rezolvare a sistemelor de ecuaţii liniare. Ea aduce printr-un număr finit de paşi succesivi sistemul de rezolvat

α­11x1 + α12x2 + … + α1jxj + … + α1sxs+ … + α1nxn = β1,

α­i1x1 + α­i2x2 + … + αijxj + … + αisxs+ … + αinxn = βi,

α­r1x1 + α­r2x2 + … + αrjxj + … + αrsxs+ … + αrnxn = βr,

α­m1x1 + α­m2x2 + … + αmjxj + … + αmsxs+ … + αmnxn = βm,

la o formă în care fiecare ecuaţie conţine o variabilă explicitată (de bază). Acest lucru se realizează selectând o ecuaţie  r  şi în ea o variabilă xs cu coeficient nenul αrs ≠ 0. Ecuaţia r se împarte la αrs. Cu ajutorul ecuaţiei obţinute:

α­r1rsx1 + α­r2rs x2 + … + αrjrs xj + … + αrsrs xs+ … + αrnrs xn = βrrs,

se elimină variabila xs din toate ecuaţiile, cu excepţia ecuaţiei r. Se obţine un sistem echivalent cu cel iniţial, în care coeficienţii variabilelor şi termenii liberi sunt calculaţi conform formulelor:

αrj: = αrj / αrs, j=1,…,n,_________________
βr := βrrs,_________________________
αij := αij – αis αrjrs, i=1,…,m,  i ≠ r, j=1,…,n,
βi := βi – αis βrrs, i=1,…,m,  i ≠ r.________

În continuare în sistemul curent se aleg iarăşi o ecuaţie şi o variabilă (cu coeficient nenul), diferite de cele alese la primul pas, şi se efectuează o eliminare după aceleaşi formule. Procedeul descris se repetă până când are loc una dintre următoarele 3 situaţii:

  1. În procesul de calcul la un anumit pas se obţine o ecuaţie contradictorie de forma: 0x1+…+0xn=bi ≠ 0. Ea indică că sistemul iniţial este incompatibil şi procesul de calcul trebuie oprit.
  2. La un pas anumit o ecuaţie se transformă într-o identitate de forma: 0x1+…+0xn=0. Ea denotă că ecuaţia dată este combinaţie liniară a celorlalte ecuaţii ale sistemului şi oate fi suprimată, iar procesul de calcul (eliminării) – continuat.
  3. Toate ecuaţiile sistemului au fost folosite pentru a elimina variabile (toate ecuaţiile conţin câte o variabilă de bază) şi nu sunt ecuaţii contradictorii. În aşa caz,  sistemul iniţial a fost redus la un sistem de forma (în care s-a efectuat o renumerotare de variabile, pentru simplitatea expresiilor obţinute):

x1_______+ α1r+1 xr+1 + … + α1n xn = β1,
___x2____+ α2r+1 xr+1 + … + α2n xn = β2,

_______xr + αrr+1 xr+1 + … + αrn xn = βr.

De unde  se obţine soluţia generală:

x1 = β1 – α1r+1 xr+1 – … – α1n xn,
x2 = β2 – α2r+1 xr+1 – … – α2n xn,

xr = βr – αrr+1 xr+1 – … – αrn xn,

căreia îi corespunde soluţia de bază x’ cu componentele de bază xi= βi , i=1,…, r, restul componentelor fiind nule.

În afară de soluţia de bază x’, sistemul mai poate avea până la Cnr soluţii de bază, care pot fi determinate aplicând acelaşi procedeu de eliminare completă, schimbând  succesiv combinaţiile de variabile de bază. Astfel metoda Gauss- Jordan permite nu numai să se afle soluţia generală, ci să se calculeze şi toate soluţiile de bază ale sistemului de ecuaţii.

Remarcă. Să reamintim că denumirea de variabilă bază e legată de faptul că vectorii-coloane  respective ale matricei sistemului de ecuaţii  formează bază în spaţiul Rr, adică sunt liniar independenţi. Termenii liberi sunt coeficienţii descompunerii vectorului b  în bază. O eliminare completă conduce la formarea altei baze prin înlocuirea unuia dintre vectorii de bază cu un vector liber, obținându-se şi descompunerea lui b în noua bază.

Procesul de calcul în metoda Gauss-Jordan se ordonează cu ajutorul unor tabele speciale, numite tabele Gauss. În ele elementul αrs, numit pivot, se marchează printr-un dreptunghi, triunghi sau cerc. Linia r e numită linie pivot, coloana s –  coloană pivot, iar o transformare a tabelului conform formulelor de mai sus – pivotare.

În procesul de calcul se aplică aşa-numita regulă (mnemotehnică) a dreptunghiului care constă în următoarele. La transformarea elementului αij (i≠r), elementul αij se proiectează imaginar pe linia pivot şi coloana pivot, obținându-se un dreptunghi cu vârfurile în αij, αis, αrj, αrs. Elementul αij se recalculează scăzînd din elementul αij, situat în unul dintre vârfurile dreptunghiului, produsul αis αrj al elementelor situate în două vârfuri opuse, împărţit la pivotul αrs, situat în cel de-al patrulea vârf – opus. Aceeaşi regulă se foloseşte şi la calcularea elementelor βi.

În fine, poate fi expus un algoritm de rezolvare a problemei de programare liniară, derivat din metoda Gauss-Jordan, algoritm ce determină soluţia optimă a problemelor de programare liniară în care a priori e cunoscut că ea există şi e finită.

  1. Dacă valoarea optimă a problemei date de programare liniară e finită, atunci se trece la pasul 2. În caz contrar, stop.
  2. k=1. Problema de programare liniară se aduce la forma standard.
  3. Se determină prin metoda Gauss-Jordan o soluţie de bază x1 a sistemului de ecuaţii liniare; tabelul corespunzător se notează T1 şi se salvează; se trece la pasul 4.Dacă sistemul nu are soluţii de bază, atunci problema de programare liniară nu are soluţii admisibile; stop.
  4. Din tabelele T1,… ,Tk se selectează un tabel şi un pivot în el pentru care pivotarea dă o soluţie de bază xk+1 ce are o combinaţie a variabilelor de bază diferită de cele ale soluţiilor de bază x1,…, xk; se efectuează pivotarea; se determină xk+1; tabelul Tk+1 se salvează; se trece la pasul 5.Dacă tabelul cu caracteristicile cerute nu există, atunci toate soluţiile de bază sunt determinate   şi se trece la pasul 6.
  5. k=k+1; se trece la pasul 4.
  6. Dacă printre x1,… , xk nu există soluţii admisibile, atunci şi problema iniţială nu are soluţii admisibile; stop. În caz contrar, se calculează valoarea funcţiei obiectiv pentru fiecare soluţie admisibilă x1,… , xk şi se alege ca punct de maxim soluţia admisibilă de bază cu cea mai mare valoare a funcţiei obiectiv.

Remarcă. Metoda Gauss-Jordan serveşte ca bază nu numai pentru acest algoritm, dar şi pentru toate variantele cunoscute ale metodei simplex.

Trecerea de la o soluţie admisibilă de bază la alta. Selectarea liniei pivot

Să presupunem că printr-o careva metodă am reuşit să determinăm o soluţie admisibilă de bază a sistemului (2). În atare supoziţie sistemul de ecuaţii (2) poate fi explicitat în raport cu m variabile şi, fără a pierde din generalitate, vom presupune că anume în raport cu primele m variabile:

x1_______+ α1m+1 xm+1 + … + α1n xn = β1,
___x2____+ α2m+1 xm+1 + … + α2n xn = β2,

_______xm + αmm+1 xm+1 + … + αmn xn = βm,

care are în calitate de soluţie admisibilă de bază vectorul x0 = (β1, β2,…, βm,  0,…, 0)T .

Trecerea de la această soluţie admisibilă de bază la altă soluţie admisibilă de bază e condiţionată de transformarea uneia dintre variabilele libere xm+1,…, xn în variabilă de bază. Pentru a realiza cu succes această trecere, e  suficient să existe un coeficient αij ≠ 0, j∈ {m+1,…, n}, i ∈ {1,…, m}. Presupunem că αrs ≠ 0, r∈ {m+1,…, n}, s ∈ {1,…, m}.

Elementul αrs îl vom numi  pivot. O eliminare completă a variabilei xs e echivalentă cu trecerea la un nou sistem, cu coeficienţi şi termeni liberi calculaţi după formulele:

αrj := αrj / αrs j=1,…, n;_________________
βr :=βr / αrs,_________________________
αij := αij – αis αrj /  αrs i=1,…,m, j=1,…, n,  i≠ r;
βi :=βi – βr αis αrj /  αrs i=1,…, m, i≠ r.______

Pentru ca soluţia de bază obţinută să fie admisibilă, din (4) reiese că trebuie să se verifice inegalităţile:

βrrs ≥ 0,________________
βi – βr αisrs ≥ 0, i=1,…,m, i≠ r,

echivalente cu:

αrs > 0,__________________
βrrs ≥ βiis, i= 1,…, m, i ≠ r,

sau cu:

αrs > 0,___________________
βrrs = min{ βiis | i: αis > 0}.

Aşadar, pivotul trebuie să fie pozitiv şi raportul termenilor liberi la elementele αis>0 din coloana s să fie cel mai mic anume pentru linia r, numită linie pivot.

Transformările efectuate conform formulelor de mai sus în condiţiile specificate se numesc transformări simplex. Ele permit să se efectueze trecerea de la o soluţie admisibilă de bază (de la un vârf al mulţimii poliedrale de soluţii admisibile) la alta (la alt vârf) după o regulă bine cunoscută – regula dreptunghiului din metoda Jordan-Gauss.

Teoremă. O transformare simplex a sistemului de ecuaţii  este echivalentă cu trecerea de la o soluţie admisibilă de bază la o altă soluţie admisibilă de bază. Dacă prima este degenerată, atunci se „glisează” pe aceeaşi soluţie admisibilă de bază, schimbându-se doar unul dintre vectorii componenţi ai bazei.

Criteriul de selectare a coloanei pivot. Criteriul de optimalitate şi cel de nemărginire

Considerăm că a fost găsită o soluţie admisibilă de bază x
0
= (β1, β2,…, βm,  0,…, 0)T a problemei standard şi presupunem în continuare, fără a pierde din generalitate, că ea are nenule primele m componente. În asemenea caz, sistemului iniţial de ecuaţii îi corespunde un sistem echivalent în care sunt explicitate primele m variabile (xB + B-1 S xS = B-1b):

x1_______+ α1m+1 xm+1 + … + α1n xn = β1,
___x2____+ α2m+1 xm+1 + … + α2n xn = β2,

_______xm + αmm+1 xm+1 + … + αmn xn = βm.

Soluţia generală a sistemului este xi = βi – ∑nj=m+1 αij xj, i=1,…, m, din care orice soluţie particulară (inclusiv şi soluţiile admisibile  de bază) se obţine atribuind valori potrivite variabilelor libere xm+a,…, xn.

Fie x=(x1, x2,…, xn)T o careva soluţie particulară. Pentru ea avem următoarea valoare a funcţiei obiectiv:

z(x)= c1 x1 + … + cn xn = c1 (β1 – ∑nj=m+1 α1j xj) + … + cmm – ∑nj=m+1 αmj xj)+ cm+1 xm+1 + … + cn xn = ∑mi=1 ci βi – ∑nj=m+1 (∑mi=1 cj αij – cj) xj = z(x0 ) – ∑nj=m+1 (zj – cj) xj = z0 – ∑nj=m+1 (zj – cj) xj,

unde zj – cj = ∑mi=1 cj αij – cj = (cBT B-1A)j – cj este estimaţie relativă sau factor relativ de cost; z0= z(x0 ) = ∑mi=1 ci βi este valoarea funcţiei obiectiv în punctul dat. Funcţia obiectiv poate fi scrisă şi în forma:

z(x)= z(x0 ) – ∑nj=m+1 (zj – cj) xj = z(x0 ) – (cBT B-1A – c )T x.

Evident, dacă zj – cj >0, j=m+1,…, n,  atunci valoarea funcţiei obiectiv pentru orice altă soluţie particulară nu poate fi mai mare decît z(x0 ), iar dacă zj – cj ≥ 0, j=m,…, n, şi există zj – cj = 0,  j∈ m+1,…, n,  atunci există o altă soluţie admisibilă de bază cu aceeaşi valoare a funcţiei obiectiv (la care se poate trece utilizând transformările simplex) şi valoarea problemei se realizează într-o infinitate de puncte – combinaţii convexe ale soluţiilor admisibile de bază optime.

În baza celor expuse au loc următoarele teoreme.

Teoremă (criteriul de optimalitate). Soluţia admisibilă de bază este punct de maxim (de minim) dacă şi numai dacă toate estimaţiile variabilelor libere sunt nenegative (nepozitive), adică:

zj – cj ≥ 0 (zj – cj ≤ 0),  j=m+1,…, n.__(3)

Dacă toate inegalităţile în (3) sunt stricte, atunci soluţia optimă e unică, iar dacă în (3) există zj – cj = 0, j∈ {m+1,… , n}, atunci există o infinitate de soluţii optime.

Teoremă (criteriul de selectare a coloanei pivot). Dacă există zs – cs <0,  s ∈ {m+1, …, n}, şi există βrrs = min{βiis | i: αis>0}, atunci o transformare simplex cu pivotul αrs va mări valoarea funcţiei obiectiv cu – βr(zs–cs)/αrs.

Teoremă (criteriul de nemărginire). Dacă există zs–cs<0,  s ∈ {m+1, …, n}, şi αis≤0 pentru toţi i=1,…, m, atunci problema nu are valoare optimă finită.

În conformitate cu teorema 2, pentru a trece de la o soluţie admisibilă de bază la alta, se selectează o estimaţie negativă zs – cs <0,  s ∈ {m+1, …, n}, şi se efectuează transformările simplex cu pivotul αrs în coloana s (r – linia pivot). Dacă termenul liber βr din linia pivot e pozitiv, atunci se va trece la o nouă soluţie admisibilă de bază, cu valoarea funcţiei obiectiv mai mare; dacă termenul liber βr din linia pivot e nul, atunci în urma transformărilor simplex soluţia admisibilă de bază rămâne neschimbată, deoarece soluţia e degenerată (xs devine variabilă de bază, iar  xr – variabilă liberă); dacă în coloana s  toate elementele sunt nepozitive, adică αis ≤ 0, i=1,…, m},  atunci tragem concluzia că problema iniţială nu are valoare optimă mărginită (funcţia obiectiv (2) poate creşte oricît de mult, deoarece în (1) variabila xs şi, respectiv, variabilele de bază xi, pentru care αis <0, pot creşte oricît de mult.

Remarcă. Din (2) reiese că estimaţia zj – cj a unei variabile libere xj , j∈ {m+1,… , n}, este egală cu valoarea cu care se schimbă valoarea funcţiei obiectiv la creşterea cu o unitate a valorii variabilei} xj ( dacă zj – cj e negativă, atunci valoarea funcţiei obiectiv creşte, în caz contrar, descreşte).

Ordonarea calculelor. Alcătuirea tabelului simplex

Dacă dorim să construim un algoritm care ar realiza trecerea de la un vârf al mulţimii poliedrale de soluţii admisibile X la alt vârf, este important ca totdeauna să fie la îndemână:

  • coeficienţii şi termenii liberi ai sistemului de ecuaţii explicitat corespunzător;
  • estimaţiile  relative zj – cj ale variabilelor.

Acest lucru poate fi asigurat reprezentând datele în formă de tabel.

Fie că a fost găsită o soluţie admisibilă de bază a problemei standard şi presupunem, fără a pierde din generalitate, că în sistemul respectiv sunt explicitate primele m variabile:

x1 + α1m+1 xm+1 + … + α1n xn = β1,
x2 + α2m+1 xm+1 + … + α2n xn = β2,

xm + αmm+1 xm+1 + … + αmn xn = βm.

În baza reprezentării (2) din paragraful precedent, funcţia obiectiv poate fi scrisă ca o ecuaţie de forma: z(x)= z(x0 ) – ∑nj=m+1 (zj – cj) xj, care  poate fi alăturată la sistemul de ecuaţii. Introducând notaţiile:

α0j = ∑mi=1 cj αij – cj,  j=1,…, n,
αi0 = β
i
, i=1,…, m,__________
α00 =  ∑mi=1 βi,___________

sistemul precedent se transformă în:

x1 + α1m+1 xm+1 + … + α1n xn = β1,
x2 + α2m+1 xm+1 + … + α2n xn = β2,

xm + αmm+1 xm+1 + … + αmn xn = βm,
z +  αom+1 xm+1 +  … + α0nxn = α00,

numit sistem lărgit.

Dacă în el se efectuează transformările simplex cu pivotul αrs (transformări ce includ şi ultima ecuaţie, fără cerinţa ca α00 să fie nenegativ), atunci elementele  noului sistem pot fi calculate utilizând bine cunoscuta regulă a dreptunghiului şi pentru linia alăturată:

α0j := αoj – αrj α0s / αrs, j=0,…, n.

Deci sistemul (4) conţine toate datele necesare pentru alcătuirea algoritmului şi de aceea e important ca (4) totdeauna să fie la dispoziţia utilizatorului. Din considerente de comoditate, claritate şi eficienţă, (4) se păstrează sub formă de tabel – aşa-numitul tabel simplex şi toate calculele se efectuează anume în cadrul tabelelor simplex.

Observăm că:

  • ultima linie din tabel conţine estimaţiile variabilelor şi valoarea funcţiei obiectiv  α00 pentru soluţia admisibilă de bază x=(α10, α20,… , αm0, 0,… , 0)T;
  • coloana a doua conţine lista variabilelor de bază;
  • coloana a treia conţine valorile variabilelor de bază (termenii liberi ai sistemului de ecuaţii);
  • prima coloană conţine coeficienţii din funcţia obiectiv ai variabilelor de bază.

Elementele αij, i=0,…, m,  j=0,…,n, ale tabelului simplex le-am interpretat, pe bună dreptate, ca coeficienţi şi termeni liberi ai sistemului de ecuaţii. Dar elementele au şi altă semnificaţie: dacă B={A1, A2,… , Am} este o bază a matricei A a sistemului de ecuaţii al problemei standard, atunci elementele αij,  j=1,…,m, sunt coordonate ale vectorului coloană Aj,   j ∈ {1, …, n},  în baza B. De aceea, elementele tabelului simplex sunt notate şi prin xij,  i=0,…, m},  j=0,…, n, subînțelegându-se, în aşa caz, coordonatele obţinute la descompunerea coloanelor matricei sistemului de restricţii (a problemei standard iniţiale) în baza corespunzătoare.

Determinarea soluţiei admisibile de bază iniţiale

A rămas neelucidată o singură chestiune: cum se determină soluţia admisibilă de bază iniţială de la care îşi începe execuţia algoritmul simplex? Desigur, în unele cazuri ea se obţine chiar din formularea problemei. De exemplu, la cercetarea problemei canonice:

c1 x1 + c2 x2 + … + cnxn → max,_____
i1x1 + a­i2x2 + … + ainxn ≤ bi, i=1,…,m,
xj ≥ 0, j=1,…,n,___________________

în care bi ≥ 0, i=1,…,m, trecerea (prin introducerea variabilelor ecart xn+1, xn+2, … , xn+m la forma standard:

c1 x1 + c2 x2 + … + cnxn → max,__________
i1x1 + a­i2x2 + … + ainxn+xn+i = bi, i=1,…,m,
xj ≥ 0, j=1,…,n+m,_____________________

este însoţită de formarea unei baze unitare B =[αn+1… αn+m = [e1 … em], căreia îi corespunde soluţia admisibilă de bază x=(0,… ,0,b1,… ,bm)T.

Dacă problema are forma standard (1)-(2) şi nu conţine o bază unitară, atunci pot fi încercate metodele cunoscute de soluţionare a sistemelor de ecuaţii liniare, cum este metoda Gauss-Jordan. Totuşi rezultatul scontat totdeauna poate fi obţinut prin metoda bazei artificiale, definitivată în două variante: metoda celor două faze şi metoda coeficienţilor de penalizare,  ambele variante reducând problema determinării soluţiei admisibile de bază iniţiale la o problemă secundară de programare liniară.

Metoda celor două faze. În faza I, în se introduc variabilele artificiale xn+1,… ,xn+m şi se rezolvă problema artificială:

xn+11 + xn+2 + … + xn+m → min,_________
i1x1 + a­i2x2 + … + ainxn+xn+i = bi, i=1,…,m,
xj ≥ 0, j=1,…,n+m,_____________________

care are soluţia admisibilă de bază  iniţială x=(0,… ,0,b1,… ,bm)T.

Dacă problema secundară are valoarea optimă nulă, atunci soluţia acestei probleme este soluţie admisibilă  de bază iniţială a problemei iniţiale, soluţie care poate fi utilizată mai departe în faza a II-a la aflarea soluţiei optime a problemei iniţiale. Dacă problema secundară are soluţie pozitivă, problema iniţială  nu are soluţii admisibile.

Metoda coeficienţilor de penalizare

Se introduc variabilele artificiale ca şi în cazul precedent, şi în locul problemei iniţiale  se rezolvă:

c1 x1 + c2 x2 + … + cnxn – Mxn+1 – … – Mxn+m → max,
i1x1 + a­i2x2 + … + ainxn+xn+i = bi, i=1,…,m,______
xj ≥ 0, j=1,…,n+m,___________________________

în care M este un număr pozitiv suficient de mare, numit coeficient de penalizare; x=(0,… ,0,b1,… ,bm)T este soluţie admisibilă de bază. Dacă după soluţionarea ultimei probleme   una dintre variabilele artificiale mai rămâne bazică, cu valoare pozitivă, atunci problema iniţială nu are soluţii admisibile; în caz contrar, soluţia optimă pentru problema cu M  este soluţie optimă şi pentru cea iniţială.

Remarca 1. Ambele variante ale metodei bazei artificiale adeseori se termină nu numai cu obţinerea soluţiei admisibile de bază iniţiale a problemei iniţiale, şi, în anumite situaţii, şi cu obţinerea soluţiei optime.

Remarcă. La soluţionarea problemelor cu variabile artificiale prin algoritmul simplex e raţ
ional ca transformarea în nebazică a uneia dintre variabilele artificiale să fie însoţită de suprimarea coloanei respective a tabelului simplex.

Remarcă. Metoda coeficienţilor de penalizare poate fi şi ea divizată în două etape, prima etapă terminându-se odată cu transformarea în nebazice a tuturor variabilelor artificiale.

Remarcă. Dacă prin metoda bazei artificiale se determină că problema de rezolvat nu are soluţii admisibile, atunci în tabelul simplex final există cel puţin o linie în care toate variabilele neartificiale au coeficienţi nepozitivi. Aceasta este echivalent cu faptul că pentru problema de rezolvat prin transformări de echivalenţă se determină o ecuaţie contradictorie în care termenul liber e pozitiv, iar coeficienţii variabilelor neartificiale sunt nepozitivi.

Algoritmul simplex

În conformitate cu cele menţionate anterior, metoda simplex este o procedură iterativă de generare a unei consecutivităţi finite de soluţii admisibile de bază (vârfuri ale mulţimii poliedrale de soluţii admisibile) x0, x1,…, xk cu proprietatea că z(xi) ≤ z(xi+1), i=0,…, k. Dacă problema iniţială are soluţie optimă, atunci xk şi este punctul de maxim.

În detaliu algoritmul simplex poate fi reprezentat astfel:

  1. Problema iniţială de programare liniară se aduce la forma standard (1)-(2).
  2. Se determină o soluţie admisibilă de bază iniţială. Dacă ea nu există, atunci problema  dată nu are soluţii admisibile (stop).
  3. Se construieşte tabelul simplex iniţial.
  4. Dacă se satisface criteriul de optimalitate (sunt nenegative toate estimaţiile relative, adică α0j=zj–cj≥0, j=1,…, n), atunci  soluţia admisibilă de bază curentă este de optimă (stop).
  5. Se alege coloana pivot s pentru care α0s<0.
  6. Se alege linia pivot r pentru care are loc: αr0rs = min{αi0is | i : αis>0}. Dacă toate elementele din coloana pivot sunt nepozitive, adică αis≤0, i=1,…,m, atunci problema iniţială nu are soluţie optimă mărginită (stop).
  7. Din ecuaţiile 0,1,…r-1,r+1, … , m se elimină variabila xs prin intermediul transformărilor simplex:

αrj :=αrjrs, j=0,…, n,__________________
αij := αij – αrj αisrs,  i=0,…, m, i≠r, j=0,…, n,

_____şi se trece la pasul 4.

Remarcă. În 1979, Leonid Khachiyan a demonstrat că problema de programare liniară are complexitate polinomială (ca funcţie de dimensiunile problemei).Teoretic, metoda simplex în cel mai rău caz poate efectua un număr exponenţial de iteraţii. În practică – numărul de iteraţii este de cele mai dese ori comparativ cu numărul de ecuaţii, ceea ce explică faptul de ce metoda se foloseşte pe larg şi în prezent la rezolvarea problemellor de programare liniară.

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

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

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