programare liniara.pdf

7/27/2019 programare liniara.pdf

1/10

Programare liniara

October 24, 2009

1

Printre metodele matematice utilizate n economie un rol impor tant l are programarea liniar a,care ofera posibilitatea obtinerii solutiei optime pentru o gama larga de probleme.

Exemple de probleme de programare liniar a

1. probleme de planificare a productiei (folosirea eficienta a resurselor limitate);

2. probleme de transport;

3. probleme de amestec;

4. utilizarea optima a capacitatii masinilor;

5. probleme de investitii;

6. reducerea pierderilor la taierea materialelor.

1


2/10

2 Problema de folosire eficienta a resurselor

O ntreprindere dispune de R1, R2,...,Rm resurse (materii prime, forta de munca, masini-unelte) n cantitatile b1, b2,...,bm, numite si disponibil de resurs asau capacitate de resurs a.

Rezultatul productiei consta n n tipuri de produse P1,...,Pn.

Vom nota cu:

cj-beneficiul obtinut pentru o unitate din produsul Pj ;

aij-cantitatea din resursa Ri folosita n fabricarea unei unitati din produsul Pj (cantitatenumita si consum specificsau coeficient tehnologic).

Se pune problema ce cantitati x1,...,xn trebuiesc produse din P1,...,Pn astfel ncat ben-eficiul total:

Z =n

j=1

cjxj

sa fie maxim; se tine seama de restrictiile impuse de disponibilul limitat.

Datele problemei se pot prezenta, n tabelul de mai jos, dupa cum urmeaza:

P1 P2 . . . P j . . . P nR1 a11 a12 . . . a1j . . . a1n b1R2 a21 a22 . . . a2j . . . a2n b2

......

... . . .... . . .

......

Ri ai1 ai2 . . . aij . . . ain bi...

...... . . .

... . . ....

...Rm am1 am2 . . . amj . . . amn bm

c1 c2 . . . cj . . . cn

Modelul matematic al problemei este:

max [Z =n

j=1

cjxj ] (1)

cu conditiile:

a11x1+ a12x2+ ... a1nxn b1a21x1+ a22x2+ ... a2nxn b2

... ... ... ...am1x1+ am2x2+ ... amnxn bm

(2)

Functia Z este numita functie obiectiv iar inegalitatile (2) se numesc restrictii. Functia

obiectiv se mai noteaza: f, g, etc.

Problema se numeste de programare liniar adeoarece toate functiile ce intervin n relatiile(1) si (2) sunt functii liniare.

3 Forme ale modelului matematic

Pentru o problema de programare liniara prezentam n continuare diferite forme ale modeluluimatematic.

Restrictiile unei probleme de programare liniara pot fi ecuatii si inecuat ii. Variabile careapar sunt supuse conditiei de negativitate iar functia obiectiv poate fi maximizata sau mini-

mizata.

2


3/10

1. Forma general a

max/min [Z =n

j=1

cjxj ]

n

j=1aijxj bi; 1 i p

nj=1

aijxj = bk; p + 1 k < s

nj=1

aijxj bl; s + 1 l m

xj 0; j = 1,...,n

2. Spunem ca o restrictie a unei probleme de programare liniara este concordant adacaeste o inegalitate cand functia obiectiv trebuie minimizata sau o inegalitate candfunctia obiectiv trebuie maximizata.

Intelegem prin form a canonic a modelul n care toate restrictiile sunt concordante iarvariabilele nenegative, adica:

min[Z =

n

j=1 cjxj ] max[Z =n

j=1 cjxj ]n

j=1

aijxj bi; i = 1,...,m saun

j=1

aijxj bi; i = 1,...,m

xj 0; j = 1, ..., m xj 0; j = 1,...,m

3. Modelul are forma standard cand toate restrictiile sunt egalitati:

max/min [Z =n

j=1

cjxj ]

nj=1

aijxj = bi; 1 i m

xj 0; j = 1,...,n

O problem a de programare liniar a sub form a general a poate fi adus a la forma standardsau forma canonic a folosind urm atoarele transform ari echivalente:

sensul unei inegalitati se schimba prin nmultire cu 1,

inegalitatile se transforma n egalitati prin adaugarea sau scaderea unor variabile pozi-tive numite variabile ecart sau variabile de compensare; variabilele ecart nu apar nfunctia obiectiv (adica apar cu coeficienti nuli),

o egalitate poate fi nlocuita cu doua inegalitati de sens contrar,

deoarce max Z = min(Z), orice problema de maximizare se poate transforma nuna de minimizare.

Deoarece un sistem de inegalitati se transforma cu ajutorul variabilelor ecart n sistemde egalitati, conform observatiei urmatoare, prin rezolvarea acestuia din urma cunoastem sisolutia sistemului de inegalitati.

Se cunoaste din algebra urmatorul rezultat:Fie sistemul de inegalitati:

a11x1 + a12x2 + ... + a1nxn b1a21x1 + a22x2 + ... + a2nxn b2

............................. ..... ...am1x1 + am2x2 + ... + amnxn bm

(3)

Oricare ar fi (x01, x02,...,x

0n) solutie a sistemului (3) exista constantele nenegative x

0n+1, x

0n+2,...,x

0n+m

astfel ncat(x01, x

02,...,x

0n, x

0n+1, x

0n+2,...,x

0n+m)

3


4/10

sa fie solutie a sistemului de egalitati:

a11x1 + a12x2 + ... + a1nxn + xn+1 = b1a21x1 + a22x2 + ... + a2nxn + xn+2 = b2

............................. ..... ...

am1x1 + am2x2 + ... + amnxn + xn+m = bm,

(4)

si reciproc.

Un rezultat asemanator obtinem si n cazul unui sistem de inegalitati de forma:

nj=1

aijxj bi, i = 1,...,m.

Concluzie. Conform celor spuse anterior ne vom ocupa numai de modelul sub form astandard:

min [Z =n

j=1 cjxj ]n

j=1

aijxj = bi; 1 i m

xj 0; j = 1,...,n

(5)

care se poate scrie sub forma matriceala:

min [Z = CTX]AX = bX 0,

(6)

unde A = (aij)i=1,...,m;j=1,...,n, bT = (b1,...,bm) ; C

T = (c1,...,cn).

Daca notam cu a1,...,an coloanele matricei A, atunci modelul se poate prezenta si sub

forma:min[Z = CTX]

a1x1 + ... + anxn = bX 0,

(7)

Deoarece modelul este al unei probleme practice, trebuie sa aiba cel putin o solutie.

Sistemul are solutii cand rangA = m < n. Daca m = n, problema are o singura solutieadmisibila si optimizarea este banala.

Daca rangul matricei A este egal cu m, m < n. Rezulta ca exista un minor de ordin m cudeterminantul diferit de zero. Fara a restrange generalitatea, putem presupune ca este formatdin primele m coloane ale matricei A. In aceste conditii, vectorii coloana: a1,...,am sunt liniar

independenti.Necunoscutele x1,...,xm corespunzatoare, se numesc variabile de baz a.Matricea A a restrictiilor si vectorul X se pot partitiona astfel:

A = (B, R); X =

XB

XR

,

unde

B = {a1,...,am}, R = {am+1, . . . , an}, XB =

x1...

xm

, XR =

xm+1...

xn

.

Atunci sistemul de restrictii (5) se scrie:

(B, R)

XB

XR

= b BXB + RXR = b. (8)

4


5/10

Deoarece matricea B este inversabila putem determina XB:

XB = B1b B1RXR. (9)

Definitie. O solutie a sistemului de restrictii AX = b, ce satisface conditia X 0, se numeste

solutie admisibila

sauprogram

.Multimea P = {X Rn/AX= b, X 0} se numeste multimea programelor.

Definitie. Un program X P pentru care obtinem valoarea minima a functiei Z se numesteprogram optim.

Observatie.

deoarece Z = min{CTX/X P} = CTX, avemCTX CTX, X P.

daca P = , convenim sa punem Z = .

daca Z = , spunem ca problema (5) are minim infinit.

Definitie. O solutie a sistemului de restrictii (5) se numeste solutie de baz a daca toatecomponentele sale diferite de zero corespund coloanelor liniar independente ale matricei A.

Observatie. O solutie de baza se poate obtine din (9) pentru XR = 0 si aceasta esteXB = B1b.

Definitie. O solutie de baza XB = B1b si XR = 0 a sistemului AX = b care satisfaceconditia X 0 se numeste program de baz a ( sau solutie admisibil a de baz a).

Definitie. Un program de baza cu exact m componente pozitive se numeste program de baz anedegenerat. In caz contrar se numeste program de baz a degenerat.

Teorema. (Teorema fundamentala a programarii liniare)

1. Daca problema (5) are un program atunci are un program de baza.

2. Daca problema (5) are un program optim atunci are un program de baza optim.

Observatie. Din teorema rezulta ca din punct de vedere teoretic determinarea programuluioptim se realizeaza astfel:

se demonstreaza ca problema are program optim;

se determina toate programele de baza;

se cauta printre acestea acela care este optim.

5


6/10

4 Metoda simplex de rezolvare a problemei de programare

liniara

In 1951 matematicianul Dantzig a creat un algoritm ce permite explorarea n mod sistematica multimii programelor de baza prin trecerea de la un program la altul care este cel put in totatat de bun ca cel precedent. Deci, problema care se pune este: cum se trece de la o baz ala o alt a baz a care ne va furniza un alt program de baz a.

Metoda simplex consta n construirea succesiva a unor solutii de baza din ce n ce maibune pana se obtine solutia optima.

Fie problema de programare liniara:

min[Z = CTX]AX = bX 0

(10)

Notam cu B = {a1, a2,...,am} si R = {am+1,...,an}. Atunci A = (B, R), unde B formeaza obaza. Sistemul de restrictii devine:

BXB + RXR = b (11)

cu solutia:XB = B1b B1RXR. (12)

Fie JB = {i/1 i m} si JR = {i/m + 1 i n}.Solutia corespunzatoare bazei B este:

XB

= B1b, XR

= 0.

Se noteaza cu:

zj = jJB

ciaB

ij (13)

Teorema. (Criteriul de optim) Daca pentru o baza B avem

j = zj cj 0, j JR,

atunci programul de baza corespunzator bazei B este program optim pentru problema deprogramare liniara.

Teorema. Daca pentru o baza exista un indice k JR pentru care

k = zk ck > 0,

atunci programul de baza corespunzator nu este optim.

Teorema. Daca pentru o baza B exista un indice k JR pentru care

k = zk ck > 0,

iar coordonatele vectorului ak n baza B, aBij 0, pentru orice i JB, atunci problema (10)are optim infinit.

Teorema. Fie o baza B pentru care k JR astfel ncat k > 0 si vectorul ak are si compo-

nente strict pozitive, adica exista aBik > 0, 1 i m. Daca indicele l JB este acela pentrucare se obtine

0 = mini{

xBiaBik

/aBik > 0} =xBlaBlk

,

atunci baza B ce difera de baza B printr-un singur vector (vectorul al s-a nlocuit cu ak) este obaza admisibila si solutia de baza corespunzatoare XB este tot atat de buna ca si XB, adicaZB ZB.6


7/10

1. Criteriul de intrare n baza: operatia de a alege dintre diferentele j > 0 pe

k = maxj

(zj cj) = zk ck

arata ca vectorul ak va intra n noua baza.

2. Criteriul de iesire din baz a: valoarea

0 = mini{

xBiaBik

}

cu aBik > 0, indica vectorul care paraseste baza.

3. Trecerea de la baza B la baza B se numeste iteratie a algoritmului simplex.4. In metoda simplex ne intereseaza la pornire o baza lesnicioasa. Aceasta este baza

unitara. Daca matricea A contine aceasta baza, vectorii aj care nu se gasesc n bazavor avea n baza unitara coordonatele asa cum apar ele n matrice. Daca matricea A nu

contine baza unitara, exista procedee prin care se obtine aceasta baza la primul pas.

7


8/10

5 Algoritmul simplex

Pasul 0: se scrie matricea A si se identifica baza unitara (presupunand ca exista). Sedetermina solutia initiala de baza XB, impunand n sistemul de restrictii XR = 0.

Deoarece n baza unitara aBij = aij se ntocmeste tabelul:

B CB XBc1a1

c2a2

....cnan

ak1 ak2 aknj 1 2 ... n

Pasul 1: Pentru fiecare j JR = {m + 1, m + 2,...,n} se calculeaza diferentele j :

j =

zj cj n cazul problemei de minimcj zj n cazul problemei de maxim ,

unde zj =m

i=1 ciaij, m + 1 j n. Diferentele j cu 1 j m (cele corespunzatoarevectorilor bazei) sunt egale cu zero.

1. Daca j 0, j JR, STOP; XB este conform criteriului de optim, solutia optima.

2. Daca exista indici j JR pentru care j > 0 se aplica criteriul de intrare n bazaalegandu-se diferenta k = max

jJRj care indica vectorul a

k ce intra n noua baza.

3. Daca toate componentele vectorului ak sunt mai mici sau egale cu zero, STOP,problema are optim infinit.

Daca vectorul ak are si componente pozitive, pentru acestea se calculeaza rapoartelexBiaik

si se alege

0 = min{x

B

iaik

} = x

B

lalk

;

conform criteriului de iesire din baza, vectorul al paraseste baza fiind nlocuit cu ak.Se obtine o noua baza. Elementul de la intersectia liniei l cu coloana k se numestepivot.

Pasul 2: Se reface tabelul simplex:

a. se scrie noua baza;

b. se completeaza coloana c corespunzatoare;

c. ncepand cu coloana lui XB, linia l a pivotului se scrie mpartita la pivot;

d. se completeaza vectorii unitari ai noii baze;

e. celelalte elemente ale tabelului se calculeaza conform formulelor de schimbare abazei cu regula dreptunghiului;

f. se calculeaza diferentele j si se reia Pasul 1 si 2.

8


9/10

5.1 Tehnici ale bazei artificiale pentru determinarea unui program initialde baza

In aplicarea algoritmului simplex este necesara existenta unei baze initiale unitare. In cazul ncare aceasta baza nu figureaza printre coloanele matricei A si nu apare nici dupa efectuarea

compensarilor prin adaugarea variabilelor ecart este necesar sa folosim tehnici prin care saobtinem acest lucru.Fie problema de programare liniara:


(14)

pentru care matricea A a sistemului de restrictii (14) nu contine baza unitara. Adaugandcate o variabila artificiala xai 0, i = 1,...,m, n fiecare restrictie a problemei (14), obtinemsistemul:

AX+ IXa = b n

j=1aijxj + x

ai = bi, i = 1, . . . , m . (15)

O solutie a sistemului (15) este solutie si pentru sistemul (14), daca n aceasta solutieelementele xai , i = 1, . . . , m sunt toate zero (numai n acest caz solutia sistemului (15) verificasi sistemul (14).

Asociem problemei (14) o problema extinsa al carui sistem de restrictii este (15). Vomurmari sa gasim o solutie de baza a modelului extins n care variabilele artificiale sa fie vari-abile nebazice (adica sa aiba valori nule). O astfel de solutie de baza a problemei extinse vareprezenta n anumite conditii o solutie de baza initiala pentru problema (14) cu care se poatencepe algoritmul simplex.

5.1.1 Metoda penalizarii

Fie problema de programare liniara:


(16)

pentru care matricea A a sistemului de restrictii (16) nu contine baza unitara. Se asociazaproblemei (16) o problema extinsa:

min[Z = CTX+ TXa]AX+ IXa = b

X, Xa 0(17)

obtinuta prin adaugarea la fiecare restrict ie a cate unei variabile artificiale xai . Aceste

variabile ar tificiale vor crea n matricea A baza unitara.In functia obiectiv variabilele artificiale apar cu coeficienti egali cu M, un numar foarte

mare pozitiv care nu va permite functiei obiectiv sa si atinga valoarea minima decat atuncicand n solutia optima nu vor mai fi variabile artificiale.

Observatie. In cazul problemei de max coeficientii variabilelor artificiale din functia obiectivsunt -M iar n cazul problemei de min coeficientii variabilelor artificiale din functia obiectiv suntM.

Coeficientul M se numeste coeficient de penalizare.Problema (17) se rezolva cu ajutorul algoritmului simplex.Pe parcursul aplicarii algoritmului simplex se pot ntalni urmatoarele situatii:

la un anumit moment al algoritmului tot i vectorii artificiali au parasit baza; se continua

algoritmul pana se obtine solutia optima.

algoritmul simplex s-a ncheiat, dar n solutia optima au ramas variabile artificiale. Inacest caz:

9


10/10

a) daca variabilele artificiale ramase n solutia optima au toate valoarea zero, prob-lema initiala admite solutie.

b) daca variabilele artifciale ramase n solutia optima nu au toate valoarea zero, prob-lema initiala nu are solutie.

Observatie. Pe parcursul algoritmului, cand un vector artificial paraseste baza, n general elnu va mai reveni n baza, deci n etapele urmatoare el nu se mai ia n considerare.

10

programare liniara.pdf

Documents