Programare Liniara

Metoda simplex
 Programarea liniara:: Simplex
Să se determine maximul funcţiei z ce depinde de N variabile
independente

cu restricţiile banale :
şi restricţii nebanale de tipul, I, II şi III. Fie m1 restricţii de tipul I, m2 restricţii de tipul
II respectiv m3 numărul de restricţii de tipul III. Numărul de restricţii va fi:
M = m1 + m2 + m3.

Restricţiile de tipul I sunt de forma: Restricţiile de tipul II sunt de forma:

Programarea liniara:: Simplex
Restricţiile de tipul III sunt de forma:

Coeficienţii restricţiilor şi ai
funcţiei de optimizat pot avea
orice valoare

Terminologia specifică metodei

Un set de valori x1…xN care satisface condiţiile I, II şi III este numit vector
candidat iar funcţia ce se optimizează se numeşte de oboicei funcţie scop sau
funcţie obiectiv.
Un vector candidat care maximizează funcţia obiectiv se numeşte vector
candidat optimal.
În ciuda faptului că se asigură optimul funcţiei, un astfel de vector nu este optimul
căutat atunci când:
a) restricţiile conduc la un sistem incompatibil şi nu avem un vector candidat viabil,
b) nu putem fi siguri ca am găsit un maxim deoarece există variabile care pot lua
valori oricît de mari fără să influenţeze restricţiile impuse şi se obţine o valoare
nemărginită a funcţiei obiectiv
Programarea liniara:: Simplex
Importanţa metodei

Metoda prezintă avantaje deosebita în cazul aplicării în practică deoarece:

-Toate mărimile pe care le putem introduce sub formă de parametrii au
valori pozitive, de exemplu timpul de menţinere peste 800oC, între 500oC şi
800oC, rezilienţa, temperatura de preâncălzire, temperatura între treceri,
preţul de cost, diametrul electrodului, densitatea curentului, etc, deci
pozitivitatea variabileloreste îndeplinită.
-Se pot introduce un număr nelimitat de restricţii liniare sau care pot fi
liniarizate astfel încât să se solutioneze probleme diverse legate atât de
restricţiile tehnice, tehnologice cât şi de aspecte economice şi se
complectează astfel restricţiile I, II si III
- Faptul că funcţia obiectiv este liniară nu este un inconvenient foarte mare
deoarece aceasta poate fi uşor liniarizată pe subintervale şi astfel printr-o
aplicare repetată a algoritmului pe acestea se poate găsi optimul căutat
 Programarea liniara:: Simplex
Exemplul numeric

Cu restricţiile nebanale:

Se observă că N = 4 şi m1 = 2, m2 = m3 = 1 deci M = 2 + 1 + 1 = 4
Programarea liniara:: Simplex
Programarea liniara:: Simplex
Consideraţii de bază

Se verifică dacă aceste posibile soluţii îndeplinesc restricţiile de tipul

egalităţilor şi a inegalităţilor.

Dacă vom reprezenta funcţia obiectiv, aceasta în cazul de faţă va fi tot o

dreaptă. Optimul valorii acesteia fiind într-unul dintre vîrfurile domeniului.
Ar fi eficient să se determine punctele de intersecţie ale dreptelor ce
definesc domeniul de admisibilitate şi să se verifice valoarea funcţiei
obiectiv în acestea pentru a se obţine maximul căutat
Dar dacă pentru un număr restrâns de parametrii această metodă ar fi
eficientă, în cazul general este eficientă utilizarea unui punct din interiorul
domeniului, trasarea funcţiei obiectiv prin acest punct şi verificarea
intersecţiilor dintre aceasta şi frontierele domeniului
Programarea liniara:: Simplex
In algoritmul implementat, se verifică valoarea gradientului în acest
punct şi urmează deplasarea pe direcţia acestuia până când se întâlneşte o
frontieră a acestuia.
Dacă s-a depăşit limita domeniului atunci se revine până la intersecţia cu
unul din vârfurile acestuia sau se caută cel mai apropiat vârf. Acest punct
are toate coordonatele definite astfel încât să satisfacă sistemul de restricţii
şi asigură şi maximul funcţiei obiectiv
Punctele care formează soluţiile candidate şi satisfac şi restricţiile în cazul
în care acestea sunt înlocuite cu egalităţi sunt denumite vectorii candidaţi
de bază.
Dacă N > M atunci un vector candidat din bază are N – M componente
egale cu [Link], cel puţin M componente ale vectorilor candidaţi ai
bazei pot fi diferite de zero.
Programarea liniara:: Simplex

Prima abordare a acestei metode a fost dată de Danzing în 1946 [5.8.2] sub
forma modului de organizare a algoritmului de calcul.
Astfel,
- se generează şi se verifică o mulţime de combinaţii ale variabilelor astfel
încât funcţia obiectiv să ia valori crescătoare.
- Vectorul candidat optim se determină după un număr de iteraţii egal cu
maximul dintre N şi M.

Aceasta abordare necesita unele modificari aduse algoritmului pentru a

simplifica procesul de implementare a acestuia intr-un program de
calculator.
Programarea liniara:: Simplex
Metoda Simplex sub formă canonică

O problemă de programare liniară se consideră adusă la forma normală

dacă toate restricţiile de formă inegalitate sunt transformate în restricţii de
tip egalitate.
Rezolvarea problemei necesită însă aducerea acesteia sub o formă mult
mai restrictivă prin impunerea unor condiţii noi asupra ecuaţiilor devenite
acum egalităţi.
Fiecare ecuaţie aflată sub forma generală trebuie să aibă cel puţin o
variabilă al cărui coeficient să fie pozitiv şi această variabilă trebuie să
aparţină numai acestei ecuaţii
Programarea liniara:: Simplex
Exemplul 2
Sub forma normală o problemă de programare liniară poate fi scrisă astfe

unde x1,x2,x3,x4 sunt pozitive şi condiţiile din setul de bază sunt:

In setul de bază avem M = 2 restricţii şi N = 4 variabile necunoscute,

dintre care x1 şi x4 sunt variabile din partea stângă iar x2 şi x3 sunt în
partea dreaptă
Funcţia obiectiv a fost scrisă astfel încât să depindă doar de variabilele din
partea dreaptă

Acest lucru se obţine prin înlocuirea variabilelor din partea

stângă cu expresia acestora din restricţiile din bază
Programarea liniara:: Simplex
Reducerea la forma canonică se face cu relativă uşurinţă mai ales că nu
este obligatoriu să se pornească de la un set de variabile şi restricţii cât
mai apropiat de soluţia optimă.
Valorile variabilelor din partea dreaptă se obţin de regulă prin înlocuirea cu
zero a variabilelor din partea stângă în ecuaţiile restricţiilor care intră în
bază. Astfel, pentru cazul considerat x1 = 2 şi x4 = 8 deoarece x2 = 0.0 si x3
= 0.0 functia obiectiv avand valoarea z = 0.0 in acest caz.
 Programarea liniara:: Simplex
Pasul 1.
Se caută în coloanele ce corespund variabilelor din dreapta coeficientul cu
valoarea pozitivă cea mai mare, deci max{2,-4} ceea ce reprezintă faptul că
influenţa maximă asupra creşterii valorii funcţiei z o are variabila x2.
Dacă toate valorile sunt negative atunci nici o variabilă din partea
dreaptă nu mai poate produce o creştera a funcţiei obiectiv şi s-a
obţinut valoarea maximă a funcţiei obiectiv

Pasul 2.
Se caută cea mai mică valoare negativă a coeficienţilor ce înmulţesc
variabila aleasă la pasul 1 în ecuaţiile restricţiilor, în cazul de faţă,
min{-6,3}  -6, acesta este coeficientul din restricţia variabilei de bază x1.
Dacă toţi coeficienţii căutaţi sunt pozitivi atunci se încheie procesul
de calcul şi se afişază soluţia.
Programarea liniara:: Simplex
Pasul 3.
Se introduce în bază variabila x2 şi se extrage din bază variabila x1.
Se reactualizeaza forma canonica

Se exprimă restricţia în funcţie de x2 (noua variabilă ce intră în bază)

Se actualizează funcţia obiectiv şi celelalte restricţii prin înlocuirea

variabilei x2 cu expresia ei în funcţie de x1 şi x3

Se reactualizează tabelul cu noile variabile din stânga şi noii coeficienţi

Programarea liniara:: Simplex
Se reactualizează tabelul cu noile variabile din stânga şi noii coeficienţi

Pasul 4.
Constă în reluarea pasului 1 şi căutarea unor noi creşteri a funcţiei
obiectiv. Cum în cazul de faţă, pe rândul funcţiei obiectiv toţi
coeficienţii variabilelor din dreapta sunt negativi, se poate afişa soluţia
 Programarea liniara:: Simplex
Dacă se defineşte pivotul ca fiind coeficientul variabilei care intră în bază
atunci se poate defini algoritmul de rezolvarea a problemei mult mai simplu
Consideratii privind algoritmul
a) Se găseşte elementul care intră în bază şi se memorează poziţia acestuia
b) Se memorează într-o variabilă separată întreaga coloană ce aparţine
pivotului
c) Se înlocuiesc rândurile sistemului cu excepţia celui pe care se găseşte
pivotul cu o combinaţie liniară de aşa manieră încât coloana pivotului să
devină nulă.
d) Se împarte rândul pivotului la valoarea pivotului şi se înmulţeşte totul cu -1.
e) Se înlocuieşte elementul pivot prin următoarea valoare din coloana
acestuia.
f) Se actualizează coloana pivotului prin împărţirea acesteia la valoarea
pivotului.
Programarea liniara:: Simplex
Utilizarea acestui algoritm permite rezolvarea problemelor de programare
liniară date sub formă canonică (redusă sau normală).
Singurul caz care nu poate fi rezolvat este cel care conduce la valori zero
atât pentru variabilele din stânga cât şi pentru cele din dreapta, caz despre
care se afirma că genereaza vectori degeneraţi ai bazei.

Aducerea problemei generale la forma canonică

Procesul de rezolvare a problemelor de programare liniară se bazează pe
transformarea formei generale a problemei într-o formă canonică care
poate fi rezolvată mault mai uşor prin utilizarea metodelor numerice
Aducerea inecuaţiilor la ecuaţii prin adăugarea unor variabile de
ajustare, notate mai departe cu y. Aceste variabile sunt în număr egal cu
cel al restricţiilor de tip I şi II, deci m1 + m2. Semnul acestora depinzând
de tipul inecuaţie
 Programarea liniara:: Simplex
Ţinând seama de restricţia de pozitivitate pe care şi aceste variabile trebuie să
o îndeplinească, rezultă că în cazul în care partea din stânga este mai mică
decât partea din dreapta acestea se vor aduna iar în caz contrar se vor scădea.
Pentru exemplul 1 restricţiile devin

Conduc la

Se genereaza un set de M variabile adiţionare, z. Aceste variabile sunt introduse pentru

a se uşura procesul rezolvării cât şi programarea numerică. Prin trecerea în partea
dreaptă a variabilelor deja existente, rezultă :
 Programarea liniara:: Simplex
S-a ajuns la forma căutată, cu preţul introducerii unui număr mult mai mare de
variabile.
Prin artificiile efectuate, valoarea acestor variabile nu influenţează rezultatul
problemei şi mai mult toate variabilele adiţionale sunt nule. Se utilizează în
continuare funcţia obiectiv, dar se recurge la un proces mai puţin utilizat
deoarece trebuiesc introduse şi variabilelor notate cu y şi z.
Se scrie o nouă funcţie obiectiv, formată prin suma variabilelor auxiliare.
Aceste variabile sunt nule iar suma lor va fi nulă şi ea, dar ne permite să
facem legătura dintre variabilele introduse pentru a transforma inecuaţiile în
ecuaţii,( cele adiţionale z) şi variabilele problemei reale x si de ajustare y.
Această nouă funcţie obiectiv o vom numi “funcţie obiectiv auxiliară” şi
deoarece este fomrată prin însumarea variabilelor adiţionale se va nota cu
z’.
Functia obiectiv a problemei

Functia obiectiv auxiliara

 Programarea liniara:: Simplex
În continuare se rezolvă problema de programare liniară canonică, formată
din maximizarea funcţiei z’ împreună cu sistemul de restricţii (z') în scopul
obţinerii unui set de variabile de bază (din stânga) care să fie format din
variabilele xi şi yi şi toate variabilele zi să fie în partea dreaptă. Se obţine
astfel setul de ecuaţii de restricţie sub formă normală pentru al doilea stadiu
de rezolvare a problemei şi se elimină variabilele zi din problemă ceea ce
conduce la obţinerea unui set de variabile din stânga viabil.
Dacă nu se poate obţine un set de variabile din bază, deci dacă nu
toate variabilele zi pot fi mutate în partea dreaptă atunci problema nu
admite soluţie şi procesul de optimizare se încheie.
Se analizează în acest caz restricţia sau restricţiile a cărei sau a căror
variabile artificiale (zi) nu au putut fi eliminate din bază, se redefinesc aceste
restricţii şi se încearcă din nou rezolvarea problemei.
 Programarea liniara:: Simplex
În ce-a de-a doua fază a optimizării se utilizează setul de variabile din stînga
obţinut în prima fază împreună cu funcţia obiectiv originală pentru a se obţine
maximul dorit ca şi valorile parametrilor xi care conduc la acesta.

Această aranjare a datelor este intuitivă, în zona coloanelor xi şi a liniilor z şi

zi apar coeficienţii din problema pusă sub formă iniţială, ceea ce este uşor de
programat. Suma pe coloane a acestor coeficienţi (cu semnul schimbat)
apare în rândul corespunzător funcţiei auxiliare de optimizare, z’. Semnul
variabilelor yi depinde de semnul inecuaţieie iar valoarea acestora este
unitară.
Programarea liniara:: Simplex
Modul de ieşire dintr-o rutină simplex poate fi:
(i) – o variabilă booleană care conţine informaţia referitoare la tipul de soluţie
determinat. Soluţie validă, soluţie imposibilă sau soluţie infinită.
(ii) – o variabilă de tip matrice ( tablou) care conţine soluţia. Pentru problema
prezentată în exemplul 1 aceasta este

Informaţiile utile sunt cuprinse într-o zonă mult mai redusă a tabelului general,
doar N +1-m3 coloane şi M + 1 rânduri. Variabilele se află în prima coloană şi
valorile acestora în cea de-a doua coloană.
După cum se observă în vectorul soluţiei apare şi variabila y1, valoarea
acesteia corespunzând limitei peste care restricţia ce corespunde acesteia
nu mai este îndeplinită
Programarea liniara:: Simplex
Variabilele care nu se găsesc în vectorul soluţiei (nu sunt în partea
stângă, sau nu se găsesc în vectorul bazei) vor lua valoarea zero.

De asemenea variabilele yi care au valoarea zero indică faptul că restricţia

care corespunde acestei variabile în urma înlocuirii soluţiei devine
egalitate.
Programarea liniara:: Simplex

Observaţii asupra implementării metodei.

S-a urmărit implementarea dată de Kuenzi, ş.a [5][8][4]. După ce s-au definit
mărimile, N,M,m1,m2,m3 se dimensionează matricea a[M+2][N+1] care
conţine coeficienţii funcţiei obiectiv pe primul rând urmate de coeficienţii
restricţiilor de tipul I, II şi III. Aceste intrări ocupă M + 1 rânduri şi N + 1
coloane din a[1…m +1][1…n + 1]. Pe rândul M + 2 se găseşte funcţia
obiectiv adiţională, z’.
Programarea liniara:: Simplex
Se utilizează doi vectori pentru indecşi:
iposv[j = 1..M]  care conţine iniţial indecşii variabilelor principale şi la
finalul rulării indecşii variabilelor din stânga (soluţia). Dacă valoarea acestui indice
este mai mare decât N, atunci referirea se face la o variabilă yi şi valoarea acesteia
nu va fi cuprinsă în soluţie.
izrov[j = 1..N]  care conţine indecşii variabileor care se găsesc în
dreapta deci nu sunt în soluţie. Dacă valoarea acestora I = izrov[j] <= N atunci
valoarea variabilei x[i] va fi nulă deoarece aceasta se găseşte în partea dreaptă.
Dacă N < I = izrov[j] < N+m1+m2 atunci se indexează variabilele yi şi dacă
i=izrov[j]>N+m1+m2 atunci se face adresarea variabilelor zi, care sunt privite ca
variabile interne programului şi în procesul de afişare a rezultatelor se anulează.
icase  variabilă întreagă de control cu scopul de a monitoriza tipul
problemei şi compatibilitatea soluţiei determinate. Valorile acestui control sunt:
0  dacă există o soluţie valabilă care să îndeplinească atât sistemul de
restricţii cât şi maximul funcţiei obiectiv.
-1  dacă sistemul de restricţii este îndeplinit dar funcţia obiectiv este
nemărginită.
+1  dacă nici o soluţie nu poate îndeplini condiţiile impuse de sistemul
de restricţii.
Programarea liniara:: Simplex

Datele de testare ale programului

Cu restricţiile nebanale:

Se observă că N = 4 şi m1 = 2, m2 = m3 = 1 deci M = 2 + 1 + 1 = 4
Programarea liniara:: Simplex
date initiale N=4 M1=2 M2=1 M3=1 M=4 Matricea A de intrare in Simplex

Matricea a de intrare in programul simplex

0.000000 1.000000 1.000000 3.000000 -0.500000
740.0000 -1.000000 0.000000 -2.000000 0.000000
0.000000 0.000000 -2.000000 0.000000 7.000000
0.500000 0.000000 -1.000000 1.000000 -2.000000
9.000000 -1.000000 -1.000000 -1.000000 -1.000000
0.000000 0.000000 0.000000 0.000000 0.000000
Programarea liniara:: Simplex
Matricea rezultatelor A[1][1] -> valoarea optima Z=17.025

17.025000 -0.950000 -0.050000 -1.950000 -1.050000

730.5500 0.100000 -0.100000 1.100000 0.900000
3.325000 -0.350000 -0.150000 -0.350000 0.350000
0.950000 -0.100000 0.100000 -0.100000 0.100000
4.725000 -0.550000 0.050000 -0.550000 -0.450000
0.000000 0.000000 0.000000 -1.000000 0.000000

variabilele rezultate Solutia problemei

| in solutie | in afara bazei | valoarea optimului Z = 17.025000
| 5 | 1 | x[1] = 0.000000
| 2 | 6 | x[2] = 3.325000
| 4 | 8 | x[3] = 4.725000
| 3 | 7 | x[4] = 0.950000
| 0 | 0 |
tip solutie 0