PROGRAMAREA LINIARĂ

Prezentare generală

Mulţimea sistemelor economice concrete şi multitudinea problemelor conducerii acestora au creat o diversitate de reprezentări economico-matematice, denumite modele.

Varietatea acestora este determinată, în principal, de structura "obiectului" analizat, de scopul cercetării precum şi de informaţia disponibilă.

Modelele de programare matematică şi mai ales subclasa acestora – modelele de programare liniară – ocupă un loc deosebit de important, atât în teoria cât şi în practica economică. Teoria economică a beneficiat de aportul abordării interdisciplinare care a permis aprofundarea analizei eficienţei maximale a sistemelor complexe, a permis descoperirea unor concepte noi ale optimului economic, a perfecţionat metodele de cercetare şi cunoaştere iar practica economică s-a îmbogăţit cu un instrument deosebit de util analizei economice şi fundamentării deciziilor.

Structura modelului general de programare liniară se constituie în primul rând prin mulţimea de activităţi {A₁, A₂, ... A_n} care compun sistemul economic analizat, mulţimea de resurse utilizate {R₁, R₂, ... R_m} precum şi prin relaţiile tehnico-economice dintre acestea. Legătura dintre activităţi şi resurse este determinată de tehnologia de fabricaţie corespunzătoare fiecărei activităţi A_j (j=1,...,n) şi poate fi caracterizată numeric prin vectorul coloană a^(j) de componente (a_1j, a_2j, ... a_mj). Elementele {a_ij, i = 1,...,m; j = 1,...,n} se numesc coeficienţi tehnici sau coeficienţi de consum specific şi arată ce cantitate din resursa R_i se consumă pentru producerea unei unităţi din produsul (serviciul) P_j (ca rezultat al activităţii A_j). Toate "tehnologiile" de fabricaţie definite de vectorii coloană a^(j) se pot organiza într-o matrice A cu m linii şi n coloane; fiecare linie se referă la o resursă R_i (i = 1,...,m) şi fiecare coloană se referă la o activitate A_j (j = 1,...,n).

Notând cu x_j (j = 1,...,n) rezultatul activităţii A_j într-o perioadă dată şi cu b_i (i = 1,...,m) cantităţile disponibile din resursele R_i (i = 1,...,m), se pot scrie matematic următoarele restricţii tehnico-economice:

(1) sau A×x £ b

unde A = ; x = şi b =

Fiecare inecuaţie/restricţie încorporează două afirmaţii:

a. cantitatea consumată dintr-o resursă nu poate depăşi volumul disponibil (propoziţie de logică economică)

b. consumul total R_ij din resursa R_i pentru efectuarea activităţii A_j este proporţional cu intensitatea acesteia, adică cu x_j, deci R_ij(*) = a_ij × x_j (ipoteză simplificatoare)

Sistemul de restricţii (1) realizează legătura dintre resurse şi activităţi prin intermediul celor m restricţii liniare.

Modelul problemei de programare liniară conţine restricţii de tipul (1) precum şi un criteriu de "performanţă" care să permită evaluarea eficienţei fiecărei activităţi. În funcţie de scopul urmărit, putem alege drept criteriu de eficienţă un indicator care măsoară efortul, unul care măsoară rezultatul sau un indicator exprimat ca raport între rezultat şi efort (sau efort pe rezultat).

Este evident că eficienţa maximă înseamnă minimizarea efortului şi maximizarea rezultatului, iar conceptul de optim se defineşte, în acest caz, ca un program xÎ Rⁿ care minimizează sau maximizează o funcţie obiectiv şi, în acelaşi timp, satisface toate restricţiile tehnico-economice.

Presupunând că fiecare componentă a vectorului linie c = (c₁, c₂, ..., c_n) măsoară eficienţa unei unităţi din rezultatul activităţii A_j, atunci se poate introduce funcţia liniară:

f(x) = c₁×x₁ + c₂×x₂ + ... + c_n×x_n

care evaluează performanţa oricărui program x.

Sintetizând, obţinem următorul program de programare liniară:

unde I₁ È I₂ = {1,2,...,m}

(2)

(3)

(1)

Relaţiile (1), (2) şi (3) constituie împreună modelul general al unei probleme de programare liniară, având fiecare un rol specific:

1. relaţia (1), unde f(x) = este denumită funcţia obiectiv de eficienţă a problemei, evaluează eficienţa/performanţa fiecărei variante de program x;

2. relaţiile (2) de tipul reprezintă restricţii de tip resurse; iar restricţiile de tipul se referă la restricţii tehnico-economice de tip calitativ (şi ca urmare indicatorul b_k este limita inferioară impusă "reţetei optime";

3. relaţia (3) x_j ³ 0 j = 1,...,n, numită condiţia de nenegativitate a variabilelor, asigură obţinerea unei soluţii realizabile din punctul de vedere al logicii economice.

După cum s-a arătat la început, structura concretă a unei aplicaţii în economie este determinată în primul rând de obiectivul urmărit.

Astfel, în cazul problemei determinării structurii sortimentale optime a producţiei, se cunosc cantităţile disponibile (cantităţile de care se poate face rost pe perioada analizată) din fiecare materie primă {b_i, i =1,...,m}, coeficienţii tehnologici {a_ij, i = 1,...,m, j = 1,...,n} (a_ij reprezintă cantitatea din materia primă i necesară fabricării unei unităţi din produsul de tipul j), cantităţile maxime {, j = 1,...,n} şi minime {, j = 1,...,n} ce pot fi produse din fiecare sortiment în perioada analizată şi profiturile unitare {p_j, j = 1,...,n} ale fiecărui tip de produs. Se cere găsirea acelor cantităţi x_j care trebuie fabricate din fiecare tip de produs astfel încât să se obţină profitul maxim, în condiţiile nedepăşirii disponibilurilor din fiecare resursă.

Pentru simplificarea modelului, se presupune că preţul unui bun nu depinde de cantitatea produsă din acesta sau din celelalte, consumul din fiecare materie primă este direct proporţional cu cantitatea produsă şi, pentru fiecare bun, consumurile dintr-o resursă sau alta nu se condiţionează reciproc.

Problema matematică echivalentă este:

În unele probleme, în loc de profiturile p_j se cunosc veniturile unitare v_j sau costurile unitare c_j sau alt criteriu de eficienţă, scopul fiind maximizarea venitului, minimizarea costurilor respectiv optimul indicatorului de eficienţă respectiv, sau toate la un loc. De asemenea pot lipsi condiţiile de limitare a producţiei sau pot exista şi alte condiţii.

La o problemă de programare operativă a producţiei restricţiile se referă la o serie de maşini (utilaje) cu care se execută produsele dorite, b_i fiind disponibilul de timp al utilajului i pe perioada analizată iar a_ij timpul necesar prelucrării unui produs de tipul j pe utilajul i, scopul fiind maximizarea producţiei.

Ca urmare, modelul are forma:

Dacă se doreşte obţinerea unui meniu (reţete furajere), care să asigure necesarurile {b_i, i = 1,...,m} dintr-un număr de m substanţe esenţiale organismului, având la dispoziţie un număr de n alimente, cunoscându-se cantităţile {a_ij, i = 1,...,m, j = 1,...,n} din fiecare substanţă pe care le conţine o unitate de măsură din fiecare aliment şi costurile {c_j, j = 1,...,n} unei unităţi de măsură din fiecare aliment, putem scrie modelul:

Variabilele x_j reprezintă, în acest caz, cantitatea din fiecare aliment ce va intra în meniu iar f(x) = este costul total al reţetei definită de vectorul x.

Vom încheia exemplificarea cu prezentarea modelului amestecului optim de produse petroliere. Presupunem că o rafinărie dispune de n tipuri de benzine, prin amestecarea acestora urmând să obţină o benzină cu m caracteristici impuse şi la un preţ minim posibil. O serie de caracteristici trebuie să fie îndeplinite cu o limită inferioară (de exemplu cifra octanică), altele cu o limită superioară (de exemplu densitatea sau temperatura de fierbere) şi altele cu egalitate (de exemplu cantitatea necesară), aceste limite fiind, i = 1,...,m₁ , , i = 1,...,m₂ respectiv , i = 1,...,m₃ cu m₁ + m₂ + m₃ = m. De asemenea, trebuie ţinut cont de cantităţile disponibile din fiecare benzină D_i, i = 1,...,n. Se cunosc caracteristicile fiecărei benzine disponibile, date într-o matrice A Î M_m´n, unde a_ij este valoarea caracteristicii i pentru benzina j şi preţurile unitare ale fiecărei benzine, notate p_j, j = 1,...,n. Dacă notăm cu x_j, j = 1,...,n, cantităţile din fiecare benzină care vor forma amestecul optim, atunci avem de rezolvat problema:

Programarea matematică

Se observă că toate aceste probleme, cu toate că reprezintă situaţii economice total diferite, sunt aplicaţii în sfera activităţii economice ale următoarei probleme de optimizare:

în care funcţiile f,g_i : Rⁿ ® R pot avea orice formă şi proprietăţi (liniare, convexe, continui, diferenţiabile etc) iar W poate fi orice submulţime a lui Rⁿ (continuă sau discretă, mărginită sau nemărginită, convexă sau neconvexă, finită sau infinită etc) şi în care dorim să găsim minimul sau maximul funcţiei f în variabilele x_i care îndeplinesc restricţiile 1.2 şi 1.3. O astfel de problemă se numeşte problemă de programare matematică.

Funcţia (1.1) se numeşte funcţia obiectiv a problemei de optimizare. În aplicaţiile economice, ea reprezintă criteriul de performanţă urmărit: maximizarea beneficiului, maximizarea producţiei marfă, minimizarea costului producţiei, maximizarea gradului de încărcare al utilajelor sau minimizarea timpului de staţionare al acestora, maximizarea veniturilor etc.

Inegalităţile (1.2), în care g_i sunt funcţii de n variabile iar b_i sunt constante, se numesc restricţii ale problemei de optimizare. Ele traduc în limbaj matematic condiţiile de natură economică sau tehnologică în care se desfăşoară procesul economic modelat, cum ar fi: nedepăşirea stocurilor disponibile de resurse (materii prime, capacităţi de producţie, forţă de muncă, fonduri băneşti, timp etc), îndeplinirea sau depăşirea unor indicatori economici (producţia fizică, netă) etc.

Condiţiile (1.3), impuse "direct" variabilelor, depind de natura problemei studiate. De cele mai multe ori, W este mulţimea vectorilor x = (x_l,...,x_n) Î Rⁿ cu toate componentele nenegative şi acest fapt se justifică prin aceea că, în general, x_i reprezintă "nivelele" unor activităţi de producţie, nivele care nu pot fi negative. În unele probleme de optimizare, cum ar fi cele de croire sau ordonanţare, variabilele desemnează mărimi indivizibile şi deci nu pot lua decât valori întregi. Mulţimea W va fi formată în acest caz din vectori x cu toate componentele întregi şi nenegative. În alte probleme, ca de pildă cele de afectare, portofoliu etc, variabilele nu pot lua decât valorile 0 sau 1 (variabile bivalente) şi ca atare W va fi formată din vectorii x = (x₁, …,x_n) cu toate componentele 0 sau 1. Caracteristic acestor tipuri de probleme este faptul că W devine o submulţime discretă din Rⁿ, de unde şi numele generic de probleme de optimizare discretă dat acestora.

O soluţie a unei astfel de probleme are deci trei proprietăţi:

P1. verifică restricţiile 1.2

P2. verifică restricţiile "directe" 1.3

P3. optimizează funcţia obiectiv pe mulţimea vectorilor care îndeplinesc condiţiile P1. şi P2.

În teoria programării matematice se folosesc, pentru claritatea şi simplitatea expunerii, următoarele noţiuni:

soluţie a problemei de optimizare	=	un vector x Î R^n care verifică restricţiile 1.2
soluţie admisibilă a problemei de optimizare	=	un vector x Î R^n care verifică restricţiile 1.2 şi 1.3 Û o soluţie care verifică restricţiile 1.3
soluţie optimă a problemei de optimizare	=	un vector x Î R^n care verifică restricţiile 1.2 şi 1.3 şi optimizează funcţia obiectiv pe mulţimea tuturor vectorilor cu această proprietate Û o soluţie care verifică restricţiile 1.3 şi optimizează funcţia obiectiv pe mulţimea tuturor soluţiilor cu această proprietate Û o soluţie admisibilă care optimizează funcţia obiectiv pe mulţimea soluţiilor admisibile

Izvorâtă din studiul problemelor extremale ale analizei matematice clasice, programarea matematică a cunoscut în ultimele decenii o dezvoltare spectaculoasă, explicabilă numai în parte prin progresele înregistrate în matematică. Într‑adevăr, această dezvoltare a fost puternic stimulată de creşterea vertiginoasă a complexităţii activităţilor economice, care a furnizat probleme cu structuri din ce în ce mai complicate, ca şi de rapida perfecţionare a mijloacelor automate de calcul, singurele capabile să testeze eficienţa practică a metodelor teoretice elaborate. La rândul ei, programarea matematică, prin rezultatele ei, a adus un considerabil aport la perfecţionarea metodelor de conducere în economie şi a impulsionat cercetările ‑ în plan teoretic ‑ privind modelarea sistemelor economice complexe, studiul şi interpretarea legilor şi proceselor economice.

În ceea ce priveşte rezolvarea acestor probleme, este evident că varietatea extremă a acestora face imposibilă găsirea unui algoritm practic care să le poată rezolva pe toate, dar putem găsi (sau ne putem aştepta să găsim), pentru fiecare caz particular, un algoritm de rezolvare care să-şi tragă eficacitatea tocmai din folosirea tuturor particularităţilor cazului respectiv. În prezent există sute de algoritmi de rezolvare, cercetarea problemei evoluând din ce în ce mai mult spre testarea şi îmbunătăţirea acestora decât spre găsirea unora noi.

Problema de programare liniară

Definiţia 1. Dacă într-o problemă de programare matematică funcţia obiectiv f şi funcţiile g_i, din restricţiile 1.2, sunt funcţii liniare atunci problema se numeşte problemă de programare liniară. O problemă de programare liniară este, deci, un caz particular al problemelor de programare matematică şi, ţinând cont de forma oricărei funcţii liniare, rezultă că forma generală a oricărei probleme de programare liniară este:

unde c_j (coeficienţii funcţiei obiectiv), a_ij (coeficienţii restricţiilor) şi b_i (termenii liberi) sunt constate reale.

Forma conică şi forma standard a unei probleme de programare liniară

Cu toate că problema de programare liniară este cea mai simplă dintre problemele de programare matematică, ea este încă destul de complicată, prin faptul că orice restricţie poate avea trei forme diferite iar obiectivul poate fi minimizarea sau maximizarea funcţiei f. Este puţin probabil că există un algoritm şi simplu şi aplicabil la toate cazurile.

Din acest motiv este mult mai simplu să găsim o anumită formă (cât mai simplă) cu proprietatea că pentru orice problemă P, există o alta problemă P' de această formă, echivalentă cu problema iniţială P (spunem că două probleme sunt echivalente dacă există un izomorfism între mulţimile soluţiilor celor două probleme şi un homeomorfism între funcţiile lor obiectiv) şi să dispunem de un algoritm care să rezolve problemele de această formă şi de o regulă prin care să găsim soluţia problemei iniţiale P din soluţia problemei P', găsită cu acest algoritm.

În acest sens (dar şi din cauza frecvenţei apariţiei lor în practică) s-au evidenţiat două forme ale problemelor de programare liniară, forma canonică şi forma standard.

Definiţia 2. Spunem că o problemă este la forma canonică dacă are una din următoarele două forme:

Forma canonică de minim	Forma canonică de maxim

Această formă este cel mai des întâlnită în practică (vezi problema determinării structurii sortimentale optime a producţiei sau problema dietei) şi, în plus, restricţiile economice sunt în general inegalităţi şi foarte rar egalităţi. De asemenea, această formă este invariantă la anumite transformări (vezi problema duală) şi asigură existenţa soluţiei (orice problemă la această formă, care are termenii liberi şi coeficienţii restricţiilor pozitivi, are soluţie).

Definiţia 3. Spunem că o problemă este la forma standard dacă are forma:

Această formă, deşi nenaturală din punct de vedere economic, este cea care se pretează cel mai bine la rezolvarea cu metodele algebrei clasice.

Propoziţie. Pentru orice problemă de programare liniară P există o problemă la forma canonică PFC şi o problemă la forma standard PFS echivalente cu P.

Demonstraţie. Într-adevăr:

a) orice problemă de maxim poate fi transformată în una de minim şi reciproc folosind relaţia:

max f(x) = – min f(–x)

b) orice restricţie de tipul "£" poate fi transformată într-o restricţie de forma "³" şi reciproc folosind relaţia:

a £ b Û –a ³ –b

c) orice restricţie inegalitate poate fi transformată în egalitate, prin introducerea unei variabile suplimentare nenegative şi folosind relaţiile:

a £ b Û şi a ³ b Û

Toate variabilele introduse pentru transformarea inegalităţilor în egalităţi se numesc variabile de abatere sau variabile de compensare.

d) orice restricţie egalitate poate fi transformată în restricţii inegalitate, folosind relaţia:

a = b Û

e) orice variabilă cu restricţie de semn negativă (x £ 0) poate fi înlocuită cu o variabilă cu restricţie de semn pozitivă (y ³ 0), folosind relaţia:

x £ 0 Û

f) orice variabilă fără restricţie de semn poate fi înlocuită cu două variabile cu restricţie de semn pozitivă, folosind relaţia:

x oarecare Û

Se demonstrează fără un efort matematic deosebit că dacă P' se obţine din P folosind doar transformările de mai sus (numite şi transformări elementare) atunci P şi P' sunt două probleme echivalente şi între soluţiile lor optime există o bijecţie.

Din cele de mai sus rezultă cum poate fi adusă orice problemă de programare liniară la forma standard (sau canonică) şi cum se obţine soluţia problemei iniţiale din soluţia problemei la forma standard (sau canonică).

Exemplu: Problemei P de mai jos îi corespunde problema la forma standard PFS alăturată:

P	PFS
(min) f = 3x1 –2x2 + 4x3	(max) g = +3a1 + 2y2 – 2z2 – 4x3

Problema PFS are o singură soluţie optimă:

a₁ = 3, y₂ = , z₂ = 0, x₃ = 0, x₄ = , x₅ = 0, x₆ = , x₇ = 0

care dă un maxim al funcţiei g egal cu .

Acestei soluţii îi corespunde singura soluţie optimă pentru P:

x₁ = -3, x₂ = , x₃ = 0

care dă un minim al funcţiei f, egal cu .

Rezolvarea problemei de programare liniară.

Analiza problemei

Fie o problemă P despre care presupunem (fără a restrânge generalitatea) că a fost adusă la forma standard. De asemenea presupunem (tot fără a restrânge generalitatea) că variabilele problemei au fost numerotate şi denumite x_j cu j = 1,...,n (n = numărul de necunoscute), coeficienţii variabilelor din funcţia obiectiv f cu c_j (c_j = coeficientul variabilei x_j), că în ecuaţii variabilele apar în ordinea indicilor, ecuaţiile fiind numerotate de la 1 la m (m = numărul de ecuaţii) şi că am notat cu b_i termenul liber al ecuaţiei i şi cu a_ij coeficientul variabilei j din ecuaţia i. În acest caz putem aşeza variabilele problemei într-un vector cu n componente, coeficienţii funcţiei obiectiv într-un vector cu n componente, termenii liberi într-un vector cu m componente, coeficienţii variabilelor din ecuaţii într-o matrice cu m linii şi n coloane şi vom avea:

x = , c = , b = , A =

(vom nota cu x^T, c^T şi b^T transpuşii acestor vectori şi cu A^T transpusa matricei A).

Alegerea aşezării ca vectori coloană a fost făcută din raţiuni de uşurinţă a calculelor şi a memorării acestora. După aceste notaţii, problema poate fi scrisă mult mai simplu:

sau

Se ştie că un sistem de forma A×x = b are soluţie doar dacă rang(A) = rang(), unde este matricea extinsă obţinută adăugând matricei A vectorul b, în acest caz sistemul devenind echivalent cu sistemul obţinut prin eliminarea restricţiilor care nu corespund minorului principal (dacă sistemul nu are soluţie atunci evident nici problema nu are soluţii, caz care este total neinteresant).

Presupunem că au fost eliminate aceste restricţii. Dacă rang A = n atunci sistemul are o singură soluţie care, dacă este admisibilă, este şi soluţia optimă căutată, altfel problema nu are soluţie. Este evident că şi acest caz este la fel de neinteresant ca primul.

Presupunem deci în continuare că:

rang(A) = m < n

Rezolvarea sistemului A×x = b se poate face într-un mod simplu (cel puţin teoretic) folosind algebra matricială astfel:

- împărţim coloanele matricei A în două submatrici: minorul principal (notat cu B, care este o matrice pătratică de dimensiune m şi va fi numit bază a sistemului) şi restul coloanelor (notat cu S, care este o matrice cu m linii şi n – m coloane);

- împărţim variabilele problemei în doi vectori: vectorul variabilelor principale (corespunzătoare coloanelor bazei) şi vectorul variabilelor secundare (notat cu x_S). Făcând eventual o renumerotare, pentru uşurinţa expunerii şi fiind evident că nu se restrânge generalitatea problemei, presupunem că variabilele principale sunt chiar primele m (această presupunere va fi făcută de câte ori va fi posibil, fără a mai specifica acest lucru).

- aducem succesiv sistemul la forma de mai jos:

A×x = b Û (BS)×= b Û B×x_B + S×x_S = b Û B×x_B = b – S×x_S Û x_B = B^-1×b – B^-1×S×x_S

- soluţia sistemului va fi submulţimea lui Rⁿ:

D_B = {x = {x_B,x_S} / x_S Î R^n-m oarecare, x_B = B^-1×b – B^-1×S×x_S}

Orice alegere a lui x_S dă o soluţie. Dintre toate alegerile posibile este remarcabilă (prin simplitatea ei) soluţia x_S = 0, care duce la soluţia particulară:

x^B =

numită soluţia de bază asociată bazei B. Deci x^B este x_B = B^-1×b la care se adaugă n-m zerouri. Cu toate acestea, vor fi ambele numite soluţie de bază, rezultând din context de care este vorba.

Observaţie: Este evident că fiecărui minor principal al sistemului (= minor de dimensiune m = bază) îi corespunde o unică soluţie de bază. O soluţie de bază care are toate componentele nenule strict pozitive se va numi soluţie de bază admisibilă iar o soluţie optimă care este de bază se va numi soluţie optimă de bază. Se observă că o soluţie de bază are cel mult m componente diferite de 0. Din cauza importanţei lor în rezolvarea problemei, vom evidenţia soluţiile de bază care au mai puţin decât m componente nenule, numite soluţii degenerate şi pe cele care au fix m elemente nenule, numite soluţii nedegenerate.

D_B este izomorfă cu Rⁿ, adică are tot atâtea elemente câte puncte sunt într-un spaţiu cu n_{_}–_{_}m dimensiuni. "Alegându-le" din acestea doar pe cele cu toate elementele pozitive, găsim mulţimea în care vom "căuta" vectorul (vectorii) care dă (dau) extremul lui f.

Rezolvarea problemei poate duce la următoarele rezultate:

R1. Sistemul A×x = b nu are soluţii sau nu are soluţii admisibile. În acest caz problema nu are soluţie.

R2. Imaginea funcţiei obiectiv pe mulţimea soluţiilor admisibile este nemărginită (la +¥ într-o problemă de maxim sau la -¥ într-o problemă de minim). În acest caz spunem că problema are optim infinit.

R3. Imaginea funcţiei obiectiv pe mulţimea soluţiilor admisibile este mărginită. În acest caz problema are cel puţin o soluţie şi spunem că problema are optim finit.

Greutatea găsirii soluţiei problemei constă în imensitatea numărului de soluţiilor posibile ale sistemului şi în respectarea condiţiei de nenegativitate a celor printre care căutăm extremul dorit al funcţiei f. Este natural ca primele încercări în rezolvare să caute în primul rând o limitare cât mai puternică a locului în care căutăm. Pe baza unor reprezentări geometrice ale problemei au fost descoperite următoarele proprietăţi ale problemei, care poartă denumirea de teoreme fundamentale ale programării liniare:

Teorema 1. Dacă problema de programare liniară are soluţii admisibile atunci are şi soluţii de bază admisibile.

Teorema 2. Dacă problema de programare liniară are soluţii optime atunci are şi soluţii optime de bază.

Teorema 3. Mulţimea soluţiilor admisibile (optime) este închisă şi convexă. Dacă este şi mărginită atunci punctele extremale ale acesteia sunt chiar soluţiile admisibile (optime) de bază ale problemei.

Cele două teoreme realizează efectiv trecerea către o problemă rezolvabilă pe calculator. Într-adevăr, deoarece o bază este un minor de ordinul m al matricii A şi unei baze îi corespunde o unică soluţie de bază rezultă că sunt cel mult soluţii de bază, adică un număr finit. În acest moment s-ar părea că nu avem decât să lăsăm calculatorul să calculeze toate soluţiile de bază şi valorile funcţiei obiectiv în cele admisibile găsind-o prin comparare pe cea care dă minimul sau maximul funcţiei printre acestea. Totuşi, această variantă se dovedeşte nepractică la o analiză mai atentă, ţinând cont de următoarele observaţii:

1. faptul că numărul soluţiilor de bază este finit ne asigură doar că problema se va termina cândva, ceea ce, din punct de vedere economic, este evident nemulţumitor. Noi dorim ca problema să fie rezolvată în timp util, adică repede. Rezolvând problema ca mai sus vom avea, pentru o problemă cu 50 variabile şi 20 restricţii, de calculat, listat şi comparat soluţii de bază, adică în jur de 10²⁰. Presupunând că suntem dotaţi cu un supercalculator care ar termina un miliard de baze pe secundă, rezolvarea ar dura 3000 ani. De altfel, o problemă ca cea de sus este foarte mică în comparaţie cu problemele "serioase" ce au peste 1000 de variabile şi 100 de restricţii. În plus, un calculator ca cel de sus nu există încă, deci în nici un caz nu e disponibil întreprinderilor obişnuite.

2. Cu algoritmul de mai sus vom găsi cea mai bună soluţie dintre soluţiile admisibile de bază, fără însă să ştim dacă problema admite, de fapt, optim (ar putea să aibă optim infinit).

3. Nu vom şti dacă un minor de m´m este bază decât după ce-i vom calcula determinantul şi nu vom şti dacă soluţia de bază corespunzătoare este admisibilă decât după ce o vom calcula.

4. Soluţia optimă, odată găsită, nu va fi recunoscută ca atare decât după ce vom calcula toate celelalte soluţii de bază, chiar dacă ea a apărut chiar la începutul calculelor.

În concluzie, pentru a fi eficient, un algoritm ar trebui să aibă următoarele proprietăţi:

a) să dispună de un criteriu de recunoaştere a faptului că problema nu are soluţii admisibile;

b) să dispună de un criteriu de recunoaştere a faptului că problema are optim infinit;

c) să dispună de un criteriu de recunoaştere dacă o soluţie este optimă sau nu;

d) să treacă de la o soluţie de bază admisibilă la una cel puţin la fel de bună (o soluţie x este mai bună decât o soluţie y dacă f(x) > f(y) într-o problemă de maxim şi f(x) < f(y) într-o problemă de minim;

e) să treacă de la o soluţie la cea mai bună dintre soluţiile cel puţin la fel de bune posibile ca succesoare;

f) să nu revină la o soluţie deja analizată;

g) să efectueze un număr de iteraţii comparabil polinomial cu dimensiunea problemei.

h) să nu introducă erori de rotunjire (sau nu prea mari);

i) să fie cât mai simplu de implementat;

Condiţiile de mai sus reprezintă de fapt un algoritm ideal. La începuturile cercetării operaţionale era suficient, de fapt, şi un algoritm care să îndeplinească măcar condiţiile b), c), d), e) şi h). Acest algoritm a fost dat de G.B. Dantzig, în 1947, care la numit algoritmul simplex. El rămâne şi în zilele noastre cel mai eficient algoritm în ceea ce priveşte viteza de lucru, simplitatea şi implementarea pe calculator, pentru problemele care apar efectiv în practica economică.

Totuşi, el nu îndeplinea condiţiile a), f) şi g).

Condiţia a) este relativ uşor de îndeplinit şi ea este acoperită prin introducerea unei faze iniţiale suplimentare la algoritmul simplex, rezultând algoritmul simplex în două faze.

Condiţia f) a fost pusă în momentul în care s-a observat că, în condiţiile existenţei soluţiilor degenerate, se poate ajunge în situaţia când, de la o soluţie dată, nu se poate ajunge decât la una la fel de bună şi tot aşa, astfel încât, dacă nu se iau măsuri de evitare, se poate ajunge la o soluţie care a mai fost, fenomen numit ciclare. Astfel de exemple a fost efectiv găsite, unul fiind exemplul lui Beale prezentat mai jos:

Se observă imediat baza admisibilă B₀ = (a₁,a₂,a₃), de la care, aplicând algoritmul sub forma clasică, se vor obţine succesiv bazele admisibile B₁ = (a₄,a₂,a₃), B₂ = (a₄,a₅,a₃), B₃ = (a₆,a₅,a₃), B₄ = (a₆,a₇,a₃), B₅ = (a₆,a₂,a₃), B₆ = (a₄,a₂,a₃) ... . Cititorul poate verifica uşor că toate aceste baze au ca soluţie de bază soluţia (0,0,1,0,0,0,0) şi valoarea funcţiei 0, dar nu îndeplinesc condiţia de optim. Pe de altă parte se vede că B₆ = B₁ şi deci algoritmul va repeta la infinit această succesiune de baze, neatingând niciodată valoarea maximă , corespunzătoare soluţiei (,0,0,1,0,1,0).

Această situaţie este îngrijorătoare nu atât din considerente practice imediate (încă nu a fost găsită o problemă din practică la care să apară acest fenomen, toate exemplele existente fiind artificial construite, ca şi cel de mai sus) cât din faptul că un algoritm implementat pe calculator s-ar putea să fie pus în faţa unei astfel de probleme, situaţie în care n-am putea rezolva problema nici pe calculator, nici manual, ea fiind prea mare. Situaţia a fost depăşită prin diferite tehnici suplimentare adăugate celei de trecere la o soluţie cel puţin la fel de bună (insuficientă, cum s-a văzut), cea mai cunoscută fiind cea care foloseşte ordonarea lexicografică a soluţiilor, care va fi prezentată şi în această carte.

În fine, referitor la condiţia g), a durat mult timp până s-a demonstrat că algoritmul, sub această formă, nu este în timp polinomial, un exemplu fiind clasa de probleme de mai jos, găsită de Klee şi Minty în 1972, în care algoritmul trebuie să analizeze 2ⁿ baze (n = numărul de necunoscute) până la găsirea celei optime.

Pentru o astfel de problemă, la 100 de variabile, algoritmul va avea 2¹⁰⁰ @ 10³⁰ iteraţii, şi chiar la o viteză de un miliard iteraţii pe secundă (mult peste puterea unui calculator actual) va termina în 10¹³ ani.

Nu se ştie încă dacă există sau nu o altă modalitate de trecere de la o bază la alta, folosind tabelele simplex, prin care algoritmul să devină în timp polinomial. Au fost însă găsiţi algoritmi care nu folosesc tabelele simplex, primul fiind algoritmul de punct interior al lui Karmakar, despre care s-a demonstrat că lucrează în timp polinomial.

În ceea ce priveşte erorile de rotunjire, inevitabile când se fac calculele pe un calculator, algoritmul se comportă într-adevăr foarte rău, orice eroare propagându-se imediat la tot tabelul cu efecte foarte mari. Acest lucru poate fi însă depăşit aplicând o variantă a algoritmului, numită varianta revizuită a algoritmului simplex.

Toate punctele slabe ale algoritmului, amintite mai sus, nu au înmormântat însă algoritmul simplex, deoarece folosirea acestuia aduce informaţii mult mai ample decât găsirea soluţiei propriu-zise, este mult mai maleabil în cazul modificărilor ulterioare ale datelor problemei (vezi analiza senzitivităţii soluţiei la datele problemei), se pretează mult mai bine la interpretări economice, este uşor de scris un program de calculator asociat, este implementat pe foarte multe calculatoare şi în plus, aşa cum aminteam mai sus, încă nu a apărut o problemă practică în faţa căruia să clacheze. Noii algoritmi rămân doar ca alternative teoretice sau pentru cazurile în care algoritmul simplex este lent, dar ei nu-l pot înlocui complet.

Fundamentarea matematică a algoritmului simplex

Algoritmul simplex pleacă de la presupunerea că dispunem deja de o soluţie admisibilă de bază x_B, corespunzătoare unei baze B. De asemenea, presupunem că am rezolvat sistemul A×x = b folosind această bază, rezultând astfel variabilele principale în funcţie de cele secundare:

x_B = B^-1×b – B^-1×S×x_S

Înlocuind variabilele, cu formula găsită, în funcţia obiectiv, obţinem:

f(x) = ×(B^-1×b – B^-1×S×x_S) + ×x_S = ×B^-1×b – (×B^-1×S – )×x_S =

= f(x^B) – (×B^-1×S – )×x_S = f(x^B) – (z– )×x_S = f(x^B) – D×x_S

unde:

- f(x^B) = ×B^-1×b este valoarea funcţiei obiectiv în soluţia de bază

- ×B^-1×S = z este un vector n-m componente z = (z_m+1, z_m+2,...,z_n).

- D = z – este un vector n-m componente D = (D_m+1, D_m+2,..., D_n)

Obţinem următoarea formă a problemei:

Din motive de organizare şi concentrare a datelor problemei, Danzig le-a trecut pe acestea într-un tabel ca cel de mai jos, numit tabel simplex.

			c1 c2 ... cm cm+1 ... cn
cB	xB	xB	x1 x2 ... xm xm+1 ... xn
c1 c2 cm	x1 x2 xm	B^-1×b	Im B^-1×S
		f(xB)	0 zm+1 ... zn
			0 Dm+1 ... Dn

Fiecărei soluţii de bază îi corespunde un tabel simplex şi reciproc, deci, de fiecare dată când vom vorbi de un tabel simplex, vom spune şi care este baza asociată.

Din forma funcţiei obiectiv se vede că:

- într-o problemă de maxim:

x^B este soluţie optimă Û oricare ar fi x_S ³ 0 Û

Û ³ 0 oricare ar fi x_S ³ 0 Û D_j ³ 0, j = 1,...,n (toţi D_j sunt pozitivi)

- într-o problemă de minim:

x^B este soluţie optimă Û oricare ar fi x_S ³ 0 Û

Û £ 0 oricare ar fi x_S ³ 0 Û D_j £ 0, j = 1,...,n (toţi D_j negativi)

Pentru a evita complicarea expunerii vom presupune în continuare că problema este de maxim, pentru cazul de minim raţionamentul fiind analog.

Rezultatul obţinut reprezintă criteriul de recunoaştere a optimalităţii soluţiei sau, mai simplu, criteriul de optim.

Dacă soluţia nu este optimă atunci există evident o altă soluţie de bază admisibilă mai bună. Se poate demonstra că dacă x şi y sunt două soluţii admisibile de bază cu f(x) £ f(y) şi numărul de variabile principale prin care diferă cele două este k, cu 1 £ k £ m, atunci există un şir de soluţii admisibile de bază: {x₁ = x, x₂, ..., x_k = y} astfel încât:

1. f(x_i) £ f(x_i+1) oricare ar fi 1 £ i < k

2. x_i diferă de x_i+1 printr-o singură variabilă, oricare ar fi 1 £ i < k

Din cele de mai sus rezultă că e suficient să căutăm o soluţie de bază admisibilă mai bună doar printre cele care diferă de cea actuală printr-o singură variabilă.

Trebuie deci să găsim acea variabilă principală care iese din bază şi acea variabilă secundară care intră în bază. Rezultatul schimbării trebuie să fie:

1. o soluţie de bază (deci coloanele corespunzătoare noii variabile să formeze un minor principal);

2. o soluţie admisibilă (adică să aibă toate componentele pozitive);

3. o soluţie mai bună;

4. cea mai bună posibilă dintre soluţiile mai bune.

Presupunem că înlocuim variabila principală x_i (1£ i £ m) cu variabila secundară x_j (m+1 £ j £ m). Aceasta este echivalent cu a scoate din ecuaţia i (singura în care apare x_i) variabila x_j, în funcţie de variabila x_i şi de celelalte variabile secundare. Este evident că acest lucru (care este echivalent cu faptul că noua soluţie trebuie să fie de bază) este posibil doar dacă coeficientul lui x_j din această ecuaţie este diferit de 0 (a_ij ¹ 0). În acest caz avem succesiv:

x_i + + a_ij×x_j = x_i Û x_j + + ×x_i = ×x_i Û

Û x_j = ×x_i ––×x_i

Înlocuind variabila x_j în celelalte ecuaţii obţinem:

x_s + + a_sj×(×x_i – – ×x_i ) = x_s Û

Û x_s + – ×x_i = x_s – ×x_i pentru s = 1,...,m şi s ¹ i

Conform formulelor de mai sus rezultă că noua soluţie de bază este admisibilă dacă:

x_s – ×x_i ³ 0 oricare ar fi s =1,...,m diferit de i Û ³ oricare ar fi s =1,...,m, s ¹ i

şi în urma schimbării noua soluţie de bază va fi:

= ×x_i şi = x_s – ×x_i pentru s ¹ i

În concluzie, dacă ne hotărâm să introducem în bază variabila j, singura variabilă care o poate înlocui (pentru ca noua soluţie să fie admisibilă de bază) nu poate fi decât aceea care corespunde acelui a_ij strict pozitiv din coloana j din matricea B^-1×S, pentru care se obţine valoarea minimă a rapoartelor dintre componentele soluţiei de bază actuale şi componentele coloanei j. Pentru evidenţierea acestora, ele se notează cu q_s şi avem:

q_i =

Condiţia de mai sus este numită criteriul de ieşire din bază.

Mai înainte am văzut ce efect are schimbarea unei variabile din bază asupra sistemului. Este important însă să vedem efectul ei şi asupra funcţiei obiectiv. Valoarea funcţiei obiectiv în noua soluţie de bază va fi:

f() = =

Pentru ca această soluţie să fie cel puţin la fel de bună trebuie ca:

f() ³ f(x^B) Û ³ f(x^B) Û D_j £ 0

În concluzie, dacă vrem să obţinem o soluţie strict mai bună vom alege o variabilă x_j corespunzătoare unui D_j < 0. Noua soluţie va exista efectiv doar dacă pe coloana j din matricea B^-1×S există o componentă a_ij strict pozitivă şi va fi efectiv strict mai bună doar dacă componenta corespunzătoare x_i din soluţia de bază este diferită de 0, îmbunătăţirea fiind egală cu .

Situaţia în care toate componentele coloanei j din matricea B^-1×S sunt mai mici sau egale cu 0 este lămurit de următoarea teoremă:

Teoremă: Dacă pe coloana j din matricea B^-1×S, corespunzătoare unei variabile x_j cu D_j < 0, toate componentele sunt mai mici sau egale cu zero atunci problema are optim infinit.

Demonstraţie: Fie o soluţie particulară a sistemului, în care variabila secundară x_j = l > 0, l oarecare iar celelalte sunt 0. În acest caz, variabilele principale vor fi: y_li = x_i – a_ij×l şi vor fi toate pozitive, ţinând cont de faptul că toţi a_ij £ 0 şi, deci, soluţia va fi admisibilă. Pentru o astfel de soluţie, valoarea funcţiei obiectiv este:

f(y_l) = f(x^B) – D_j×l. şi avem:

deci imaginea funcţiei f este nemărginită şi afirmaţia este demonstrată.

Presupunem în continuare că există o componentă a_ij strict pozitivă. Deoarece dorim să trecem la cea mai bună dintre bazele posibile, vom alege dintre toate variabilele cu D_j < 0, pe cea pentru care se obţine:

Această condiţie este criteriul de intrare în bază.

Deoarece calculul necesar găsirii acestuia este laborios, Danzig a preferat înlocuirea acestei alegeri cu alegerea acelui j care corespunde celui mai negativ D_j (= –), variantă care este uşor de aplicat, îmbunătăţeşte soluţia şi prin care se obţine, în marea majoritate a cazurilor, acelaşi j.

În acest moment ştim cum să găsim o soluţie mai bună, dacă ea există şi am putea calcula din nou elementele necesare analizării noii soluţii, din tabelul simplex, folosind formulele fiecăruia:

x_B = B^-1×b

z = ×B^-1×A

D = z – c

Acest mod de lucru este efectiv folosit în anumite variante ale algoritmului simplex (vezi forma revizuită) dar el presupune calcularea inversei matricei B, ceea ce necesită foarte mult timp. Acest motiv era suficient de convingător pentru ca Danzig să-şi fi pus problema dacă nu cumva noul tabel simplex poate fi calculat pe baza fostului tabel simplex, făcând mult mai puţine calcule şi utilizând formule uşor de memorat şi aplicat. Această întrebare era natural de pus, dacă ţinem cont că noua soluţie diferă de fosta soluţie printr-o singură variabilă. Aceste formule au fost efectiv găsite, ele putând fi obţinute urmărind efectul înlocuirii lui x_i cu x_j asupra sistemului:

- noua soluţie de bază se obţine din fosta soluţie cu formulele deja găsite mai sus:

= ×x_i şi

= x_s – ×x_i pentru s ¹ i

- noii coeficienţii ai variabilelor în cele m ecuaţii vor fi:

1. variabilă principală x_s va avea coeficientul 1 în ecuaţia k şi 0 în celelalte ecuaţii;

2. o variabilă secundară x_k, diferită de x_i, va avea coeficienţii în ecuaţiile s ¹ i şi coeficientul în ecuaţia i.

3. noua variabilă secundară x_i va avea coeficienţii în ecuaţiile s ¹ i şi coeficientul în ecuaţia i.

4. noua valoare a funcţiei obiectiv va fi: f() =

1. noii D_j îi obţinem înlocuind în funcţia obiectiv variabila x_j în funcţie de x_i:

f(x) = f() – – D_j×(– – ×x_i + ×x_i) =

= – –×x_i =

= f() – –×x_i

de unde rezultă că pentru k ¹ i şi

Deşi par să fie foarte multe formule complicate, frumuseţea algoritmului şi meritul lui Danzig constă tocmai în faptul că toate respectă o regulă vizuală uşor de memorat, numită regula dreptunghiului, aşa cum se va vedea în algoritmul simplex.

ALGORITMUL SIMPLEX

Reamintim că presupunem că problema este la forma standard de maxim şi că dispunem de o soluţie de bază admisibilă.

Pasul 1. Se construieşte tabelul simplex corespunzător bazei de care dispunem în ordinea următoare:

1. pe linia a doua se trec toate variabilele într-o ordine oarecare;

2. pe prima linie se trec coeficienţii funcţiei obiectiv, fiecare deasupra variabilei corespunzătoare;

3. se construieşte matricea A, fiecare coloană fiind formată din coeficienţii unei variabile din toate ecuaţiile (ordinea în care se parcurg ecuaţiile trebuie să fie aceeaşi pentru toate variabilele), având grijă ca, coloanele să fie trecute în ordinea în care au fost trecute variabilele pe linia 2;

4. se construieşte baza B, ordinea coloanelor fiind cea în care apar ele în matricea A;

5. se calculează B^-1;

6. se calculează B^-1×A şi se trece în partea centrală a tabelului;

7. se trec variabilele principale în a doua coloană, în aşa fel încât, la intersecţia liniei şi coloanei corespunzătoare acestei variabile, să se afle valoarea 1.

8. se trec în prima coloană coeficienţii corespunzători variabilelor principale din funcţia obiectiv, fiecare în dreptul variabilei corespunzătoare;

9. se calculează soluţia de bază cu formula B^-1×b, având grijă ca ordinea în care au fost trecuţi termenii liberi în vectorul b să fie aceeaşi cu ordinea în care au fost parcurse ecuaţiile la formarea matricii A;

10. se trec în a treia coloană valorile variabilelor principale din soluţia de bază, fiecare în dreptul variabilei corespunzătoare;

11. se calculează f(x_B) înmulţind două câte două componentele coloanei 1 cu cele din coloana 3 aflate pe aceeaşi linie şi adunând toate produsele între ele (adică facem produsul scalar dintre c_B şi x_B);

12. se calculează pe rând fiecare z_j j = 1,...,n un z_j obţinându-se înmulţind scalar c_B cu coloana j din B^-1×A aflată în centrul tabelului (această linie se calculează şi se trece doar în primul tabel, scopul ei fiind calcularea lui D);

13. se calculează pe rând fiecare D_j j = 1,...,n scăzând din linia lui z linia lui c (D_j = z_j - c_j)

Pasul 2. Se analizează valorile D_j corespunzătoare variabilelor secundare (e uşor de văzut că întotdeauna, cei corespunzători variabilelor principale sunt toţi 0, deci neinteresanţi).

- dacă toţi sunt mai mari sau egali cu 0 atunci soluţia actuală este cea optimă. Dacă există D_j = 0 în afara bazei, atunci pot apărea două cazuri:

1) toate elementele din coloana a_j din B^-1×A sunt mai mici sau egale cu 0. Atunci toate soluţiile de forma x_B - a_j×l sunt soluţii optime, unde l > 0 oarecare;

2) există o componentă a_ij a coloanei a_j strict pozitivă. Atunci introducând variabila x_j în bază în locul variabilei principală x_i obţinem altă soluţie de bază optimă.

Dacă apar numai cazuri de tipul 2), obţinem toate soluţiile de bază optime, mulţimea tuturor soluţiilor optime fiind formată din toate combinaţiile convexe ale acestora. Dacă apare şi cazul 1) atunci mulţimea soluţiilor optime este nemărginită fiind formată din combinaţiile convexe ale soluţiilor de forma x_B - a_j×l unde x_B sunt toate soluţiile optime de bază.

- dacă există D_j < 0 atunci îl alegem pe cel mai negativ: D_k = . Variabila x_j va fi cea care intră în noua bază. Dacă minimul este multiplu atunci alegem, la întâmplare, unul dintre aceştia (cei minimi).

Pasul 3. Se analizează elementele coloanei a_j din B^-1×A, corespunzătoare variabilei alese la pasul 2.

- Dacă toate sunt mai mici sau egale cu 0 atunci problema are optim infinit şi algoritmul ia sfârşit;

- Dacă există componente strict pozitive, pentru acestea se calculează rapoartele q_s = . Variabila x_i corespunzătoare raportului minim este cea care va ieşi din bază. Dacă acest minim este multiplu sunt posibile două cazuri:

1) minimul este strict pozitiv. În acest caz se alege unul dintre aceştia la întâmplare;

2) minimul este 0. Atunci x_i corespunzători sunt 0, deci soluţia este degenerată şi noua soluţie este la fel de bună. Această situaţie poate duce la ciclarea algoritmului şi alegerea la întâmplare nu mai este suficientă, fiind nevoie de o regulă de alegere suplimentară care să evite ciclarea. O metodă de alegere se bazează pe faptul că, aşa cum vom vedea, întotdeauna prima bază este matricea unitate şi în dreptul ei, în toate tabelele simplex, se va afla inversa bazei corespunzător fiecăruia. În acest caz, pentru poziţiile în care s-a obţinut minimul împărţim prima coloană a lui B^-1 la coloana a_j şi alegem minimul dintre aceste rapoarte. Dacă minimul dintre aceştia este tot multiplu continuăm procedeul, pentru poziţiile ce dau noul minim, cu coloana a doua din B^-1 şi aşa mai departe, până minimul rămâne unic. Nu este posibil să se epuizeze toate coloanele lui B^-1 şi minimul să rămână multiplu, deoarece, în acest caz, am avea: , pentru toţi indicii j_k ai coloanelor lui B^-1, i₁ şi i₂ fiind doi din indicii care dau acelaşi minim până la sfârşit sau altfel scris pentru orice j_k Þ liniile i₁ şi i₂ din B^-1 sunt proporţionale, fapt ce contrazice faptul că B^-1 este inversabilă.

Pasul 4. Se calculează componentele tabelului simplex corespunzător noii baze pe baza tabelului actual şi folosind următoarele reguli:

1. se încadrează elementul a_ij, aflat la intersecţia coloanei variabilei care intră în bază cu linia variabilei care iese din bază, care a fost numit de Danzig pivot, într-un dreptunghi

2. coloana pivotului va avea 1 în dreptul pivotului şi 0 în rest (inclusiv D_j);

3. linia pivotului este linia actuală împărţită la pivot (inclusiv în soluţia de bază);

4. restul elementelor se calculează cu regula dreptunghiului (inclusiv soluţia de bază, D şi f(x_B)). Regula dreptunghiului se bazează pe observaţia că în toate formulele prin care se calculează acestea nu apare decât valoarea lor actuală, pivotul şi cele două elemente care ar completa dreptunghiul ce are poziţia de calculat şi pivotul pe diagonală. Regula dreptunghiului se enunţă literar astfel: "noua valoare = produsul dintre elementele de pe diagonala pivotului minus produsul dintre cele aflate pe cealaltă diagonală totul împărţit la pivot". (pentru scurtarea timpului de lucru se poate observa că elementele unei linii care are 0 pe coloana pivotului rămân aceleaşi şi de asemenea elementele unei coloane care are 0 pe linia pivotului)

Operaţia de calculare a noului tabel prin regulile de mai sus poartă denumirea de pivotare.

Pasul 5. Se reia algoritmul de la pasul 2.

Exemplu: Fie problema de programare liniară:

pentru care ştim că baza formată din coloanele a₁, a₂, a₃ este admisibilă. Pentru rezolvare vom aduce problema la forma standard de maxim introducând variabilele de abatere x₇, x₈, x₉ obţinând:

Vom aşeza în tabelul simplex variabilele în ordinea indicilor şi vom avea:

c = , A = , B = , c_B =

vom calcula matricea B^-1 = şi pe baza acesteia soluţia de bază x_B = B^-1×b = şi matricea B^-1×A = care se trec în tabelul simplex:

			3 2 1 4 3 5 0 0 0
cB	xB	xB	x1 x2 x3 x4 x5 x6 x7 x8 x9
3 2 1	x1 x2 x3	1 2 3

şi în final se vor calcula valoarea funcţiei obiectiv în această soluţie, z_j şi D_j:

			3 2 1 4 3 5 0 0 0
cB	xB	xB	x1 x2 x3 x4 x5 x6 x7 x8 x9
3 2 1	x1 x2 x3	1 2 3
		10

Din tabel se observă că există D_j < 0, aceştia fiind D₄, D₅, D₆, D₈ iar minimul lor este D₆.

Observaţie Dacă vom căuta acel D_j care dă cea mai bună îmbunătăţire vom avea de găsit acel D_j dintre cei negativi pentru care se obţine şi deci de calculat:

= =

= =

= =

= =

şi în final max (,,,) = şi corespunde tot lui D₆.

În concluzie, soluţia actuală nu este optimă şi soluţia cea mai bună dintre cele posibile ca succesoare va avea variabila x₆ printre cele principale.

Analizând coloana a₆ observăm că există componente strict pozitive (de fapt, în acest caz sunt chiar toate) şi calculăm pentru acestea rapoartele q_i obţinând:

q₁ = = , q₂ = = 14, q₃ = =

deci minimul corespunde variabilei x₁ şi aceasta este cea care va ieşi din bază. În cest moment cunoaştem noua bază şi vom construi tabelul simplex pe baza regulilor de calcul de la pasul 4:

1. pivotul este a₁₆ =

4. de exemplu, pentru elementul de pe poziţia a₃₄ avem dreptunghiul:

şi noua valoare de pe această poziţie va fi: = –1

În final, tabelul corespunzător noii baze va fi:

			3 2 1 4 3 5 0 0 0
cB	xB	xB	x1 x2 x3 x4 x5 x6 x7 x8 x9
5 2 1	x6 x2 x3

Continuând algoritmul vom găsi tabelele:

			3 2 1 4 3 5 0 0 0
cB	xB	xB	x1 x2 x3 x4 x5 x6 x7 x8 x9
5 2 0	x6 x2 x8

			3 2 1 4 3 5 0 0 0
cB	xB	xB	x1 x2 x3 x4 x5 x6 x7 x8 x9
5 3 0	x6 x5 x8	5 1 2
		28

Ultimul tabel conţine soluţia optimă, deoarece toţi D_j ³ 0. Deoarece nu mai există nici un D_j = 0 în afara celor din bază rezultă că soluţia optimă este unică.

Determinarea unei soluţii de bază admisibile de start

Presupunem încă odată că problema este la forma standard.

Algoritmul simplex necesită, pentru pornire, o soluţie admisibilă de bază. Găsirea acesteia pur şi simplu prin încercări nu este deloc o sarcină uşoară, gândindu-ne că aceasta presupune găsirea unui minor principal, inversarea acestuia şi calcularea soluţiei, abia în acest moment putând vedea dacă aceasta are toate componentele pozitive, această căutare putând dura foarte mult.

Rezolvarea problemei pleacă de la observaţia că singura bază pentru care calculul de mai sus se poate face imediat este matricea unitate, caz în care soluţia de bază corespunzătoare este chiar vectorul termenilor liberi. Aceasta presupune ca problema să aibă toţi termenii liberi mai mari sau egali cu 0 şi în matricea A să existe toate coloanele matricii unitate.

Dacă toţi termenii liberi pot fi făcuţi mai mari sau egali cu 0 foarte simplu, prin înmulţirea eventual cu –1 a restricţiei respective, existenţa tuturor coloanelor matricii unitate este evident că este foarte puţin probabilă şi mai greu de obţinut.

În acest sens plecăm de la observaţia că existenţa unui vector din coloana unitate printre coloanele matricii A este echivalentă cu existenţa unei variabile care apare doar în ecuaţia corespunzătoare lui 1 din acel vector, cu coeficientul 1. Acest lucru poate fi obţinut în două moduri:

a) Începând de la prima ecuaţie, căutăm o variabilă care are coeficientul de acelaşi semn cu termenul liber, o scoatem din această ecuaţie în funcţie de celelalte variabile, o înlocuim în celelalte şi repetăm procedeul pornind de la a doua ecuaţie. Pot apărea trei cazuri:

1) la un moment dat obţinem o ecuaţie în care toţi coeficienţii variabilelor au semn contrar termenului liber, măcar unul dintre toţi fiind diferit de 0. În acest caz ecuaţia nu are evident soluţie admisibilă(pozitivă) şi deci problema nu are soluţie;

2) toţi coeficienţii variabilelor şi termenul liber sunt 0. În acest caz rezultă că această ecuaţie rezultă din cele anterioare şi ea va fi eliminată, trecându-se la următoarea;

3) se epuizează toate ecuaţiile. În acest moment, variabilele care au fost scoase din fiecare ecuaţie formează baza dorită.

Procedeul de mai sus poate părea atractiv, dar presupune introducerea unui algoritm diferit de simplex, cu efect asupra omogenităţii calculelor şi a vitezei de lucru. De asemenea, prin efectuarea calculelor de mai sus, datele problemei nu mai au semnificaţia economică iniţială, ne mai putându-se face interpretări economice.

b) Pentru toţi vectorii coloană introducem în ecuaţiile corespunzătoare câte o variabilă cu coeficientul 1. Vom obţine evident un nou sistem de restricţii şi rămâne de văzut ce legătură este între soluţiile acestuia şi cel iniţial. Cele două sisteme au forma:

A×x = b şi A×x + y = b

Este evident că o soluţie a primului sistem este soluţie şi a celui de-al doilea (luăm y = 0) iar o soluţie a celui de-al doilea este soluţie şi pentru primul doar dacă y = 0. Scopul nostru va fi deci, ca pornind de la soluţia iniţială a celei de-a doua probleme să ajungem la o soluţie a acesteia în care y = 0. Ţinând cont că în soluţiile de bază, variabilele secundare sunt toate egale cu 0, vom încerca să scoatem din bază variabilele y. Scopul algoritmului simplex este însă maximizarea funcţiei obiectiv, nu scoaterea a uneia sau alteia din variabile din bază. Pentru a echivala cele două scopuri putem proceda în două feluri:

1) Alegem o nouă funcţie obiectiv care să-şi atingă extremul printre soluţiile pozitive chiar pentru y = 0 şi în momentul când am obţinut soluţia respectivă pornim cu aceasta ca soluţie iniţială algoritmul simplex pentru fosta problemă.

2) Adăugăm la fosta funcţie obiectiv noile variabile cu nişte coeficienţi de asemenea natură aleşi încât aportul variabilelor y la valoarea funcţiei să fie contrar scopului dorit (foarte mari pozitivi într-o problemă de minim şi foarte mari negativi într-o problemă de maxim).

Vom detalia în continuare cele două metode:

Algoritmul simplex în două faze

Dată problema de programare liniară la forma standard de maxim:

în care am aranjat deja ca toţi termenii liberi să fie pozitivi (b ³ 0).

Faza 1 Construim problema:

pe care o rezolvăm cu algoritmul simplex pornind rezolvarea de la baza matrice unitate, putând ajunge la două situaţii:

1) minimul funcţiei g este strict pozitiv. Aceasta este echivalent cu faptul că egalitatea Ax + y = b se poate obţine doar pentru y > 0 sau altfel spus Ax > b pentru orice x ³ 0, deci sistemul Ax = b nu are soluţii admisibile şi în concluzie problema iniţială nu are soluţie.

2) minimul funcţiei g este 0. În acest caz, soluţia optimă obţinută are y = 0, deci verifică Ax = b fiind în concluzie o soluţie admisibilă de bază a primei probleme.

Faza 2 Începând de la soluţia găsită la faza 1 se rezolvă problema iniţială cu algoritmul simplex.

Dezavantajul metodei constă în faptul că tabelul simplex final de la faza 1 trebuie modificat pentru a obţine tabelul simplex iniţial de la faza 2 (vectorii x, c, c_B, z, D, f(x_B), se elimină coloanele corespunzătoare lui y) şi în plus nu vom mai avea în tabelele simplex ale problemei iniţiale inversa bazei (care se găsea în dreptul coloanelor matricii unitate din prima fază) necesară în anumite variante ale algoritmului simplex.

Metoda bazei artificiale (metoda penalizării)

Dată problema de programare liniară la forma standard de maxim:

în care am aranjat deja ca toţi termenii liberi să fie pozitivi (b ³ 0).

Construim problema:

în care M este o constantă presupusă foarte mare (mai mare decât orice constantă care ar putea apare în rezolvarea problemei). Rezolvăm problema cu algoritmul simplex pornind rezolvarea de la baza matrice unitate, putând ajunge la trei situaţii:

1) problema are optim infinit. În acest caz, problema iniţială are optim infinit.

2) problema are optim finit şi în soluţia de bază avem cel puţin o variabilă din vectorul y. În acest caz problema iniţială nu are soluţii admisibile.

3) problema are optim finit şi în soluţia de bază nu avem nici o variabilă din vectorul y. În acest caz problema iniţială are optim finit, soluţia optimă şi maximul funcţiei fiind aceleaşi cu cele ale problemei modificate.

În final vom remarca faptul că variabilele y nu corespund unor mărimi economice ca celelalte, ele fiind introduse doar ca un artificiu de calcul pentru a putea porni algoritmul simplex. Din acest motiv ele se numesc variabile artificiale.

Exemplu Fie problema de programare liniară:

Forma standard a problemei va fi:

Avem deja termenii liberi şi o coloană a matricii unitate corespunzătoare variabilei x₃. Pentru a obţine şi a doua coloană vom introduce variabila x₅ cu coeficientul 1 în a doua ecuaţie şi în final vom avea de rezolvat problema:

Algoritmul simplex în două faze	Metoda bazei artificiale

Aplicând algoritmul simplex în două faze vom obţine în prima fază succesiunea de tabele:

			0	0	0	0	1
cB	xB	xB	x1	x2	x3	x4	x5
0	x3	10	3	1	1	0	0
1	x5	2	1	4	0	-1	1
		2	1	4	0	-1	1
			1	4	0	-1	0

			0	0	0	0	1
cB	xB	xB	x1	x2	x3	x4	x5
0	x3			0	1
0	x2			1	0
		0	0	0	0	0	-1

Am obţinut optimul egal cu 0 în soluţia de bază (x₃,x₂) care va fi soluţia iniţială pentru algoritmul simplex aplicat problemei iniţiale în a doua fază. Eliminăm din tabel coloana lui x₅, înlocuim valorile coeficienţilor funcţiei obiectiv şi deci şi valoarea acesteia, valorile D şi obţinem tabelul:

			2	3	0	0
cB	xB	xB	x1	x2	x3	x4
0	x3			0	1
3	x2			1	0
				0	0

			2	3	0	0
cB	xB	xB	x1	x2	x3	x4
0	x3	4	0	-11	1	3
2	x1	2	1	4	0	-1
		4	0	5	0	-2

			2	3	0	0
cB	xB	xB	x1	x2	x3	x4
0	x4		0			1
2	x1		1			0
			0			0

			2	3	0	0
cB	xB	xB	x1	x2	x3	x4
0	x4	38	11	0	4	1
3	x2	10	3	1	1	0
		30	7	0	3	0

Soluţia optimă a primei probleme este deci x₁ = 0 şi x₂ = 10 care dă un maxim al funcţiei egal cu 30. Dacă aplicăm a doua metodă vom obţine succesiv tabele:

			2	3	0	0	-M
cB	xB	xB	x1	x2	x3	x4	x5
0	x3	10	3	1	1	0	0
-M	x5	2	1	4	0	-1	1
		-2M	-M	-4M	0	M	-M
			-M-2	-4M-3	0	M	0

			2	3	0	0	-M
cB	xB	xB	x1	x2	x3	x4	x5
0	x3			0	1
3	x2			1	0
				0	0		M+

			2	3	0	0	-M
cB	xB	xB	x1	x2	x3	x4	x5
0	x3	4	0	-11	1	3	-3
2	x1	2	1	4	0	-1	1
		4	0	5	0	-2	2+M

			2	3	0	0	-M
cB	xB	xB	x1	x2	x3	x4	x5
0	x4		0			1	-1
2	x1		1			0	0
			0			0	M

			2	3	0	0	-M
cB	xB	xB	x1	x2	x3	x4	x5
0	x4	38	11	0	4	1	-1
3	x2	10	3	1	1	0	0
		30	7	0	3	0	M

Rezultatul final este evident acelaşi.

VARIANTE ALE ALGORITMULUI SIMPLEX

1. Algoritmul simplex dual

Pentru expunerea acestui algoritm trebuie introduse noţiunile de bază dual admisibilă şi soluţie dual admisibilă de bază. Prin definiţie numim:

soluţie de bază dual admisibilă	=	soluţie de bază pentru care toţi Dj ³ 0
bază dual admisibilă	=	bază corespunzătoare unei soluţii de bază dual admisibile

Ca şi în cazul algoritmului simplex, pentru a putea rezolva problema cu algoritmul simplex dual trebuie să dispunem deja de o bază iniţială dual admisibilă. Această soluţie poate exista ca urmare a unor calcule anterioare (vezi capitolul cu reoptimizarea) sau, ca şi în cazul algoritmului simplex, poate fi aplicată o procedură prin care să găsim această bază. Prezentarea acesteia este mai complicată decât cea de la algoritmul simplex astfel încât:

- dacă dispunem de o bază dual admisibilă vom rezolva problema cu algoritmul simplex dual

- dacă nu dispunem de o bază dual admisibilă vom rezolva problema cu algoritmul simplex.

Pentru a evita orice confuzie, vom numi în continuare algoritmul simplex obişnuit algoritm simplex primal şi o bază admisibilă bază primal admisibilă.

Se observă că o soluţie dual admisibilă nu este în general primal admisibilă şi reciproc, iar o soluţie care este simultan primal şi dual admisibilă este o soluţie optimă şi reciproc.

Presupunem că am adus problema la forma standard de maxim şi dispunem de o bază dual admisibilă şi dispunem deja de de o bază dual admisibilă. Algoritmul simplex dual constă în următorii paşi:

Pasul 1. Se construieşte tabelul simplex asociat acestei baze, la fel ca şi la algoritmul simplex primal;

Pasul 2. Se analizează componentele soluţiei:

- Dacă toate componentele sunt mai mari sau egale cu 0 atunci soluţia este şi primal admisibilă, deci optimă.

- Dacă există componente strict negative, variabila corespunzătoare celei mai negative (x_i = ) este cea care iese din bază. Dacă minimul este multiplu se ia una la întâmplare.

Pasul 3. Se analizează linia l_i corespunzătoare variabilei x_i aleasă la pasul 2:

- Dacă toate componentele a_ij j = 1,...,n sunt mai mari sau egale cu 0, atunci am avea o ecuaţie cu toţi coeficienţii necunoscutelor pozitivi şi termenul liber strict negativ, deci problema nu are soluţii primal admisibile.

- Dacă există componente strict negative, atunci pentru acestea se găseşte acel indice pentru care se obţine (prin am notat modulul numărului a). Dacă minimul este multiplu alegem unul dintre aceştia la întâmplare. Variabila corespunzătoare acestuia este cea care intră în bază.

Pasul 4. Se construieşte tabelul corespunzător noii baze aplicând aceleaşi reguli ca la algoritmul simplex primal;

Pasul 5. Se reia algoritmul de la pasul 2

2. Forma secundară

Este evident că modul de organizare al datelor în tabelul simplex nu este unicul mod de a organiza datele într-un tabel. Forma secundară este tocmai o astfel de alternativă. Presupunem şi în acest caz că problema este la forma standard de maxim, că problema este la forma standard şi că dispunem de o soluţie iniţială de bază care este primal sau dual admisibilă.

Pasul 1. Datele problemei vor fi organizate într-un tabel de forma:

			cS
c	x	f	xS
		f(xB)	DS
cB	xB	xB = B^-1×b	B^-1×S
cS	xS	0	–In-m

Se observă că singura diferenţa este că la coloana variabilelor bazei din stânga se adaugă şi cele secundare, pe orizontală se lasă doar variabilele secundare iar în loc de matricea unitate în dreptul variabilelor principale vom avea matricea unitate în dreptul celor secundare (dar cu minus), D fiind calculat la fel, neglijându-se cei din dreptul variabilelor principale, care oricum erau 0.

Pasul 2. + Pasul 3. Se găsesc variabila care iese din bază şi cea care intră în bază cu aceleaşi reguli ca la algoritmul simplex primal sau, după caz, ca la cel dual.

Pasul 4. Se construieşte tabelul asociat noii baze aplicând regulile:

1) Pivotul este acelaşi ca la tabelul simplex;

2) Linia pivotului are –1 în dreptul pivotului şi 0 în rest;

3) Coloana pivotului se împarte la pivotul cu semn schimbat

4) Celelalte elemente se calculează cu regula dreptunghiului

Pasul 5. Se reia algoritmul de la pasul 2.

Exemplu Fie problema de programare liniară rezolvată mai sus:

Forma standard a problemei va fi:

iar după introducerea variabilelor artificiale obţinem:

Tabelul corespunzător va fi:

			2	3	0
cB	xB	xB	x1	x2	x4
		-2M	-M-2	-4M-3	M
2	x1	0	-1	0	0
3	x2	0	0	-1	0
0	x3	10	3	1	0
0	x4	0	0	0	-1
-M	x5	2	1	4	-1

Aplicăm simplex primal şi obţinem cel mai negativ D_j corespunzător lui x₂ şi q_i minim corespunzător lui x₅. În acest moment avem o soluţie de bază a problemei iniţiale şi putem elimina variabila x₅. Obţinem:

			2	-M	0					2	0
cB	xB	xB	x1	x5	x4		cB	xB	xB	x1	x4
				M+¾	-¾						-¾
2	x1	0	-1	0	0		2	x1	0	-1	0
3	x2	½	¼	¼	-¼	Û	3	x2	½	¼	-¼
0	x3			-¼	¼		0	x3			¼
0	x4	0	0	0	-1		0	x4	0	0	-1
-M	x5	0	0	-1	0

şi în continuare:

			3	0					3	0
cB	xB	xB	x2	x4		cB	xB	xB	x2	x3
		4	5	-2
2	x1	2	4	-1		2	x1
3	x2	0	-1	0	®	3	x2	0	-1	0
0	x3	4	-11	3		0	x3	0	0	-1
0	x4	0	0	-1		0	x4

				2	0
	cB	xB	xB	x1	x3
			30	7	3
®	2	x1	0	-1	0
	3	x2	10	3	1
	0	x3	0	0	-1
	0	x4	38	11	4

Din rezolvarea de mai sus se observă că această metodă este mai eficientă doar dacă numărul variabilelor secundare este mai mic decât numărul variabilelor principale. Totuşi, motivul principal pentru care a fost introdusă această variantă, este existenţa unor probleme în care, pe parcursul rezolvării, se adaugă foarte multe restricţii (de exemplu rezolvarea problemelor în numere întregi), pentru o restricţie în plus tabelul simplex mărindu-se cu o linie şi o coloană (cum se va vedea la capitolul de reoptimizare) iar tabelul corespunzător formei secundare doar cu o linie.

3. Forma revizuită a algoritmului simplex

O problemă mare (de exemplu cu 1000 variabile şi 100 restricţii) necesită în algoritmul simplex introducerea, memorarea şi lucrul cu un tabel cu 100.000 componente, adică un număr imens de date. Din acest motiv, şi remarcând faptul că în algoritmul simplex doar o parte din acestea contribuie efectiv la luarea deciziilor, s-a construit un algoritm care să ţină cont de observaţiile de mai sus, numit "forma revizuită a algoritmului simplex", în care se lucrează cu minimul necesar din datele tabelului simplex. Astfel, pentru testarea soluţiei actuale şi trecerea eventuală la o nouă bază avem nevoie doar de următoarele elemente:

(1) inversa bazei curente B^-1

(2) componentele vectorului D pentru a face testul de optim şi a găsi variabila care intră în bază (dacă soluţia nu e optimă)

(3) coloana a_k din B^-1A corespunzătoare celui mai negativ D_j (dacă există strict negativi) pentru a face testul de optim infinit

(4) soluţia curentă pentru a găsi variabila care iese din bază (dacă mai e cazul)

Aceste elemente se aşează într-un tabel de forma:

cB	xB	xB = B^-1b	B^-1
		f(xB)	π = ×B^-1

numit tabelul simplex redus.

Operaţiile ce se efectuează în cadrul algoritmului simplex revizuit sunt (presupunem că problema este la forma standard de maxim şi deţinem o soluţie admisibilă de bază şi inversa bazei corespunzătoare):

Pasul 1. Se calculează D_j corespunzători variabilelor secundare cu formula cunoscută:

D_j = ×B^-1×P_j - c_j = π×P_j - c_j

unde P_j este coloana corespunzătoare variabilei x_j din matricea iniţială.

Pasul 2. Se analizează D_j calculaţi:

- dacă toţi sunt mai mari sau egali cu 0 soluţia curentă este optimă. STOP

- dacă există D_j strict negativi se alege minimul dintre aceştia D_k, variabila x_k va intra în bază şi se trece la pasul 3.

Pasul 3. Se calculează a_k = B^-1P_k care se ataşează ca nouă coloană la tabel:

cB	xB	xB = B^-1b	B^-1	ak = B^-1Pk
		f(xB)	π = ×B^-1	Dk

Pasul 4. Se analizează componentele coloanei a_k:

- dacă toate sunt mai mici sau egale cu 0 problema are optim infinit. STOP

- dacă există a_ik strict pozitivi se alege cel pentru care se obţine:

a_rk =

şi variabila x_r va ieşi din bază apoi se trece la pasul 5.

Pasul 5. Se pivotează întregul tabel simplex şi se elimină ultima coloană.

Pasul 6. Se reia algoritmul de la pasul 2.

Exemplu Fie problema de programare liniară rezolvată mai sus:

Forma standard a problemei va fi:

iar după introducerea variabilelor artificiale obţinem:

Iteraţia 1. Prima bază este B = I₂ = B^-1 corespunzătoare variabilelor x₃ şi x₅ de unde rezultă x_B = şi π = (0,-M)×I₂ = (0,-M). Primul tabel redus va fi:

0 -M	x3 x5	10 2	1 0	0 1
		-2M	0	-M

Se calculează D_S = π×S – c_S = (0,-M)× – = de unde rezultă că cel mai negativ este D₂ şi vom calcula coloana a₂ = I₂× = care se adaugă la tabelul anterior rezultând:

0 -M	x3 x5	10 2	1 0	0 1	1 4
		-2M	0	-M	-4M-3

q_i minim este cel corespunzător lui x₅ şi deci variabila x₂ va intra în locul variabilei x₅.

După pivotare şi eliminarea ultimei coloane obţinem:

0 3	x3 x2	½	1 0	-¼ ¼
			0	¾

Deoarece variabila artificială x₅ a ieşit din bază ea va fi eliminată din problemă.

Iteraţia 2. D_S = π×S – c_S = (0,¾)× – = ()

cel mai negativ este D₁ şi vom calcula coloana a₁ = × = care se adaugă la tabelul anterior rezultând:

0 3	x3 x2	½	1 0	-¼ ¼	¼
			0	¾

q_i minim este cel corespunzător lui x₂ şi deci variabila x₁ va intra în locul variabilei x₂.

După pivotare şi eliminarea ultimei coloane obţinem:

0 2	x3 x1	4 2	1 0	-3 1
		4	0	2

Iteraţia 3. D_S = π×S – c_S = (0,2)× – = ()

cel mai negativ este D₄ şi vom calcula coloana a₄ = × = care se adaugă la tabelul anterior rezultând:

0 2	x3 x1	4 2	1 0	-3 1	3 -1
		4	0	2	-2

q_i minim este cel corespunzător lui x₃ şi deci variabila x₄ va intra în locul variabilei x₃.

După pivotare şi eliminarea ultimei coloane obţinem:

0 2	x4 x1			-1 0
				0

Iteraţia 4. D_S = π×S – c_S = (,0)× – = ()

cel mai negativ este D₂ şi vom calcula coloana a₂ = × = care se adaugă la tabelul anterior rezultând:

0 2	x4 x1			-1 0
				0

q_i minim este cel corespunzător lui x₁ şi deci variabila x₂ va intra în locul variabilei x₁.

După pivotare şi eliminarea ultimei coloane obţinem:

0 3	x4 x2	38 10	4 1	-1 0
		30	3	0

Iteraţia 5. D_S = π×S – c_S = (3,0)× – = () >0 deci soluţia este optimă (şi unică) STOP

Chiar dacă la prima vedere calculele par mai împrăştiate şi deci mai lente, pentru probleme mari, pe calculator se economiseşte foarte multă memorie şi se măreşte foarte mult viteza de calcul.

Totuşi, marele avantaj al acestei metode este acela că, la fiecare iteraţie, se folosesc datele problemei iniţiale, ceea ce face ca erorile inerente de rotunjire să nu se propage, rămânând în limite acceptabile.

---

(*) De aici rezultă posibilitatea să calculăm coeficienţii a_ij pe baza informaţiilor disponibile privind cantităţile consumate R_ij şi nivelul x_j: a_ij = ; i = 1,...,m; j = 1,...,n