OPTIMIZAREA PROCESELOR ECONOMICE UTILIZÂND PROGRAMARE A LINIARĂ [601458]
CAPITOLUL III*)
OPTIMIZAREA PROCESELOR ECONOMICE UTILIZÂND PROGRAMARE A LINIARĂ
3.1. Forma generală a unei probleme de programare liniară
Problemele de maxim și de minim apar frecvent în cele mai diferite domenii ale
matematicilor pure sau aplicate. În domeniul economic, asemenea probleme sunt foarte naturale.
Astfel, firmele încearc ă să maximizeze profiturile sau s ă minimizeze costurile. Exper ții în planificare
macroeconomic ă se preocup ă de maximizarea bun ăstării unei comunit ăți economico -sociale.
Consumatorii doresc s ă cheltuiasc ă venitul lor într-un mod care s ă le maximizeze satisfac ția (de
natur ă material ă dar și spiritual ă etc.)
Programarea liniar ă se ocup ă de o clas ă special ă de probleme de optimizare care apar
deseori în aplica țiile economice. Aceste probleme constau în maximizarea sau minimizarea unei
funcții liniare , numit ă funcție obiectiv , ale c ărei variabile trebuie s ă satisfac ă:
un sistem de rela ții date sub forma unor ecua ții și/sau inecua ții liniare nestricte , denumite
generic restric ții;
cerin ța de a lua numai valori numerice nenegative (0).
3.1.1. Exemple
1) Problema firmei . Consider ăm un sistem de produc ție, de exemplu o firmă, care produce n
bunuri G 1,G2,…,G n utiliz ând pentru aceasta m categorii de resurse R 1,R2,…,R m (materii p rime, for ță
de munc ă, capacit ăți de produc ție, combustibili și energie etc.). Adopt ăm ipoteza c ă tehnologia de
transformare a resurselor în bunuri este liniar ă în sensul c ă:
Pentru fiecare bun, consumul dintr -o anumit ă resurs ă este direct propor țional cu c antitatea
produs ă.
Consumurile dintr -o resurs ă sau alta nu se condi ționeaz ă reciproc.
Fie atunci aij cantitatea din resursa i utilizat ă pentru producerea unei unit ăți din bunul G j. Fie
deasemeni bi cantitatea disponibil ă din resursa R i și cj prețul (sau pr ofitul) unitar al bunului G j.
Prețul unui bun nu depinde de cantitatea produs ă și nici de situa ția vânzărilor celorlalte
bunuri.
Problema const ă în determinarea unui program de fabrica ție care s ă maximizeze venitul (sau
profitul) firmei.
Să notăm cu xj cantitatea din bunul G j care urmeaz ă a fi produs ă. Problema enun țată mai
înainte devine:
Să se găseasc ă valorile numerice x 1,×2,…,xn care maximizeaz ă funcția venit (sau profit) total :
fcxcx cxnn 11 22…
cu satisfacerea restric țiilor:
axax ax b
axax ax b
axax ax bnn
nn
m m mn n m11 1 12 2 1 1
21 1 22 2 2 2
11 22
* ) Suportul de curs al Capitolelor 3 și 4 are la bază lucrarea: Nica, V., Ciobanu, Gh., Mustață Floare, Mărăcine Virginia , “Cercetări
operaționale I – Programare liniară, Probleme de optimizare în rețele de transport și distribuție, Teoria jocurilor strategice ”
Editura MATRIX ROM, București 1998 CURSUL 6
I. PROGRAMARE LINIARA
32
și a condi țiilor de nenegativitate :
x x xn 1 20 0 0 , ,
Observa ție: Ipotezele de liniaritate f ăcute nu sunt verificate întotdeauna în practic ă. Rațiunea
lor este dubl ă:
conduc la modele matematice în general simple;
pe baza modelelor liniare se p ot formula concluzii calitative și legit ăți economice care își
mențin valabilitatea – în anumite limite – și într-un context neliniar.
2) Problema dietei a devenit o ilustrare clasic ă a program ării liniare, fiind întâlnită în mai
toate textele de specialitat e. Ea se ocup ă cu hr ănirea unei colectivit ăți, să zicem un grup de militari,
în cel mai economic mod cu condi ția satisfacerii anumitor cerin țe de nutri ție. Mai concret, este vorba
de a prepara un aliment complex pornind de la n sortimente de hran ă F1,F2,…,Fn. Un num ăr de
elemente sau principii nutritive N 1,N2,…,N m – proteine, glucide, gr ăsimi calciu,etc. sunt avute în
vedere în sensul c ă alimentul combinat trebuie s ă conțină cel pu țin b 1,b2,…,b m unități specifice
din fiecare. S ă presupunem c unoscute urm ătoarele:
cantitatea aij din principiul nutritiv N i conținută într-o unitate din tipul de hran ă Fj;
prețul unitar cj al tipului de hran ă Fj.
Notăm cu x1,x2,…,xn cantit ățile din felurile de hran ă F1,F2,…,F n care trebuie cump ărate în
vedere a elabor ării dietei. Formal, x1,x2,…,xn vor trebui determinate astfel încât:
costul total
fcxcx cxnn 11 22… al alimentelor cump ărate s ă fie minim.
amestecul s ă conțină principiile nutritive N 1,N2,…,N m în cantit ăți cel pu țin egale cu
b1,b2,…,bm, adică:
ax ax ax b
axax ax b
axax ax b
x x xnn
nn
m m mn n m
n11 1 12 2 1 1
21 1 22 2 2 2
11 22
1 20 0 0
…
…
…………………………..
…
, ,…,
Din nou au fost tacit utilizate ipotezele de liniaritate întâlnite și în modelul precedent.
3.1.2 Solu ții admisibile ale unei probleme de programare liniar ă
Consider ăm o problem ă de programare liniar ă (P) cu m restric ții egali tăți și/sau inegalit ăți
nestricte, n variabile și cu func ția obiectiv f. Un ansamblu de n valori numerice care satisfac
restric țiile se va numi Soluție a programului (P). Dac ă în plus sunt verificate și condi țiile de
nenegativitate, ansamblul se nume ște Soluție Admisibilă . O solu ție admisibil ă care maximizeaz ă sau
minimizeaz ă – după caz – funcția obiectiv se va numi Soluție optimă . Notând cu A mulțimea
soluțiilor admisibile, problema (P) se scrie:
Să se determine x* A cu proprietatea : f(x*) =
max min () sau
xfx
A
Este posibil ca (P) s ă aibă soluții dar nici una din ele s ă fie admisibil ă: A = . Spunem în acest caz
că problema (P) este incompatibil ă. Chiar dac ă A , este posibil ca func ția obiectiv s ă fie
nemărginit ă pe A , adic ă să existe un șir de so luții admisibile de -a lungul c ăruia func ția obiectiv s ă
33
tindă spre + sau – , dup ă caz. în aceast ă situa ție vom spune c ă (P) are optim infinit. Dacă (P) are
(cel pu țin) o solu ție optim ă, zicem c ă (P) are optim finit .
Deoarece eventualele restric ții inegalit ăți sunt nestricte mulțimea A este închis ă (în topologia
uzual ă a spa țiului Rn), adic ă o dat ă cu un șir convergent de puncte con ține și limita acestuia . Aceast ă
proprietate este esen țială pentru existen ța unei solu ții optime a problemei (P)! Conform unui rezultat
clasic al analizei matematice, dac ă A este mărginit ă, atunci f își atinge efectiv extremele pe A, și
deci (P) are optim finit . În consecin ță, dac ă (P) are optim infinit , cu siguran ță A este nemărginit ă.
Reciproca nu este în general adev ărată: este posibil ca A să fie nem ărginit ă și totu și (P) s ă aibă
optim finit.
3.1.3 Forma canonic ă a unei probleme de programare liniar ă
O restric ție a unei probleme (P) de programare liniar ă se zice concordant ă dacă este o
inegalitate de tipul "" când funcția obiectiv se maximizeaz ă și de tipul " " când func ția obiectiv se
minimizeaz ă. O restric ție inegalitate care nu este concordant ă se va numi neconcordant ă. Restric țiile
egalit ăți nu fac obiectul acestei clasific ări.
Spunem c ă o problem ă de programa re liniar ă este în form ă canonic ă dacă toate restric țiile ei
sunt inegalit ăți concordante .
În consecin ță, o problem ă în form ă canonică de maximizare arată astfel:
ax bi m
x j n
f cxijj
jn
i
j
jj
jn
1
11
0 1,…,
,…,
(max) sau matricial
Ax b
x
fcx
0
(max) unde:
Aa a a
a a a
a a abb
b
bxx
x
xn
n
m m mn m n
11 12 1
21 22 2
1 21
21
2
c cc cn 1 2
O problem ă în form ă canonică de minimizare se va scrie:
ax b
x
f cxijj
jn
i
j
jj
jn
1
10
(min)
Ax b
x
fcx
0
(min)
De exemplu, problema firmei (1.1, exemplul 1)) este o form ă canonic ă de maximizare în timp ce
problema dietei (1.1, exemplul 2) ) este o form ă canonic ă de minimizare.
Orice problem ă de programare liniar ă se poate pune sub o form ă canonic ă de maximizare sau
minimizare, f ără modificarea mul țimii solu țiilor admisibile, observ ând că:
o egalitate se poate înlocui cu dou ă inegalit ăți de sens contrar;
o restric ție neconcordant ă devine concordant ă prin înmul țire cu -1;
I. PROGRAMARE LINIARA
34
putem schimba sensul optimiz ării func ției obiectiv, gra ție formulei generale:
xfx
xfx
A Amin () max () (1.3.1)
În consecin ță, putem face anumite ra ționamente teoretice pe o form ă canonic ă (ca de exemplu în
teoria dualit ății liniare ), fără ca prin aceasta s ă restrângem generalitatea.
Exemplul 1.3.1
(max)
, ,f x x x
x x x
x x
x x
x x x
2 3 4
3 5 3
3 5
2 10
0 0 01 2 3
1 2 3
1 2
1 3
1 2 3
(min)( )
, ,
f x x x
x x x
x x x
x x
x x
x x x2 3 4
3 5 3
3 5 3
3 5
2 10
0 0 01 2 3
1 2 3
1 2 3
1 2
1 3
1 2 3
Programul (P) Forma canonic ă de minimizare a pro gramului (P)
3.1.4 Forma standard a unei probleme de programare liniar ă
Spunem c ă o problem ă de programare liniar ă este în form ă standard dacă toate restric țiile ei
sunt egalit ăți. Importan ța acestei forme particulare rezult ă din faptul c ă metoda de re zolvare a
problemelor de programare liniar ă care va fi expus ă mai departe cere ca problema s ă fie în aceast ă
prezentare.
În consecin ță, o problem ă (P) care are și restric ții inegalit ăți va fi înlocuit ă – în vederea
rezolv ării ei – cu o alta în care toate restric țiile sunt egalit ăți. Noua problem ă, numit ă forma standard
a problemei (P) și notat ă (FSP), se construie ște astfel:
O restric ție inegalitate din problema original ă (P) de tipul " " (respectiv de tipul " ") se
transform ă în egalitate prin ad ăugarea (respectiv prin sc ăderea) unei variabile nenegative din
membrul s ău stâng. Aceste variabile se numesc variabile de abatere sau de ecart .
Restric țiile egalit ăți nu se modific ă.
Noile variabile introduse nu apar în func ția obiectiv a problemei originale (alt ernativ,
spunem c ă ele apar cu coeficien ți nuli)
Exemplul 1.4.1
()(max)
, ,Pf x x x
x x x
x x x
x x x
x x x
7 9 8
5 2 4
3 5
2 3 9
0 0 01 2 3
1 2 3
1 2 3
1 2 3
1 2 3
( )(max)
, ,…,FSPf x x x
x x x x
x x x
x x x x
x jj
7 9 8
5 2 4
3 5
2 3 9
0 151 2 3
1 2 3 4
1 2 3
1 2 3 5
Problema care apare în acest context este aceea de a explica modul în care se ob ține solu ția
optim ă a problemei (P) dac ă se cunoa ște solu ția optim ă a formei sale standard (FSP). Se poate ar ăta
ușor că între mul țimile de solu ții admisibile AP , ale problemei (P) și AFSP, ale problemei (FSP),
exist ă o coresponden ță bijectiv ă care conserv ă soluțiile optime. Vom ar ăta cum func ționeaz ă aceast ă
coresponden ță pe exemplul precedent.
Notând-o cu , aceasta corespondență va asocia unei solu ții admisibile
x = (
xxx1 23 ,, ) a
problemei (P) vectorul:
35
()(,,, , ) x xxxx xx x x x 1 2 3 1 2 3 1 2 3 5 2 49 2 3
care prin construc ție se dovede ște a fi o solu ție admisib ilă a problemei (FSP). Reciproc, unei solu ții
admisibile
~(~,~,~,~,~) x xxxxx 1 2 3 4 5 a problemei (FSP) coresponden ța invers ă -1 îi asociaz ă vectorul
(~,~,~) xxx1 2 3
care satisface în mod clar restric țiile problemei originale (P). Dac ă
x este solu ția optim ă a
problemei (P) atunci (
x) este solu ția optim ă a problemei (FSP) și reciproc, dac ă cunoa ștem solu ția
optim ă
~x a problemei (FSP) ,
1(~)x reprezint ă soluția optim ă a problemei (P).
În problemele concrete, variabilele de abatere au interpret ări economice precise așa că în
analiza solu ției optime valorile lor vor fi luate în considerare laolalt ă cu valorile variabilelor
originale. Astfel, în problema firmei (1.1, exemplul1)) variabilele de abatere xn+1, xn+2, …, xn+m
definite prin:
x b axi mni i ijj
jn
1
1,…,
reprezint ă cantități de resurse neconsumate și prin urmare cunoa șterea valorilor lor în solu ția
optim ă oferă indica ții utile în analiza modului în care sunt utilizate resursele firmei: mate rii prime,
capacit ăți de produc ție, for ță de munc ă, etc.
În problema dietei (1.1, exemplul 2)) variabilele de abatere:
x axbi mni ijj i
jn
1
1,…,
reprezint ă cantit ățile de principii nutritive cu care sunt dep ășite nivelele minimale specificate în
rețetă.
3.1.5 Rezolvarea grafic ă a problemelor de programare liniar ă
Să consider ăm problema:
(max)
,f x x
x x
x x
x x
x x
3 4
3 4 12
6
2 2
0 01 2
1 2
1 2
1 2
1 2
Identific ăm x1, x2 cu abscisa, respectiv ordonata unui punct din planul raportat la un sistem ortogonal
de axe. Este cunoscut faptul c ă mulțimea punctel or din plan ale c ăror coordonate satisfac prima
restric ție coincide cu unul din semiplanele determinate de dreapta d1 de ecua ție -3×1+4×2 = 12. Mai
precis, este vorba de semiplanul care con ține originea (0,0) , deoarece coordonatele acesteia satisfac
eviden t prima restric ție. În mod analog, urm ătoarele restric ții sunt verificate în semiplanele
determinate de dreapta d2 de ecua ție x1+x2 = 6 și respectiv d3 de ecua ție -2×1+x2 = 2 și care con țin
originea. În fine, condi ția x1 0 are loc în semiplanul “din drea pta” axei verticale, în timp ce condi ția
x2 0 are loc “deasupra” axei orizontale.
Soluțiile admisibile ale problemei se identific ă cu punctele comune celor cinci semiplane.
Acestea formeaz ă interiorul și frontiera poligonului OABCD din figura 1.5.1.
Funcția obiectiv determin ă – pentru f variabil – o mul țime de drepte paralele care
intersecteaz ă sau nu mul țimea A. Astfel punctele situate pe dreapta 3 x1+4×2=12 reprezint ă diferite
combina ții ale m ărimilor x1, x2 care dau func ției obiectiv f aceea și valoar e 12. Întruc ât aceast ă
dreapt ă taie A, rezult ă că problema are solu ții admisibile – chiar o infinitate – care ofer ă funcției
obiectiv valoarea 12. Dreapta 3 x1+4×2=24 nu mai taie A și deci nici o solu ție admisibil ă a problemei
I. PROGRAMARE LINIARA
36
nu este capabil ă să asigure fu ncției obiectiv valoarea 24. Conchidem c ă maximul func ției f este
“undeva” între 12 și 24. Se observ ă ușor că acest maxim se atinge în vârful C al frontierei lui
A. Punctul C este intersec ția dreptelor d1 și d2 și deci coordonatele sale, care reprezint ă soluția
optim ă a problemei, se determin ă rezolv ând sistemul format din ecua țiile celor dou ă drepte. Se
găsește în acest fel
x x112
7 230
7* *, maximul lui f fiind
222
7 . Solu ția optim ă satisface cu egalitate
primele dou ă restricții și cu inegalitate strict ă pe ceea de a treia.
Figura 1.5.1
În mod asem ănător se arat ă că dacă funcția de maximizat ar fi fost f = – x1+x2 atunci optimul
ar fi fost atins în vârful B de coordonate x1=4/5, x2=18/5 .
Examin ând ace st exemplu putem trage urm ătoarele concluzii :
1. Mul țimea A este convexă , adic ă o dat ă cu dou ă puncte con ține și segmentul care le
unește. O consecin ță intuitiv ă a acestei propriet ăți este c ă soluția optim ă, dac ă există, se g ăsește
“undeva” pe frontiera lui A .
2. Frontiera lui A este un contur poligonal cu un număr finit de vârfuri și o solu ție optim ă
se găsește neapărat într -unul din ele .
Aceste concluzii, care se confirm ă pe orice alt ă problem ă în dou ă sau trei variabile (mul țimea
soluțiilor admisi bile put ând fi “vizualizat ă“ în planul R2 sau spa țiul R3) au constituit sursa întregii
teorii a program ării liniare.
D C
B
A
O d2 d1
d3 x1 x2
f=12 f=
222
7 f=24
A
37
3.2. Dualitatea în programarea liniară
În principiu, oric ărei probleme de programare liniar ă i se asociaz ă o alta, n umită duala sa și
în esen ță teoria dualit ății const ă în studiul rela țiilor dintre cele dou ă probleme. Fire ște, construc ția
problemei duale depinde nemijlocit de structura problemei ini țiale denumit ă și problema primală .
Întotdeauna sensul optimiz ării în cele dou ă probleme este diferit: dac ă în primal ă funcția obiectiv se
maximizeaz ă (minimizeaz ă) în dual ă funcția obiectiv se minimizeaz ă (maximizeaz ă). Studiul și
interpretarea economic ă a problemei duale aduc informa ții suplimentare în analiza proceselor
economice și în fundamentarea deciziilor.
3.2.1 Reguli de construire a problemei duale
Pentru a conferi construc ției problemei duale maxima generalitate vom sl ăbi condi ția de
nenegativitate impus ă tuturor variabilelor, admi țând c ă unele din ele nu p ot lua dec ât valori
nepozitive ( 0) în timp ce altele pot lua orice valoare real ă.
Cu aceast ă observa ție duala unei probleme de programare liniar ă cu m restric ții și n variabile
se construie ște dup ă următoarele reguli:
1) Dac ă în primal ă funcția obiectiv se maximizeaz ă (respectiv se minimizeaz ă) în problema
duală funcția obiectiv se minimizeaz ă (respectiv se maximizeaz ă).
2) Restric ției de rang i , i=1,…,m din primal ă îi corespunde în dual ă o variabil ă ui; dac ă
restric ția primal ă este o inegalitate con cordant ă (respectiv neconcordant ă, respectiv o egalitate)
variabila dual ă asociat ă este nenegativ ă ( 0), ( respectiv nepozitiv ă ( 0), respectiv f ără restric ție
de semn).
3) Variabilei x j , j=1,…,n din problema primal ă îi corespunde în dual ă restric ția de rang j.
Membrul st âng al acestei restric ții este o combina ție liniar ă a variabilelor duale u i realizat ă cu
coeficien ții variabilei x j din toate restric țiile primalei (ace știa sunt a ij, i=1,…,m). Termenul s ău liber
este coeficientul c j al lui x j din funcția obiectiv primal ă. În fine, dac ă variabila primal ă xj este
nenegativ ă (respectiv nepozitiv ă, respectiv f ără restric ție de semn) restric ția dual ă asociat ă va fi o
inegalitate concordant ă (respectiv neconcordant ă, respectiv o egalitate).
4) Coeficien ții func ției obiectiv ai problemei duale sunt termenii liberi b i ai restric țiilor
problemei primale.
Exemplul 2.1.1
Problema primal ă Problema dual ă
3 2 4 6
2 2 5 9
6 2 3
0
0
0
8 3 5 71 2 3 4 5
1 3 4 5
1 2 3 4
1
2
3
4
5
1 2 3 4 5x x x x x
x x x x
x x x x
x
x
xfrs
xfrs
x
f x x x x x
…
…
max
u
ufrs
u
u u u
u u
u u u
u u u
u u
gu u u u1
2
3
1 2 3
1 3
1 2 3
1 2 3
1 2
1 2 30
0
3 2 8
2 6 3
2 1
4 5 2 5
7
6 9 3
…
min ()
CURSUL 7
I. PROGRAMARE LINIARA
38
Observa ții: 1) Problema dual ă are at âtea variabile (res pectiv restric ții) c âte restric ții
(respectiv variabile) are problema primal ă.
2) Regulile 1) – 4) pun în eviden ță următoarele coresponden țe de termeni prin trecere la
duală:
min
(restric ție) concordant ă
(restric ție) neconcordant ă
(restric ție) egalitate
termen liber al unei restric ții
max
(variabil ă) nenegativ ă
(variabil ă) nepozitiv ă
(variabil ă) fără restric ție de semn
coeficient al func ției obiectiv
3) Din construc ția de mai sus rezult ă următoarea concluzie:
Duala dualei este problema primală .
Spunem c ă dualitatea în programarea liniară are un caracter involutiv .
În consecin ță, fiind dat ă o problem ă de programare liniar ă (P) și duala sa (Q), vom vorbi
despre cuplul de probleme în dualitate (P,Q), f ără a mai specifica în mod expres care din probleme
este primala și care duala.
3.2.2. Dualele unor forme particulare de probleme de programare liniar ă
1) Duala unei forme canonice de maximizare este o form ă canonic ă de minimizare și
reciproc.
ax ax ax b
ax ax ax b
axax ax b
x
x
x
fcxcx cxnn
nn
m m mn n m
n
nn11 1 12 2 1 1
21 1 22 2 2 2
11 22
1
2
11 220
0
0
……………………………………….
max
u
u
u
auau au c
auau au c
auau au c
gbubu bum
m m
m m
n n mn m n
mm1
2
111 21 2 1 1
12 1 22 2 2 2
1 1 2 2
11 220
0
0
. ……….
………………………………………
min
Cu nota țiile m atriciale introduse în (1.3) la care se adaug ă:
uuu um 1 2,,…, , cuplul format din cele
două probleme de mai sus devine:
()
max ()PAx b
x
fx cx
0 (Q)
uA c
u
gu ub
0
min ()
2) Conservarea formei de prezentare se pierde atunci c ând se consider ă duala unei probleme
în form ă standard.
ax bi m ufrsi m
x j n auc j n
f cx g buijj i
jn
i
j iji j
im
jj ii
im
jn
1
1
1 11 1
0 1 1,…, … ,…,
,…, ,..,
max min
sau matricial:
39
()
max ()PAx b
x
fx cx
0
() (…)
min ()QuA c
uRfrs
guubm
(f.r.s. fără restric ție de semn!)
În mod analog se construie ște duala formei standard în care func ția obiectiv se minimizeaz ă:
()
min ()PAx b
x
fx cx
0
() …
max ()QuA c
ufrs
guub
Observa ție: De re ținut este faptul c ă dualele a dou ă probleme de programare liniar ă
echivalente sunt ele însele echivalente adică au aceea și mul țime de solu ții admisibile și acelea și
soluții optime.
3.2.3. Teoreme de dualitate
Cu nota țiile matriciale din (2.2) s ă consider ăm cuplul de probleme în dualitate în form ă
canonic ă:
()(max) ()
Pfxcx
Ax b
x
0
()(min) ()
Qguub
uA c
u
0
Teorema 2.3.1 Fie
x xx xnT1 2,,…, o solu ție admisibil ă a problemei (P) și
u uu um 1 2,,…,
o solu ție admisibil ă a problemei (Q). Atunci:
1)
fx gu () ()
2) Dacă
fx gu () () atunci
x este o solu ție optim ă a problemei (P) iar
u este o soluție
optim ă a problemei (Q).
Demonstrați e: 1) Prin ipoteză
Axbx, 0 și
uAc ,
u0 .Deducem că
uAxub și
uAxcx
(nenegativitatea vectorilor
x și
u este esențială!) de unde:
fxcxuAxubgu () ()
2) Dacă
fx gu () () și dacă
x nu ar fi soluție optimă a problemei (P) ar exista o
soluție admisibilă
x' mai bună, adică
fx fx (') () .Rezultă inegalitatea
fx gu (') () contrară
celor demonst rate la punctul precedent.
Clasificarea cuplurilor de probleme de programare liniar ă în dualitate este f ăcută de
următoarea teorem ă:
Teorema 2.3.2 (Teorema fundamental ă a dualit ății) Pentru un cuplu de probleme în
dualitate una și numai una din u rmătoarele situa ții este posibil ă:
1) Ambele probleme au solu ții admisibile; atunci ambele au solu ții optime și valorile optime
ale func țiilor obiectiv coincid :
fx gu () () .
2) Numai una din probleme are solu ții admisibile, iar cealalt ă nu are; a tunci problema
compatibil ă are optim infinit.
3) Nici una din probleme nu are solu ții admisibile.
I. PROGRAMARE LINIARA
40
Simetria teoremei 2.3.2 nu constituie totu și un r ăspuns pentru reciproca teoremei 2.3.1
Specific ăm acest lucru în mod expres pentru c ă în programarea nelin iară el nu are loc.
Teorema 2.3.3 Dacă una din problemele unui cuplu de probleme în dualitate a re soluție
optim ă atunci și cealalt ă are și valorile optime ale func țiilor obiectiv coincid.
Nu d ăm demonstra ția teoremei 2.3.2 deoarece preg ătirile necesare depășesc cadrul impus acest ui
curs. Vom demonstra însă teorema 2.3.3 dup ă ce vom prezenta metoda general ă de rezolvare a
problemelor de programare liniar ă.
Teorema 2.3.4 (Teorema ecarturilor complementare – TEC ) Fie (P,Q) un cuplu de
probleme canonice în dualitate:
cxxfxb Ax
P
)( max0 )(
ub uguc uA
Q
)( min0
Un cuplu de solu ții admisibile (
x ,
u) este un cuplu de soluții optime dacă și numai dac ă:
( )
( )uAcx
ubAx
0
0 (2.3.1)
Demonstrație: Să presupunem relațiile (2.3.1) verificate de cuplul (
x ,
u):
uAxcx
ubuAxcxub xu
0
0(,)
este un cuplu de soluții optime în virtutea teoremei
2.3.1.Reciproc, să presupunem că (
x ,
u) constituie un cuplu de soluții optime. Atunci
cxub ,în
virtutea teoremei fundamentale a dualității și prin urmare:
( ) ( ) uAcxubAx 0
Deoarece
x ,
u sunt soluții admisibile avem:
( ) ,( ) uAcx ubAx 0 0 și deci
( ) ,( ) uAcx ubAx 0 0
relații care arată că
x ,
u verifică (2.3.1).
În nota țiile sec țiunii (2.2) rela țiile matriciale (2.3.1) se pot scrie:
aucx
ub axiji j
im
j
jn
i
im
i ijj
jn
1 1
1 10
0
Aceste rela ții sunt echivalente cu:
aucx j n
ub ax i miji j
im
j
i i ijj
jn
1
10 1
0 1,…,
,…,
Verificarea acestor egalit ăți de c ătre un cuplu de solu ții admisibile
x xx xnT1 2,,…, și
u uu um 1 2,,,
reprezint ă deci o condiție necesară și suficientă de optimalitate .
Pe lângă formularea precedent ă, teorema 2.3.4. mai are următoarea interpretare:
Cuplul (
x ,
u) de solu ții admisibile este un cuplu de solu ții optime dac ă și numai dac ă verific ă
seturile de implica ții:
41
x au c
au b uj iji jim
iji ijn
i
0
01
1
u ax b
auc xi ijj
jn
i
iji
im
j j
0
01
1
Observa ție. Deși prezenta tă pe un cuplu de probleme canonice, teorema 2.3.4. este valabil ă
pentru orice cuplu de probleme în dualitate. Astfel pentru cuplul:
max fcx
Ax b
x
0
min
…gub
uA c
ufrs
ele se reduc la:
( ) ,…,. uA cx aucu j niji j
im
j
0 0 1
1
Și mai concret, consider ăm cuplul din:
Exemplul 2.3.1
()min
,,Pf x x x
x x x
x x x
x x x
xxx
5 2
6 2 3 6
3 2 12
2 4 4
01 2 3
1 2 3
1 2 3
1 2 3
1 2 3
()max
, …,Qg u u u
u u u
u u u
u u u
u ufrsu
6 12 4
6 2 5
2 3 2
3 2 4 1
0 01 2 3
1 2 3
1 2 3
1 2 3
1 2 3
Conform TEC , condi ția necesar ă și suficient ă pentru ca dou ă soluții admisibile ale celor dou ă
probleme:
x xxxT(,,)1 2 3 și
u uuu(,,)1 2 3
să fie optime este satisfacerea rela țiilor:
( ) ()
( ) ()
( ) ()
( ) ()
( ) (5)56 2 0 1
22 3 0 2
13 2 4 0 3
66 2 3 0 4
2 4 4 01 2 3 1
1 2 3 2
1 2 3 3
1 2 3 1
1 2 3 3
uu ux
u u ux
u u ux
x x xu
xx x u
O consecin ță important ă a TEC este faptul c ă rezolvarea unei probleme de programare liniar ă
este echivalent ă cu rezolvarea dualei sale în sensul c ă dacă se cunoa ște solu ția optim ă a uneia din ele
putem deduce relativ simplu solu ția optim ă a celeilalte. Pentru ilustrare vom determina solu ția
optim ă a problemei (P) din exemplul precedent știind c ă duala (Q) are solu ția optim ă u* de
componente:
u u u1 29
14 31
14 0* * *, , .
Înlocuind u* în (1) – (5) se constat ă că relațiile (2),(3),(4) sunt sat isfăcute de orice valori
numerice acordate variabilelor x1 , x2 , x3. În schimb din (1) și (5) ob ținem rela țiile: x1=0 și 2×1 – x2 +
4×3 – 4 = 0 care împreun ă cu restric ția egalitate din (P) constituie un sistem liniar:
x
x x x
x x x1
1 2 3
1 2 30
2 4 4
3 2 12
Rezolv ând siste mul, ob ținem solu ția optim ă a problemei (P):
x x x f fx gu g1 220
7 312
752
7 0* * *
max* *
min , , () ()
Echivalen ța amintit ă mai înainte este folositoare în rezolvarea efectiv ă a problemelor de
programare liniar ă știut fiind c ă efortul de calcul este relativ mai mic dac ă numărul restric țiilor este
I. PROGRAMARE LINIARA
42
mai mic. În consecin ță, pentru o problem ă cu multe restric ții și un num ăr restr âns de variabile, va fi
mai comod s ă rezolv ăm duala sa.
3.2.4. Interpretarea economic ă a dualit ății
Relu ăm problema firmei din sec țiunea 1.1 exemplul 1). Consider ăm o întreprindere care
produce bunurile G1,G2,…,G m la pre țurile c1,c2,…,c n folosind pentru aceasta mai multe resurse
R1,R2,…,R m disponibile în cantit ățile limitate b1,b2,…,b m. Consumurile specifice de resurse pentru
unul sau altul din bunurile realiz abile de c ătre firm ă sunt specificate în matricea:
Aa a a
a a a
a a an
n
m m mn
11 12 1
21 22 2
1 2
Obiectivul firmei este maximizarea veniturilor rezultate din v ânzarea bunurilor produse. În
ipotezele de liniaritate uzuale, programul liniar pentru determinarea combina ției optime de bunuri
este:
(P)
(max) ()
, ,,fx cxcx cx
ax ax ax b
ax ax ax b
axax ax b
x x xnn
nn
nn
m m mn n m
n
11 22
11 1 12 2 1 1
21 1 22 2 2 2
11 22
1 20 0 0
……………………………………..
Să notăm cu
x xx xn *(,,…,)* * *1 2 combina ția de bunuri care aduce firmei venitul maxim:
* *
22*
11 … *)( max*nnxc xcxc xff V
Dacă admitem c ă singura posibilitate a firmei de a ob ține venitul V* const ă în transformarea
resurselor disp onibile în bunuri conform programului x* și vânzarea acestora este natural s ă ne
întreb ăm care este contribu ția fiec ărei resurse în parte la formarea acestui venit.
La baza discu ției vom pune acelea și ipoteze de liniaritate care ne -au condus la modelul
matematic (P) și anume:
contribu ția unei resurse la venitul maxim al firmei este – până la o anumit ă limită – direct
propor țional ă cu cantitatea disponibil ă;
nivelul contribu ției unei resurse nu este condi ționat de celelalte resurse, ci numai de
cantitatea în care ea se afl ă disponibil ă.
Să notăm atunci cu
uu um 1 2* * *,,…, aportul unei unit ăți din resursa R1, din resursa R2, ș.a.m.d. la
formarea venitului maxim V*. În virtutea ipotezelor de liniaritate amintite putem scrie:
V bubu bumm * …* * *11 22
(2.4.1)
Producerea unei unit ăți din bunul Gj necesit ă a1j unități din resursa R1, a2j unități din resursa
R2, ….., amj unități din resursa Rm.
Partea din venitul maxim V* corespunz ătoare acestor cantit ăți este:
auau auj j mj m 11 2 2* * *…
Aceast ă mărime trebuie s ă acopere pre țul pe care firma îl încaseaz ă prin v ânzare de vreme ce ea nu
are alte resurse de formare a venitului în afara transform ării resurselor în bunuri. Se conchide c ă
sistemul
u uu um *(,,…,)* * *1 2 trebuie s ă satisfacă relațiile:
43
au au au c
au au au c
au au au cm m
m m
n n mn m n111 21 2 1 1
12 1 22 2 2 2
1 1 2 2* * *
* * *
* * *…
…
…
…………………….. (2.4.2)
și de asemen ea condi țiile de nenegativitate:
u u um 1 20 0 0* * *, ,…, (2.4.3)
Sunt suficiente rela țiile (2.4.1) – (2.4.3) pe ntru determinarea efectiv ă a valorilor
uu um 1 2* * *,,…, ? Teoria
dualit ății dă un răspuns afirmativ pe baza urm ătoarelor observa ții:
1) Relațiile (2.4.2) și (2.4.3) arat ă că
u uu um *(,,…,)* * *1 2 constituie o solu ție admisibil ă a
dualei (Q) asociat ă problemei (P):
()(min) () …
…
…
……………………………..
…
, ,…,Qgxbubu bu
auau au c
auau au c
auau au c
u u umm
m m
m m
n nn mn m n
m
11 22
111 21 2 1 1
12 1 22 2 2 2
1 1 2
1 20 0 0
2) Relația (2.4.1) rescris ă în forma f(x*) = g(u*), coroborat ă cu teorema de dualitate 2.3.1, ne
arată că u* este chiar solu ția optim ă a problemei duale Q.
Astfel, am g ăsit un con ținut economic coerent variabilelor duale u1, u2,…, um din problema dual ă (Q).
Ele reprezint ă niște valori bănești asociate la câte o unitate din fiecare resursă disponibilă a firmei
și exprim ă aportul unitar al fiec ărei resurse la formarea venitului maxim . Strict dimensional,
variabilele u1, u2,…, um au semnifica ția unor prețuri atașate resurselor. Totu și aceste pre țuri nu au
nimic comun cu valoarea intrinsec ă a resurselor ci – așa cum a rezultat din interpretarea dat ă –
reflect ă numai m ăsura particip ării lor la formarea venitului maxim. To cmai pentru a preveni
identificarea lor cu pre țurile reale ale resurselor, în literatura de specialitate, aceste entit ăți au fost
denumite prețuri umbră (shadow prices ). A rezultat de asemen ea și o modalitate de calcul a acestor
mărimi: se rezolv ă problema duală (Q).
Teoria dualit ății arat ă că venitul maxim V* al firmei – privit ca func ție de cantit ățile
disponibile de resurse – depinde liniar de aceste disponibile prin intermediul pre țurilor duale optime
– vezi rela ția (2.4.1)
În consecin ță :
V
bu i m
ii*
*,…, 1 (2.4.4)
Prin urmare pre țurile duale optime ne arat ă cu cât se modific ă venitul maxim V* al firmei la
o varia ție cu o unitate a disponibilului unei resurse.
Este important de re ținut faptul c ă aceste concluzii rămân valabile numai în situa ția în care
componentele vectorului b variaz ă între anumite limite! În cazul general, atunci c ând se iau în
considerare toate valorile posibile ale lui b, adic ă
bRm , func ția V*(b) este subadi tivă și pozitiv
omogen ă. Aceasta înseamn ă:
Vbb VbVb bbR
Vtb tVb t bRm
m* * *
* *( ') () (') (),'
() () ,
( )0
I. PROGRAMARE LINIARA
44
Reamintim c ă în baza TEC soluțiile optime x*, u* al problemelor (P) și (Q) satisfac rela țiile:
x au au au c
axax ax b u
u axax ax b
au au au c xj j j mj m j
i i inn i i
i i i inn i
j j mj m j j* * * *
* * * *
* * * *
* * * *…
…
…
…
0
0
0
01 1 2 2
11 22
11 22
1 1 2 2
(..)
(..')
(..)
(..')245
245
246
246
(2.4.5) arat ă că dacă bunul Gj intră în combina ția optim ă atunci pre țul său este egal cu partea din
venitul maxim al firmei corespunz ătoare resurselor încorporate într-o unitate din el.
(2.4.5') arat ă că dacă o resurs ă nu este prev ăzută a se consuma în întregime – spunem c ă este
excedentar ă – prețul său dual este 0. Aceast ă concluzie reprezint ă versiunea liniar ă a
legii cererii și ofertei – prețul unei m ărfi pentru care oferta este mai mare dec ât cererea
trebuie s ă scadă.
(2.4.6) arat ă că o resurs ă cu pre ț dual semnificativ trebuie consumat ă în întregime; cre șterea cu o
unitate a disponibilului aduc ând o cre ștere a venitului maxim conform (2.4.4).
(2.4.6') arat ă că dacă pentru un bun valoarea resurselor încorporate într-o unitate – valoare
măsurat ă în pre țurile duale optime – depășește pre țul său atunci acesta nu intr ă în
combina ția optimal ă. Diferen ța
au cijj j
im*
1 reprezint ă pierderea poten țială de venit pe
care firma o va înregistra dac ă totuși decide realizarea unei unit ăți din bunul j.
Condi țiile (2.4.5), (2.4.5'), (2.4.6), (2.4.6') date de TEC se mai numesc și condiții de echilibru
de unde și numele de prețuri de echilibru dat uneori pre țurilor duale optime.
3.3. Structura mulțimii soluțiilor admisibile ale unei probleme de
programare liniară
În aceast ă secțiune ne vom opri asupra principalelor propriet ăți geometrice pe care le posed ă
mulțimea solu țiilor unui sistem de ecua ții și inecua ții liniare. Aceste propriet ăți sunt determinante în
înțelegerea mecanismului metodei simplex de rezolvare a programelor liniare.
Parcurgerea acest ei sec țiuni necesit ă câteva rudimente de calcul matricial și algebr ă liniar ă.
Vectorii cu care se va opera vor fi sub înțeleși, dup ă caz, fie linii fie coloane. De regul ă, scrierea în
text a unui vector se va face în linie ca de exemplu
vaa am (,,…,)1 2 ; dac ă este necesar ca
v să fie
considerat vector coloan ă se va folosi operatorul de transpunere:
vaa am (,,…,)1 2T.
3.3.1 Câteva elemente de analiză convexă liniară
Fiind date dou ă puncte
xyRn, mulțimea:
1 0, ) 1( , y x z yx
se nume ște segment (închis) cu extremit ățile x și y. Se știe că în R2 sau în R3 acest concept se
suprapune peste conceptul geometric uzual. Pentru
0 , respectiv
1 , avem
zx , respectiv
zy
. Punctele
z x y ( ) 1 corespunz ătoare valorilor
(,)01 se numesc puncte
interioare ale segmentului
xy, . Pentru
1
2 găsim
z xy1
2( ) mijlocul segmentului
xy,
.
O mul țime
X Rn se zice convexă dacă o dat ă cu dou ă puncte con ține și segmentul care le
unește.
45
Formal :
Xconvex xyX z x yX ă (), ,() ,,( ) 01 1
Se verific ă imediat c ă intersec ția mai multor mul țimi convexe este o mul țime convex ă.
Fie
aaa an (,,…,)1 2 un vector nenul și
b un scalar. Este u șor de v ăzut c ă mulțimea:
S x xx x ax b axax axbnT
nn (,,…,) …1 2 11 22
este convex ă. Ea se nume ște semispațiu , în timp ce mul țimea:
H x xx x ax b axax ax bnT
nn (,,…,) …1 2 11 22
se nume ște hiperplan . Este clar c ă și H este o mul țime convex ă ca intersec ție a semispa țiului S de
mai sus, cu semispa țiul:
S xRax b ax b axax ax bn
nn'() … 11 22
O intersec ție finit ă de semispa ții se nume ște mulțime poliedrală . Evident, o mul țime
poliedral ă este convex ă, reciproca nefiind în general adev ărată.
În figura 3 .1.1 sunt prezentate c âteva mul țimi convexe și neconvexe în plan. Este clar c ă
mulțimile a) și b) nu sunt convexe. Discul c) este o mul țime convex ă dar nu este poliedral ă, fiind în
fapt intersec ția infinit ă a tuturor semispa țiilor care con țin discul și sun t mărginite de tangentele la
circumferin ță. Poligonul convex d) este intersec ția a 4 semispa ții așa cum se arat ă în fig.3.1.2
S1 S2 S3
S4
Figura 3.1.2
a) poligon concav b) coroană circulară c) disc
d) poligon convex e) mulțime poliedrală nem ărginită
Notă: Toate mul țimile specificate sunt presupuse închise adică își con țin frontierele .
Figura 3.1.1
I. PROGRAMARE LINIARA
46
Din cele de mai sus rezult ă că orice mulțime poliedral ă în
Rn se identific ă cu mu lțimea
soluțiilor unui sistem de ecua ții și/sau inecua ții liniare în n variabile. În particular:
Mulțimea AP a solu țiilor admisibile ale unui program liniar (P) este o mulțime convexă ,
poliedral ă și închis ă. Frontiera sa se compune din toate punctele al e căror coordonate satisfac cu
egalitate cel pu țin una din restric ții.
Se nume ște vârf al unei mul țimi convexe
X Rn un punct
vX cu proprietatea c ă nu
exist ă un segment [ x,y]
X care s ă conțină pe v ca punc t interior. În
R2 sau
R3 regăsim conceptul
geometric uzual.
O mul țime poliedral ă are întotdeauna un num ăr finit de v ârfuri (posibil nici unul ); de
exemplu, poligonul d) din fig. 3.1.1 are patru v ârfuri în timp ce un semi spațiu nu are v ârfuri. Discul
c) are o infinitate de v ârfuri: orice punct de pe circumferin ță are aceast ă calitate.
Mulțimile d) și e) din fig.3.1.1 sunt am ândou ă poliedrale dar e) este nemărginit ă. Pentru a
caracteriza aceast ă proprietate avem nevoie de un nou concept , cel de rază extrem ă. Pentru a nu
depăși cadrul orar al cursului vom lăsa la latitudinea cititorului aprofundarea conceptului utilizând ca
suport bibliografic www.asecib.ase.ro – Cursuri on -line – 9. Nica V. și colectiv, Cercetări
Operaționale I . Vom caracteriza însă în detaliu această situație în cadrul metodei Simplex de
rezolvare a programelor liniare (vezi secțiunea 4 a Cap. 3).
3.3.2 Teorema centrală a programării liniare
Să consider ăm acum un program liniar (P) în care func ția obiectiv se maximizeaz ă și să ne
situăm în cazul în care programul (P) este compatibil adic ă mulțimea solu țiilor sale admisibile AP
este nevid ă. Am v ăzut c ă AP este o mul țime poliedral ă și convex ă având un num ăr fini t de v ârfuri
vv v1 2,,…..,p
. Așa cum va rezulta din sec țiunea 4.1, AP are cel pu țin un v ârf, adic ă
p1 . Vom
enun ța acum teorema central ă a program ării liniare .
TEOREMA*). Dacă programul (P) are optim finit, atunci o solu ție op timă se găsește într-
unul din v ârfurile mul țimii solu țiilor admisibile AP .
Importanța acestei teoreme este covârșitoare: ea reduce problema găsirii unei soluții optime
x*
din mulțimea, în general infinită, AP a tuturor soluțiilor admis ibile ale programului (P), la
identificarea acestei soluții în mulțimea finită a vârfurilor lui AP.
Recapitul ând modul în care diferitele propriet ăți discutate au fost implicate în ob ținerea
acestui rezultat fundamental s ă reținem c ă:
Convexitatea mul țimii solu țiilor admisibile AP situeaz ă soluțiile optime, dac ă acestea
există, pe frontiera lui AP;
Deoarece AP este poliedral ă, iar func ția obiectiv este liniar ă, cel puțin una din solu țiile
optime este un v ârf al lui AP.
Teorema furnizeaz ă următorul proced eu "naiv" de rezolvare a unui program liniar (P):
se "genereaz ă" lista (finit ă) a vârfurilor mul țimii AP;
*) NOTĂ: Pentru demonstrațiile Teoremelor și Lemelor din acest capitol, vezi www.asecib.ase.ro – Cursuri on -line – 9.
Nica V. și colectiv, Cercetări Operaționale I .
47
prin înlocuire succesiv ă în func ția obiectiv se re ține v ârful care ofer ă acesteia valoarea
maxim ă (sau minimă, după caz) .
Procedeul ridic ă la rândul său urm ătoarele probleme principiale :
1) Cum recunoa ștem compatibilitatea programului (P) ?
2) Cum "calcul ăm" un v ârf al mul țimii AP sau mai corect spus cum se caracterizeaz ă
"algebric" un v ârf ?
3) Pentru ob ținerea solu ției optime este necesar s ă generăm toate v ârfurile mul țimii AP?
întrebarea este serioas ă deoarece și pentru programe liniare de dimensiuni reduse (adic ă cu un num ăr
relativ mic de restric ții și variabile) num ărul vârfurilor este foarte mare.
4) Chiar dac ă reușim, prin enumerarea expli cită a tuturor v ârfurilor, s ă găsim pe acela care
maximizeaz ă funcția obiectiv, aceasta nu înseamn ă obligatoriu c ă am rezolvat programul dat! Este
posibil ca programul respectiv s ă aibă optim infinit! Cum se recunoa ște acest fapt?
Vom r ăspunde progresiv la toate chestiunile men ționate în sec țiunile urm ătoare.
3.3.3 Corespondența AP ~ AFSP
Consider ăm o problem ă de programare liniar ă (P) care con ține cel pu țin o restric ție inegalitate
și fie (FSP) forma sa standard (vezi sec țiunea 1.4) Pentru simplif icarea nota țiilor, vom presupune c ă
(P) este în formă canonică de maximizare :
()max
Pfcx
Ax b
x
0
unde:
Aa a a
a a a
a a abb
b
bxx
x
x
ccc cn
n
m m mn m n
n
11 12 1
21 22 2
1 21
21
2
1 2
(3.3.1)
știm din sec țiunea 1.3 c ă orice program liniar poate fi scris în aceast ă form ă. Forma standard a
programului (P) va fi:
( )max
,FSPfcx
Ax yb
x y
0 0
în care:
yy
y
ym
1
2
este vectorul variabilelor de abatere.
Între mul țimile de solu ții admisibile AP Rn și AFSP Rn+m exist ă o coresponden ță bijectiv ă (x)
= (x, y) , unde y = b – Ax, a cărei invers ă este proiec ția -1(x,y) = x . Am remarcat deja în sec țiunea
1.4 c ă prin coresponden ța , solu țiile optime ale celor dou ă probleme se corespund. În fapt, are
următoarea proprietate mai general ă.
Teorema 3.3.1 Dacă x este un v ârf al mul țimii AP atunci (x) = (x, y) cu y = b – Ax este un
vârf al mul țimii AFSP . Reciproc, dac ă (x, y) este un v ârf al mul țimii AFSP atunci -1(x,y) = x este un
vârf al mul țimii AP .
I. PROGRAMARE LINIARA
48
În baza acestei teoreme precum și a teoremei centrale a program ării liniare (secțiunea 3.2), pentru a
rezolva problema (P) este suficient s ă căutăm soluția optimă a formei sale standard (FSP) printre
vârfurile mul țimii AFSP .
Vom vedea în sec țiunea urm ătoare cum se caracterizeaz ă “algebric” v ârfurile mul țimii solu țiilor
admisibil e ale unui program liniar în form ă standard. Tot acolo vom ar ăta că dacă un program (P)
este compatibil atunci AP are cel pu țin un v ârf și în orice caz un num ăr finit de asemenea elemente.
Pe baza acestor rezultate, vom putea descrie în paragraful 4 o meto dă efectiv ă de rezolvare a unei
probleme de programare liniar ă.
3.3.4. Solu ții de baz ă ale unui program liniar
Să consider ăm acum un program liniar (P) în form ă standard:
()max
Pfcx
Ax b
x
0
în care masivele A,b,c,x au semnifica țiile din (3.3.1). Vom pune în eviden ță coloanele matricii A:
A = [A1 , A2 , … , An ]
Defini ție: Soluția
x xx xnT(,,…,)1 2 a problemei în form ă standard (P), nu neap ărat
admisibil ă, se nume ște soluție de bază dacă mulțimea coloanelor Ai corespunz ătoare componentelor
xi
0 este liniar independentă .
Fie I(
x) mulțimea indicilor i {1, 2,…, m} cu proprietatea c ă
xi 0.
Lema 1 : Dacă
x și
x sunt solu ții de baz ă ale programului (P) și I(
x ) I(
x) atunci
x
=
x (și deci I(
x ) = I(
x )).
Demonstrație: Este clar că
xi =
xi = 0 pentru indicii i I(
x). Atunci egalitățile:
xA xA bii
iIxii
iIx
() ()
implică:
( )
()xxAi ii
iIx
0
de unde rezultă
xi =
xi pentru toți i I(
x), deoarece prin ipoteză coloanele Ai , i I(
x) sunt
liniar independente.
Lema 2 : Fie
x xx xnT(,,…,)1 2 o solu ție admisibil ă a problemei (P) care nu este solu ție de
bază. Atunci exist ă un vector y Rn și un interval [ ,
] Rn {- , +} astfel încât:
1) Ay = 0;
2) [ ,
] con ține pe 0 și nu se reduce la acest punct; și
nu sunt simultan infinite;
3) pentru orice [ ,
] vectorul x( ) =
x + y este o solu ție admisibil ă a problemei (P);
4) Dacă de exemplu,
este finit și
x = x(
) atunci I(
x ) I(
x) dar I(
x ) I(
x) - 1
adică
x are mai pu ține compo nente nenule dec ât
x .
CURSUL 8
49
Demonstrație: Din ipoteză rezultă că mulțimea coloanelor Ai , i I(
x) este liniar independentă.
Există prin urmare scalarii yi , i I(
x) nu toți nuli astfel încât:
yAii
iIx
()0
Punând yi = 0 pentru i I(
x) obținem un vector y = (y 1 ,y2 ,…,y n) Rn cu proprietatea că:
yA Ayii
in
10 0
Afirmația 1) este demonstrată.
Pentru orice R vectorul x() =
x + y este o soluție a problem ei (P) deoarece Ax() =
A
x+ Ay =b.
Impunând condiția de admisibilitate x() 0 obținem pentru intervalul de valori permise [ ,
] în care:
=
iIxyi
i
ix
y
(),max
0
0 daca toti yi
=
iIxyi
i
ix
y
(),min
0
0 daca toti yi
Avem < 0 <
și deoarece y 0, cel puțin una din extremitățile ,
este finită. Astfel și
afirmațiile 2) , 3) sunt probate.
Să presupunem, în final că
este finit. Atunci va exista un indice r I(
x) astfel că : yr <
0 și
= –
x
yr
r .Dacă
x = x(
) este clar că I(
x ) I(
x) și cum
x x yr r r 0 iar
xr0
urmează că I(
x ) < I(
x) și ultima afirmație este dovedită.
Teorema 3.4.1 O solu ție admisibil ă
x xx xnT(,,…,)1 2 a problemei (P) este un vârf al
mulțimii AP dacă și numai dac ă
x este o solu ție de baz ă.
Demonstrație: Să presupunem că
x este vârf dar nu este soluție de bază. Conform lemei 2 există
y Rn cu Ay = 0 și intervalul [ ,
] care conține pe 0 și nu se reduce la acesta, astfel încât x()
=
x+ y să fie o soluție a programului (P) oricare ar fi [ ,
]. Alegem > 0 suficient de
mic astfel încât [ - ,+ ] [ ,
] și punem: x1 =
x-y, x2 =
x+y . Atunci x1,x2 AP , x1 x2 și
x xx1
21 2( )
în contradicție cu ipoteza că
x este vârf al mulțimii AP .
Pentru reciprocă să presupunem că
x este o soluție de bază fără a fi vârf. Atunci există
x1,x2 AP, x1 x2 și (0,1) astfel încât
x = (1 - )x1 + x2. Pentru iI(
x) avem
( ) 1 01 2 x xi i
și cum
x xi i1 20 0, rezultă
x xi i1 20 . în co nsecință, I(x1) I(
x),
I(x2) I(
x) și în virtutea lemei 1 rezultă x1 = x2 =
x, în contradicție cu ipoteza făcută.
Teorema 3.4.2 Dacă programul în form ă standard (P) este compatibil atunci mul țimea
soluțiilor sale admisibile AP are cel pu țin o solu ție de baz ă, deci un v ârf.
Demonstrație Fie
x =
(,,…,) xx xnT
1 2 o soluție admisibilă a problemei (P). Vom proceda prin
inducție după numărul k al componentelor
xi0 .Dacă k = 0 atunci
x = (0,0,…,0) este o soluție
de bază întrucât o mulțime vidă de vectori este, prin convenție,liniar independentă. Dacă k > 0
există două situații de examinat:
1) Coloanele Ai, i I(
x) sunt li niar independente. Atunci
x este o soluție de bază.
2) Coloanele Ai, i I(
x) sunt liniar dependente. Conform lemei 2 va exista o soluție
I. PROGRAMARE LINIARA
50
admisibilă
x cu I(
x ) I(
x) dar cu mai puține componente nenule decât
x . Repetând
raționamentul, este clar că într -un număr finit de pași se ajunge la situația 1) adică la o soluție de
bază.
Consecin ță: Mulțimea AP a solu țiilor admisibile ale unui program liniar compatibil are cel
puțin un v ârf.
Demonstrație: Să presupunem că (P) nu este în formă standard, altminteri avem teorema 3.4.2.
Fie (FSP) forma standard a programului (P). Deoarece avem corespondența bijectivă : AP AFSP
deducem că AFSP pentru că prin ipoteză AP . Prin teorema 3.4.2 mulțimea AFSP are cel puțin
un vârf; acesta, prin proiecția -1 va fi un vârf al mulțimii AP , grație teoremei 3.3.1.
Având în vedere caracterizarea algebric ă a vârfurilor dat ă în teorema 3 .4.1, teorema central ă a
program ării liniare poate fi formulat ă și în urm ătorii termeni.
Teorema 3.4.3 Dacă un program liniar în form ă standard are optim finit, cel pu țin una din
soluțiile sale optime este o solu ție de baz ă.
Mai r ămâne de ar ătat că mulțimea solu țiilor admisibile ale unui program liniar are un num ăr
finit de v ârfuri. În virtutea teoremelor 3.3.1 și 3.4.1, aceasta revine la a ar ăta că un program liniar (P)
în form ă standard are un num ăr finit de solu ții admisibile de baz ă. Faptul rezult ă nemijlocit din aceea
că numărul sistemelor liniar independente ce pot fi extrase dintr -o mulțime finită de vectori este finit .
Vom preciza acest lucru sub forma unei teoreme în sec țiunea urm ătoare, în care vom introduce un
concept u șor diferit de cel de s oluție de baz ă, acela de soluție asociat ă unei baze a programului (P).
Noul concept are avantajul de a fi mai u șor de manipulat în practic ă.
3.3.5. Baze ale unui program liniar în form ă standard. Solu ția asociat ă unei baze
În nota țiile sec țiunii precedente fac em ipoteza:
rangA = m < n (3.5.1)
Ipoteza ne asigur ă că ecuațiile ce compun sistemul liniar Ax = b al restric țiilor sunt independente și
că acest sistem are o infinitate de solu ții. Să notăm că ipotez a nu implic ă în mod necesar și existen ța
soluțiilor admisibile (adic ă cu toate componentele nenegative) pentru sistemul considerat. Dup ă cum
vom vedea în sec țiunea 4.6 ipoteza f ăcută nu este deloc restrictiv ă.
Deoarece rangA = m, în matricea A va exista cel pu țin un grup de m coloane liniar
independente, constituind deci o baz ă a spa țiului Rm. Un asemenea grup se va numi bază a
programului (P) și num ărul acestora este finit , nedep ășind
Cn
mnmnm!
!( )! .
Fie B o baz ă a programului (P), I mulțimea indi cilor coloanelor din B și J mulțimea indicilor
coloanelor din A care nu sunt în B. Renumerot ând convenabil variabilele programului vom scrie
matricea A în forma:
A = [B , S] cu B = [Ai]i I , S = [Aj]j J
Parti ționăm corespunz ător vectorul (coloa nă) x al variabilelor:
xx
xx x x xB
SB
iiIS
jjJ
cu ,
ca și vectorul (linie) al coeficien ților func ției obiectiv:
51
c = [cB,cS] cu cB = [c i]i I , cS = [c j]j J
în raport cu baza B aleas ă, variabilele xi , i I se vor numi variabile bazice , iar toate celelalte
nebazice sau secundare .
Scriem sistemul Ax = b în forma:
BSx
xb Bx Sx bB
SB S,
Deoarece B este o baz ă a spa țiului Rm, B (ca matrice!) este nesingular ă deci inversabil ă. Înmul țind la
stânga cu B-1 obținem:
x Sx b SBSa bBbbB S
ijiIjJiiI
cu1 1
,, (3.5.2)
Va fi util s ă punem în eviden ță coloanele matricii S:
Jjj
Jjj
JjjA AB ABS
1 1
cu
A BA aj j
ijiI
1 (3.5.3)
Utiliz ăm (3.5.2) pentru a elimina din expresia func ției obiectiv variab ilele bazice:
fccx
xcx cx cbSx cxB SB
SBB SS B S SS
, ( )
cb cScx fcxB B S S SS( )
(3.5.4)
unde:
fcb cBb cbB B
iiiI
( )1 (3.5.5)
și:
c cSc cBSc cS B S B S
jjJ
( )1
în care:
ccA c cBA c ca cjB j
jB j
j iij jiI
( )1 (3.5.6)
Astfel, în raport cu baza B, programul (P) poate fi adus la urm ătoarea form ă echivalent ă, conform
(3.5.2) și (3.5.4):
0 ,0max
)(
S BS BSS
B
x xb xS xxcff
P
Jj xIi xIibxa xxc ff
P
j ii
Jjjij iJjjj
B
,0 ;,0max
)( (3.5.7)
(PB) se nume ște forma explicită a programului (P) în raport cu baza B . Compar ând (P B) cu (P)
constat ăm că efectul înmul țirii cu B -1 a sistemului Ax = b este explicitarea variabilelor bazice x i , iI
în func ție de cele nebazice x j , j J.
Luând în (P B):
xS = 0 xj = 0 , j J (3.5.8)
obținem:
I. PROGRAMARE LINIARA
52
x b xbiIB
i i (3.5.9)
Vectorul:
xb x
xB
S
0 (3.5.10)
este evident o solu ție a programului (P), numit ă soluția asociată bazei B . Vom spune c ă B este o
bază admisibil ă dacă soluția asociat ă (3.5.10) este admisibil ă, ceea ce revine la a spune c ă
b iIi0, .
Prin constru cție, soluția asociat ă unei baze a programului (P) este o solu ție de baz ă în sensul
defini ției din sec țiunea precedent ă. Reciproca nu este în general adev ărată. Astfel, dac ă
x =
(,,…,) xx xnT
1 2
este o solu ție de baz ă a programului ( P), num ărul componentelor nenule este m.
Dacă acest num ăr este exact m atunci
x este solu ția asociat ă bazei formate din coloanele matricii A
corespunz ătoare celor m componente nenule. Spunem în acest caz c ă
x este o soluție de bază
nedegenerată . Dacă numărul componentelor nenule este < m, coloanele corespunz ătoare acestor
componente pot fi completate p ână la o baz ă în mai multe moduri, astfel c ă
x se asociaz ă la mai
multe baze! Dac ă se întâmplă așa spunem c ă
x este o soluție degenerată .
Deoarece (P) are un număr finit de baze, el va avea și un număr finit de soluții asociate
acestor baze și de aici un număr finit de soluții de bază.
În baza rela țiilor (3.5.8), (3.5.9) constanta
f din (3.5.5) reprezint ă valoarea funcției obiectiv
a programului (P) în solu ția (3.5.10) asociat ă bazei B. Componentele
cj , j J (definite în (3.5.6)) ale
vectorului
cS din (3.5.4) vor juca un rol es ențial în caracterizarea optimalit ății unei solu ții admisibile
de baz ă. Ele se numesc costuri reduse (notate j în alte materiale de specialitate) și sunt întotdeauna
asociate variabilelor nebazice . Coeficien ții numerici ai formei explicite (3.5.7) se trec într-un tabel
(TB) al cărui format este indicat în tabelul 3.5.1. Tabelul (T B) se nume ște tabelul simplex asociat
bazei B. Coloana “B” con ține vectorii bazei B, coloana “CB” con ține Coeficien ții din func ția
obiectiv ai variabilelor Bazice iar în coloana “ VVB” apar Valorile Variabilelor Bazice. În ultima linie
a tabelului, numit ă și linia test , apar valoarea
f a func ției obiectiv în solu ția asociat ă bazei B precum
și costurile reduse
cj , j J corespunz ătoare coloanelor nebazice. Formula (3.5.5) arat ă că
f este
produsul scalar al coloanelor “CB” și “VVB” în timp ce rela ția (3.5.6) arat ă că
cj se ob ține din
produsul scalar al coloanelor “CB” și “Aj” scăzând costul cj scris deasupra col oanei “Aj”.
Tabelul 3.5.1
ci cr cj ck
CB B VVB Ai Ar Aj Ak
ci Ai bi 1 0 aij aik (TB)
cr Ar br 0 1 arj ark
f
f * *
cj
ck
Extindem defini ția costului redus și la coloanele “Ai” , i I :
ccci i i0 . Aceste costuri
reduse au fost notate în linia test cu asteriscuri (*) spre a le deosebi de eventualele costuri reduse nule
cj
, j J care, dup ă cum vom vedea în sec țiunea 3.4.2, indic ă – “la optim” – prezen ța mai multor
soluții optime de baz ă.
53
3.4. Metoda simplex
Deoarece știm c ă dacă programul în form ă standard (P) are optim finit o solu ție optim ă va fi
cu necesitate o solu ție de baz ă și deci va fi asociat ă unei baze B*, este natural s ă ne întreb ăm cum
găsim aceast ă bază optimal ă B*. Traduc ând în termeni algebrici procedeul geometric “naiv”, descris
în finalul sec țiunii 3.2, rezult ă următoarea procedur ă:
se genereaz ă toate bazele programului (P) și se calculeaz ă soluțiile asociate acestora;
se elimin ă soluțiile de baz ă neadmisibile și dintre cele admisibile se re ține acea solu ție care
oferă funcției obiectiv valoarea maxim ă.
Nu mai insist ăm asupra dezavantajelor și lipsurilor acestei scheme deoarece ele au fost deja
menționate în sec țiunea 3.2. “Metoda” descris ă are o alternativ ă care, din fericire, s -a dovedit a fi
deosebit de eficient ă din punct de vedere practic. Este vorba de Metoda Simplex datorat ă
matematicianului american G eorge B. Dantzig (1947).
Aceast ă metod ă este un procedeu de cercetare sistematic ă a solu țiilor admisibile de baz ă ale
unui program liniar în form ă standard (P). Ea presupune cunoscut ă o asemenea solu ție, numit ă
soluție ini țială sau de start și în continuare construie ște un șir de solu ții admisibile de baz ă de-a
lungul c ăruia valoarea func ției obiectiv crește progresiv . Metoda simplex ofer ă un test simplu de
recunoa ștere a optimalit ății unei solu ții de baz ă și de asemen ea un test de recunoa ștere a optimului
infinit. Practica numeric ă a arătat că numărul solu țiilor admisibile de baz ă efectiv generate este de
regul ă mult mai mic dec ât num ărul total al acestora .
Cu anumite precau ții, ușor de îndeplinit, metoda simplex garanteaz ă convergen ța procesului
iterativ în sensul c ă o baz ă admisibil ă cercetat ă la un moment dat nu mai revine în itera țiile ulterioare
(vezi sec țiunea 4.5). Cum num ărul bazelor este finit, urmeaz ă că într-un num ăr finit de pa și se ajunge
fie la solu ția optim ă fie la concluzia c ă programul are optim infinit.
Firește, în aceas tă descriere succint ă, am plecat de la ipoteza cunoa șterii unei solu ții
admisibile de baz ă inițiale, adic ă de la premiza c ă (P) este un program compatibil . În sec țiunea 4.3
vom vedea cum se face recunoa șterea incompatibilit ății unui program liniar.
3.4.1. Teorem ele fundamentale ale metodei simplex
În prezentarea fundamentelor teoretice ale metodei simplex vom folosi nota țiile introduse în
secțiunea 3.3.5. În mod constant vom presupune c ă soluția (3.5.10), asociat ă bazei B, este admisibil ă,
adică
b iIi0, .
Teorema A (testul de optimalitate): Dacă toți
c jJj0, atunci solu ția (3.5.10) asociat ă
bazei B este optim ă. Dac ă în plus
c jJj0, , atunci ea este și unica solu ție optim ă a programului
(P).
Demonstrație: Fie y = (y 1,y2,…,yn)T A o soluție admisibilă arbitrar aleasă. Deoarece y1 0, y 2
0, …,y n 0 vom avea:
fy f cy ffxjj
jJ() ()
Inegalitatea de mai sus arată că, dintre toate soluțiile admisibile ale programului(P),soluția
x din
(3.5.10) oferă fun cției obiectiv f cea mai mare valoare posibilă. Dacă costurile reduse sunt pozitive
și y
x atunci inegalitatea de mai sus este strictă, fapt care probează unicitatea soluției optime
x
.
I. PROGRAMARE LINIARA
54
Teorema B (recunoaștere a optim ului infinit ): Presupunem c ă există indicele kJ astfel c ă
ck0
și toți
a iI Aikk 0 0 , ( ) . Atunci programul (P) are optim infinit.
Demonstrație: Pornind de la soluția
x din (3.5.10) construim o soluție admisibi lă variabilă după
cum urmează. înlocuim în (3.5.7):
xk = 0 ; x j = 0 , j J , j k (4.1.1)
Rezultă:
x b aiIi i ik, (4.1.2)
Notăm cu
x () soluția ale cărei componente sunt definite în (4.1.1) și (4.1.2). Condiția enunțului
face ca
x () A , () 0. Evaluăm funcția obiectiv în soluția
x () :
fx fck (()) (4.1.3)
Rezultă imediat că:
lim(()) fx .Deci f este nemărginită superior pe A și ca urmare (P) are
optim infinit.
Teorema C (criteri ul de modificare a bazei): Presupunem c ă există k J astfel încât
ck0
dar exist ă și indici i I cu
a 0ik . Fie r I indicele determinat prin formula:
b
ab
ar
rk iIai
ik ik
0min (4.1.4)
Atunci grupul de coloane B' ob ținut din B înlocuind coloana Ar cu coloana Ak este o baz ă admisibil ă
a programului (P) și solu ția
x asociat ă ei este cel pu țin la fel de bun ă ca și solu ția
x asociat ă
bazei B, adic ă f(
x) f(
x).
Demonstrație: Din (4.1.4) rezultă că
a 0rk . Din Ak = B-1Ak avem:
A BA aA aAk k
iki
iIirrkr
,
Deoarece
a 0rk putem exprima Ar în funcție de Ai , i r și Ak:
Aa
aAaAr ik
rki
iIik rkk
,1
Din teorema substituției rezultă că sistemul B', format din coloanele Ai , i r și Ak, este o bază a
problemei (P).
Să luăm în soluția variabilă
x () construită în demonstrația teoremei B:
b
ar
rk (4.1.5)
Din formulele (4.1.1) , (4.1.2) rezultă:
xb
ax jJjk
x bb
aa iIkr
rkj
i ir
rkik
; , ,
,0
Pentru i = r avem
x bb
aar rr
rkrk 0 așa că soluția de mai sus poate fi rescris ă astfel:
x jJjkx
x bb
aa iIirxb
aj r
i ir
rkik kr
rk
0 0 , , ;
, , ; (4.1.6)
Notăm cu
x soluția ale cărei componente sunt definite în (4.1.6). Vom observa mai întâi
55
că
x este soluție admisibilă a problemei (P) , adică are toate componentele nenegative. Î ntr-
adevăr:
– dacă
a 0ik atunci x i 0;
– dacă
a 0ik atunci
bb
aab
ab
air
rkiki
ikr
rk 0 care are loc conform alegerii
indicelui r (vezi (4.1.4)).
În al doilea rând remarcăm că
x este soluția asociată bazei B'. într -adevăr, din (4.1.6) rezultă că în
x
toate variabilele secundare în raport cu baza B' au valoarea 0. Afirmația rezultă acum din
unicitatea soluției asociate unei baze.
Utilizând formulele ( 4.1.3) și (4.1.5) obținem:
fx fb
ac ffxr
rkk () () (4.1.7)
În concluzie,
x este cel puțin la fel de bună ca și
x .
Observa ții: 1) Bazele B și B' ap ărute în enun țul teoremei C difer ă una de alta printr -o
singur ă coloan ă a matricii A. Dou ă baze ale programului (P) cu aceast ă proprietate se vor numi în
continuare baze vecine și tot vecine se vor numi și solu țiile asociate.
2) Teoremele B și C afirm ă că dacă o solu ție de baz ă admisibil ă
x nu satisface criteriul de
optimalitate al teoremei A atunci sau (P) are optim infinit (Teorema B) sau, printre soluțiile vecine
cu
x exist ă cel pu țin una la fel de bun ă ca și
x dacă nu chiar mai bun ă (Teorema C) .
Recapitul ând materialul expus în aceast ă secțiune constat ăm că testarea optimalit ății solu ției
x
asociate bazei B presupune cunoa șterea formei explicite (3.5.7) a problemei ini țiale în raport cu
baza B. Mai mult, dac ă
x nu verific ă criteriul de optimalitate al teoremei A, construc ția solu ției de
bază mai bune
x se face cu ajutorul elementelor aceleia și forme (3.5.7). În consecin ță, testarea
optimalit ății solu ției
x asociat ă bazei vecine B' va necesita cunoa șterea formei explicite a problemei
inițiale în raport cu noua baz ă B':
()max
,
,,…,',
,
,Pff cx cx
x ax ax biIir
x ax ax b
xx xBjj
jJjkrr
i ijj
jJjkirr i
k kjj
jJjkkrr k
n
12 0 (4.1.8)
(Vom remarca faptul c ă unele elemente din (4.1.8) sunt deja evaluate! Astfel, termenii liberi, adic ă
valorile noilor variabile bazice, sunt da ți de (4.1.6) în timp ce constanta
f , care este valoarea
funcției obiectiv în noua solu ție de baz ă
x, a fost ob ținută în (4.1.7).)
Firește, (4.1.8) se poate ob ține ca și (3.5.7) prin înmul țirea la st ânga a sistemului original de
restric ții Ax = b cu matricea invers ă (B')-1. Putem deduce (4.1.8) direct din (3.5.7) cu ajutorul
următoarelor opera ții:
Din ecua ția r a sist emului (3.5.7):
x ax ax br rjj
jkrkk r
explicit ăm x k, împărțind rela ția cu
ark :
I. PROGRAMARE LINIARA
56
xa
axaxb
akrj
rkj
jk rkrr
rk
1 (4.1.9)
Substituim x k dat de (4.1.9) în celelalte ecua ții ale sistemului din ( 3.5.7). Ob ținem:
x aa
axa
ax bb
aa iIiri ijrj
rkj
jkik
rkr ir
rkik
( ) , , (4.1.10)
Ecua țiile (4.1.9) , (4.1.10) reprezint ă sistemul Ax = b explicitat în noile variabile bazice x i, i I, i r
și xk.
Mai departe substituim acela și xk și în expresia func ției obiectiv din (3.5.7). G ăsim:
ffb
ac ca
acxc
axr
rkk jrj
rkk jk
rkr
jk
( ) ( ) (4.1.11)
Astfel, am exprimat func ția obiectiv cu ajutorul noilor variabile nebazice x j, j J, j k și xr.
Prin urmare (4.1.9), (4.1.10) , (4.1.11) constituie forma explicit ă a problemei originale în
raport cu noua baz ă B'. Identific ând coeficien ții din aceste ecua ții cu coeficien ții corespunz ători din
(4.1.8) rezult ă formulele:
a aa
aaiIir
jJjkaa
aiIirij ijrj
rkik irik
rk,
,; ,
aa
ajJjk aakjrj
rkkr
rk, ;1 (4.1.12)
ffb
ac c ca
ac jJjk cc
ar
rkk j jrj
rkk rk
rk; , ;
cunoscute și sub numele de formule de schimbare a bazei.
3.4.2. Algoritmul simplex
Rezolvarea efectiv ă a unui program liniar în form ă standard (P) se face cu ajutorul
algoritmului simplex . Acesta este un pachet invariabil de in struc țiuni logice și de calcul care,
aplicate unei solu ții admisibile de baz ă a programului (P), stabile ște dac ă soluția respectiv ă este
optim ă și, în caz contrar, pune în eviden ță situa ția de optim infinit sau construie ște efectiv o solu ție
admisibil ă de bază mai bun ă decât cea curent ă.
Să consider ăm o baz ă admisibil ă B precum și forma explicit ă (PB) a programului (P) în raport
cu aceast ă bază. (vezi nota țiile sec țiunii 3.5)
În raport cu aceste date de intrare, con ținutul unei itera ții simplex este urm ătorul:
Pasul 1. (Test de optimalitate) Dac ă toți
c jJj0, soluția de baz ă curent ă (adic ă soluția
(3.5.10), asociat ă bazei B) este optim ă: STOP . Altminteri :
Pasul 2. Se alege indicele nebazic k J astfel ca :
57
c ck
jJj
min (4.2.1)
Pasul 3. Dacă:
a iI Aikk 0 0 , ( )
programul (P) are optim infinit : STOP. Altminteri :
Pasul 4. Se determin ă indicele bazic r I cu formula:
b
ab
ar
rk iIai
ik ik
0min (4.2.2)
Pasul 5. Se construie ște forma explicit ă a programului (P) în raport cu baza B' dedus ă din B
prin înlocuirea coloanei Ar cu coloana Ak. Se revine la Pasul 1 în cadrul u nei noi itera ții.
Observa ții: 1) La pasul 2 avem cu necesitate
ck0 . Despre coloana nebazic ă Ak vom spune
că intră în baza curent ă. În demonstra ția Teoremei C s -a arătat că varia ția valorii func ției obiectiv la
schimbarea coloanei bazic e Ar cu coloana Ak este dat ă de formula:
fx fxb
acr
rkk ()()
(4.2.3)
Cum
b
ar
rk0 (vezi (4.2.2)) urmeaz ă că introducerea în baz ă a oric ărei coloane nebazice Aj cu
cj0
îmbun ătățește valoarea curent ă a func ției obiectiv. Alegerea coloanei nebazice care va intra în baza
curent ă după formula (4.2.1) asigur ă funcției obiectiv cea mai mare vitez ă de varia ție și în general
conduce la terminarea algoritmului în mai puține itera ții.
2) Se poate ar ăta ușor că dacă situa ția descris ă în pasul 3 are loc atunci vectorul w =
(w1,w2,…,w n)T definit prin:
w a iIw jJjkwi ik j k , ; , , ; 0 1 (4.2.4)
este o raz ă extrem ă a mul țimii poliedrale AP.
3) Despre coloana bazic ă Ar al cărei indice se determin ă cu formula (4. 2.2) vom spune c ă
părăsește baza curent ă. Alegerea ei dup ă formula amintit ă asigur ă admisibilitatea solu ției asociate
noii baze B'.
4) Elementul
ark , unde k este indicele coloanei care intr ă în baz ă iar r este indicele coloanei
care iese din baz ă se nume ște pivot și opera ția de calculare a elementelor formei explicite în raport cu
baza B' din elementele formei explicite în raport cu baza veche B prin aplicarea formulelor d e
schimbare a bazei (4.1.12) poart ă numele de pivotare gaussian ă.
5) În principiu, problemele de minimizare se reduc la cele de maximizare în baza rela ției
(1.3.1). Algoritmul simplex descris mai sus este aplicabil și problemelor de minimizare cu
următoarele mici modific ări:
în pasul 1: solu ția curent ă este optim ă dacă
c jJj0, ;
în pasul 2: pentru determinarea indicelui coloanei nebazice care intr ă în baza curent ă se va
utiliza formula
c ck
jJj
max
De aceast ă dată vom avea
ck0.
I. PROGRAMARE LINIARA
58
6) Să presupunem c ă baza curent ă B este optimal ă (adic ă soluția asociat ă ei verific ă testul de
optimalitate) și că exist ă indici nebazici j J cu
cj0 . Formula (4.2.3) arat ă că introducerea în baza
curent ă a oric ărei coloane Ak pentru care
ck0 conduce la solu ții de baz ă la fel de bune ca și cea
curent ă, deci optime. Se poate ar ăta că dacă
xx xpp 122 ,,…,, sunt toate solu țiile de baz ă optime
ale programului (P) atunci acesta are o infinitate de solu ții optime c are au forma:
x x x x cu sipp
p p 11
22
1 2 1 2 0 1 … ,,…, …
(altfel spus, orice solu ție optim ă este o combina ție convex ă a solu țiilor optime de baz ă)
7) În rezolvarea manual ă a programelor liniare (fire ște de mici dimensiuni) se utilizeaz ă
tabelele simplex (3.5.1) asociate di feritelor baze cercetate. Aceste tabele se deduc unul din altul prin
pivotare gaussian ă.
În continuare vom aplica algoritmul simplex pe o problem ă simpl ă, în dou ă variabile, pentru a
putea ilustra grafic modul în care ac ționeaz ă procedura.
Exemplul 4.2.1 Consider ăm programul:
()max
; ;
,Pf x x
x x x x x x
x x
2
43 18 2 6
0 01 2
1 2 1 2 1 2
1 2
a cărui mul țime de solu ții admisibile AP este vizualizat ă în figura 4.2.1.
Figura 4.2.1
Aducem (P) la forma standard ad ăugând variabilele de abatere x3, x4, x5:
( )max
, ,…,FSPf x x
x x x
x x x
x x x
x jj
2
4
3 18
2 6
0 151 2
1 2 3
1 2 4
1 2 5
AP
S0: x1=0, x 2=0 S1: x1=4, x 2=0 S2: x1=7, x 2=3 S3: x1=42/5, x 2=36/5 x2
x1
59
Se observ ă că matricea A a coeficien ților formei standard (FSP) con ține baza unitar ă E = [ A3,A4,A5]
(deci FSP este chiar forma bună a lui P pentru aplicarea algoritmului Simplex Primal) a cărei solu ție
asociat ă:
1 = 0 , x 2 = 0 , x 3 = 4 , x 4 = 18 , x5 = 6
este admisibil ă. În continuare sunt date tabelele rezultate prin aplicarea algoritmului simplex (tabelele
4.2.1 – 4.2.4). În partea dreapt ă am indicat formele explicite ale problemei (FSP) în raport cu bazele
cercetate. În trei itera ții s-a obținut solu ția optim ă
x x142
5 236
5 , , valoarea maxim ă a func ției
obiectiv fiind 24; variabilele de abatere au în solu ția optim ă valorile
x x x314
5 4 50 , .
2 1 0 0 0 Formele explicite ale problemei (FSP) în
cB B VVB A1 A2 A3 A4 A5 raport cu baz ele cercetate
0 A3 4 1 -1 1 0 0 x1 – x2 + x 3 = 4
0 A4 18 3 -1 0 1 0 3×1 – x2 +x4 = 18
0 A5 6 -1 2 0 0 1 -x1+2x 2 +x5 = 6
f 0 -2 -1 * * * -2×1 -x2 +f = 0
22 A1 4 1 -1 1 0 0 x1 -x2 + x 3 = 4
0 A4 6 0 2 -3 1 0 2×2 -3×3 +x4 = 6
0 A5 10 0 1 1 0 1 x2 + x 3 +x5 = 10
f 8 * -3 2 * * -3×2 +2x 3 +f = 8
2 A1 7 1 0 -1/2 1/2 0 x1 – 1/2x 3+1/2x 4 = 7
1 A2 3 0 1 -3/2 1/2 0 x2 -3/2x 3+1/2x 4 = 3
0 A5 7 0 0 5/2 -1/2 1 5/2x 3 – 1/2x 4 +x5 = 7
f 17 * * -5/2 3/2 * -5/2x 3+3/2x 4 +f = 17
2 A1 42/5 1 0 0 2/5 1/5 x1 +2/5x 4 +1/2x 5 = 42/5
1 A2 36/5 0 1 0 1/5 3/5 x2 +1/5x 4 +3/5x 5 = 36/5
0 A3 14/5 0 0 1 -1/5 2/5 x3 -1/5x 4 +2/5x 5 = 14/5
f 24 * * * 1 1 x4 + x 5 +f = 24
Tabelele 4.2.1 – 4.2.4
Soluția
Baza Componentele
soluției de bază
generată de algoritm
Soluția
programului
Valoarea
funcției
x1 x2 x3 x4 x5 (P) obiectiv
S0 B0 = [A3 , A4 , A5] 0 0 4 18 6 (0 , 0) 0
S1 B1 = [A1 , A4 , A5] 4 0 0 6 10 (4 , 0) 8
S2 B2 = [A1 , A2 , A5] 7 3 0 0 7 (7 , 3) 17
S3 B3 = [A1 , A2 , A3] 42/5 36/5 14/5 0 0 (42/5 , 36/5) 24
Tabelul 4.2.5
Este util s ă recapitul ăm într-un tabel solu țiile admisibile de baz ă ale programului (FSP) , efectiv
generate de algoritm, împreun ă cu solu țiile programului (P), asociate prin coresponden ța din
finalul sec țiunii 3.3 (vezi tabelul 4.2.5).
Urmărind imaginea grafic ă (fig. 4.2.1), deducem sensul geometric al algoritmului simplex:
procedura pleac ă dintr -un v ârf al mul țimii solu țiilor admisibile apoi se deplaseaz ă către un v ârf
“vecin” mai bun ș.a.m.d. p ână la găsirea solu ției optime.
I. PROGRAMARE LINIARA
60
3.4.3. Determinarea unei solu ții admisibile de start (Metoda bazei artificiale)
După cum s -a specificat, aplicarea algoritmului simplex necesit ă cunoașterea unei baze
admisibile de start precum și a formei explicite asociate acesteia, celelalte forme explicite
deduc ându-se una din alta prin pivotare gaussian ă. Chiar și pentru probleme de dimensiuni mici,
găsirea unei asemenea baze de start prin simpl a inspectare a coloanelor matricii A, se dovede ște a fi o
treab ă complicat ă, ne mai vorbind de faptul c ă este posibil ca problema s ă nu aibă soluții admisibile.
În plus, s ă nu uit ăm că teoria metodei simplex s -a bazat esen țial pe ipoteza c ă restric țiile pr oblemei
sunt liniar independente, lucru iar ăși greu de verificat în practic ă. Pentru ob ținerea formei explicite
inițiale avem nevoie de c âteva preg ătiri.
Vom spune c ă programul în form ă standard (P) este în form ă bună dacă matricea A con ține o
submatrice unitate de ordinul m (= num ărul restric țiilor) iar termenii liberi sunt nenegativi . Dac ă
este a șa, (P) satisface condi ția (3.5.1) iar solu ția asociat ă bazei unitare este admisibil ă și poate fi
considerat ă ca solu ție de start pentru aplicarea algoritmului simplex. Dac ă (P) nu este în form ă bună,
el se poate aduce la aceast ă form ă, notat ă (FBP), în felul urm ător:
în caz c ă unele restric ții ale programului ini țial au termeni liberi negativi înmul țim aceste
restric ții cu -1; în acest fel to ți termenii liberi ai restric țiilor problemei de rezolvat vor fi 0.
Se aduce problema la forma standard ad ăugând variabile de abatere în restric țiile
inegalit ăți.
Dacă matricea programului rezultat nu con ține toate coloanele matricii unitate de ordinul
m, în anumite restri cții se vor ad ăuga noi variabile nenegative pentru crearea coloanelor lips ă;
aceste noi variabile se numesc variabile artificiale și, spre deosebire de cele de abatere, apar și în
funcția obiectiv cu un coeficient comun, foarte mare în valoare absolut ă. Coeficientul va fi negativ
dacă funcția obiectiv se maximizeaz ă și pozitiv în caz contrar .
Se observ ă imediat c ă dacă programul ini țial (P) este compatibil , solu țiile sale admisibile se
identific ă cu acele solu ții ale formei bune în care variabilele artifi ciale au valoarea zero . Prin faptul
că variabilele artificiale sunt însoțite în expresia func ției obiectiv de ni ște “penaliz ări” foarte mari,
metoda simplex este “instruit ă” să caute tocmai asemenea solu ții! Și astfel, rezolvarea formei bune
ne conduce la unul din urm ătoarele cazuri:
1. Forma bun ă are optim infinit. Atunci și programul ini țial are optim infinit.
2. Forma bun ă are optim finit dar în solu ția optim ă cel pu țin o variabil ă artificial ă are
valoare nenul ă. Atunci programul original este incompatibil.
3. Forma bun ă are optim finit și în solu ția optim ă toate variabilele artificiale au valoarea
zero. Ignor ând valorile acestor variabile se ob ține solu ția optim ă a programului ini țial.
Exemplul 4.3.1 Consider ăm urm ătorul program împreun ă cu forma sa standard:
()(max)
,Pf x x
x x
x x
x x
x x
2 3
2 40
3 30
30
0 01 2
1 2
1 2
1 2
1 2
( )(max)
, ,…,FSPf x x
x x x
x x x
x x x
x jj
2 3
2 40
3 30
30
0 151 2
1 2 3
1 2 4
1 2 5
Se constat ă că (FSP) nu este în forma bun ă necon ținând dec ât un singur vector al matricii unitare de
ordinul 3. Vom creea o asemenea matrice introduc ând în primele dou ă restric ții variabilele artificiale
x6 și x7. Obținem programul: CURSUL 9
61
( )(max)
, ,…,, FBPf x x Mx Mx
x x x x
x x x x
x x x
x jM
j
2 3
2 40
3 30
30
0 1 701 2 6 7
1 2 3 6
1 2 4 7
1 2 5
Putem aplica algoritmul simplex programului (FBP) plec ând de la baza unitar ă E = [A6, A7, A5] și
de la solu ția asociat ă acesteia:
x1 = x 2 = x 3 =x4 = 0 , x5 = 30 , x 6 = 40 , x 7 = 30 .
După trei itera ții (ve zi tabelele 4.3.1 – 4.3.4) se ob ține solu ția optim ă a programului (FBP) în care
variabilele artificiale x 6 , x7 au valoarea zero. Ignor ând aceste valori se ob ține solu ția optim ă a formei
standard (FSP) și implicit solu ția optim ă a programului original (P):
x x f1 2 10 20 80 ,max
variabilele de abatere av ând valorile:
x x x3 4 5 0 40 0 , , .
2 3 0 0 0 -M -M
cB B VVB A1 A2 A3 A4 A5 A6 A7
-M A6 40 2 1 -1 0 0 1 0
-M A7 30 1 3 0 -1 0 0 1
0 A5 30 1 1 0 0 1 0 0
f -70M -3M-2 -4M-3 M M * * *
-M A6 30 5/3 0 -1 1/3 0 1 -1/3
3 A2 10 1/3 1 0 -1/3 0 0 1/3
0 A5 20 2/3 0 0 1/3 1 0 -1/3
f -30M+30 -5/3M -1 * M -M/3-1 * * 4M/3+1
2 A1 18 1 0 -3/5 1///5 0 3/5 -1/5
3 A2 4 0 1 1/5 -2/5 0 -1/5 2/5
0 A5 8 0 0 2/5 1/5 1 -2/5 -1/5
f 48 * * -3/5 -4/5 * M+3/5 M+4/5
2 A1 10 1 0 -1 0 -1 1 0
3 A2 20 0 1 1 0 2 -1 0
0 A4 40 0 0 2 1 5 -2 -1
f 80 * * 1 * 4 M-1 M
Tabelele 4.3.1 – 4.3.4
Punctele din R2 corespunz ătoare celor patru solu ții generate de algoritm sunt S0 = (0,0) , S1 = (0,10),
S2 = (18,4), S3 = (10,20). Urm ărind fig. 4.3.1 se constat ă că punctele S0 și S1, ce corespund unor
soluții ale programului (FBP) în care cel pu țin o variabil ă artificial ă are valoare nenul ă, sunt în afara
mulțimii AP în timp ce S2 și S3, corespunz ătoare unor solu ții în care x 6 = x 7 = 0, su nt vârfuri ale
acestei mul țimi.
I. PROGRAMARE LINIARA
62
Figura 4.3.1
Pentru determinarea unei soluții admisibile de bază de start, în situația în care programul
inițial (P) nu este în formă bună, se poate aplica și așa numita metodă a celor două faze :
se introduc în restric ții variabile artificiale, bine înțeles acolo unde este cazul, în scopul
form ării unei baze unitare de start (termenii liberi ai restric țiilor se presupun a fi nenegativi);
în faza I se minimizeaz ă suma w a variabilelor artificiale intro duse. Deoarece și aceste
variabile sunt supuse condi ției de nenegativitate, urmeaz ă că (min)w 0. în caz c ă (min)w > 0 este
clar c ă programul ini țial (P) este incompatibil; dac ă (min)w = 0 se trece la:
faza a II -a, în care se optimizeaz ă funcția obiectiv a programului ini țial (P) plec ând de la
soluția de baz ă rezultat ă la finele fazei I. (Aten ție, la începutul acestei faze, vom avea grij ă să
recalcul ăm costurile reduse
cj în raport cu coeficien ții func ției obiectiv din (P)!)
3.4.4. Inve rsa bazei curente. Solu ția optim ă a problemei duale
Să consider ăm un program liniar (P) în form ă bună. Renumerot ând convenabil variabilele
programului, matricea coeficien ților sistemului de restric ții are forma:
A = [A’ , E] ,
unde E este matricea unitate de ordinul m = num ărul restric țiilor din (P). Dup ă cum am v ăzut, E se
ia ca baz ă de start în procesul rezolv ării programului (P) prin algoritmul simplex. Dac ă B este o baz ă
cercetat ă de algoritm, atunci matricea formei explicite asociat ă bazei B va fi:
B-1A = [B-1A’ , B-1]
Cum matricea B-1A apare în “corpul mare” al tabelului simplex corespunz ător bazei B, deducem
următoarea concluzie important ă:
La fiecare itera ție, algoritmul simplex pune în eviden ță inversa B-1 a bazei curente. Ea este
format ă din coloaneleAj corespunz ătoare coloanelor unitare Aj care au format baza de start , în
ordinea în care acestea s -au aflat în baza de start .
Exemplul 4.4.1 Ne referim la programul (P) rezolvat în exemplul 4.3.1. Deoarece baza de
start a fost matricea unita te E = [A6, A7, A5], inversa bazei optime B = [A1, A2, A4] se “cite ște” din
ultimul tabel simplex: S0: x1=0 , x 2=0
S2: x1=18 , x 2=4 S1: x1=0 , x 2=10 S3: x1=10 , x 2=20 x2
x1 AP
63
B AAA
1 6 7 51 0 1
1 0 2
2 15,,
O calitate remarcabil ă a algoritmului simplex este aceea c ă produce nu numai solu ția optim ă
a problemei c ăreia i se aplic ă ci și solu ția optim ă a problemei duale .
Să consider ăm un cuplu de probleme în dualitate în care una este în form ă standard (vezi
secțiunea 2.2):
()max ()
Pfx cx
Ax b
x
0
()min ()
Qgu ub
uA c
u
oarecare
Cu nota țiile sec țiunii 3.5 avem urm ătoarea:
Teorema 4.4.1 Presupunem c ă (P) are o solu ție optim ă x* asociat ă unei baze B. Atunci:
u* = cBB-1 (4.4.1)
este o solu ție optim ă a problemei duale (Q).
Demonstrație: Vom arăta că u* satisfac e restricțiile uAj cj , j = 1,…,n ale problemei duale (Q).
într-adevăr u*Aj – cj =cBB-1Aj -cj =
cj, conform (3.5.6). Avem
cj 0 , j = 1,…,n, deoarece x* este
prin ipoteză soluția optimă a programului (P), astfel că u* este o soluție a dualei (Q). Mai departe
f(x*) = g(u*) = cBB-1b. Concluzia teoremei decurge acum din teorema 2.3.1.
Practic, pentru determinarea solu ției optime duale se procedeaz ă astfel. Am ar ătat c ă
rezolvarea unei probleme în form ă standard se reduce la rezolvarea unei probleme de acela și tip a
cărei matrice con ține o submatrice unitate av ând ordinul egal cu num ărul restric țiilor.
Atunci inversa bazei optimale B-1 se cite ște în tabelul simplex asociat acestei baze pe
coloanele Aj corespunz ătoare vectorilor care au format baza unitar ă de start !
Extrăgând B-1 din tabel se poate aplica formula (4.4.1).
Procedeul descris este valabil și pentru un cuplu general de probleme în dualitate (P,Q). Într-
adev ăr, dup ă cum am v ăzut deja, aducerea proble mei (P) la o form ă (P1) convenabil ă aplic ării
algoritmului simplex se face prin ad ăugare de variabile: de abatere și/sau artificiale. În consecin ță,
duala (Q 1) a problemei (P 1) va avea acelea și variabile și aceea și func ție obiectiv ca și duala (Q) a
proble mei ini țiale (P), diferen ța const ând în num ărul restric țiilor și în condi țiile impuse variabilelor.
Se poate ar ăta fără dificultate c ă aceast ă “diferen ță” nu înseamn ă altceva dec ât dou ă modalit ăți de
scriere a uneia și aceleia și probleme, altfel spus (Q) și (Q 1), în esen ță, coincid! În acest fel, teorema
de dualitate 2.3.3 este probat ă.
Exemplul 4.4.2 Ilustr ăm cele de mai sus, determin ând solu ția optim ă a programului liniar:
0 ,0 ,03 3;2 230 30 40)( min
)(
3 2 13 2 13 2 13 2 1
u u uuu uuuuu u u ug
Q
I. PROGRAMARE LINIARA
64
care este dualul programului (P) rezolvat în exemplul 4.3. 1. Dup ă adăugarea variabilelor de abatere și
a celor artificiale, din (P) s -a obținut programul (P 1) = (FBP) al c ărui dual este:
()min ()
,,Qgu u u u
u u u
u u u
u
u
u
u M
u M
uuu11 2 3
1 2 3
1 2 3
1
2
3
1
2
1 2 340 30 30
2 2
3 3
0
0
0
f.r.s.
Restric ția u 3 0 este de fapt condi ția de nenegativitate impus ă variabilei u 3 în (Q) iar -u1 0 , -u2 0
înseamn ă u1 0 , u 2 0. Ultimele dou ă restric ții din (Q 1) sunt superflue pentru c ă M este prin
defini ție >> 0. Prin urmare (Q) și (Q 1) coincid. Din tabelul simplex 4.3.4 extragem inve rsa bazei
optimale comune B = [ A1,A2,A4] a programelor (P) și (P 1) – vezi exemplul precedent – astfel c ă
soluția optim ă a problemei duale (Q) este :
u cBB
12301 0 1
10 2
2 15104
adică:
u u u1 2 3 1 0 4 , , .
Observa ție: Folosind nota țiile din 3.5 punem în eviden ță componentele vectorului linie cBB-1:
Jjac Ac
Iiijij B
j
,
Pentru coloanele unitare Ai corespunz ătoare vectorilor Ai din baza curent ă punem:
i = c i , i I
Din (3.5.6) rezult ă atunci c ă:
cj
=j – cj , j=1,…,n
și deci m ărimile j sunt efectiv calculate în procesul evalu ării coeficien ților
cj ! Acesta este și
motivul pentru care de multe ori m ărimile j sunt puse în eviden ță într-o linie separat ă plasat ă în
tabelul simplex deasupra liniei test. Cu aceste preg ătiri, formula (4.4.1) arat ă că:
Solu ția optim ă a problemei duale este dat ă de coeficien ții j din tabelul simplex al
problemei primale, corespunz ători coloanelor unitare care au format baza de start.
3.4.5. Convergen ța algoritmului simplex
Se arat ă ușor că dacă minimul din (4.2.2) nu este unic atunci noua solu ție de bază
x este
degenerat ă, adică are un num ăr de componente nenule < m. Aceast ă situa ție este delicat ă prin faptul
că poate implica neconvergen ța algoritmului. Mai precis, este posibil ca algoritmul s ă genereze un șir
de solu ții de baz ă neoptimale
xx xp 1 2,,…, , de-a lungul c ăruia valoarea func ției obiectiv sta ționeaz ă,
adică
fx fx fxp()() ()1 2 , astfel încât
x xp1 !!! Fenomenul descris, numit ciclare , deși
65
teoretic posibil, nu a fost întâlnit în nici o aplica ție prac tică, existen ța lui fiind probat ă doar prin
câteva exemple “artificial” construite.
Exemplul 4.5.1 [Beale] Se consider ă programul liniar:
x x x x
x x x x x
x
x x x x1 4 5 7
2 4 51
26 7
3
4 51
26 78 9 0
12 3 0
20 6 + x
+
+ x =1
(max)f =1
4 6
1
2
6
3
4
O baz ă admisibil ă de start este B0 = E = [A1,A2,A3] a cărei solu ție asociat ă x0 este degenera tă. Într-
adev ăr, variabilele bazice au valorile:
x1 = 0 , x 2 = 0 , x 3 = 1 (toate celelalte variabile fiind nule)
Propunem cititorului s ă arate c ă succesiunea de baze admisibile:
B1 = [A4,A2,A3] , B2 = [A4,A5,A3] , B3 = [A6,A5,A3] , B4 = [A6,A7,A3], B5 = [A6,A2,A3] , B6
=[A4,A2,A3]
poate fi dedus ă din B0 prin aplicarea regulilor algoritmului simplex. Se constat ă fără dificultate c ă
valoarea func ției obiectiv în solu țiile de baz ă asociate este zero și că nici una din aceste solu ții, toate
degenerate, nu verific ă criteriul de optimalitate. Pe de alt ă parte observ ăm că baza B6 este identic ă cu
baza B1 și deci algoritmul intr ă într-un ciclu infinit f ără a putea determina solu ția optim ă (care exist ă
și este unic ă după cum vom vedea).
Pentru problemele ale c ăror solu ții de baz ă admisibile sunt toate nedegenerate convergen ța
algoritmului este asigurat ă de urm ătoarea:
Teorema 4.5.1 Dacă programul în form ă standard (P) este compatibil și toate solu țiile sale
admisibile de baz ă sunt nedegenerate atunci aplicare a algoritmului simplex descris în 4.2 se termin ă
într-un num ăr finit de itera ții, fie cu g ăsirea solu ției optime, fie cu concluzia c ă programul are optim
infinit.
Demonstrație: Fie
xxx0 1 2,,,… soluțiile cercetate în cursul aplicării algoritmului ,
x0 fiind soluția
inițială. Avem
fx fx fx () () ()….0 1 2
Ipoteza nedegenerării precum și formula (4.2.3) arată că de fapt
fx fx fx () () ()0 1 2 … și deci
nici o soluție admisibilă de bază nu va fi cercetată de două ori. Concluzia teoremei re zultă acum
din faptul că numărul soluțiilor de bază este finit (vezi secțiunea 3.5).
Din fericire, exist ă proceduri de evitare a cicl ării care constau într-o mic ă modificare a regulii
(4.2.2). Ele sunt încorporate în orice pachet de programe des tinat rezolv ării problemelor de
programare liniar ă. O asemenea metod ă este descris ă în www.asecib.ase.ro – Cursuri on -line – 9.
Nica V. și colectiv, Cercetări Operaționale I .
3.4.6. Interpretarea economic ă a algo ritmului simplex
Să consider ăm cazul în care problema de maximizare în form ă standard:
I. PROGRAMARE LINIARA
66
max fcx
Ax b
x
0
reprezint ă modelul de optimizare a activit ății unei firme (sec țiunea 1.1, exemplul 1). Se cere
determinarea combina ției de bunuri ce urmeaz ă a fi realizate precum și a cantit ăților în care acestea
vor fi produse , x*, astfel încât venitul firmei s ă fie maxim cu condi ția consum ării integrale a
resurselor disponibile. Ultima cerin ță nu este deloc restrictiv ă întruc ât în lista activit ăților productive
putem include la nevoie un num ăr de activit ăți fictive ale c ăror nivele s ă reprezinte resursele
neconsumate (aceste activit ăți fictive corespund variabilelor de abatere).
O prim ă concluzie care se desprinde din teoria metodei simplex este aceea c ă în orice soluție
optim ă a modelului , numărul bunurilor ce vor fi efectiv realizate este cel mult egal cu num ărul
resurselor folosite .
Aceasta rezult ă din faptul c ă în orice solu ție de baz ă numărul componentelor nenule nu
depășește num ărul restric țiilor. În con secin ță, realizarea unor bunuri ce nu sunt incluse în "lista
optim ă" implic ă adăugarea unor noi restric ții în model, fapt care duce la diminuarea optimului ini țial.
Să consider ăm acum un program de produc ție "de baz ă", adic ă o solu ție admisibil ă de baz ă,
asociat ă unei baze B. Activit ățile i corespunz ătoare coloanelor Ai din B vor fi numite în continuare
activit ăți de baz ă, iar celelalte activit ăți secundare. Conform defini ției, acest program nu prevede
folosirea activit ăților secundare iar cantit ățile de bunuri realizate în activit ățile de baz ă trebuie astfel
dimensionate încât să se asigure consumarea întregului stoc de resurse. În nota țiile sec țiunii 3.3.5 :
BxB = b , xS = 0 , de unde xB = B-1b =b
După cum se vede, lista activit ăților de bază determin ă în mod unic cantit ățile de bunuri ce pot fi
produse și ca atare detectarea unui program mai bun se poate face numai studiind oportunitatea
utiliz ării unor activit ăți secundare care s ă înlocuiasc ă o parte din activit ățile bazice curente. Pent ru
aceasta avem nevoie de un criteriu care s ă permit ă compararea unei activit ăți secundare j cu grupul
activit ăților de baz ă. Să examin ăm coloana Aj a tabelului simplex asociat bazei B. Conform (3.5.3)
Aj = B-1Aj de unde Aj = BAj sau:
A aA aA aAj
j j mjm11
22…. (4.6.1)
în ipoteza c ă
B AA Am1 2,,…, . Sensul economic al egalit ății (4.6 .1) este urm ătorul: din punctul
de vedere al consumului de resurse producerea unei unit ăți din bunul j este echivalent ă cu producerea
cantit ăților
aa aj j mj 1 2,,…, din bunurile activit ăților de baz ă. În consecin ță, dac ă se dore ște
producerea unei unit ăți din bunul j, produc ția activit ăților de baz ă trebuie diminuat ă cu cantit ățile
aa aj j mj 1 2,,…,
. Analiza oportunit ății introducerii în fabrica ție a bunului j se va face prin compararea
aportului s ău la cre șterea venitului firmei cu aportul valoric al cantit ăților
aa aj j mj 1 2,,…, . Astfel,
realizarea unei unit ăți din bunul j determin ă creșterea valorii curente a func ției obiectiv cu pre țul său
cj în timp ce renun țarea la producerea cantit ăților
aa aj j mj 1 2,,…, înseamn ă diminuarea aceleia și
valori cu suma
ca ca caj j mmj 11 22… . Prin urmare dac ă diferen ța:
c ca ca ca cj j j mmj j 11 22…
este 0 realizarea bunului j nu este rentabil ă deoarece nu duce la cre șterea valorii produc ției
asigurate prin programul curent. Dac ă cj 0 pentru toate activit ățile secundare, programul de
fabrica ție curent este optim. Am reg ăsit astfel criteriul de optimalitate din teorema A secțiunea 4.1.
Dacă cj < 0, utilizarea activit ății secundare j duce la o sporire a venitului realizabil prin programul
67
curent, viteza de cre ștere fiind –cj . Interpretarea criteriului de intrare în baz ă (4.2.1) este acum
clară: dacă mai multe activit ăți secundare sunt rentabile în raport cu grupul activit ăților de baz ă
este preferat ă activitatea care asigur ă cea mai ridicat ă viteză de cre ștere a valorii curente a
produc ției. Fie k aceast ă activitate. Ultima problem ă const ă în stabilirea cantit ății din bunul k ce
poate fi realizat ă în condi țiile date. Confor m celor de mai sus producerea unei cantit ăți din acest
bun implic ă micșorarea produc ției din bunurile activit ăților de baz ă cu cantit ățile
a a ak k mk 1 2, ,…, :
xb axb a x b ak k m m mk 1 1 1 2 2 2 , ,…,
Deoarece desf ășurarea unei activit ăți la un nivel negativ este lipsit ă de sens va trebui s ă avem
b a i mi ik 0 1,..,
de unde:
00 ia
iki
ikb
a ,min
(excludem cazul optimului infinit, nesemnificativ din punct de vedere economic). Dac ă
0b
ar
rk și
0
obținem cre șterea maxim ă a valorii curente a produ cției prin utilizarea activit ății k. În acest
caz activitatea k nu mai este folosit ă întruc ât
x b a bb
aar r rk rr
rkrk 0 0 . Am ob ținut din nou
criteriul de ie șire din baz ă (4.2.2).
I. PROGRAMARE LINIARA
68
3.5. Algoritmul simplex dual
Exist ă situa ții în care pentru rezolvarea unui program liniar, dispunem de o solu ție de baz ă
care nu este admisibil ă. Urm ătoarele considera ții au drept scop s ă pună în eviden ță o altă clasă de
soluții de baz ă cu care se poate opera într-o manier ă asem ănătoare celei în care lucreaz ă algoritmul
simplex descris în paragraful 4.
3.5.1. Admisibilitate primal ă și dual ă
Fie (P) un program liniar în form ă standard:
(),…,
,…,
(max)Pax bi m
x j n
f cxijj
jn
i
j
jj
jn
1
11
0 1
Ax b
x
fcx
0
(max)
(vezi nota țiile matriciale (3.3.1)) Fie B o baz ă a programul ui (P), I mul țimea indicilor coloanelor din
B, J mul țimea indicilor coloanelor din A care nu sunt în B. În sec țiunea 3.5 am scris (P) în forma:
()(max)
, ; ,Pff cx
x ax b
x iIx jJBjj
jJ
i ijj
jJi
i j
0 0
(max)
,ffcx
x Sx b
x xSS
B S
B S
0 0
(vezi nota țiile (3.5.2 -3.5.7)), numit ă forma explicit ă a programului (P) în raport cu baza B.
Să consider ăm acum dualul programului (P):
m
iiiim
ij iij
ub gm i oarecareun jcua
Q
11
(min),…,1,,…,1
)(
uA c
uoarecare
gub
(min)
(vezi nota țiile din 2.2) Aducem sistemul de inegalit ăți uA c la forma standard introduc ând
variabilele de abatere v1, v2, …, v n reunite în vectorul linie v.
m
iiij ij jm
iiij
ub gn j vm i oarecariuc vua
FSQ
11
(min),…,1 0 ; ,…,1, ) (
uA vc
uoarecare v
gub
,
(min)0
Parti ționând:
vvv cuv v v vB S B
iiIS
jjJ , ,
sistemul liniar din (FSQ) devine succesiv: CURSUL 10
69
uA vc uBS vv ccuB v c
uS v cB S B SB B
S S
, , ,(..)
(..)511
512
Deoarece B este nesingular ă din (5.1.1) re zultă:
ucB vBB B 1 1 (5.1.3)
Introducem u în (5.1.2):
( ) cB vBSv c v vBScBSc v vScB B S S S B B S S B S 1 1 1 1
(cu nota țiile 3.5.2 -3.5.7) Folosind din nou (5.1.3) elimin ăm u din func ția obiectiv dual ă:
gu cB vBbcBbvBbfvbB B B B B()( ) 1 1 1 1
In acest fel, am adus (FSQ) la forma echiva lentă:
() ,
(min)Qv vSc
v v
gfvbBS B S
S B
B
0 0
variabilele originale ui , i=1,…, m fiind legate de variabilele vj , j=1,…, n prin rela ția (5.1.3).
Programul (Q B) se va numi forma explicit ă a dualului (Q) în raport cu baza B.
Pentru a sublinia simetria existent ă între pro blemele (P B) și (Q B) le vom scrie al ăturat at ât
scalar c ât și matricial:
() , ; ,
(max)Px ax b iI
x iIx jJ
ff cxBi ijj
jJi
i j
jj
jJ
0 0
() , ; ,
(min)Qv avc jJ
v jJv iI
gf vbBj iji
iIj
j i
ii
iI
0 0
x Sx b
x x
ffcxB S
B
S
SS
0 0 ,
(max)
v vSc
v v
gfvbS B S
S B
B
0 0 ,
(min)
Observa ție: Cu ajutorul rela ției (5 .1.3) am rescris dualul (Q) în alte variabile care sunt supuse
condi ției de nenegativitate ca și variabilele programului primal (P). Putem vorbi acum de solu ții și
soluții admisibile pentru programul (Q) și când facem acest lucru ne referim la forma echiva lentă
(QB).
Prin analogie cu conceptul de solu ție a primalei (P) asociat ă bazei B introducem termenul de
soluție a dualei (Q) asociat ă bazei B anulând în sistemul restric țiilor lui (Q B) variabilele "secundare"
vi , i I :
vB 0 vS =
cS
(5.1.4)
vi=0 , i I vj=c j , j J
Rezult ă imediat c ă valoarea func ției obiectiv duale în solu ția construit ă este const anta f .
I. PROGRAMARE LINIARA
70
Folosind (5.1.3), solu ția dualei (Q), corespunz ătoare solu ției (5.1.4) este:
u = cBB-1 (5.1.5)
Soluția (5.1.4) va fi o solu ție admisibil ă pentru duala (Q) dac ă:
cS 0 c j 0 , j J
Mai departe, exact ca în demonstra ția teoremei A a metodei simplex ( vezi sec țiunea 4.1 ) solu ția
(5.1.4), presupus ă admisibil ă, va fi optim ă dacă:
b 0 bi 0 , i I
Reamintim c ă soluția primalei (P) asociat ă bazei B este:
xS=0 xB=b
(5.1.6)
x jJ xbiIj ii 0, ,
Aceast ă soluție este admisibil ă dacă
b b iI i 0 0, și în plus optim ă dacă
c c jJS
j 0 0, .
Obținem urm ătoarele concluzii remarcabile :
Soluția (5.1.6) a primalei (P) asociat ă bazei B este admisibil ă (respectiv satisface criteriul
de optimalitate al algoritmului simplex) dac ă și numai dac ă soluția (5.1.4) a dualei (Q) asociat ă
aceleia și baze satisface criteriul de optimalitate (respectiv este admisibil ă).
Valorile func țiilor obiectiv primal ă și dual ă în cele dou ă soluții eviden țiate coincid (cu
constanta f )
Soluția (5.1.6) este o solu ție optim ă a programului (P B) (P) dac ă și numai dac ă soluția
(5.1.4) este optim ă pentru programul (Q B), ceeace echival ează cu a spune c ă soluția (5.1.5) este
optim ă pentru programul dual (Q).
În rezumat, pornind de la problema original ă (P) și de la o baz ă B a sa am construit dou ă
probleme în dualitate (P B) și (Q B) și am pus în eviden ță două soluții ale acestora, pe car e le-am numit
soluții asociate bazei B. Cuplul de solu ții eviden țiat are propriet ățile:
i)Una din solu ții este admisibil ă (verific ă criteriul de optimalitate al algoritmului simplex)
dacă și numai dac ă cealalt ă verific ă criteriul de optimalitate (respecti v este admisibil ă) în particular
una este optim ă dacă și numai dac ă cealalt ă este optim ă.
ii)Valorile func țiilor obiectiv în cele dou ă soluții coincid.
Contextul astfel creat sugereaz ă următoarea schimbare de terminologie:
O solu ție de baz ă a programului (P) se va numi primal admisibil ă dacă este admisibil ă în
sensul de p ână acum , adică are toate componentele nenegative.
O solu ție de baz ă a programului (P) se va zice dual admisibil ă dacă verific ă criteriul de
optimalitate al algoritmului simplex . O baz ă a programului (P) se va numi dual admisibil ă dacă
soluția asociat ă este dual admisibil ă.
În terminologia introdus ă, proprietatea i) de mai sus se reformuleaz ă astfel:
Una din solu ții este primal admisibil ă dacă și numai dac ă cealalt ă este dual ad misibil ă.
Oricare din ele este optim ă dacă și numai dac ă este simultan primal și dual admisibil ă.
71
3.5.2. Algoritmul simplex dual
Considera țiile precedente sugereaz ă posibilitatea rezolv ării programului original (P) utiliz ând
clasa solu țiilor dual ad misibile. Urm ătorul algoritm, numit algoritmul simplex dual, rezult ă
nemijlocit din aplicarea teoremelor A, B, C ale metodei simplex la problema (Q B).
Presupunem cunoscut ă o solu ție de baz ă dual admisibil ă a programului (P) și tabelul simplex
(uzual) aso ciat. În nota țiile deja utilizate, o itera ție a algoritmului simplex dual se compune din
următorii pa și:
Pasul 1. (Test de optimalitate) Dac ă toți
b iI i0, STOP : solu ția de baz ă dual
admisibil ă curent ă este optim ă. În caz contrar:
Pasul 2. Se determin ă indicele bazic r I cu proprietatea:
b b b r
iIi r
min ( )0
Coloana Ar părăsește baza curent ă.
Pasul 3. Dacă pentru to ți jJ avem a rj 0 STOP: problema primal ă nu are solu ții
admisibile (este incompatibilă) . Altminteri:
Pasul 4 . Se determin ă indicele nebazic k J cu proprietatea:
rjj
rkk
ac
ac
rja 0min
Coloana Ak intră în baza curent ă.
Pasul 5. Se pivoteaz ă tabelul simplex curent cu pivotul ark < 0. În acest fel se ob ține forma
explicit ă a programului (P) în raport cu baz a B' dedus ă din B prin înlocuirea coloanei Ar cu coloana
Ak. Se revine la pasul 1 în cadrul unei noi itera ții.
Observa ții: 1) Considera țiile expuse în aceast ă secțiune sunt valabile cu mici modific ări și în
cazul în care func ția obiectiv din programul or iginal (P) se minimizeaz ă. Cititorul va verifica imediat
că algoritmul prezentat mai sus r ămîne valabil și pentru asemenea probleme.
2) Concluzia din pasul 3 este consecin ța teoremei fundamentale a dualit ății. Într-adev ăr, dac ă
arj 0 , jJ atunci prog ramul dual (Q) are optim infinit și în consecin ță programul (P) este
incompatibil.
3) Nu insist ăm asupra modalit ății de determinare a unei solu ții de baz ă dual admisibile de
start deoarece algoritmul va fi aplicat numai în situa ții în care o asemenea sol uție este disponibil ă.
Exemplu 5.2.1 Consider ăm programul:
()(min)
,,Pf x x x
x x x
x x x
xxx
12 2 6
3 2 3
4 4
01 2 3
1 2 3
1 2 3
1 2 3
Introducem variabilele de abatere x4 și x5 după care înmul țim cu -1 egalit ățile rezultate:
3 2 3
4 41 2 3 4
1 2 3 5x x xx
x x x x
I. PROGRAMARE LINIARA
72
Soluția asociat ă bazei unitare E = A4 , A5 nu este adm isibil ă:
x1=x2=x3=0 x4= – 3 , x5= – 4 ,
dar dac ă evalu ăm costurile reduse c1 , c2 , c3 constat ăm că ele verific ă criteriul de optimalitate al
algoritmului simplex (bine înțeles pentru probleme de minimizare!).Vezi tabelele 5.2.1 -5.2.4.
Se co nstat ă că soluția optim ă a programului dat are componentele :
x x x f11
7 2 324
7156
7 0* * *
min , , ;
Observa ție final ă. Pentru simetrie, algoritmul descris în sec țiunea 4.2 se va numi algoritmul
simplex primal . Recapitul ând teoria se constat ă fără dificultate c ă maximul (minimul) unei func ții
obiectiv se atinge prin valori cresc ătoare (descresc ătoare) în simplexul primal și prin valori
descresc ătoare (cresc ătoare) în simplexul dual.
12 2 6 0 0
cB B VVB A1 A2 A3 A4 A5 A5 iese din baza curent ă.
0 A4 -3 3 2 -1 1 0 min{-12/-4 , -2/-1 , -6/-1} =
0 A5 -4 -4 -1 -1 0 1 = 2 A2 intră în baza curent ă.
f 0 -12 -2 -6 * * ***
0 A4 -11 -5 0 -3 1 2 A4 iese din baza curent ă.
2 A2 4 4 1 1 0 -1 min{-4/-5 , -4/-3} = 4/5
f 8 -4 * -4 * -2 A1 intră în baza curent ă.
12 A1 11/5 1 0 3//5 -1//5 -2/5 ***
2 A2 -24/5 0 1 -7/5 4/5 3/5 A2 iese din baza curent ă.
f 84/5 * * -8/5 -4/5 -18/5 A3 intră în baza curent ă.
12 A1 1/7 1 3/7 0 1/7 -1/7 ***
6 A3 24/7 0 -5/7 1 -4/7 -3/7 Soluția curent ă este dual și primal
f 156/7 * -8/7 * -12/7 -30/7 admisibil ă.
Tabelele 5.2.1 – 5.2.4
3.6. Analiza sensitivit ății. Postoptimizare. Programare parametric ă
Orice program liniar în form ă standard în care func ția obiectiv se maximizeaz ă este perfect
determ inat de cunoa șterea urm ătoarelor trei masive:
A matricea coeficien ților sistemului de restric ții
b vectorul (coloan ă) al termenilor liberi
c vectorul (linie) al coeficien ților func ției obiectiv
drept care va fi identificat în continuare prin sigla P(A,b,c):
PAbcAx b
x
fcx(,,)
(max)
0
Până acum, elementele masivelor A, b, c au fost presupuse a fi cunoscute cu exactitate și
fixate, de unde și numele de constante atribuit lor. În situa țiile practice, suntem obliga ți să privim
aceste "constante" și din alte unghiuri de vedere. S ă presupunem c ă P(A,b,c) modeleaz ă activitatea
unei firme. Atunci elementele aij ale matricii A au semnifica ția de consumuri de resurse,
componentele bi ale vectorului b reprezint ă plafoanele resurselor disponibile iar componentele cj ale
vectorului c pot fi dup ă caz, pre țuri sau profituri unitare.
73
Se poate întâmpla ca unele dintre aceste elemente s ă nu fie cunoscute cu exactitate, ele
oscil ând în jurul unor valori "probabile", ca în urm ătoarele exemple:
"exper ții firmei estimeaz ă că pentru luna urm ătoare pre țul bunului … va fi în jur de 18 u.m."
sau:
"directorul executiv apreciaz ă că pentru luna urm ătoare disponibilul resursei … va fi cam de
130 unit ăți".
În asemenea situa ții suntem interesa ți să știm dac ă la varia ții "mici" ale unor constante
corespund varia ții "mici" ale solu ției modelului, altfel spus, dac ă soluția modelului depinde
"continuu " de aceste constante. Dac ă este a șa, vom spune c ă soluția modelului este stabil ă.
Studiul stabilit ății este important din punct de veder e economic deoarece este posibil ca
varia ții mici ale unor constante s ă antreneze modific ări majore în solu ția optim ă și în acest caz este
necesar s ă știm cauzele și propor țiile instabilit ății pentru a putea lua decizia adecvat ă.
În acest context, analiz a sensitivit ății are ca obiect studiul stabilit ății soluției optime a unei
probleme de optimizare . În cazul liniar, pentru fiecare constant ă se poate determina un interval de
varia ție cu proprietatea c ă baza optimal ă sau chiar solu ția asociat ă rămân neschimbate. Acest interval
se nume ște interval de stabilitate al solu ției optime în raport cu coeficientul considerat.
Relu ând problema firmei sunt situa ții în care constantele modelului sunt cunoscute cu
exactitate și fixate doar pe o anumit ă perioad ă, o parte din ele suferind modific ări de mai mic ă sau
mai mare amplitudine prin trecerea la o nou ă perioad ă. Ce efect au aceste schimb ări asupra solu ției
optime este o alt ă chestiune cu serioase motiva ții economice. De exemplu, suntem interesa ți în a afla
dacă optimalitatea unei combina ții de bunuri se mai men ține c ând profitul unui bun rentabil scade.
Mai departe, ne putem întreba ce se întâmplă dacă disponibilul de resurse sufer ă unele ajust ări. De
asemenea este interesant de v ăzut ce efect are introducerea unei noi activit ăți productive,
considerarea unei noi resurse al c ărei disponibil limitat face inoperant programul de produc ție
actual sau modificarea tehnologiei de transformare a resurselor în bunuri.
Evident, la toate aceste întreb ări se poate r ăspund e rezolv ând de sine st ătător problema
modificat ă. În continuare, vom ar ăta cum se ob ține solu ția problemei modificate plec ând de la solu ția
problemei originale. Subiectul în discu ție este tentant din start, deoarece este din nou de a șteptat ca,
la mici mod ificări ale datelor ini țiale, s ă rezulte schimb ări de mic ă amploare în solu ția optim ă
original ă, schimb ări ce se pot determina cu un efort de calcul relativ mic, oricum mai mic dec ât în
cazul în care problema modificat ă ar fi rezolvat ă "de la cap ăt".
Prob lematica relevat ă este cunoscut ă sub numele de postoptimizare.
În fine, programarea parametric ă se ocup ă de studiul comport ării solu ției unei probleme de
optimizare atunci c ând una sau mai multe constante ale problemei depind de un sistem de parametri .
(Ne vom m ărgini aici numai la cazul dependen ței liniare de un singur parametru .)
Cele trei teme sunt str âns legate între ele. În esen ță, determinarea unui interval de stabilitate a
soluției optime în raport cu un coeficient este o problem ă parametric ă în care însuși coeficientul
respectiv este considerat ca parametru. De asemenea , o problem ă de postoptimizare poate fi privit ă
ca un caz particular al unei probleme mai generale, parametrice etc.
3.6.1. Analiza sensitivit ății. Studiu de caz
Conducerea fir mei X, specializat ă în producerea de aparatur ă electronic ă a inițiat un ambi țios
program de îmbun ătățire a activit ății sale. Ea dore ște în primul r ând să știe care este cel mai bun mod
de utilizare a resurselor sale interne: capacit ăți de produc ție, for ță de munc ă, spa ții de depozitare,
etc. urm ând ca în func ție de rezultate s ă-și definitiveze programul de aprovizionare cu materii prime
și componente semifabricate precum și programul de produc ție pe urm ătoarele luni. Directorul
I. PROGRAMARE LINIARA
74
executiv a apelat la o echip ă de Cercetare Opera țional ă care a propus programarea liniar ă ca mijloc
de investigare și analiz ă. Pentru exemplificare, au fost alese trei resurse mai importante R 1, R2, R3 și
trei produse reprezentative G1, G2, G3. Din analiza situa ției curente a rezulta t că pe durata unei luni
activit ățile av ând drept scop producerea celor trei bunuri pot fi considerate ca fiind liniare. În tabelul
6.1.1 sunt date cantit ățile din resursele considerate, disponibile la nivelul unei luni și consumurile
specifice pentru fiec are bun în parte.
Tabelul 6.1.1
Produse Consumuri specifice
Resurse G1 G2 G3 Disponibil
R1 1 2 1 130
R2 1 1 2 100
R3 2 1 3 140
Desigur, în compararea diferitelor moduri de utilizare a resurselor tr ebuie avut în vedere un criteriu
de performan ță cum ar fi maximizarea profitului total sau a venitului total sau a ratei profitului,
minimizarea costului produc ției etc. Se poate pune chiar problema elabor ării unui program de
fabrica ție acceptabil din punc tul de vedere al mai multor criterii ca în cadrul analizei multicriteriale ,
dar acest subiect nu va fi tratat în cadrul acestui curs .
Pentru început, directorul executiv a cerut echipei s ă elaboreze o propunere de program de
produc ție care, plec ând de l a resursele sus amintite, s ă maximizeze profitul total al firmei relativ la
bunurile G1, G2, G3.
Profiturile pe unitatea de produs sunt estimate în momentul de fa ță la 3, 4 respectiv 2 unit ăți
monetare (u.m.). Not ând cu x1, x2, x3 cantit ățile în care bu nurile G1, G 2, G 3 vor fi realizate și ținând
seama de ipoteza de liniaritate rezult ă următorul model matematic:
()
,,
maxPx x x
x x x
x x x
xxx
f x x x1 2 3
1 2 3
1 2 3
1 2 3
1 2 32 130
2 100
2 3 140
0
3 4 2
Aducem problema (P) la forma standard prin introducerea variabilelor de abatere x4, x5, x6 .
Reamintim con ținutul economic al noilor variabile. Deoarece expresia x1 + 2×2 + x3 din membrul
stâng al primei restric ții reprezint ă cantitatea din resursa R 1 necesar ă pentru realizarea combina ției de
bunuri ( x1, x2, x3) iar termenul liber 130 este cantitatea disponibil ă din aceea și resurs ă, urmeaz ă că
diferen ța 130 – (x1 + 2×2 + x3), ce define ște valoarea vari abilei de abatere x4, va semnifica tocmai
cantitatea din R 1 nefolosit ă. Analog, x5 și x6 vor reprezenta cantit ățile din R 2 și R3 neutilizate.
Aplic ăm algoritmul simplex plecând de la baza unitar ă de start E = A4,A5,A6:
3 4 2 0 0 0
CB B VV
B A1 A2 A3 A4 A6 A6
0 A4 130 1 2 1 1 0 0
0 A5 100 1 1 2 0 1 0
0 A6 140 2 1 3 0 0 1
f 0 -3 -4 -2 * * *
75
4 A2 65 1/2 1 1/2 1/2 0 0
0 A5 35 1/2 0 3/2 -1/2 1 0
0 A6 75 3/2 0 5/2 -1/2 0 1
f 260 – 1 * 0 2 * *
4 A2 40 0 1 -1/3 2/3 0 -1/3
0 A5 10 0 0 2/3 -1/3 1 -1/3
3 A1 50 1 0 5/3 -1/3 0 2/3
f 310 * * 5/3 5/3 * 2/3
Tabelele 6.1.2 – 6.1.4
Pe baza informa țiilor numerice cuprinse în tabelul 6.1.4 al solu ției optime echipa C.O. a formulat
următoarele concluzii:
Profitul maxim pe care firma îl poate ob ține lu ând în calcul numai datele prezentate este de
310 u.m. Aceast ă valoare reprezint ă limita superioar ă a posibilit ăților actuale și s-ar ob ține dac ă nu ar
exista nici un fel d e probleme în leg ătură cu procurarea altor resurse, cu situa ția vânzărilor și în
general cu tot ce ține de actul complex al aprovizion ării, produc ției și desfacerii. Marja de manevr ă a
conducerii este limitat ă nu numai de plafoanele resurselor considerate ci și de o mul țime de al ți
factori (unii controlabili al ții nu) astfel c ă în realitate profitul este mai mic. Totu și cifra ob ținută
trebuie considerat ă ca o valoare de referin ță în raport cu care este necesar s ă fie evaluate toate
celelalte decizii privin d produc ția.
În contextul dat, combina ția optim ă de bunuri se compune din:
x1* = 50 unit ăți din A1 și x2* = 40 unit ăți din A2
Din punct de vedere economic, neincluderea produsului A3 in combina ția optim ă se justific ă astfel
(vezi ra ționamentul din sec țiunea.7):
Notând cu B baza optim ă A2,A5,A1 din tabelul 6.1.4 rezult ă:
A BA A A A3 3 1
32 2
35 5
31
Se conchide c ă producerea unei unit ăți din A3 ar implica cre șterea produc ției din A2 cu 1/3 unit ăți și
diminuarea produc ției din A1 cu 5/3 unit ăți. Varia ția prof itului are expresia:
2 4 0 31
32
35
35
3 3 ( ) ..um c
Prin urmare profitul total ar sc ădea cu 5/3 u.m. la fiecare unitate din A3 inclus ă în programul de
fabrica ție. în consecin ță A3 nu este rentabil a fi realizat dac ă se are în vedere în exclusivitate criteriul
de performan ță ales. Dup ă cum vom vedea în continuare, situa ția produsului A3 se va schimba în
raport cu alte criterii de evaluare.
Resursele R 1 și R 3 sunt prev ăzute a se consuma în întregime deoarece în solu ția optim ă
x x4 60
. Din resursa R 2 rămâ n nefolosite
x510 unități. Cum aceste considera ții premerg
definitivarea programului de fabrica ție, analiza modului de utilizare a resursei R 2 poate fi continuat ă
în mai multe direc ții. Astfel, conducerea firmei ar putea decide utilizarea ce lor 10 unit ăți în alte
activit ăți productive care nu au fost luate în considerare. Alternativ, se poate impune condi ția
utiliz ării integrale a resursei R 2 (vezi sec țiunea urm ătoare).
În fine, o a treia cale ar fi suplimentarea disponibilelor din R 1 și R 3 în scopul utiliz ării mai
bune a resursei R 2, fire ște în ipoteza c ă acest lucru este posibil și că structura sortimental ă de
produc ție g ăsită este în concordan ță cu op țiunile firmei. Analiza acestui scenariu ne va prilejui o
interesant ă aplicare a teoriei dualit ății. Într-adev ăr, pre țurile duale optime ale celor trei resurse sunt
u u u15
3 2 32
3 0 , ,
(vezi exemplul 4.4.2) și ele arat ă cu c ât cre ște profitul maxim la o
I. PROGRAMARE LINIARA
76
suplimentare cu o unitate a disponibilului acestora. A șa stând lucrurile, conducerea firme i ar fi mai
interesat ă să măreasc ă disponibilul din R 1 decât pe cel din R 3 dar nici o cre ștere combinat ă nu poate
fi exclus ă din start. S ă notăm cu b1 și b3 cantit ățile suplimentare din resursele R 1, R3 pe care firma
ar putea s ă le direc ționeze c ătre pr oducerea bunurilor A1, A2, A3. Noul vector al disponibilului ar fi:
bb
bb
bb b '
130
100
140130
100
14001
31
3
astfel c ă soluția asociat ă bazei B devine:
xBx
x
xBbBbB bb
b' '
2
5
11 1 140
10
5023013
13113
130231
0
3
402
311
33
101
311
33
501
312
33
b b
b b
b b
Menținerea structurii sortimentale optime actuale înseamn ă:
xBb b
b b
b b'
02
311
3340
1
311
3310
1
312
3350
Variația valorii (optime) a func ției obiectiv la modific ările survenite este dat ă de formula:
fcBxBcBxBcBBbB bcBBbcBB bub ' ( )1 1 1 1
5
312
33 b b
Maximiz ând f pe domeniul determinat de inegalit ățile precedente se g ăsește (fie grafic fie cu
ajutorul algoritmului s implex):
( b1)* = 30 ( b3)* = 0 (max)f = 50
Recapitul ând, dac ă vectorul disponibilului ar fi:
b
130 30
100
140 0160
100
140
atunci resursele ar fi în întregime consumate, combina ția optim ă de bunuri ar fi:
x11
3 50 30 40
unități din A1 ,
x22
3 40 30 60 unități din A2 ,
x30
iar profitul maxim ar avea valoarea 310 + 50 =360 u.m.
Să presupunem acum c ă firma hot ărăște să păstreze pentru mai multe perioade (luni)
viitoare actuala structur ă sortimental ă în cadrul c ăreia produc e numai bunurile A1 și A2. Pe parcurs
însă pot interveni modific ări ale profiturilor unitare sau schimb ări de la o lun ă la alta în disponibilele
resurselor (urmare a unor modific ări în structura costurilor de produc ție, sc ăderi și/sau cre șteri de
prețuri p e pia ța de desfacere, schimb ări în structura programelor de aprovizionare cauzate de
modificarea pre țurilor materiilor prime la furnizori etc.) .
77
În aceast ă situa ție conducerea este interesat ă în a ști între ce limite poate varia profitul unui
produs sau di sponibilul unei resurse astfel încât actuala structur ă a produc ției să se men țină.
Să consider ăm profitul unitar al bunului A1 a cărui valoare luat ă în calculele anterioare este
3u.m. Recalcul ăm costurile reduse c3 ,c4 și c6 înlocuind 3 cu profitul va riabil c1 (vezi tabelul
6.1.4) și impunem condi ția de optimalitate cj 0. Ob ținem:
c c c
c c c
c c c31
32
35
3 15
3 110
3
42
31
31
3 18
31
3 1
61
31
32
3 12
3 14
34 0 2 0
4 0 0 0
4 0 0 0
()
() ()
() ()
din care rezult ă intervalul de stabilitate: 2 c1 8. Deci at ât timp c ât profitul pe unitatea de produs
A1 se men ține între 2 și 8 u.m. programul d e produc ție optim r ămâne neschimbat:
x x x1 2 3 50 40 0
numai profitul total maxim variaz ă: max f = 50 c1 +4 40 = 160 + 50 c1.
Pentru profiturile unitare ale bunurilor A2 și A3 intervalele de stabilitate corespunz ătoare sunt
3
2 2 311
3 6 c c,
.
Recalcul ăm valorile variabilelor bazice x 2, x 5 și x 1 reunite în vectorul xB, înlocuind
disponibilul actual al resursei R 1 de 130 unit ăți cu disponibilul variabil b1. Condi ția de optimalitate
xB 0 conduce la inegalit ățile:
x
x
xBb b b
b
b2
5
1112
31
3
1
31
3
1
32
312
31140
3
1
31140
3
1
31280
3100
1400
1
0100
140100 0
b b b1 1 1 70 160 280 , ,
din care rezult ă intervalul de stabilitate: 70 b1 160. în concluzie, dac ă firma men ține disponibilul
resursei R 1 între 70 și 160 unit ăți în combina ția optim ă vor intra numai bunurile A1 și A2 dar în
cantit ățile variabile:
x bx b1280
31
31 22
31140
3
profitul maxim fiind și el variabil:
(max) ( ) ( ) f b b b 3 4280
31
312
31140
3280
35
31
Încă o dat ă remarc ăm faptul c ă viteza de cre ștere a profitului este dat ă tocmai de pre țul dual optim
u15
3
u.m. al resursei R 1.
Pentru resursele R 2 și R3 intervalele de stabilitate corespunz ătoare sunt b2 90 respectiv 65 b3
170.
I. PROGRAMARE LINIARA
78
3.6.2. Postoptimizare: A) cazul modific ării unor coeficien ți din func ția obiectiv (c)
Cazuistica postoptimizării cuprinde:
A) Cazul în care se modifică unii coeficienți din funcția obiectiv (c);
B) Cazul în care modificările se produc în vectorul termenilor liberi (b);
C) Introducerea unei noi activități în model;
D) Adăugarea unei noi restricții ;
E) Modificarea unei coloane din matricea coeficienților.
Concret, în cadrul cursului vom aborda ca zurile A, B și D. Pentru cazurile C și E, a se vedea
www.asecib.ase.ro – Cursuri on -line – 9. Nica V. și colectiv, Cercetări Operaționale I .
A) cazul în care se modifică unii coeficienți din funcția obiectiv (c)
Fie: Problema original ă Problema modificat ă
()
(max)PAx b
x
fcx
0
(')
(max) ''PAx b
x
fcx
0
unde
ccc cn '(,,…,)' ' '1 2 este vectorul noilor coeficien ți ai func ției obiectiv. S ă presupunem c ă (P) a
fost deja rezolvat ă cu aju torul algoritmului simplex și că soluția optim ă x* este asociat ă unei baze B.
Se remarc ă faptul c ă (P) și (P') au aceea și mul țime de solu ții admisibile. În consecin ță, x* este o
soluție de baz ă admisibil ă pentru programul modificat (P'). Pentru a testa opt imalitatea solu ției x* în
raport cu noua func ție obiectiv se recalculeaz ă costurile reduse:
ccBA c jJjB j
j ' ,1
Dacă toți c'j 0 , j J , x* este solu ție optim ă și pentru (P'). În caz contrar, rezolvarea programului
(P') se face cu ajutorul algoritm ului simplex primal, lu ând x* ca solu ție de start.
Exemplul 6.2.1 În studiul, de caz din sec țiunea 6.1 am determinat intervalele de stabilitate ale
soluției optime x* în raport cu fiecare din coeficien ții c1, c2, c3 ai func ției obiectiv. Deoarece valoril e
actuale 3, 4, 2 u.m. ale acestor coeficien ți sunt situate în interiorul intervalelor de stabilitate
corespunz ătoare, conchidem c ă soluția x* este stabil ă în raport cu fiecare din ei și chiar cu ansamblul
lor: varia ții "mici" (de c âteva procente, s ă zicem ) ale profiturilor unitare în jurul valorilor actuale nu
modific ă soluția optim ă găsită și implic ă doar o varia ție "mic ă" a profitului total.
Pentru exemplificare, s ă presupunem c ă profiturile bunurilor A1 și A3 cresc cu 5% iar profitul
bunului A2 scade cu 10%:
c c c15
100 210
100 35
100 3 3315 4 436 2 221 , , ,
Înlocuind în tabelul 6.1.4 coeficien ții c1 = 3 , c2 = 4 , c3 = 2 cu coeficien ții de mai sus și recalcul ând
costurile reduse rezult ă tabelul:
3,15 3,6 2,1 0 0 0
CB B VVB A1 A2 A3 A4 A5 A6
3,6 A2 40 0 1 -1/3 2/3 0 -1/3
0 A5 10 0 0 2/3 -1/3 1 -1/3
3,15 A1 50 1 0 5/3 -1/3 0 2/3
f 301,5 * * 1,95 1,35 * 0,9 CURSUL 11
79
Tabelul 6.2.1
Prin urmare efectul combinat al schimb ărilor survenite în structura vectorului profiturilor u nitare se
materializeaz ă doar într-o reducere a profitului total cu 310 – 301,5 = 8,5 u.m. ceea ce reprezint ă
2,74% din valoarea ini țială!
Altfel stau lucrurile dac ă, de exemplu, profitul unitar al bunului A1 ar fi de 2 u.m. în loc de 3
u.m. Ne reamintim c ă 2 este extremitatea st ângă a intervalului de stabilitate al solu ției x* în raport cu
c1 = 3! Introducem aceste modific ări în tabelul 6.1.4 obținând tabelul 6.2.2.
2 4 2 0 0 0
CB B VVB A1 A2 A3 A4 A5 A6
4 A2 40 0 1 -1/3 2/3 0 -1/3
0 A5 10 0 0 2/3 -1/3 1 -1/3
2 A1 50 1 0 5/3 -1/3 0 2/3
f 260 * * 0 2 * 0
Tabelul 6.2.2
Se observ ă că c3 = 0 , c6 = 0 de unde tragem concluzia c ă problema are mai multe solu ții optime de
bază (vezi sec țiunea 4.2). Acestea se ob țin introduc ând succesiv în baza c urent ă coloanele A3 și A6
(vezi tabelele 6.2.3 – 6.2.4).
2 4 2 0 0 0
CB B VVB A1 A2 A3 A4 A5 A6
4 A2 45 0 1 0 1/2 1/2 -1/2
2 A3 15 0 0 1 -1/2 3/2 -1/2
2 A1 25 1 0 0 3/2 -5/2 3/2
f 260 * * * 2 0 0
Tabelul 6.2.3
2 4 2 0 0 0
CB B VVB A1 A2 A3 A4 A5 A6
4 A2 65 1/2 1 1/2 1/2 0 0
0 A5 35 1/2 0 3/2 -1/2 1 0
0 A6 75 3/2 0 5/2 -1/2 0 1
f 260 0 * 0 2 * *
Tabelul 6.2.4
Celelalte dou ă soluții optime de baz ă au componentele:
x x x1 2 3 25 45 15 , ,
(val. var. de abater e:
x x x4 5 60 )
respectiv:
0 ,65 ,03 2 1 x x x
(val. var. de abatere:
75 ,35 ,06 5 4 x x x )
Ne reamintim c ă în aceast ă situa ție exist ă o infinitate de solu ții optime de forma:
x x x x 1 2 3
cu 1 , 2 , 3 0 și 1 + 2 + 3 = 1
(combina ții convexe ale solu țiilor optime de baz ă),în care:
x1 = 50 1 + 25 2 x4 = 0
x2 = 40 1 + 45 2 + 653 x5 = 10 1 + 35 3
I. PROGRAMARE LINIARA
80
x3 = 15 2 x6 = 75 3
Dacă se ia de exemplu: 1 = 3/5 , 2 = 1/5 , 3 = 1/5 se g ăsește solu ția:
x1 = 35 , x2 = 46 , x3 = 3 ( x4 = 0 , x5 = 13 , x6 = 15 )
care, de și optim ă, nu este o solu ție de baz ă având cinci componente nenule, cu dou ă mai mult dec ât
numărul restric țiilor!
Să ne întoarcem la problema stabilit ății solu ției x* în situa ția mic șorării profitului bunului A1
la 2 u.m.
Urmărind datele din tabelele 6.2.3 – 6.2.4 se constat ă că o nou ă scădere oric ât de mic ă a
profitului bunului A1 face ca solu țiile x** și x** să nu mai fie optime! Solu ția care maximizeaz ă
profit ul este x*** și ea prevede producerea în exclusivitate a bunului A2 spre deosebire de solu țiile x*
și x** care au o structur ă sortimental ă mai larg ă! Astfel o mic ă scădere a profitului bunului A1 sub
valoarea actual ă de 2 u.m. antreneaz ă schimb ări chiar în structura sortimental ă a programului de
produc ție! În consecin ță, solu ția x* este instabil ă în raport cu eventualele oscila ții ale profitului
bunului A1 în jurul valorii de 2 u.m.
Exemplul 6.2.2 În studiul de caz din sec țiunea 6.1 a fost avansat ă o propunere de program de
produc ție care urm ărea maximizarea profitului total. În prezent, firma vinde produsele A1, A2, A3 la
prețurile 12, 18 respectiv 16 u.m. astfel c ă profitul maxim de 310 u.m. ar corespunde unui venit total
de:
50 12 + 40 18 = 1320 u.m.
În varianta construit ă rata profitului ar fi de
310
1320100 235%, . Se pune firesc întrebarea dac ă
propunerea de plan elaborat ă în 6.1 maximizeaz ă venitul total al firmei, bine înțeles în ipotezele date
adică mărginindu -ne numai la r esursele R 1, R2, R3 și la bunurile A1, A2, A3 ! Pentru a r ăspunde la
întrebare, în tabelul simplex optim 6.1.4 schimb ăm coeficien ții c1 = 3, c2 = 4, c3 = 2 ai func ției "profit
total" f cu coeficien ții
c c c1 2 3 12 18 16 , , ai func ției "venit total" f' și recalcul ăm costurile
reduse
ccc3 4 6 ,, . Găsim:
c c c3 4 6 2 8 2 , , . Deoarece
c30 , solu ția care maximizeaz ă profitul
total nu conduce și la un venit maxim: introducerea bunului A3 în combina ția actual ă ar majora
venitul actual de 1320 u.m. cu 2 u.m. pe unitatea de produs A3!
Aplic ând algoritmul simplex primal, într-o singur ă iterație se ob ține solu ția care maximizeaz ă
venitul total (vezi tabelele 6.2.5 – 6.2.6):
x125
u. din A1 ,
x235 u. din A2 ,
x315 u. din A3
La un venit maxim de 1350 u.m. profitul firmei ar fi de: 25 3 + 35 4 + 15 2 = 245 u.m. iar
rata profitului ar fi în acest caz de numai 18,1%.
12 18 16 0 0 0
CB B VVB A1 A2 A3 A4 A5 A6
18 A2 40 0 1 -1/3 2/3 0 -1/3
0 A5 10 0 0 2/3 -1/3 1 -1/3
12 A1 50 1 0 5/3 -1/3 0 2/3
f' 1320 * * -2 8 * 2
18 A2 35 0 1 0 1/2 1/2 -1/2
16 A3 15 0 0 1 -1/2 3/2 -1/2
12 A1 25 1 0 0 1/2 -5/2 3/2
f' 1350 * * * 7 3 1
Tabelele 6.2.5 – 6.2.6
81
Deși rata profitului a sc ăzut cu 23, 5 – 18,1 = 5,4% noua solu ție are o serie de calit ăți: asigur ă
o produc ție diversificat ă întruc ât se produc toate bunurile și utilizeaz ă integral resursele disponibile.
Să observ ăm de asemenea că prețurile duale optime ale celor trei resurse s -au modificat:
u u u1 2 3 7 3 1 , ,
față de
u u u15
3 2 32
3 0 , ,
Se justific ă astfel afirma ția din sec țiunea 2.4 potrivit c ăreia pre țurile duale nu reflect ă
valoarea intrinsec ă a resurselor ci arat ă măsura implic ării acestora în procesul de optimizare a
obiectivulu i urm ărit.
Exemplul 6.2.3 Am v ăzut c ă în solu ția care maximiza profitul, resursa R 2 nu era folosit ă în
întregime. Se poate pune problema determin ării unei solu ții care s ă maximizeze profitul cu condi ția
utiliz ării integrale a acestei resurse. Pentru a o bține un r ăspuns prin reoptimizare, transform ăm
variabila de abatere x5 în variabil ă artificial ă înlocuind în func ția obiectiv coeficientul s ău c5 = 0 cu o
constant ă negativ ă -M << 0. Introducem acest coeficient în tabelul 6.1.4 și aplic ăm algoritmul
simp lex primal. Invit ăm cititorul s ă facă calculele necesare anun țându-l că va trebui s ă obțină soluția
care maximizeaz ă venitul firmei.
3.6.3. Postoptimizare: B) cazul modific ărilor în vectorul termenilor liberi (b)
Problema original ă Problema modificat ă
()
(max)PAx b
x
fcx
0
(')'
(max)PAx b
x
fcx
0
unde
bbb bmT' ,,…,' ' '1 2 este noul vector de termeni liberi. Se observ ă ușor că (P) și (P') au acelea și
baze dual admisibile. Fie B o baz ă optimal ă a programului (P). Calcul ăm solu ția x' a programului
modificat (P'), asociat ă bazei B:
x'B=B-1b' x'S=0
Cum am remarcat deja, x' este o solu ție dual admisibil ă pentru (P'). Dac ă x'B 0 atunci x' este și
admisibil ă și deci optim ă. Altminteri , rezolvarea problemei (P') se va face cu ajutorul algoritmului
simplex dual, lu ând x' ca solu ție de start.
3.6.4. Postoptimizare: D) adăugarea unei noi restric ții
Problema original ă Problema modificat ă
()…
…
………………………………….
…
, ,…,
(max) …Paxax ax b
axax ax b
axax ax b
x x x
fcxcx cxnn
nn
m m mn n m
n
nn11 1 12 2 1 1
21 1 22 2 2 2
11 22
1 2
11 220 0 0
(')…
…
…………………………………..
…
…
, ,…,
(max) …Paxax ax b
axax ax b
axax ax b
x x x
x x x
fcxcx cxnn
nn
m m mn n m
nn
n
nn11 1 12 2 1 1
21 1 22 2 2 2
11 22
11 22
1 2
11 220 0 0
I. PROGRAMARE LINIARA
82
Fie B baza optim ă a programului (P) g ăsită prin aplicarea algoritmului simplex. În consecin ță, forma
explicit ă a problemei (P) în raport cu baza B:
(),
, ; , Px ax b iI
x iIx jJ
f cx fBiijji
jJ
i j
jj
jJ
0 0 (6.5.1)
este disponibil ă, constantele alc ătuitoare form ând tabelul simplex optim. Dac ă soluția optim ă x* a
programului (P) verific ă restric ția suplimentar ă atunci x* este solu ția optim ă și a problemei extinse. În
caz contrar, adic ă atunci c ând :
11 22 x x xnn* * *… (6.5.2)
proced ăm dup ă cum urmeaz ă:
Transform ăm inegalitatea suplimentar ă în egalitate ad ăugând variabila de abatere x n+1:
11 22 1 x x xxnn n … (6.5.3)
Folosind forma explic ită (6.5.1.) elimin ăm din (6.5.3.) variabilele bazice xi , iI (în caz c ă
apar). Ob ținem o egalitate de forma:
jj n
jJx x
1 (6.5.4.)
Se constat ă imediat c ă este nega tiv deoarece :
jj
jn
x*0
1 conform (6.5.2.)
Adăugând (6.5.4.) la (6.5.1) ob ținem forma explicit ă a programului extins P' în raport cu baza B'
format ă din coloanele bazei B (coloane extinse cu coeficien ții corespunz ători din restric ția
suplimentar ă ! ) plus coloana unitar ă:
An+1=(0,0,…,o,1)TRn+1
Soluția asociat ă acestei baze:
xi=bi ,iI ; x n+1=0 ; x j=0 , jJ (6.5.5)
nu este admisibil ă dar verific ă criteriul de optimalitate, altfel spus este d ual admisibil ă. În consecin ță,
pentru rezolvarea problemei extinse (P') vom aplica algoritmul simplex dual, pornind de la solu ția
(6.5.5).
Exemplul 6.5.1 În studiul de caz din sec țiunea 6.1, la elaborarea programului de produc ție
care maximizeaz ă profi tul total, au fost avute în vedere numai resursele R 1, R2, R3 . Dacă în procesul
de produc ție sunt folosite și alte resurse, se na ște întrebarea dac ă nu cumva solu ția găsită implic ă
consumuri ce dep ășesc disponibilul din acestea. Pentru exemplificare, s ă consider ăm o a patra
resurs ă R4 al cărei stoc disponibil b4 nu este deocamdat ă stabilit. Pentru cele trei bunuri A1, A2, A3
consumurile specifice din R 4 sunt de 2, 2 respectiv 1 unit ăți. Condi ția de încadrare a consumului din
R4 în disponibil conduce la ine galitatea:
2 21 2 3 4 x xxb (6.5.6)
Pentru ca solu ția care maximizeaz ă profitul total:
x x x1 2 3 50 40 0 (6.5.7)
83
să satisfac ă restric ția de mai sus este necesar ca:
2 50 + 2 40 +1 0 b4 b4 180
Prin urmare dac ă firma reu șește să asigure un disponibil de cel pu țin 180 unit ăți din R 4, programul
(6.5.7) nu sufer ă modific ări. Dac ă b4 < 180, solu ția (6.5.7) nu mai satisface restric ția suplimentar ă
(6.5.6).S ă vedem ce se întâmplă în acest caz!
Tran sform ăm (6.5.6) în egalitate, ad ăugând variabila de abatere x7:
2 21 2 3 7 4 x xxxb (6.5.8)
Exprim ăm variabilele bazice x1 , x2 în func ție de cele nebazice folosind datele din tabelul 6.1.4:
40 40
50 5021
332
341
36 21
332
341
36
15
331
342
36 15
331
342
36
x x x x x x x x
x x x x x x x x (6.5.9)
Elimi nând x1 , x2 din (6.5.8) se g ăsește în final:
5
332
342
36 7 4180 x x xxb (6.5.10)
Introducem coeficien ții egalit ății (6.5.10) în tabelul simplex 6.1.4:
3 4 2 0 0 0 0
CB B VVB A1 A2 A3 A4 A5 A6 A7
4 A2 40 0 1 -1/3 2/3 0 -1/3 0
0 A5 10 0 0 2/3 -1/3 1 -1/3 0
3 A1 50 1 0 5/3 -1/3 0 2/3 0
0 A7 b4 – 180 0 0 -5/3 -2/3 0 -2/3 1
f 310 * * 5/3 5/3 * 2/3 *
Tabelul 6.5.1
Conform instruc țiunilor algoritmului simplex dual, A7 părăsește baza curent ă. Raport ând costurile
reduse cj la elementele corespunz ătoare, dar negative din linia "A7" a tabelului 6.5.1 g ăsim c ă A3
sau A6 trebuie s ă intre în baz ă pentru a asigura dual admisibilitatea noii solu ții (adic ă satisfacerea
testului de optimalitate). Din punct de vedere economic ,se impune introducerea lui A3 pentru c ă
aceasta ar însemna includerea bunului A3 în programul de fabrica ție, bine înțeles în ipoteza c ă noua
soluție ar fi și primal admisibil ă!
Înlocuind A7 cu A3 în baza curent ă obținem solu ția dual admisibil ă din tabelu l 6.5.2 (pivotul
transform ării este deja marcat în tabelul 6.5.1):
CB B VVB A1 A2 A3 A4 A5 A6 A7
4 A2 76 – (1/5) b4 0 1 0 4/5 0 -1/5 -1/5
0 A5 (2/5) b4 – 62 0 0 0 -3/5 1 -3/5 2/5
3 A1 b4 – 180 1 0 0 -1 0 0 1
2 A3 108 –
(3/5) b4 0 0 1 2/5 0 2/5 -3/5
f 130 + b4 * * * 1 * 0 1
Tabelul 6.5.2
Condi ția de admisibilitate primal ă conduce la inegalit ățile:
I. PROGRAMARE LINIARA
84
76 0 380
62 0 155
130 0 130
108 0 180155 1801
54 4
2
54 4
4 4
3
54 44
b b
b b
b b
b bb (6.5.11)
În concluzie, dac ă b4 satisface (6.5.11) atunci solu ția din tabelul 6.5.2 adic ă:
xb x bx b1 4 21
54 33
54 130 76 108 (6.5.12)
este optim ă, aduc ând firmei, în caz de realizare un profit de 130 + b4 u.m. Toate resursele sunt
prevăzute a fi utilizate integral cu excep ția lui R 2 din care r ămîn
x b52
5462 unități.
Observ ăm că dacă b4 = 155 unit ăți din R 4, toate resursele sunt folosite, programul de
fabrica ție (6.5.12) va avea componentele:
x1 = 25 x2 = 45 x3 = 15
și profitul corespunz ător ar fi de 130 +155 = 285 u.m.
Pe m ăsură ce b4 se apropie de valoarea maxim ă 180 cre ște și profitul c ătre valoarea 130 + 180
= 310 u.m. în acela și timp cantitatea nefolosit ă din R 2 se m ărește apropiindu -se de valoarea 10 iar
produc ția bunului A3 tinde c ătre 0. Pentru b4 = 180 reg ăsim solu ția (6.5.7).
Exemplul 6.5.2 Relu ăm problema maximiz ării profitului f irmei X. Care va fi programul de
produc ție dac ă se impune cerin ța ca cel pu țin 8% din venitul firmei s ă fie realizat din desfacerea
bunului A3?
Folosind pre țurile anun țate în exemplul 6.2.2 noua condi ție se formalizeaz ă prin inegalitatea:
16 12 18 16 6 9 92 03 1 2 3 1 2 38
100x x x x x x x ( ) (6.5.13)
Introducem variabila de abatere x7 și elimin ăm variabilele bazice x1, x2 folosind rela țiile (6.5.9).
Rezult ă egalitatea:
99 4 6603 4 6 7 x xxx
ai cărei coeficien ți se ata șează tabelului simplex 6.1.4, dup ă care se aplic ă algoritmul simplex dual
(vezi tabelele 6.5.3 – 6.5.4)
Într-o singur ă iterație se ob ține programul optim:
x x x f18
9 22
9 32
38
9 38 42 6 298** ** **(max) (6.5.14)
(valorile variabilelor de abatere:
x x x4 6 54
9 0 5** ** **, )
3 4 2 0 0 0 0
CB B VVB A1 A2 A3 A4 A5 A6 A7
4 A2 40 0 1 -1/3 2/3 0 -1/3 0
0 A5 10 0 0 2/3 -1/3 1 -1/3 0
3 A1 50 1 0 5/3 -1/3 0 2/3 0
0 A7 -660 0 0 -99 -4 0 -1 1
f 310 * * 5/3 5/3 * 2/3 *
A2 380/9
A5 50/9
A1 350/9
A3 20/3
f 2690/9
Tabelele 6.5.3 – 6.5.4
85
Acest exemplu ne ofer ă ocazia de a semnala și discuta un aspect nou, care nu a fost avut în
vedere în considera țiile teoretice dezvoltate p ână acum. Deoarece firma X produce aparatur ă
electronic ă este de presupus c ă bunurile A1, A2, A3 se măsoară în unit ăți indivizibile ca de exemplu în
bucăți. Dac ă bunul A1 este în fapt un calculator, a produce o frac ție din el este lipsit de sens; ori se
fabric ă un întreg calculator ori nu. Prin urmare în orice solu ție admisibil ă valorile variabilelor x 1, x2,
x3 trebuie s ă fie nu numai nenegative dar și întregi! Iată de ce solu ția (6.5.14) nu poate fi însușită.
Vom proceda la rotunjirea componentelor frac ționare în ideea c ă soluția optim ă întreag ă se
află în "apropierea" solu ției optime "frac ționare". Opera ția de rotunjire trebuie astfel f ăcută încât
rezultatul s ă fie o solu ție admisibil ă adică să verifice restric țiile problemei. Este firesc s ă accept ăm
soluția ob ținută în acest mod cel pu țin ca solu ție suboptimal ă – în unele contexte practice acest lucru
este p erfect justificat de faptul c ă valorile permise variabilelor sunt suficient de mari astfel încât
efectul rotunjirii s ă fie neglijabil.
Rotunjind superior
x1** și inferior
x2** ,
x3** se găsește combina ția:
x x x1 2 3 39 42 6
care se încadreaz ă în disponibilele date dar nu verific ă restric ția suplimentar ă (6.5.13), deoarece
valoarea produc ției din A3 reprezint ă numai 7,3% din valoarea întregii produc ții.
Rotunjind inferior
x1** ,
x2** și superior
x3** se ob ține o solu ție admisibil ă întreag ă:
x x x fx1 2 3 38 42 7 296 ()
u.m.
care nu este optim ă. Cea mai bun ă soluție întreag ă este:
x x x fx10
20
30 037 43 7 297 () u.m. (6.5.15)
În cadrul acestui program, valoa rea produc ției din bunul A3 reprezint ă 8,4% din valoarea întregii
produc ții. Obținerea acestei soluții se face prin aplicarea metodelor specifice Programării Liniare în
Numere Întregi (Curs CO anul 3).
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: OPTIMIZAREA PROCESELOR ECONOMICE UTILIZÂND PROGRAMARE A LINIARĂ [601458] (ID: 601458)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.