ALGORITMUL SIMPLEX

ALGORITMUL  SIMPLEX

Reamintim ca presupunem ca problema este la forma standard de maxim si ca dispunem de o solutie de baza admisibila.

Pasul 1. Se construieste tabelul simplex corespunzator bazei de care dispunem in ordinea urmatoare:

pe linia a doua se trec toate variabilele intr-o ordine oarecare;

pe prima linie se trec coeficientii functiei obiectiv, fiecare deasupra variabilei corespunzatoare;

se construieste matricea A, fiecare coloana fiind formata din coeficientii unei variabile din toate ecuatiile (ordinea in care se parcurg ecuatiile trebuie sa fie aceeasi pentru toate variabilele), avand grija ca, coloanele sa fie trecute in ordinea in care au fost trecute variabilele pe linia 2;

se construieste baza B, ordinea coloanelor fiind cea in care apar ele in matricea A;

se calculeaza B^-1;

se calculeaza B^-1 A si se trece in partea centrala a tabelului;

se trec variabilele principale in a doua coloana, in asa fel incat, la intersectia liniei si coloanei corespunzatoare acestei variabile, sa se afle valoarea 1.

se trec in prima coloana coeficientii corespunzatori variabilelor principale din functia obiectiv, fiecare in dreptul variabilei corespunzatoare;

se calculeaza solutia de baza cu formula B^-1 b, avand grija ca ordinea in care au fost trecuti termenii liberi in vectorul b sa fie aceeasi cu ordinea in care au fost parcurse ecuatiile la formarea matricii A;

se trec in a treia coloana valorile variabilelor principale din solutia de baza, fiecare in dreptul variabilei corespunzatoare;

se calculeaza f(x_B) inmultind doua cate doua componentele coloanei 1 cu cele din coloana 3 aflate pe aceeasi linie si adunand toate produsele intre ele (adica facem produsul scalar dintre c_B si x_B);

se calculeaza pe rand fiecare z_j j = 1,,n un z_j obtinandu-se inmultind scalar c_B cu coloana j din B^-1 A aflata in centrul tabelului (aceasta linie se calculeaza si se trece doar in primul tabel, scopul ei fiind calcularea lui D

se calculeaza pe rand fiecare D_j j = 1,,n scazand din linia lui z linia lui c (D_j = z_j - c_j)

Pasul 2. Se analizeaza valorile D_j corespunzatoare variabilelor secundare (e usor de vazut ca intotdeauna, cei corespunzatori variabilelor principale sunt toti 0, deci neinteresanti).

daca toti sunt mai mari sau egali cu 0 atunci solutia actuala este cea optima. Daca exista D_j = 0 in afara bazei, atunci pot aparea doua cazuri:

toate elementele din coloana a_j din B^-1 A sunt mai mici sau egale cu 0. Atunci toate solutiile de forma x_B - a_jl sunt solutii optime, unde l > 0 oarecare;

exista o componenta a_ij a coloanei a_j strict pozitiva. Atunci introducand variabila x_j in baza in locul variabilei principala x_i obtinem alta solutie de baza optima.

Daca apar numai cazuri de tipul 2), obtinem toate solutiile de baza optime, multimea tuturor solutiilor optime fiind formata din toate combinatiile convexe ale acestora. Daca apare si cazul 1) atunci multimea solutiilor optime este nemarginita fiind formata din combinatiile convexe ale solutiilor de forma  x_B - a_jl unde x_B sunt toate solutiile optime de baza.

daca exista D_j < 0 atunci il alegem pe cel mai negativ: D_k = . Variabila x_j va fi cea care intra in noua baza. Daca minimul este multiplu atunci alegem, la intamplare, unul dintre acestia (cei minimi).

Pasul 3. Se analizeaza elementele coloanei a_j din B^-1 A, corespunzatoare variabilei alese la pasul 2.

Daca toate sunt mai mici sau egale cu 0 atunci problema are optim infinit si algoritmul ia sfarsit;

Daca exista componente strict pozitive, pentru acestea se calculeaza rapoartele q_s = . Variabila x_i corespunzatoare raportului minim este cea care va iesi din baza. Daca acest minim este multiplu sunt posibile doua cazuri:

minimul este strict pozitiv. In acest caz se alege unul dintre acestia la intamplare;

minimul este 0. Atunci x_i corespunzatori sunt 0, deci solutia este degenerata si noua solutie este la fel de buna. Aceasta situatie poate duce la ciclarea algoritmului si alegerea la intamplare nu mai este suficienta, fiind nevoie de o regula de alegere suplimentara care sa evite ciclarea. O metoda de alegere se bazeaza pe faptul ca, asa cum vom vedea, intotdeauna prima baza este matricea unitate si in dreptul ei, in toate tabelele simplex, se va afla inversa bazei corespunzator fiecaruia. In acest caz, pentru pozitiile in care s-a obtinut minimul impartim prima coloana a lui B^-1 la coloana a_j si alegem minimul dintre aceste rapoarte. Daca minimul dintre acestia este tot multiplu continuam procedeul, pentru pozitiile ce dau noul minim, cu coloana a doua din B^-1 si asa mai departe, pana minimul ramane unic. Nu este posibil sa se epuizeze toate coloanele lui B^-1 si minimul sa ramana multiplu, deoarece, in acest caz, am avea: , pentru toti indicii j_k ai coloanelor lui B^-1, i₁ si i₂ fiind doi din indicii care dau acelasi minim pana la sfarsit sau altfel scris  pentru orice j_k T liniile i₁ si i₂ din B^-1 sunt proportionale, fapt ce contrazice faptul ca B^-1 este inversabila.

Pasul 4. Se calculeaza componentele tabelului simplex corespunzator noii baze pe baza tabelului actual si folosind urmatoarele reguli:

se incadreaza elementul a_ij, aflat la intersectia coloanei variabilei care intra in baza cu linia variabilei care iese din baza, care a fost numit de Danzig pivot, intr-un dreptunghi

coloana pivotului va avea 1 in dreptul pivotului si 0 in rest (inclusiv D_j

linia pivotului este linia actuala impartita la pivot (inclusiv in solutia de baza);

restul elementelor se calculeaza cu regula dreptunghiului (inclusiv solutia de baza, D si f(x_B)). Regula dreptunghiului se bazeaza pe observatia ca in toate formulele prin care se calculeaza acestea nu apare decat valoarea lor actuala, pivotul si cele doua elemente care ar completa dreptunghiul ce are pozitia de calculat si pivotul pe diagonala. Regula dreptunghiului se enunta literar astfel: 'noua valoare = produsul dintre elementele de pe diagonala pivotului minus produsul dintre cele aflate pe cealalta diagonala totul impartit la pivot'. (pentru scurtarea timpului de lucru se poate observa ca elementele unei linii care are 0 pe coloana pivotului raman aceleasi si de asemenea elementele unei coloane care are 0 pe linia pivotului)

Operatia de calculare a noului tabel prin regulile de mai sus poarta denumirea de pivotare.

Pasul 5. Se reia algoritmul de la pasul 2.

Exemplu: Fie problema de programare liniara:

pentru care stim ca baza formata din coloanele a₁, a₂, a₃ este admisibila. Pentru rezolvare vom aduce problema la forma standard de maxim introducand variabilele de abatere x₇, x₈, x₉ obtinand:

Vom aseza in tabelul simplex variabilele in ordinea indicilor si vom avea:

c = , A = , B = , c_B =

vom calcula matricea B^-1 =   si pe baza acesteia solutia de baza x_B = B^-1 b = si matricea B^-1 A =  care se trec in tabelul simplex:

si in final se vor calcula valoarea functiei obiectiv in aceasta solutie, z_j si D_j

Din tabel se observa ca exista D_j < 0, acestia fiind D D D D   iar minimul lor este D

Observatie Daca vom cauta acel D_j care da cea mai buna imbunatatire vom avea de gasit acel D_j dintre cei negativi pentru care se obtine  si deci de calculat:

 = =

 = =

 = =

 = =

si in final max ( , , , ) =  si corespunde tot lui D

In concluzie, solutia actuala nu este optima si solutia cea mai buna dintre cele posibile ca succesoare va avea variabila x₆ printre cele principale.

Analizand coloana a₆ observam ca exista componente strict pozitive (de fapt, in acest caz sunt chiar toate) si calculam pentru acestea rapoartele q_i obtinand:

q =  = ,   q =  = 14,   q =  =    

deci minimul corespunde variabilei x₁ si aceasta este cea care va iesi din baza. In cest moment cunoastem noua baza si vom construi tabelul simplex pe baza regulilor de calcul de la pasul 4:

pivotul este a₁₆ =

de exemplu, pentru elementul de pe pozitia a₃₄ avem dreptunghiul:

si noua valoare de pe aceasta pozitie va fi:   =  -1

In final, tabelul corespunzator noii baze va fi:

Continuand algoritmul vom gasi tabelele:

Ultimul tabel contine solutia optima, deoarece toti D_j 0. Deoarece nu mai exista nici un D_j = 0 in afara celor din baza rezulta ca solutia optima este unica.

Determinarea unei solutii de baza admisibile de start

Presupunem inca odata ca problema este la forma standard.

Algoritmul simplex necesita, pentru pornire, o solutie admisibila de baza. Gasirea acesteia pur si simplu prin incercari nu este deloc o sarcina usoara, gandindu-ne ca aceasta presupune gasirea unui minor principal, inversarea acestuia si calcularea solutiei, abia in acest moment putand vedea daca aceasta are toate componentele pozitive, aceasta cautare putand dura foarte mult.

Rezolvarea problemei pleaca de la observatia ca singura baza pentru care calculul de mai sus se poate face imediat este matricea unitate, caz in care solutia de baza corespunzatoare este chiar vectorul termenilor liberi. Aceasta presupune ca problema sa aiba toti termenii liberi mai mari sau egali cu 0 si in matricea A sa existe toate coloanele matricii unitate.

Daca toti termenii liberi pot fi facuti mai mari sau egali cu 0 foarte simplu, prin inmultirea eventual cu -1 a restrictiei respective, existenta tuturor coloanelor matricii unitate este evident ca este foarte putin probabila si mai greu de obtinut.

In acest sens plecam de la observatia ca existenta unui vector din coloana unitate printre coloanele matricii A este echivalenta cu existenta unei variabile care apare doar in ecuatia corespunzatoare lui 1 din acel vector, cu coeficientul 1. Acest lucru poate fi obtinut  in doua moduri:

a) Incepand de la prima ecuatie, cautam o variabila care are coeficientul de acelasi semn cu termenul liber, o scoatem din aceasta ecuatie in functie de celelalte variabile, o inlocuim in celelalte si repetam procedeul pornind de la a doua ecuatie. Pot aparea trei cazuri:

la un moment dat obtinem o ecuatie in care toti coeficientii variabilelor au semn contrar termenului liber, macar unul dintre toti fiind diferit de 0. In acest caz ecuatia nu are evident solutie admisibila(pozitiva) si deci problema nu are solutie;

toti coeficientii variabilelor si termenul liber sunt 0. In acest caz rezulta ca aceasta ecuatie rezulta din cele anterioare si ea va fi eliminata, trecandu-se la urmatoarea;

se epuizeaza toate ecuatiile. In acest moment, variabilele care au fost scoase din fiecare ecuatie formeaza baza dorita.

Procedeul de mai sus poate parea atractiv, dar presupune introducerea unui algoritm diferit de simplex, cu efect asupra omogenitatii calculelor si a vitezei de lucru. De asemenea, prin efectuarea calculelor de mai sus, datele problemei nu mai au semnificatia economica initiala, ne mai putandu-se face interpretari economice.

b) Pentru toti vectorii coloana introducem in ecuatiile corespunzatoare cate o variabila cu coeficientul 1. Vom obtine evident un nou sistem de restrictii si ramane de vazut ce legatura este intre solutiile acestuia si cel initial. Cele doua sisteme au forma:

A x = b     si    A x + y = b

Este evident ca o solutie a primului sistem este solutie si a celui de-al doilea (luam y = 0) iar o solutie a celui de-al doilea este solutie si pentru primul doar daca y = 0. Scopul nostru va fi deci, ca pornind de la solutia initiala a celei de-a doua probleme sa ajungem la o solutie a acesteia in care y = 0. Tinand cont ca in solutiile de baza, variabilele secundare sunt toate egale cu 0, vom incerca sa scoatem din baza variabilele y. Scopul algoritmului simplex este insa maximizarea functiei obiectiv, nu scoaterea a uneia sau alteia din variabile din baza. Pentru a echivala cele doua scopuri putem proceda in doua feluri:

Alegem o noua functie obiectiv care sa-si atinga extremul printre solutiile pozitive chiar pentru y = 0 si in momentul cand am obtinut solutia respectiva pornim cu aceasta ca solutie initiala algoritmul simplex pentru fosta problema.

Adaugam la fosta functie obiectiv noile variabile cu niste coeficienti de asemenea natura alesi incat aportul variabilelor y la valoarea functiei sa fie contrar scopului dorit (foarte mari pozitivi intr-o problema de minim si foarte mari negativi intr-o problema de maxim).

Vom detalia in continuare cele doua metode:

Algoritmul simplex in doua faze

Data problema de programare liniara la forma standard de maxim:

in care am aranjat deja ca toti termenii liberi sa fie pozitivi (b

Faza 1 Construim problema:

pe care o rezolvam cu algoritmul simplex pornind rezolvarea de la baza matrice unitate, putand ajunge la doua situatii:

minimul functiei g este strict pozitiv. Aceasta este echivalent cu faptul ca egalitatea Ax + y = b se poate obtine doar pentru y > 0 sau altfel spus Ax > b pentru orice x 0, deci sistemul Ax = b nu are solutii admisibile si in concluzie problema initiala nu are solutie.

minimul functiei g este 0. In acest caz, solutia optima obtinuta are y = 0, deci verifica Ax = b fiind in concluzie o solutie admisibila de baza a primei probleme.

Faza 2 Incepand de la solutia gasita la faza 1 se rezolva problema initiala cu algoritmul simplex.

Dezavantajul metodei consta in faptul ca tabelul simplex final de la faza 1 trebuie modificat pentru a obtine tabelul simplex initial de la faza 2 (vectorii x, c, c_B, z, D, f(x_B), se elimina coloanele corespunzatoare lui y) si in plus nu vom mai avea in tabelele simplex ale problemei initiale inversa bazei (care se gasea in dreptul coloanelor matricii unitate din prima faza) necesara in anumite variante ale algoritmului simplex.

Metoda bazei artificiale (metoda penalizarii)

Data problema de programare liniara la forma standard de maxim:

in care am aranjat deja ca toti termenii liberi sa fie pozitivi (b

Construim problema:

in care M este o constanta presupusa foarte mare (mai mare decat orice constanta care ar putea apare in rezolvarea problemei). Rezolvam problema cu algoritmul simplex pornind rezolvarea de la baza matrice unitate, putand ajunge la trei situatii:

problema are optim infinit. In acest caz, problema initiala are optim infinit.

problema are optim finit si in solutia de baza avem cel putin o variabila din vectorul y. In acest caz problema initiala nu are solutii admisibile.

problema are optim finit si in solutia de baza nu avem nici o variabila din vectorul y. In acest caz problema initiala are optim finit, solutia optima si maximul functiei fiind aceleasi cu cele ale problemei modificate.

In final vom remarca faptul ca variabilele y nu corespund unor marimi 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 liniara:

Forma standard a problemei va fi:

Avem deja termenii liberi si o coloana a matricii unitate  corespunzatoare variabilei x₃. Pentru a obtine si a doua coloana  vom introduce variabila x₅ cu coeficientul 1 in a doua ecuatie si in final vom avea de rezolvat problema:

Aplicand algoritmul simplex in doua faze vom obtine in prima faza succesiunea de tabele:

Am obtinut optimul egal cu 0 in solutia de baza (x₃,x₂) care va fi solutia initiala pentru algoritmul simplex aplicat problemei initiale in a doua faza. Eliminam din tabel coloana lui x₅, inlocuim valorile coeficientilor functiei obiectiv si deci si valoarea acesteia, valorile D si obtinem tabelul:

Solutia optima a primei probleme este deci x₁ = 0 si x₂ = 10 care da un maxim al functiei egal cu 30. Daca aplicam a doua metoda vom obtine succesiv tabele:

Rezultatul final este evident acelasi.

VARIANTE  ALE  ALGORITMULUI  SIMPLEX

Algoritmul simplex dual

Pentru expunerea acestui algoritm trebuie introduse notiunile de baza dual admisibila si solutie dual admisibila de baza. Prin definitie numim:

Ca si in cazul algoritmului simplex, pentru a putea rezolva problema cu algoritmul simplex dual trebuie sa dispunem deja de o baza initiala dual admisibila. Aceasta solutie poate exista ca urmare a unor calcule anterioare (vezi capitolul cu reoptimizarea) sau, ca si in cazul algoritmului simplex, poate fi aplicata o procedura prin care sa gasim aceasta baza. Prezentarea acesteia este mai complicata decat cea de la algoritmul simplex astfel incat:

daca dispunem de o baza dual admisibila vom rezolva problema cu algoritmul simplex dual

daca nu dispunem de o baza dual admisibila vom rezolva problema cu algoritmul simplex.

Pentru a evita orice confuzie, vom numi in continuare algoritmul simplex obisnuit algoritm simplex primal si o baza admisibila baza primal admisibila.

Se observa ca o solutie dual admisibila nu este in general primal admisibila si reciproc, iar o solutie care este simultan primal si dual admisibila este o solutie optima si reciproc.

Presupunem ca am adus problema la forma standard de maxim si dispunem de o baza dual admisibila si dispunem deja de de o baza dual admisibila. Algoritmul simplex dual consta in urmatorii pasi:

Pasul 1. Se construieste tabelul simplex asociat acestei baze, la fel ca si la algoritmul simplex primal;

Pasul 2. Se analizeaza componentele solutiei:

Daca toate componentele sunt mai mari sau egale cu 0 atunci solutia este si primal admisibila, deci optima.

Daca exista componente strict negative, variabila corespunzatoare celei mai negative (x_i = ) este cea care iese din baza. Daca minimul este multiplu se ia una la intamplare.

Pasul 3. Se analizeaza linia l_i corespunzatoare variabilei x_i aleasa la pasul 2:

Daca toate componentele a_ij j = 1,,n sunt mai mari sau egale cu 0, atunci am avea o ecuatie cu toti coeficientii necunoscutelor pozitivi si termenul liber strict negativ, deci problema nu are solutii primal admisibile.

Daca exista componente strict negative, atunci pentru acestea se gaseste acel indice pentru care se obtine  (prin  am notat modulul numarului a). Daca minimul este multiplu alegem unul dintre acestia la intamplare. Variabila corespunzatoare acestuia este cea care intra in baza.

Pasul 4. Se construieste tabelul corespunzator noii baze aplicand aceleasi reguli ca la algoritmul simplex primal;

Pasul 5. Se reia algoritmul de la pasul 2

Forma secundara

Este evident ca modul de organizare al datelor in tabelul simplex nu este unicul mod de a organiza datele intr-un tabel. Forma secundara este tocmai o astfel de alternativa. Presupunem si in acest caz ca problema este la forma standard de maxim, ca problema este la forma standard si ca dispunem de o solutie initiala de baza care este primal sau dual admisibila.

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

Se observa ca singura diferenta este ca la coloana variabilelor bazei din stanga se adauga si cele secundare, pe orizontala se lasa doar variabilele secundare iar in loc de matricea unitate in dreptul variabilelor principale vom avea matricea unitate in dreptul celor secundare (dar cu minus), D fiind calculat la fel, neglijandu-se cei din dreptul variabilelor principale, care oricum erau 0.

Pasul 2. +   Pasul 3.  Se gasesc variabila care iese din baza si cea care intra in baza cu aceleasi reguli ca la algoritmul simplex primal sau, dupa caz, ca la cel dual.

Pasul 4.  Se construieste tabelul asociat noii baze aplicand regulile:

Pivotul este acelasi ca la tabelul simplex;

Linia pivotului are -1 in dreptul pivotului si 0 in rest;

Coloana pivotului se imparte la pivotul cu semn schimbat

Celelalte elemente se calculeaza cu regula dreptunghiului

Pasul 5.   Se reia algoritmul de la pasul 2.

Exemplu Fie problema de programare liniara rezolvata mai sus:

Forma standard a problemei va fi:

iar dupa introducerea variabilelor artificiale obtinem:

Tabelul corespunzator va fi:

Aplicam simplex primal si obtinem cel mai negativ D_j corespunzator lui x₂ si q_i minim corespunzator lui x₅. In acest moment avem o solutie de baza a problemei initiale si putem elimina variabila x₅. Obtinem:

si in continuare:

Din rezolvarea de mai sus se observa ca aceasta metoda este mai eficienta doar daca numarul variabilelor secundare este mai mic decat numarul variabilelor principale. Totusi, motivul principal pentru care a fost introdusa aceasta varianta, este existenta unor probleme in care, pe parcursul rezolvarii, se adauga foarte multe restrictii (de exemplu rezolvarea problemelor in numere intregi), pentru o restrictie in plus tabelul simplex marindu-se cu o linie si o coloana (cum se va vedea la capitolul de reoptimizare) iar tabelul corespunzator formei secundare doar cu o linie.

Forma revizuita a algoritmului simplex

O problema mare (de exemplu cu 1000 variabile si 100 restrictii) necesita in algoritmul simplex introducerea, memorarea si lucrul cu un tabel cu 100.000 componente, adica un numar imens de date. Din acest motiv, si remarcand faptul ca in algoritmul simplex doar o parte din acestea contribuie efectiv la luarea deciziilor, s-a construit un algoritm care sa tina cont de observatiile de mai sus, numit 'forma revizuita a algoritmului simplex', in care se lucreaza cu minimul necesar din datele tabelului simplex. Astfel, pentru testarea solutiei actuale si trecerea eventuala la o noua baza avem nevoie doar de urmatoarele elemente:

inversa bazei curente B^-1

componentele vectorului D pentru a face testul de optim si a gasi variabila care intra in baza (daca solutia nu e optima)

coloana a_k din B^-1A corespunzatoare celui mai negativ D_j (daca exista strict negativi) pentru a face testul de optim infinit

solutia curenta pentru a gasi variabila care iese din baza (daca mai e cazul)

Aceste elemente se aseaza intr-un tabel de forma:

numit tabelul simplex redus.

Operatiile ce se efectueaza in cadrul algoritmului simplex revizuit sunt (presupunem ca problema este la forma standard de maxim si detinem o solutie admisibila de baza si inversa bazei corespunzatoare):

Pasul 1. Se calculeaza D_j corespunzatori variabilelor secundare cu formula cunoscuta:

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

unde P_j este coloana corespunzatoare variabilei x_j din matricea initiala.

Pasul 2. Se analizeaza D_j calculati:

daca toti sunt mai mari sau egali cu 0 solutia curenta este optima. STOP

daca exista D_j strict negativi se alege minimul dintre acestia D_k, variabila x_k va intra in baza si se trece la pasul 3.

Pasul 3. Se calculeaza a_k = B^-1P_k care se ataseaza ca noua coloana la tabel:

Pasul 4. Se analizeaza componentele coloanei a_k:

daca toate sunt mai mici sau egale cu 0 problema are optim infinit. STOP

daca exista a_ik strict pozitivi se alege cel pentru care se obtine:

a_rk =

si variabila x_r va iesi din baza apoi se trece la pasul 5.

Pasul 5. Se pivoteaza intregul tabel simplex si se elimina ultima coloana.

Pasul 6. Se reia algoritmul de la pasul 2.

Exemplu Fie problema de programare liniara rezolvata mai sus:

Forma standard a problemei va fi:

iar dupa introducerea variabilelor artificiale obtinem:

Iteratia  1.  Prima baza este B = I₂ = B^-1 corespunzatoare variabilelor x₃ si x₅ de unde rezulta x_B =  si π = (0,-M) I₂ = (0,-M). Primul tabel redus va fi:

Se calculeaza D_S S - c_S = (0,-M)  -  =  de unde rezulta ca cel mai negativ este D si vom calcula coloana a₂ = I₂ =  care se adauga la tabelul anterior rezultand:

q_i minim este cel corespunzator lui x₅ si deci variabila x₂ va intra in locul variabilei x₅.

Dupa pivotare si eliminarea ultimei coloane obtinem:

Deoarece variabila artificiala x₅ a iesit din baza ea va fi eliminata din problema.

Iteratia 2.  D_S S - c_S = (0,)  -  = ( )

cel mai negativ este D si vom calcula coloana a₁ = =  care se adauga la tabelul anterior rezultand:

q_i minim este cel corespunzator lui x₂ si deci variabila x₁ va intra in locul variabilei x₂.

Dupa pivotare si eliminarea ultimei coloane obtinem:

Iteratia 3.  D_S S - c_S = (0,2)  -  = ( )

cel mai negativ este D si vom calcula coloana a₄ = =  care se adauga la tabelul anterior rezultand:

q_i minim este cel corespunzator lui x₃ si deci variabila x₄ va intra in locul variabilei x₃.

Dupa pivotare si eliminarea ultimei coloane obtinem:

Iteratia 4.  D_S S - c_S = ( ,0)  -  = ( )

cel mai negativ este D si vom calcula coloana a₂ = =  care se adauga la tabelul anterior rezultand:

q_i minim este cel corespunzator lui x₁ si deci variabila x₂ va intra in locul variabilei x₁.

Dupa pivotare si eliminarea ultimei coloane obtinem:

Iteratia 5. D_S S - c_S = (3,0)  -  = ( ) >0 deci solutia este optima (si unica) STOP

Chiar daca la prima vedere calculele par mai imprastiate si deci mai lente, pentru probleme mari, pe calculator se economiseste foarte multa memorie si se mareste foarte mult viteza de calcul.

Totusi, marele avantaj al acestei metode este acela ca, la fiecare iteratie, se folosesc datele problemei initiale, ceea ce face ca erorile inerente de rotunjire sa nu se propage, ramanand in limite acceptabile.