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