PROGRAMARE LINIARĂ
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).
1
Exemple:
1) Problema firmei. Considerăm un sistem de producţie, de exemplu
o firmă, care produce n bunuri G1,G2,...,Gn utilizând pentru aceasta m
categorii de resurse R1,R2,...,Rm (materii prime, 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 cantitatea 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 Gj. Fie deasemeni bi cantitatea disponibilă din resursa Ri şi
cj preţul (sau profitul) unitar al bunului Gj.
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 Gj care urmează a fi produsă. Problema
enunţată mai înainte devine:
Să se găsească valorile numerice x1,x2,...,xn care maximizează funcţia:
f = c1x1+c2x2+ …+cnxn
cu satisfacerea restricţiilor:
a11x1 + a12x2 + … + a1nxn ≤ b1
a21x1 + a22x2 + … + a2nxn ≤ b2
……………………..
am1x1 + am2x2 + …+amnxn ≤ bm
2
şi a condiţiilor de nenegativitate:
x1 ≥ 0, x2 ≥ 0, … xn ≥ 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 pot 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 specialitate. 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 N1, N2, … Nm sunt avute în
vedere în sensul că alimentul combinat trebuie să conţină cel puţin b1, b2, …
bm unităţi specifice din fiecare. Să presupunem cunoscute următoarele:
cantitatea aij din principiul nutritiv Ni conţinută într-o unitate din tipul
de hrană Fj;
preţul unitar cj al tipului de hrană Fj.
Notăm cu x1,x22,...,xn cantităţile din felurile de hrană F1,F2,...,Fn care
trebuie cumpărate în vederea elaborării dietei. Formal, x1, x2, ... xn vor trebui
determinate astfel încât:
costul f = c1x1 + c2x2 + … + cnxn al alimentelor cumpărate să fie
minim.
amestecul să conţină principiile nutritive N1,N2,...,Nm în cantităţi cel
puţin egale cu b1,b2,...,bm, adică:
3
a11x1 + a12x2 + … + a1nxn ≥ b1
a21x1 + a22x2 + … + a2nxn ≥ b2
am1x1 + am2x2 + … + amnxn ≥ bm
........................................
x1 ≥ 0, x2 ≥ 0, … xn ≥ 0
Din nou au fost tacit utilizate ipotezele de liniaritate întâlnite şi în
modelul precedent.
Soluţii admisibile ale unei probleme de programare liniară
Considerăm o problemă de programare liniară (P) cu m restricţii
egalităţ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ă.
Să se determine: x* € A cu proprietatea: f *(x) = max sau min f(x), x € A
Este posibil ca (P) să aibe 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 soluţii admisibile dealungul căruia funcţia obiectiv să 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
inchisă (î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
4
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ă aibe
optim finit.
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 programare 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:
n
∑ aj xj ≤ bi i=l, …, mf = 1
xj ≥ 0 j=l, …, n sau n
(max) f= ∑ cjxj
f =1
matriceal Ax ≤ b x ≥ 0 unde ( max ) f =cx
a11 a12 …… a1n A = a21
a22 ……. a2n
am1 am2 ……. amn
b1
5
b2
. b = . . bm
x1
x = x2
. . xn
c = c1, c2,… cn
O problemă în formă canonică de minimizare se va scrie:
n
∑ aijxj ≥ bi Ax ≥ b
f =1 ↔ x ≥ 0
xj ≥ 0 (min) f= cx
n
(min) f= ∑ cjxj
f=1
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ă:
egalitate se poate înlocui cu două inegalităţi de sens contrar;
restricţie neconcordantă devine concordantă prin înmulţire cu -1;
6
putem schimba sensul optimizării funcţiei obiectiv, graţie formulei
generale:
min f(x)= -max –f(x)
x€A x€A
Î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.
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 rezolvare 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:
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.
Restricţiile inegalităţi nu se modifică.
Noile variabile introduse nu apar în funcţia obiectiv a problemei
originale (alternativ, spunem că ele apar cu coeficienţi nuli).
7
Exemplu
(max)f = 7x1 + 9x2 + 8x3
5x1 + 2x2- x3 ≥ 4
(P) 3x1 + x2 + x3 = 5 →
x1 + 2x2 + 3x3 ≤ 9
x1≥ 0, x2≥ 0, x3 ≥0
(max) f= 7x1 + 9x2+ 8x3
5x1 + 2x2 – x3 – x4 = 4
(FSP) 3x1 + x2 + x3 =5
x1 + 2x2 +3x3 + …. +x5 = 9
xj ≥ 0, j= 1,…,5
ELEMENTE DE PROGRAMARE NELINIARĂ
Caracteristic unei probleme de programare liniară este faptul că toate
funcţiile implicate în ea – funcţia obiectiv şi restricţii – sunt liniare. Deşi
ipotezele de liniaritate au loc în numeroase situaţii practice tot atât de
frecvent ale nu sunt îndeplinite. De fapt, mulţi economişti teoreticieni au
constatat că un anume grad de neliniaritate este regula şi nu excepţia în
problemele de planificare economică.
8
Există deci o puternică motivaţie economică pentru studiul
problemelor de programare neliniară a căror formă canonică de prezentare
este:
Dacă în cazul liniar ( f si gi sunt funcţii liniare) există (cel puţin) o
metodă generală de rezolvare – de exemplu metoda simplex – în cazul
neliniar nu există o asemenea metodă. Totuşi progrese substanţiale au fost
făcute în unele cazuri speciale prin impunerea unor condiţii asupra funcţiilor
f si gi .Aria acestor cazuri speciale este destul de mare astfel că nu ne vom
putea opri decât asupra unora mai relevante.
Neliniaritatea în modelarea proceselor economice
Să considerăm problema firmei al cărei obiectiv este determinarea
unui program de producţie astfel încât:
necesarul de resurse pentru susţinerea programului să se încadreze în
disponibile date;
profitul total, rezultat din vânzarea bunurilor produse să fie maxim.
În multe situaţii practice, preţurile şi costurile unitare de fabricaţie pot fi
considerate constante astfel că şi profiturile unitare vor fi la fel. În
consecinţă, în aceste cazuri funcţia obiectiv, care reprezintă profitul total, va
fi liniară:
(xj reprezintă cantitatea produsă şi vândută din bunul j;Pj este profitul unitar
corespunzător bunului j ).
9
Nu întotdeauna tot ceea ce se produce dintr-un bun se poate şi vinde la
un anumit preţ. Apare aşa numita problemă a elasticităţii preţului: cantitatea
de marfă vândută se află într-o relaţie inversă cu preţul cerut aşa cum arată
curba preţ – cerere .
O altă sursă de neliniarităţi în funcţia obiectiv o constituie variaţia
costului marginal - pentru producerea a încă unei unităţi dintr-un produs - în
funcţie de nivelul producţiei. Acest cost marginal poate să scadă în unele
situaţii (ca urmare a trecerii la producţia de serie, al acumulării experienţei şi
al perfecţionării procesului de producţie) iar în altele poate să crească (ore
suplimentare, utilizarea în regim de urgenţă a unor capacităţi de producţie
mai costisitoare pentru satisfacerea unor cereri imediate).
Neliniaritatea poate apare şi în restricţii într-o manieră asemănătoare. De
exemplu, dacă există o restricţie bugetară asupra costului producţiei, relaţia
corespunzătoare va fi cu siguranţă neliniară în cazul în care costul marginal
al producţiei este variabil.
Pentru restricţiile privitoare la alte tipuri de resurse, neliniaritatea
apare ori de câte ori consumurile nu sunt direct proporţionale cu nivelele de
producţie.
În problema transporturilor se urmăreşte determinarea unui program
pentru transportul unui produs de la diferite surse la diverşi consumatori,
cunoscându-se cantităţile disponibile şi cererile, astfel încât costul total al
transportului să fie minim. În programarea liniară, costul transportului unei
unităţi de produs de la o anumită sursă la o anumită destinaţie a fost
considerat constant, independent de cantitatea transportată. De multe ori se
întâmplă ca la cantităţi mari să se acorde la transport anumite reduceri; în
aceste situaţii, costul marginal al transportului unei unităţi suplimentare
10
tinde să scadă şi ca o consecinţă costul C(x) al transportării cantităţii x este
dat de o funcţie neliniară.
Fie x cantitatea transportată şi C(x) costul transportării cantităţii x.
dacă 0 x 6 costul unitar de transport este de 6.5 u.m. deci
C1(x) = 6.5x u.m.;
dacă 6 x 15 , 6 unităţi vor fi transportate cu costul 6.5 u.m. per unitate
iar următoarele cu numai 5 u.m. per unitate astfel că :
C2(x) = 6.5 6 + 5.(x - 6) = 9 + 5.x
dacă 15 x 27 , 15 unităţi vor fi transportate cu costul C2(15) = 84 iar
următoarele cu numai 4 u.m. per unitate. Costul total va fi :
C3(x) = 84 + 4.(x – 15) = 24 + 4.x
dacă 27 < x 45 , 27 unităţi vor fi transportate cu costul C3(27) = 132 iar
următoarele cu 3 u.m. per unitate de unde costul total:
C4(x) = 132 + 3.(x – 27) = 51 + 3.x
Prin urmare, costul C(x) al transportării a x unităţi este dat de funcţia:
care este neliniară dar “liniară pe porţiuni”. Din fig. 4.2b) rezultă că pantele
porţiunilor liniare ale graficului funcţiei C(x) sunt chiar costurile marginale
Dacă fiecare cuplu (sursă i , destinaţie j ) are o funcţie cost similară,
aşa încât costul transportului a xij unităţi de la i la j este dat de funcţia
neliniară Cij(xij) atunci costul total este reprezentat de funcţia de asemenea
neliniară;
11
Aceste consideraţii nu modifică restricţiile problemei de transport care
rămân liniare:
suma cantităţilor livrate de sursa i nu
depăşeşte disponibilul său;
suma cantităţilor primite de consumatorul j
acoperă cererea sa.
La terminalul unei conducte petroliere situat într-un port sosesc vasele
A,B,C pentru a fi încărcate. Vasul A trebuie încărcat cu 15 mii tone în
maximum 48 de ore, vasul B trebuie încărcat cu 20 mii tone în maximum 60
de ore iar vasul C trebuie încărcat cu 45 mii tone în maximum 70 de ore.
(timpii de staţionare pentru încărcare se numesc timpi de stalii şi sunt
prevăzuţi în contractul de transport; orice depăşire a acestor timpi
(contrastalii) se penalizează, penalizarea depinzând de tipul navei etc)
Terminalul dispune de pompe şi conducte care însumează o capacitate de
încărcare de 1200 tone pe oră. Se pune problema de a stabili ce debit trebuie
afectat fiecărei nave astfel încât ele să fie încărcate în cel mai scurt timp.
Dacă se notează cu y1 , y2 , y3 deditele repartizate vaselor A,B,C şi cu
x1 , x2 , x3 numărul de ore necesar încărcării lor se obţine uşor următorul
program neliniar:
Eliminând y1 , y2 , y3 rezultă modelul mai simplu:
12
Dificultăţi cauzate de neliniaritate
Considerăm problema de optimizare:
a cărei mulţime de soluţii admisibile o notăm cu A:
A =
(P) se rescrie:
Să se determine x*A cu proprietatea:
Este cunoscut faptul că dacă (P) este un program liniar (adică f şi
g1,g2,…,gm sunt funcţii liniare) atunci mulţimea A este convexă şi mai mult
chiar poliedrală (intersecţie finită de semispaţii).Aceste proprietăţi ale
mulţimii A plus faptul că funcţia obiectiv este şi ea liniară ne asigură că:
soluţie optimă – dacă există – este un punct de minim global adică:
f(x*) f(x) () x A
cel puţin o soluţie este un vârf al mulţimii A.
Cum numărul vârfurilor mulţimii poliedrale A este finit urmează că,
pentru programul liniar (P), problema determinării unei soluţii optime x* din
mulţimea, în general infinită, a tuturor soluţiilor admisibile se reduce la
găsirea lui x* în mulţimea finită a vârfurilor acestei mulţimi.
Metoda simplex realizează în mod sistematic această căutare oferind într-un
număr finit de paşi (iteraţii) soluţia optimă x*.
Neliniaritatea obiectivului sau a unora dintre restricţii face ca unele din
proprietăţile relevate mai sus să dispară fapt care duce la complicarea
sarcinii de determinare a optimului.
Clase de probleme neliniare
1) Problemele de optimizare fără restricţii au forma generală:
13
Să se determine x* Rn care minimizează valoarea funcţiei
minimul fiind luat dupa toţi x Rn în care funcţia f este definită.
2) Probleme de optimizare cu restricţii liniare şi funcţie obiectiv
neliniară. În această clasă un loc deosebit îl ocupă problemele de
programare patratică în care funcţia obiectiv este un polinom de gradul doi
în variabilele sale:
Importanţa problemelor de programare patratică este motivată prin:
faptul că modelează cu suficientă acurateţe multe situaţii practice;
se rezolvă prin metode derivate din metoda simplex într-un număr
finit de paşi;
rezolvarea multor probleme cu restricţii liniare şi funcţie obiectiv
neliniară se poate reduce la rezolvarea unei secvenţe de probleme de
programare patratică ale căror funcţii obiectiv aproximează din ce în
ce mai bine obiectivul neliniar original.
3) Problemele de programare convexă se caracterizează prin:
funcţie obiectiv convexă dacă aceasta se minimizează (echivalent:
funcţie obiectiv concavă dacă aceasta se maximizează);
restricţiile inegalităţi sunt de forma în care gi este o funcţie
convexă (echivalent cu gi funcţie concavă);
eventualele restricţii egalităţi sunt liniare, cerinţă motivată prin
aceea că funcţiile liniare sunt singurele funcţii simultan convexe şi
concave.
Problemele convexe au următoarele proprietăţi fundamentale:
mulţimea soluţiilor admisibile este convexă;
14
funcţia obiectiv admite cel mult un optim (minim sau maxim) local; automat
acesta va fi un optim global şi va reprezenta optimul problemei;
dacă optimul liber (nerestricţionat) al funcţiei obiectiv nu este o soluţie
admisibilă atunci optimul restricţionat se găseşte cu necesitate pe frontiera
mulţimii A .Importanţa acestei clase de probleme este covârşitoare. Într-
adevăr:
programarea convexă include programarea liniară ;
în acest domeniu a fost depus cel mai mare efort de cercetare şi s-au obţinut
cele mai puternice rezultate teoretice (cum ar fi teoria dualităţii neliniare,
condiţiile de optimalitate Kuhn – Tucker) şi practice (metode şi algoritmi de
optimizare);
întregul formalism matematic al teoriei economice moderne se bazează pe
ipotezele de convexitate.
4)Problemele de programare separabilă se caracterizează prin
faptul că funcţia obiectiv f ca şi funcţiile gI din restricţii sunt separabile în
sensul următoarei definiţii:
Funcţia se numeşte separabilă dacă ea se poate scrie ca o sumă
de funcţii, fiecare de câte o singură variabilă:
Separabilitatea este importantă prin aceea că uşurează optimizarea. De
exemplu, optimizarea unei funcţii separabile fără restricţii se reduce la
optimizarea independentă a termenilor.
5) Problemele de programare neconvexă reunesc toate problemele
care nu satisfac ipotezele de convexitate. Ele sunt “grele” în primul rând din
cauza faptului că au mai multe minime locale. După cum s-a mai spus,
metodele actuale pot determina un asemenea optim dar nu garantează că
optimul găsit este cel global. Din fericire, există câteve tipuri de probleme
15
neconvexe, utile în practică, care pot fi rezolvate fără dificultăţi deosebite
prin metode speciale. rintre aceste tipuri, se numără problemele de
programare fracţionară. Iată un exemplu:
unde se presupune că pe A ={x Rn Ax b , x 0}.
O asemenea problemă se reduce la un program liniar uzual punând:
astfel că .
Rezultă programul liniar echivalent în n + 1 variabile y = (y1,y2,…,yn) şi t:
Algoritmul simplex
Se consideră problema de programare (2) şi un program de bază
nedegenerat X . După unele renumerotări şi rearanjări putem considera
X x x xm
T 1 2 0 0 0, ,..., , , ,..., ; deci variabilele x x xm1 2, ,..., sunt principale iar
x xm n1,..., secundare, iar vectorii coloană a a am1 2, ,..., formează baza B a
programului de bază X . Fie N a a am m n 1 2, ,..., .
Mai notând:
X
x
x
X
x
x
C
c
c
C
c
cp
m
s
m
n
p
m
s
m
n
1 1 1 1
; ; ; problema (2) poate fi scrisă:
7
0
min f X C X C X
B X N X L
X
pT
p sT
s
p s
Înmulţind BX NX Lp s la stânga cu B 1 obţinem:
16
8 1 1E X B N X B Lp s
care reprezintă transcrierea sistemului de restricţii în baza B, căci dacă
scriem a z a j njij
i
i
m
1
1, (exprimarea vectorilor coloană în funcţie de
vectorii bazei B) vom avea:
zij ij pentru 1 i, j m si z pentru m + 1 j n.ij 0 Corespunzător programului X
problema (2) devine:
91
1
f X c x
x z x x
i ii
m
i ij j ij m
n
Deci xi sunt componentele vectorului L în baza B.
L B X B L X z B Nij i mm j n
11
1
1iar
Deci relaţia (8) devine:
10 1X B NX Xp s de unde
11 1X X B NXp s şi atunci
: f X C X C X C X B NX C X C X C C B N XpT
p sT
s pT
s sT
s pT
sT
pT
s 1 1
sau explicit:
121 11
f X c x c c z xi ii
m
j j iji
m
j m
n
j
Notând: c x Z c z Z m j ni ii
m
i iji
m
j
1 1
1si , atunci:
131
f X Z c Z xj j jj m
n
Observăm că Z f X C B LpT
si Z 1 .
Acum putem asocia problemei PL- min următorul tabel:
17
C Bp
c1 c2
cn
X
a1 a2
an
vecto
rii
bazei
z z z
z z z
n
m m mm
11 12 1
1 2
...
...
componen
tele
nenule ale
lui X
C Zj j .........................
................
f X
Teorema II.4.1. Dacă X este un program de bază nedegenerat pentru
PL - min şi în tabelul asociat (S) avem c Z m j nj j 0 1 atunci X este program
optim.
Demonstraţie: Din (13) avem:
f X f X c Z x f Xj jj m
n
j
0
1 0 pentru orice program admisibil X. Deci X
este optim.
Teorema II.4.2. Dacă X este un program de bază nedegenerat şi în
tabelul simplex asociat (S) există un t, m t n 1 , astfel încât
c Z i mt t 0 0 1si z it , atunci PL - min nu are optim finit.
Demonstraţie: Fie: X x x xnT
1 2, ,..., unde:
x R
x x z i m
x m j n j t
t
i i it
j
,
;
; ,
1
0 1
Astfel avem x j nj 0 1 .
18
(S)
Pentru 1 i m avem:
a x a x a x a x z a a x a z aij jj
n
ij jj
m
ij jj m
n
ij j jtj
m
it ij jj
m
ij jt itj
m
1 1 1 1 1 1
(folosind (9))
a x z x a z aij j jh h
h m
n
j
m
ij jtj
m
it11 1
a x a z x a a a x a z x
a x a z x a x x a z a x
x a a x x
ij jj
m
ijj
m
jh hh m
n
it it ij jj
m
ij jh hh m
n
j
m
ij jj
m
ij jh hj
m
h m
n
ij jj
m
h ij jhj
m
h m
n
ij jj
m
h ihh m
n
ij jj
m
1 1 1 1 11
1 11 1 11 1
1 1
(renotãm pe h cu j) j ijj m
n
ij jj
n
ia a x b
1 1
Deci
X este soluţie admisibilă. Avem:
f X c x c Z x c x c Zj jj
m
j jj m
n
j j jj
m
t t
1 1 1
din definirea lui X .
Deoarece 0 0si ct Zt atunci f X , adică funcţia obiectiv nu are
optim finit.
Teorema II.4.3. Dacă X este un program de bază nedegenerat pentru
PL - min, iar în tabelul simplex asociat (S) există un t, m t n c Zt t 1 0cu
şi cel puţin un indice i, 1 i m , astfel încât zit 0 , atunci alegând s s m, 1 ,
după criteriul:
14 1 0x
z
x
zi m zs
st
i
itit
min / ,
se poate substitui în baza B vectorul a s cu vectorul a t , obţinând o bază B' ,
corespunzătoare unui program de bază X ' care ameliorează valoarea funcţiei
obiectiv.
19
Demonstraţie. Deoarece zst 0, folosind lema substituţiei rezultă că
înlocuind a s în B cu a t sistemul de vectori nou obţinut B', este o bază. Soluţia
de bază corespunzătoare lui B'este dată tot de lema substituţiei:
15
1
0
0
0 1
x xx
zz i m i s
x
xx
z
x m j n j t
i is
stit
s
ts
st
j
'
'
'
'
, ,
, ,
cu toate componentele nenegative (pentru 1 i m i s, dacă zit 0 atunci
x xx
zzi i
s
stit
'
, deci o sumă de numere nenegative; iar dacă zit 0 avem
x zx
z
x
zi iti
it
s
st
'
şi ţinând seama de (14) înseamnă că xi' este produs de două
numere nenegative).
Deci X x x xn
T' , ,...,' ' ' 1 2 este o soluţie de bază. Valoarea funcţiei obiectiv
pentru X ' este:
f X f X c Z x f X c Z x f Xj jj m
n
j t t t' .' '
1
Acum putem prezenta algoritmul simplex pentru o problemă PL - min
în formă standard.
-Pasul 10: Se găseşte un program de bază nedegenerat X cu baza B; se
construieşte tabelul simplex (S).
-Pasul 2 : Se verifică dacă diferenţele c Zj j 0pentru orice j j n,1 . Dacă
DA se trece la pasul 5; dacă NU, dintre toate diferenţele c Zj j , negative, se
alege cea mai mică. Indicele j corespunzător să-l notăm cu t. (Dacă există
mai mulţi t se alege primul de la stânga la dreapta). Vectorul a t va intra în
bază. Se cercetează dacă zit 0 pentru 1 i m. Dacă DA, se trece la pasul 4,
dacă NU, se trece la pasul 3.
-Pasul 3 : Se alege s, astfel încât x
z
x
zi m zs
st
i
itit
min / ,1 0 .
20
Vectorul a s va ieşi din bază. Elementul zst devine pivot. Se construieşte un
nou tabel simplex folosind regula dreptunghiului:
a) se împarte linia pivotului la pivot.
b) în coloana pivotului, elementele z cu j tsj se înlocuiesc cu 0
c) elementele z i s j tij , ,cu se înlocuiesc cu z zz z
zij ijit sj
st
'
.
Se obţine un alt program de bază X ' cu baza B' şi o nouă valoare a funcţiei
obiectiv.
Se revine la pasul 2 cu B B 'şi X X '
-Pasul 40 .Concluzie: “PL - min nu are optim finit” şI algoritmul se opreşte.
-Pasul 5 .Concluzie: “PL - min are optim X iar valoarea minimă f X ".
STOP.
Exemplul II.4.1. Fie problema:
min
, , ... ,
f x x x x x
x x x x x
x x x x xx jj
5 7 9 2
3 2 5 3 7
2 3 40 1 2 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
Alegem XT 1 2 0 0 0, , , , . Avem:
a a a a a B a a1 2 3 4 5 1 23
2
2
1
1
1
5
3
3
1
; ; ; ; ,
Coordonatele vectorilor a a1 2si în baza B sunt 1
0
, respectiv
0
1
. Pentru
a afla coordonatele lui a 3 se procedează astfel: punem
a a a R31
12
21 2 , , , deci:
1 2
1 2
1 2
3
2
2
1
1
1
3 2 1
2 1
ceea ce ne dă 1 21 1 , . Deci în
baza B, a B3 1
1
. Analog se găsesc: a aB B
4 51
1
1
3
,
Aşadar tabelul simplex corespunzător bazei B are forma:
21
5 7 9 2
1
a a a a a1 2 3 4 5
5
7a
a
1
2
1 0 1 1
-1
0 1 -1 1
1
2
c Zj j 0 0 11 -10
-15
19
Deci a 5 intră în bază, a2 iese din bază, z25 - pivot. Se execută pivotajul
şi obţinem:
5
1a
a
1
5
1 1/3 2/3
0
0 1/3 -1/3 1/3
1
5 3
2 3
/
/
c Zj j 0 5 6 -5
0
9
Intră în baza a4 şi iese a1 .
2
1a
a
4
5
3 4 1 4 1 2 1 0
1 4 1 4 1 2 0 1
/ / /
/ / / 5 4
1 4
/
/
c Zj j 15/4 25/4 17/2
0 0
11 4/
22
3
4/3 X f X'
/
/
'
5 3
0
0
0
2 3
9
Şi am obţinut c Z jj j 0 1 5.Deci programul optim este
0,0,0,5 4 1 4/ , / minT
fcu =11
4.
Algoritmul se aplică şi problemelor PL - max în forma standard cu
observaţia că max minf f . De asemenea algoritmul se aplică şi în cazul
în care funcţia obiectiv are forma f c x Rj jj
n
1
, , deoarece punctele de
extrem ale acesteia sunt aceleaşi cu punctele de extrem ale funcţiei:
g c xj jj
n
1
.
23