BISP_ID_UI_4

Unitatea de nvare 4

PROBLEME DE TRANSPORT.

ELEMENTE DE PROGRAMARE NELINIAR I DINAMIC

Obiectivele unitii de nvare: nelegerea i nsuirea principalelor (celor mai uzuale) metode de

rezolvare a problemelor de transport; nsuirea cunotinelor de baz i deprinderilor practice necesare

pentru aplicarea problemei de transport n situaii specifice ingineriei sistemelor de producie;

nsuirea cunotinelor teoretice privind elementele de baz ale programrii neliniare i ale programrii dinamice;

dezvoltarea aptitudinilor de identificare a situaiilor din conducerea optimal a sistemelor de producie n care pot fi aplicate programarea neliniar sau programarea dinamic.

Cuprinsul unitii de nvare:

4.1. Probleme de transport 2 4.1.1. Formularea general a problemei de transport 2 4.1.2. Metoda distributiv (a celulelor) de rezolvare 3

Teste de autoevaluare (seciunea 4.1) 12 Problem propus (seciunea 4.1) 12

4.2. Elemente de programare neliniar 13 4.2.1. Formularea problemei i dificulti specifice 13 4.2.2. Metode de rezolvare a problemelor de programare neliniar 15 4.2.3. Programarea geometric 15

Teste de autoevaluare (seciunea 4.2) 16 4.3. Elemente de programare dinamic 17

Teste de autoevaluare (seciunea 4.3) 19 Bibliografie 20 Soluia problemei propuse (seciunea 4.1) 20

Conf. dr. ing. Andrei Dumitrescu

2

4.1. Probleme de transport

n continuare, va fi studiat un caz particular al problemelor de

programare liniar, i anume problemele de transport. Astfel, prezentm nti formularea general a unei probleme de transport, iar apoi cea mai rspndit metod de rezolvare a sa, i anume metoda distributiv.

4.1.1. Formularea general a problemei de transport Problema de transport are drept obiectiv determinarea unui plan de

transport optim (adic cu minimizarea cheltuielilor), pentru un produs omogen, de la m centre de aprovizionare (depozite) la n centre de desfacere (de consum). Produsul se afl n cantitatea ai la depozitul i, 1 i m, i este cerut n cantitatea bj la centrul de consum j, 1 j n. Cantitatea (necunoscut iniial) ce urmeaz a fi transportat de la depozitul i la centrul de consum j se noteaz xij, iar preul de transport al unei uniti din produsul considerat de la depozitul i la centrul de desfacere j se noteaz cij (pentru simplificare, se presupune c acest pre unitar nu depinde de cantitatea transportat, xij).

n particular, centrele de aprovizionare i pot fi sisteme de producie (fabrici, uzine, ateliere), ale cror produse sunt repartizate la mai multe puncte de desfacere. n acest caz, ai reprezint capacitatea de producie a sistemului i. Este, de asemenea, posibil ca centrele de consum s fie sisteme de producie, alimentate cu materii prime sau materiale de la mai multe centre de aprovizionare.

Cantitatea transportat de la depozitul i la toate cele n centre de consum trebuie s fie cel mult egal cu cantitatea aflat n depozitul i, adic:

miaxxxx in

jijinii =+++

=1pentru ,...

121 . (4.1)

Cantitatea transportat de la toate cele m depozite la centrul de consum j trebuie s fie cel puin egal cu cantitatea necesar la centrul j, adic:

njbxxxx jm

iijmjjj =+++

=1pentru ,...

121 . (4.2)

Costul transportului de la depozitul i la centrul de consum j este cijxij, iar costul total al transportului (de la toate cele m depozite la toate cele n centre de consum) este dat de suma de mai jos:

F = .1 1

ij

m

i

n

jij xc

= = (4.3)

Se urmrete minimizarea acestui cost, care reprezint funcia obiectiv a problemei de transport, F.

Pentru ca s se poat efectua transportul (s existe o soluie a problemei formulate) este necesar i suficient ca s fie satisfcut condiia evident:

= =

m

i

n

jji ba

1 1 . (4.4)

Prin combinarea relaiilor (4.1), (4.2) i (4.3) de mai sus, se obine un program liniar, caracterizat de urmtoarele elemente principale:

Bazele Ing. Sist. de Producie 4.Probleme de transport. Programare Neliniar i Dinamic

3

10. funcia obiectiv (costul total al transportului):

= =

=m

i

n

jijij xcF

1 1 = minim ; (4.5)

20. sistemul de restricii, alctuit din urmtoarele inegaliti:

, 1 ,

1 ,

1

1

njbx

miax

m

ijij

n

jiij

=

= = =

m

i

n

jji ba

1 1 unde ; (4.6)

30. condiiile de nenegativitate, aplicabile i n acest caz necunoscutelor:

njmixij 1 ,1 ,0 . (4.7) Tipul de program liniar caracterizat de cele trei elemente enunate (4.5,

4.6, 4.7) se numete program de transport. n cele mai multe cazuri ns, condiia (4.4) de mai sus se poate aduce la urmtoarea form, care simplific mult problema:

= =

=m

i

n

jji ba

1 1 . (4.8)

n condiiile ndeplinirii acestei ultime condiii (4.8), metodele de rezolvare se simplific mult i se spune c problema de transport este echilibrat, forma ei devenind urmtoarea:

= =

=m

i

n

jijij xcF

1 1

min

, 1 ,

, 1 ,

1

1

njbx

miax

m

ijij

n

jiij

=

=

=

= = =

=m

i

n

jji ba

1 1 , unde (4.9)

njmixij 1 ,1 ,0 . Se remarc faptul c problema de mai sus este o problem de programare

liniar n forma standard, cu m + n restricii i mn variabile. n continuare, ne vom ocupa doar de rezolvarea problemele de transport echilibrate.

Observaie: Se poate demonstra, prin aplicarea teoremelor de calcul matriceal, c orice soluie de baz a problemei de transport echilibrate are cel mult m + n 1 componente nenule. Dac o soluie de baz a problemei are exact m + n 1 componente nenule, se spune c este o soluie nedegenerat. n caz contrar, soluia se numete degenerat.

4.1.2. Metoda distributiv (a celulelor) de rezolvare Rezolvarea unui program de transport presupune parcurgerea a dou

faze, pentru fiecare existnd o serie de metode diferite de rezolvare: A. determinarea unei soluii iniiale de baz; B. determinarea soluiei optimale, realizat printr-un proces iterativ.

Observaie: Pentru simplificarea rezolvrii unei probleme de transport, se utilizeaz prezentarea coeficienilor ai, bj i cij n aa-numitul tabel de transport, avnd m linii (corespunztoare celor m depozite) i n coloane


4

(corespunztoare centrelor de consum), la care se adaug o coloan suplimentar unde sunt trecute cantitile ai i o linie suplimentar indicnd cantitile bj. Acest tabel, notat n continuare cu T, este de forma:

][ ijcnjni

11 niia 1][

njjb 1][

Metoda general de determinare a unei soluii iniiale de baz (faza A) presupune parcurgerea urmtoarelor etape (unde s-a notat cu ijx valoarea numeric, care poate fi eventual i zero, a variabilei xij):

10. se atribuie unei variabile de baz oarecare valoarea: },min{ jiij bax = ; 20. se nlocuiesc, n T, ai i bj repectiv prin iji xa i ijj xb i se

suprim linia i din T, dac iij ax = , sau coloana j, dac jij bx = , rezultnd un tabel T redus;

30. se repet etapele 10 i 20 pn cnd toate cererile sunt satisfcute (toate variabilele problemei de transport au atribuit o valoare).

Observaie: Suprimarea unei linii / coloane din tabel este echivalent cu faptul c toate valorile ijx ale variabilelor corespunztoare acelei linii / coloane sunt nule, cu excepia celei egale cu ai sau bj. Variabilele care au valori nule sunt variabilele din afara bazei, iar cele cu valori nenule alctuiesc baza iniial i se vor trece n tabelul T, alturi de valorile cij, n aceleai celule. Valorile variabilelor din afara bazei (cele nule) nu se vor trece n tabel.

Celula se definete ca fiind un element (csu) din tabelul T / T redus. Metoda are cazuri particulare din punctul de vedere al alegerii variabilei

xij la etapa 10. Vom aplica metoda colului de Nord-Vest (numit i stepping-stone), cea mai utilizat, care presupune alegerea variabilei din celula situat n prima linie i prima coloan a tabelului T / T redus.

Soluia de baz iniial, odat determinat, se poate indica n tabelul T, astfel: se trec valorile variabilelor bazei iniiale n colul din dreapta jos al fiecrei celule, alturi de coeficienii cij, iar valorile variabilelor nule (din afara bazei) nu se trec n tabel.

La finalul fazei A, se poate verifica soluia de baz obinut cu ajutorul tabelului T, nsumnd pe fiecare coloan, respectiv linie valorile variabilelor de baz. Aceste sume trebuie s rezulte egale cu coeficienii bj, respectiv ai.

Pentru determinarea soluiei optimale (faza B), prezentm aici metoda cel mai des utilizat, i anume metoda distributiv (numit i metoda celulelor), care este iterativ i presupune parcurgerea urmtoarelor etape:

10. Se noteaz cu I mulimea celulelor (i, j) corespunztoare variabilelor de baz (cele cu valori nenule), determinate n cursul fazei A. Se introduc variabilele ui i vj, corespunztoare liniei ai, respectiv coloanei bj din tabelul T / T redus. Se determin valorile variabilelor ui i vj din rezolvarea sistemului de mai jos, pornind de la u1 = 0:

ui + vj = cij, pentru orice (i, j) I . (4.10) 20. Se calculeaz, pentru celulele (i, j) I, coeficienii dai de relaia:


5

ij = ui + vj - cij , (4.11) n continuare, dac ij 0, (i, j) I, soluia de baz obinut dup

iteraia precedent este cea optim; dac NU (n caz contrar), se calculeaz }{max

),( ijIjikl

= i se determin

un ciclu cu celula (k, l) i celule corespunztoare variabilelor de baz. Un ciclu reprezint un contur poligonal nchis prin celulele tabelului T. Etapa 20 de mai sus exprim, de fapt, criteriul de intrare n baz, deoarece celula (k, l) corespunde variabilei ce intr n baz.

30. Se marcheaz cu celulele pare din ciclul obinut n etapa 20. n celulele marcate, se evideniaz variabila xps de valoare minim aceasta va reprezenta variabila ce iese din baz (s-a enunat astfel criteriul de ieire din baz).

40. Se scade valoarea lui xps din valorile variabilelor din celulele marcate i se adun la valorile variabilelor din celelalte celule ale ciclului. Noua soluie de baz este constituit din xkl (cu valoarea lui xps) i variabilele bazei precedente (cu valori modificate dup cum s-a artat mai sus), iar variabila xps prsete baza.

50. Se repet etapele 10 ...40 pn cnd se obine (la 20) soluia OPTIM.

Aplicaia 4.1: Se consider patru benzinrii care sunt aprovizionate de la trei depozite. Preurile de transport, al unui metru cub de benzin, de la depozitele Di la benzinriile Sj sunt indicate n tabelul urmtor (n uniti valorice):

S1 S2 S3 S4 D1 8 3 5 2 D2 4 1 6 7 D3 1 9 4 3

Depozitele dein urmtoarele cantiti de benzin: D1 10 m3, D2 15 m3 i D3 25 m3. Benzinriile necesit urmtoarele cantiti de benzin: S1 5 m3, S2 10 m3, S3 20 m3, S4 15 m3. Se cere s se determine cantitile de produs xij [m3], ce trebuie transportate de la depozitele Di la benzinriile Sj, astfel nct s se asigure necesarul de benzin cu minimum de cheltuieli totale de transport.

Tabelul T corespunztor acestei probleme de transport este urmtorul:

8 3 5 2

4 1 6 7

1 9 4 3

10

15

25

5 10 20 15

Observm c: m = 3 : a1 = 10 m3 , a2 = 15 m3 , a3 = 25 m3 , n = 4 : b1 = 5 m3 , b2 = 10 m3 , b3 = 20 m3 , b4 = 15 m3 .

Se verific condiia: = =

=+++==++=3

1

4

1501520105251510

i jji ba m

3.

Rezolvarea fazei A (determinarea bazei iniiale):


6

Iteraia 1. Se atribuie nti valoarea variabilei x11, cea aflat iniial n colul de NV al tabelului T , astfel: 11111 55) ,10min(),min( bbax ==== .

Se nlocuiete apoi a1=10 cu a1- 11x =10-5=5 i b1=5 cu b1- 11x =5-5=0. Se elimin n final coloana 1 (a lui b1) din tabel, deoarece 11x = b1 = 5.

Eliminarea acestei coloane implic anularea variabilelor: x21, x31 ( 21x = 31x = 0). Rezult urmtorul tabel T redus dup iteraia 1, tabel n care s-au

nlocuit valorile coeficienilor cij, care nu sunt utilizai (neavnd niciun rol) n faza A a rezolvrii problemei de transport, cu variabilele xij:

x12 x13 x14

x22 x23 x24 x32 x33 x34

5

15

25

10 20 15

Iteraia 2. Variabila din colul de NV este acum x12, creia i se atribuie valoarea: 5)10,5min(12 ==x . Se suprim apoi linia 1 i se nlocuiete b2=10 cu b2- 12x =10-5=5, rezultnd urmtorul tabel redus (dup iteraia 2):

x22 x23 x24 x32 x33 x34

15

25

5 20 15

Iteraia 3. Variabila din colul de NV este acum x22, creia i se atribuie valoarea: 5)5 ,15min(22 ==x . Se suprim apoi coloana 2 i se nlocuiete a2=15 cu a2- 22x =15-5=10, rezultnd urmtorul tabel redus (dup iteraia 3):

x23 x24 x33 x34

10

25

20 15

Iteraia 4. Variabila din colul de NV este acum x23, creia i se atribuie valoarea: 10)02 ,10min(23 ==x . Se suprim apoi linia 2 i se nlocuiete b3=20 cu b3- 23x =20-10=10, rezultnd urmtorul tabel redus (dup iteraia 4):

x33 x34 25

10 15

Din ultimul tabel T redus, rezult imediat valorile: 33x =10 i 34x =15. Soluia de baz iniial determinat mai sus este deci urmtoarea: variabile de baz: x11, x12, x22, x23, x33, x34, cu valorile calculate:

11x = 5, 12x = 5, 22x = 5, 23x = 10, 33x =10 i 34x =15; variabile din afara bazei: x21, x31, x13, x14, x32, x24, toate cu valoarea

zero.


7

Aceast soluie de baz se indic n tabelul T, astfel: celulele corespunztoare variabilelor de baz ale bazei iniiale se mpart n dou prin trasarea unei diagonale; n colul din dreapta jos al fiecrei celule (sub diagonal) se trec valorile variabilelor respective, iar valorile coeficienilor cij, se scriu deasupra diagonalei (n colul din stnga sus); celulele corespunztoare variabilelor din afara bazei (nule) nu se divid, deoarece valorile acestor variabile nu se trec n tabel (se scriu doar valorile cij n centrul celulelor). Rezult astfel tabelul (n care valorile variabilelor sunt scrise ngroat):

8 5

3 5 5 2 10

4 1 5 6 10 7 15

1 9 4 10 3 15 25

5 10 20 15

Rezolvarea fazei B (determinarea soluiei optimale) Iteraia 1 (descris pe etape):

10. Se rezolv sistemul (4.10) n necunoscutele ui i vj pentru mulimea celulelor variabilelor de baz: I = {(1, 1); (1, 2); (2, 2); (2, 3); (3, 3); (3, 4)}. Se pleac de la: 01 =u . Rezult succesiv: 88 1011 1 ==+ = vvu u ;

.73;...;86

;21;33

44

4332

32

23

2220

21

32

21

= =+= =+==+==+

==

==

vvuvvuuvuvvu

uu

vu

Valorile obinute sunt trecute pe marginea tabelului T1 (inclus mai jos). 20. Se calculeaz cu relaia (4.11) valorile coeficienilor ij, care se trec

n colul din stnga sus n celulele tabelului pentru care (i, j) I (aceste valori sunt scrise cu caractere cursive n tabelul T1, prezentat mai jos).

Deoarece exist valori ij > 0, se determin 5}{max 14),( === ijIjikl . Variabila corespunztoare lui kl este variabila ce intr n baz (xkl = x14).

Se alege ciclul urmtor: (1, 4) (3, 4)* (3, 3) (2, 3)* (2, 2) (1, 2)* (1, 4).

Ciclul adoptat se marcheaz i n tabel (vezi tabelul T1 de mai jos).

T1 v1 = 8 v2 = 3 v3 = 8 v4 = 7

u1 = 0

8

5

3

5 *

3

5

5

2 10

u2 = -2 2

4

1

5

6

10 *

-2

7 15

u3 = -4 3

1

-10

9

4

10

3

15 * 25

5 10 20 15

30. Se marcheaz cu celulele pare ale ciclului ales, att n tabelul T1

ct i pe ciclu (vezi mai sus). Variabila de valoare minim este: xps = x12


8

(deoarece 512 =x ). Aceasta este variabila din baza iniial care va iei din baz (va lua valoarea zero).

40. Se determin noua soluie de baz, astfel: se scade 5 (valoarea lui xps) din valorile variabilelor de baz din celulele marcate cu * i se adun 5 la valorile variabilelor din celelalte celule ale ciclului. Procednd astfel valoarea lui xps = x12 (care iese din baz) devine zero, iar variabila xkl = x14 ia valoarea lui xps. Rezult tabelul T2, inclus mai jos, care conine i rezultatele primelor trei etape ale iteraiei 2, descrise pe scurt n continuare.

T2 v1 = 8 v2 = -2 v3 = 3 v4 = 2

u1 = 0 8

5 *

-5

3

-2

5

2

5 10

u2 = 3 7

4

1

10

6

5

-2

7 15

u3 = 1 8

1

-10

9

4

15

3

10 * 25

5 10 20 15

Iteraia 2 (pe etape): 10. Valorile ui i vj sunt marcate n tabelul T2.

20. Valorile ij sunt incluse n tabelul T2. Exist i n acest caz valori ij > 0 i se obine: 8}{max 31),( === ijIjikl , deci variabila x31 va intra n baz. Se alege ciclul (3, 1) (3, 4)* (1,4) (1, 1)* (3, 1), indicat i n tabelul T2 (inclus mai sus).

30. Rezult (dintre celulele marcate) variabila ce iese din baz, deoarece are valoarea minim: 511 = xx ps .

40. Se determin noua soluie de baz, procednd la fel ca la iteraia 1. Variabila ce intr n baz este x13 = xkl, iar variabila ce iese este 11xxps = . Se obine tabelul T3, inclus mai jos, n care sunt prezentate i etapele 10 i 20 ale iteraiei 3 (care va fi i ultima).

Iteraia 3 (pe etape): 10. Valorile ui i vj sunt marcate n tabelul T3. 20. Valorile ij sunt incluse n tabelul T3 de mai jos. Deoarece toi

aceti coeficieni sunt acum negativi ( 0ij ), soluia de baz obinut dup iteraia 2 este i soluia OPTIM a problemei de transport considerat.

T3 v1 = 0 v2 = -2 v3 = 3 v4 = 2

u1 = 0 -8

8

-5

3

-2

5

2

10 10

u2 = 3 -1

4

1

10

6

5

-2

7 15

u3 = 1 1

5

-10

9

4

15

3

5 25

5 10 20 15


9

Soluia OPTIM presupune deci urmtoarele valori ale variabilelor:

,0,5 ,15 ,5,5 ,10 ,10

322421131211

343331

232214

============

xxxxxxxxxxxx

unde s-a notat cu ijx valoarea optim a variabilei xij. Valoarea minim a funciei obiectiv se poate calcula dup cum urmeaz,

utiliznd valorile de mai sus (indicate i n tabelul T3, sub diagonale) i cele ale coeficienilor cij (din acelai tabel):

fmin = 210 + 110 + 65 + 15 + 415 + 35 = 140 uniti valorice Printr-un calcul analog, dup iteraia 1, valoarea funciei f rezult a fi

egal cu 180, iar valoarea corespunztoare bazei iniiale este f = 205. Se observ c, dup cum era de ateptat, valoarea funciei obiectiv a sczut de la o iteraie la alta.

Aplicaia 4.2: S se rezolve problema de transport caracterizat de urmtorul tabel T:

2 3 2

1 3 4

2 8 1

12

10

8

10 15 5

Rezolvare: Se verific nti condiia urmtoare:

.3051510810123

1

3

1 = =

=++==++=i j

ji ba

Faza A: Iteraia 1: 11111 10)10,12min(),min( bbax ==== . Se suprim coloana 1, iar a1=12 se nlocuiete cu a1- 11x =12-10=2. Rezult tabelul redus (n acest exemplu, vom pstra valorile coeficienilor cij n tabel, fr a le nlocui cu variabilele xij):

3 2

3 4

8 1

2

10

8

15 5

Iteraia 2: 2)2,15min(12 ==x . Se suprim linia 1, iar b2=15 se nlocuiete cu b2- 12x =15-2=13. Rezult tabelul redus de mai jos:

3 4

8 1

10

8 13 5

Iteraia 3: 10)13 ,10min(22 ==x . Se suprim linia 2, iar 13 se nlocuiete cu 13- 22x =13-10=3. Rezult tabelul redus:


10

8 1 8 3 5

Din acest ultim tabel, rezult evident: 32x = 3 i 33x = 5. Soluia de baz iniial obinut este caracterizat de urmtoarele valori

ale variabilelor de baz: 11x = 10, 12x = 2, 22x = 10, 32x = 3 i 33x = 5. Variabilele din afara bazei (cu valori nule) sunt deci: x21, x31, x13, x23.

Aceast soluie de baz se indic n tabelul T, conform regulilor prezentate n cadrul Aplicaiei 4.1, rezultnd astfel tabelul (n care valorile variabilelor sunt scrise ngroat):

2 10

3 2 2 12

1 3 10 4 10

2 8 3 1 5 8

10 15 5 Se poate apoi verifica soluia de baz obinut nsumnd pe fiecare

coloan, respectiv linie valorile variabilelor de baz. Aceste sume trebuie s rezulte egale cu coeficienii bj, respectiv ai. Se poate de asemenea calcula valoarea funciei obiectiv corespunztoare bazei iniiale, obinndu-se:

f = 210 + 32 + 310 + 83 + 15 = 85 u.v. Faza B - Iteraia 1 (pe etape):

10. Valorile ui i vj sunt marcate n tabelul T1 de mai jos. 20. Valorile ij sunt incluse n tabelul T1. Deoarece exist valori ij > 0,

se obine: 531 == kl . Se alege ciclul indicat n tabelul T1 de mai jos. 30. Celulele pare ale ciclului ales sunt marcate n tabelul T1. Rezult,

ca variabil ce iese din baz: 332 = xx ps . 40. Se determin noua soluie de baz, iar rezultatele calculului sunt

indicate n tabelul T2 (vezi mai jos). Variabila ce intr n baz este x31 = xkl.

T1 v1 = 2 v2 = 3 v3 = -4

u1 = 0 2

10 *

3

2

-6

212

u2 = 0 1

1

3

10

-8

410

u3 = 5 5

2

8

3 *

1

5

8

10 15 5


11

Se poate verifica i aceast nou soluie de baz, la fel ca cea iniial, iar valoarea funciei obiectiv corespunztoare noii baze rezult astfel (se observ c este mai mic dect cea calculat pentru baza iniial):

f = 27 + 35 + 310 + 23 + 15 = 70 u.v. Iteraia 2 (pe etape):

10. Valorile ui i vj sunt marcate n tabelul T2 de mai jos. 20. Valorile ij sunt incluse n tabelul T2. Deoarece exist o valoare ij

> 0, se obine: 121 == kl . Se alege ciclul indicat n tabelul T2 de mai sus. 30. Celulele pare ale ciclului ales sunt marcate n tabelul T2. Rezult,

ca variabil ce iese din baz: 711 = xx ps .

T2 v1 = 2 v2 = 3 v3 = 1

u1 = 0 2

7 *

3

5

-1

212

u2 = 0 1

1

3

10 *

-3

4

10

u3 = 0 2

3

-5

8

1

58

10 15 5

40. Se determin noua soluie de baz, iar rezultatele calculului sunt

indicate n tabelul T3 (vezi mai jos). Variabila ce intr n baz este x21 = xkl. Valoarea funciei obiectiv pentru aceast nou soluie rezult astfel:

f = 312 + 17 + 33 + 23 + 15 = 63 u.v. Iteraia 3 (pe etape):

10. Valorile ui i vj sunt marcate n tabelul T3 de mai jos. 20. Valorile ij sunt incluse n tabelul T3. Deoarece NU exist valori

ij > 0, soluia de baz obinut dup iteraia 2 este i cea OPTIM.

T3 v1 = 1 v2 = 3 v3 = 0

u1 = 0 -1

2

3

12

-2

212

u2 = 0 1

7

3

3

-4

410

u3 = 1 2

3

-4

8

1

58

10 15 5


12

Soluia OPTIM presupune deci urmtoarele valori ale variabilelor:

.0

,5 ,3,3 ,7 ,12

32231311

3331

222112

======

===

xxxxxx

xxx

Valoarea minim a funciei obiectiv (vezi mai sus) este: fmin = 63 u.v.

Teste de autoevaluare (seciunea 4.1)

1. Care sunt particularitile formulrii unei probleme de transport faa de formularea general a unei probleme de programare liniar?

2. Indicai o situaie concret care ar putea fi rezolvat prin formularea unei probleme de transport.

3. n ce condiii putem spune c o problem de transport este echilibrat? Din ce motiv o astfel de problem este mai simplu de rezolvat dect una neechilibrat?

4. Ce conine tabelul de transport i care este scopul utilizrii acestuia? 5. Care este condiia ce trebuie ndeplinit de ctre o soluie de baz a

unei probleme de transport pentru a nu fi degenerat? 6. Cum se poate determina o soluie de baz iniial a unei probleme de

transport? Care este utilitatea acesteia? 7. Descriei, pe scurt, metoda celulelor. Pentru rezolvarea crui tip de

probleme se utilizeaz aceast metod? 8. Care este criteriul de ieire n baz la rezolvarea unei probleme de

transport cu metoda celulelor? De ce este necesar utilizarea unui astfel de criteriu?

9. Care este criteriul de intrare n baz la rezolvarea unei probleme de transport cu metoda celulelor i care este utilitatea acestuia?

10. Ce reprezint un ciclu ntr-un tabel de transport i n ce scop se construiete acesta?

Problem propus (seciunea 4.1)

S se rezolve problema de transport caracterizat de urmtorul tabel:

8 3 5

7 4 2

1 6 3

10

8

12

7 9 14


13

4.2. Elemente de programare neliniar

n cele ce urmeaz, vor fi studiate alte dou metode ale programrii

matematice: programarea neliniar i cea dinamic (dar numai la nivel elementar, fr a fi prezentate teoreme, algoritmi sau metode de rezolvare).

Astfel, n aceast seciune, prezentm doar cteva elemente de programare neliniar, ncercnd s evideniem, n primul rnd, dificultile specifice acestui tip de programare matematic, fa de programarea liniar, care este, de fapt, un caz particular al programrii neliniare.

4.2.1. Formularea problemei i dificulti specifice Formularea unei probleme de programare neliniar este, de fapt,

identic cu cea general a problemei programrii de optimizare, deja prezentat n partea introductiv a cursului (subseciunea 1.4.3).

De cele mai multe ori, neliniar este funcia obiectiv, ai crei coeficieni ci sunt variabili (n funcie de xi). Domeniul de aplicare coincide practic cu cel al programrii liniare, prezentat n subseciunea 3.1.2 (programarea liniar reprezint, de fapt, o simplificare).

Exemplu: Preul unitar al unei reparaii depinde, de fapt, de volumul reparaiilor, astfel:

=

=n

iijiojj xcc

1

, (4.12) unde cj este preul unitar, iar xi numrul de echipamente de tip i ce necesit reparaii, 1 i, j n. Rezult urmtoarea funcie obiectiv (ce reprezint costul total al reparaiilor pentru toate cele n tipuri de echipamente considerate):

= = = =

==n

j

n

j

n

j

n

iijjijojjj xxxcxcF

1 1 1 1

. (4.13) Se observ c funcia obiectiv nu mai este, n acest caz, liniar, ci ptratic.

Prezentm, n continuare, cteva dificulti specifice problemelor de programare neliniar. Considerm nti cazul unor restricii neliniare i al unei funcii obiectiv liniare. Astfel, n figurile 4.2 i 4.3 de mai jos, sunt prezentate cteva exemple tipice privind consecinele existenei unei restricii neliniare, care sunt comparate cu cazul restriciilor liniare (figura 4.1).

Figura 4.1 reprezint cazul programrii liniare, n care restriciile sunt liniare, domeniul soluiilor posibile este un poligon convex, iar soluia optim se afl n unul dintre vrfurile poligonului.

n figura 4.2, este prezentat cazul n care una dintre restricii este neliniar, domeniul soluiilor posibile este convex (dar nu mai este un poligon), iar soluia optim se poate afla n orice punct C, de pe arcul AB.

n figura 4.3, este prezentat cazul, mai dificil, n care una dintre restricii este neliniar, iar domeniul soluiilor posibile nu este convex (deoarece pe segmentul de dreapt AB, definit de dou puncte aflate n interiorul domeniului, exist puncte ce nu aparin domeniului). n acest caz, apar puncte de optim local sau global: astfel, unul dintre punctele C i D va fi, n funcie de reprezentarea grafic a funciei obiectiv, punctul de optim global


14

(corespunztor soluiei optime a problemei de programare neliniar), cellalt fiind doar un punct de optim local.

Fig. 4.1 Fig. 4.2 Fig. 4.3 Considerm, n continuare, cazul restriciilor liniare i al funciei

obiectiv neliniare, caz ilustrat grafic n figurile 4.4 i 4.5 de mai jos. Funcia obiectiv, n ambele cazuri considerate, i atinge optimul

(minimul sau maximul) n punctul zo(xo1, xo2), prezentnd valori mai mici sau mai mari pe curbele z1, z2, ..., caracterizate de faptul c n toate punctele lor, funcia obiectiv prezint aceeai valoare. Domeniul convex OACD reprezint, n ambele cazuri, domeniul soluiilor posibile, definit la fel ca n cazul programrii liniare (restriciile sunt liniare).

n primul exemplu (figura 4.4), soluia optim a problemei corespunde punctului zo, care este i maximul sau minimul absolut (global) al funciei obiectiv, care, n acest caz, aparine domeniului soluiilor posibile OACD.

n cel de-al doilea exemplu (figura 4.5), soluia optim corespunde punctului B (aflat la intersecia curbei z2 cu segmentul AC de pe frontiera domeniului OACD), care este doar un maxim / minim local al funciei obiectiv. Maximul / minimul global al acestei funcii corespunde punctului zo, care n acest caz nu aparine ns domeniului soluiilor posibile i deci nu poate fi soluia problemei de programare neliniar.

Observaie (condiia de concavitate - convexitate): Pentru a putea rezolva o problem de maxim, funcia obiectiv trebuie s fie o funcie concav. Pentru a putea rezolva o problem de minim, funcia obiectiv trebuie s fie o funcie convex. Aceste condiii sunt ilustrate, doar pentru cazul unei funcii cu o singur variabil, f(x), n figurile 4.6 i 4.7 de mai jos.

Condiia de concavitate este ilustrat de figura 4.6 i se poate exprima matematic astfel:

10 ),()1()(])1([ 2121 ++ xfxfxxf . (4.14)

x1

x2

x1 z2 A z1 C

*zo O x2 D

Fig. 4.4

z1 x1 *zo z2 A B

C O x2 D Fig. 4.5

x1 A B x2

x1 C

A D B x2


15

Condiia de convexitate este ilustrat de figura 4.7 i se poate exprima matematic astfel:

10 ),()1()(])1([ 2121 ++ xfxfxxf . (4.15)

Fig. 4.6 Fig. 4.7

4.2.2. Metode de rezolvare a problemelor de

programare neliniar De-a lungul timpului, s-au dezvoltat muli algoritmi destinai rezolvrii

problemelor de programare neliniar, dintre care unii sunt generali, deci aplicabili n toate cazurile, iar alii particulari, destinai unor cazuri particulare, cum ar fi programarea ptratic sau geometric (vezi subseciunea 4.2.3).

Prezentm mai jos doar principalii algoritmi utilizai, fr a-i detalia ns. Algoritmii generali sunt bazai pe soluiile matematice ale calculului

variaional (n special metoda multiplicatorilor lui Lagrange), adaptai ns exigenelor calculului automat. Unele tehnici generale i propun transformarea problemelor n unele de minim fr restrictiv (de tip Lagrange), cu mai multe variabile, altele sunt adaptri ale algoritmului simplex etc.

Un algoritm des utilizat este programarea separabil (liniarizarea secional). Metoda const n transformarea problemei de programare neliniar n una de programare liniar, prin nlocuirea funciei obiectiv (restriciei) care este neliniar cu mai multe funcii liniare pe seciuni, utiliznd aproximarea poligonal (liniarizarea pe poriuni).

O alt metod des ntlnit este metoda gradientului. Prin algoritmul gradient se caut (prin reprezentri discrete, cu diferene finite, a ecuaiilor programului neliniar) s se gseasc direcia i sensul de cretere maxim a gradientului funciei obiectiv n planul descris de variabilele sale, prin creteri mici K,, 21 xx date variabilelor pe direcii perpendiculare pe cercurile

sxx =+ 2221 din spaiul acestor variabile, tiindu-se c prin definiie gradientul unei funcii este derivata ei dup direcia perpendicular pe curbele de aceeai valoare (echiscalare).

4.2.3. Programarea geometric Programarea geometric este un caz particular al programrii neliniare,

n care funcia obiectiv este de forma:

imi am

an

iiii xxcg ... unde , 11

1=

== . (4.16)

f f() f(x1) f(x2) f(x1)+(1-)f(x2)

x x1 =x1+(1-)x2 x2

f

f(x1)+(1-)f(x2) f(x1) f(x2)

f()

x x1 =x1+(1-)x2 x2


16

Prezentm n continuare doar cteva elemente care stau la baza algoritmilor de rezolvare a problemelor de programare geometric.

Astfel, rezolvarea este bazat pe utilizarea inegalitii urmtoare:

=

=++n

iinnn

in u1

111 ...... 1 , (4.17)

n care: 1...21 =+++ n . (4.18)

Din aceast inegalitate rezult, dac se nlocuiesc i expresiile i din funcia obiectiv g:

............ 111

11

1

1

11

m

nn

Dm

D

n

n

n

nn xx

cc

=

++

, (4.19)

unde: . 1

ij

n

iij aD

== (4.20)

n continuare, se aleg parametrii i , care trebuie s ndeplineasc condiia =

n

ii

1 = 1 , astfel nct Dj = 0 , pentru 1 j m, i, ca urmare, termenii iDix

dispar din relaia (4.19). Se pot, de asemenea, determina parametrii i i astfel nct funcia g s fie minim.


1. Indicai un exemplu de aplicaie a programrii matematice n care funcia obiectiv s fie neliniar.

2. Care sunt principalele dificulti ntlnite la rezolvarea problemelor de programare neliniar cu una sau mai multe restricii neliniare, dar cu o funcie obiectiv liniar? Cum credei c pot fi rezolvate acestea?

3. Care este principala dificultate ntlnit n rezolvarea unei probleme de programare liniar n care doar funcia obiectiva este neliniar? n ce situaii aceast dificultate este mai uor de rezolvat?

4. n ce situaii considerai c este mai util un model bazat pe programarea neliniar dect unul bazat pe programarea liniar?

5. Enunai condiia de concavitate (sau pe cea de convexitate) pentru o funcie cu o singur variabil. Care este utilitatea acestei condiii n programarea geometric?

6. ncercai s extindei condiiile enunate pentru concavitate i convexitate n cazul unei funcii de dou variabile.

7. Menionai cteva metode de rezolvare a problemelor de programare neliniar. Care credei c sunt cele mai utilizate?

8. Care sunt particularitile unei probleme de programare geometric?


17

4.3. Elemente de programare dinamic Programarea dinamic reprezint, de fapt, un proces particular

secvenial de luare de decizii, n care se urmrete maximizarea sau minimizarea unei funcii obiectiv n condiiile unor restricii date.

Vom studia, n continuare, doar cazul programrii discrete, deterministe i cu orizont finit, pornind de la un exemplu concret, simplificat.

Exemplu: Considerm o problem de planificare a produciei, n cazul unui fabricant (de ngheat), ce are o cerere sptmnal rn, pentru n = 1, 2, , N (N sptmni), unde valorile rn sunt date iniial. Costul de pregtire a fabricaiei i de depozitare sunt ridicate, iar costul de producie i preul de vnzare se consider fixe. Se cere programul optim de fabricaie (cantitatea de ngheat qn produs sptmnal), astfel nct costul total s fie minim.

Ne propunem s prezentm doar formularea matematic a problemei, fr a indica i modul de rezolvare efectiv a sa. Fie sn stocul de produs disponibil la sfritul sptmnii n. Ecuaia de bilanare va fi, n acest caz:

sn = sn-1 + qn - rn , (4.21)

unde sn 0 , pentru n = 1, 2,..., N . Presupunem c s0 = 0 i sN = 0 (dac aceast ipotez nu este valabil,

cele dou valori ale stocului se pot adopta ca fiind egale cu zero). Costul de pregtire a produciei este: a(qn) , unde (qn) este

operatorul delta al lui Kronecker, definit astfel:

( )

>==

0pentru , 10pentru , 0

n

nn q

qq . (4.22)

Costul pstrrii stocului este: hsn, unde h este costul de stocare corespunztor unui produs.

Costul total, care reprezint funcia obiectiv a problemei considerate ca exemplu, este dat de relaia:

minim])([1

=+= =

N

nnn shqaC . (4.23)

Funcia obiectiv (4.23), mpreun cu ecuaia de bilanare (4.21) i cu condiiile s0 = sN = 0 , qn 0 , constituie formularea matematic a problemei considerate, care s-ar putea rezolva i prin aplicarea algoritmilor programrii neliniare prezena operatorului Kronecker (4.22) face ca funcia obiectiv s fie neliniar.

Elementele unei probleme de programare dinamic, care se pot identifica i pentru cazul exemplului enunat mai sus, sunt urmtoarele:

10. Starea, car reprezint setul de parametri ce conine toate informaiile necesare pentru luarea deciziilor actuale i n viitor i este notat cu Si ; n cazul exemplului, starea este sn-1 (cantitatea de produse aflate n stoc).

20. Etapa (epoca), ce exist ori de cte ori este necesar luarea unei decizii i se noteaz cu n; n cazul exemplului, etapa este n (fiecare sptmn).

30. Spaiul de decizie D = {dn}, ce reprezint spaiul tuturor variabilelor de decizie posibile dn, care cuantific o decizie: dnD(n, Sn) ; n


18

cazul exemplului, D = {qn} , unde 10 =

nNnj

jn srq (conform celei de a

doua inegaliti, cantitatea produs n sptmna n trebuie s fie sub cererea total din sptmna n pn la sfrit sptmna N).

40. Funcia de transformare, f, ce reprezint legtura dintre noua stare a sistemului i cea veche: Sn+1 = f (Sn, dn) ; n cazul exemplului, ea este exprimat prin ecuaia de bilanare (4.21).

50. Funcia obiectiv reprezint msura performanei sistemului i este de forma: C = C(S0, {dn}) , deci depinde de starea iniial i de toate deciziile luate. Valoarea sa optim (minim sau maxim) se noteaz cu fN(S0) pentru un orizont de studiu N (dac N este finit, avem o problem cu orizont finit). n cazul exemplului de mai sus:

)]()([min)( 11),(

01

nnn

N

nnsnDqN

rqshqasfnn

++= =

, (4.24)

unde fN(s0) corespunde unui ir de decizii optim: {dn}optim . Observaie: se poate defini i funcia gn, care reprezint ctigul sau

pierderea asociat etapei n: Sn = gn(Sn-1, dn) , (4.25)

iar C = =

N

nnnn dSg

1),( . (4.26)

Se poate defini i un ctig (pierdere) pentru toate cele N perioade: SN = gn(S0, {dn}). (4.27)

n cazul exemplului:

gn (sn-1, qn) = a (qn) + h (sn-1+qn-rn) . (4.28) Soluia problemei de programare dinamic avnd elementele prezentate

mai sus, care este tipic pentru rezolvarea tuturor problemelor de programare dinamic cu orizont discret finit, se obine utiliznd ecuaia funcional care rezult n urma raionamentului urmtor:

Fie fN(S0) costul minim pentru un orizont de planificare de N etape cu stocul iniial S0. Analog, se definesc costurile minime fN-n+1(Sn-1), pentru etapele n, n+1, , N.

Rezult, astfel, relaia, pentru n = 1, 2, , N:

( ) ( ) ( )[ ]NNNSnDqN qSgqSgqSgSf n ,...,,min)( 1212101),(0 1 +++= . (4.29) Deoarece funciile g2, , gn sunt independente de decizia q1 i deoarece

costul este o funcie aditiv, relaia (4.29) se poate scrie:

( ) ( ) ( ) ( ) ( ) ( )[ ]11101,11 1,101),1(0 ,min,min,min)( 01101 SfqSgqSgqSgSf NSDqN

nnnnSnDqSDqN nn

= +=

+=

(4.30)

Relaia (4.30) reprezint ecuaia funcional, care indic faptul c, pentru evaluarea lui fN(S0), trebuie cunoscute valorile lui fN-1(S1) pentru toate valorile posibile ale lui S1 ce rezult din decizia q1 i cererea r1.

Analog, rezult urmtoarea relaie:


19

)](),([min)( 22212),2(11 12SfqSgSf NSDqN += . (4.31)

Procednd recursiv, se ajunge la f1(SN-1) ce trebuie evaluat pentru toate valorile posibile ale lui SN-1 cum SN = 0, se obine f0(SN) = 0. Evaluarea pentru cazul unei valori posibile reprezint problema optimizrii pe o etap.

Observaia A: Prin formularea de mai sus, s-a redus o problem de programare neliniar n spaiul N-dimensional (problema cutrii lui {qn}optim) la o problem de N cutri succesive n spaiul uni-dimensional (determinarea lui qn,optim pentru etapa n), cu reducerea fantastic a efortului de calcul.

Observaia B: Programarea dinamic este o metod, un mod de abordare a problemei, i nu un algoritm (acesta din urm se elaboreaz pentru rezolvarea problemei pentru o etap i prezint mai multe variante).

Observaia C: Ecuaia fundamental a programrii dinamice este o reprezentare a principiului optimalitii, formulat astfel de Bellman, n 1952:

O succesiune optimal de decizii n cadrul unui proces de decizie n mai multe etape are proprietatea c, indiferent de etapa iniial, de starea i decizia iniial, celelalte decizii trebuie s constituie o succesiune de decizii optime pentru restul problemei, etapa i starea care rezult ca urmare a primei decizii fiind considerate drept condiii iniiale.

Cu alte cuvinte, o problem de programare dinamic este optimizat dac toate etapele ei au fost optimizate.


1. Ce reprezint, de fapt, programarea dinamic? Care este diferena esenial dintre acesta i programarea liniar sau neliniar?

2. Care sunt avantajele programrii dinamice faa de programarea liniar sau neliniar?

3. Indicai un domeniu de aplicaie al programrii dinamice i un exemplu concret de aplicare din acel domeniu.

4. Care sunt elementele unei probleme de programare dinamic? ncercai s le identificai pentru un exemplu concret.

5. Ce reprezint starea n cazul problemei de programare dinamic? Dar spaiul de decizie? Exist o legtur ntre acestea?

6. Ce reprezint i care este rolul funciei de transformare n programarea dinamic?

7. Ce reprezint ecuaia funcional a programrii dinamice i cum poate fi dedus aceasta?

8. Comentai principiul optimalitii al lui Bellman n cazul unui domeniu de aplicaie al programrii liniare.


20

Bibliografie

1. Baciu, A., Pascu, A., Puca, E., Aplicaii ale cercetrii operaionale,

Editura Militar, Bucureti, 1988. 2. Bebea, N., Metode pentru rezolvarea problemelor de optimizare,

Editura Didactic i Pedagogic, Bucureti, 1976. 3. Dumitrescu, A., Bazele ingineriei sistemelor, Editura Universitii

din Ploieti, 2005. 4. Dumitrescu, I., .a., Aplicaii inginereti ale calculatoarelor, Vol. 2

Optimizri, Editura Didactic i Pedagogic, Bucureti, 1976. 5. Kaufmann, A., Metode i modele ale cercetrii operaionale, Editura

tiinific, Bucureti, 1967. 6. Malia, M., Zidroiu, C., Matematica organizrii, Editura Tehnic,

Bucureti, 1971. 7. Nica, V., Ciobanu, Gh., .a., Cercetri operaionale, Vol. I, Ed.

Matrix Rom, Bucureti, 1998. 8. Oprian, Gh., Simion, E., Elemente de cercetri operaionale i

criptologie, Editura Politehnica Press, Bucureti, 2002. 9. Rendi, Dorina-Marieta, Metode ale cercetrii operaionale:

programare liniar, teoria jocurilor, teoria grafurilor, Editura Orizonturi Universitare, Timioara, 2002.

10. Teodorescu, N., Boldur, Gh., Stoica, M., Stancu-Minasian, M., Bncil, I., Metode ale cercetrii operaionale n gestiunea ntreprinderilor, Editura Tehnic, Bucureti, 1972.

Soluia problemei propuse (la seciunea 4.1)

Soluia optim este (precizm nti variabilele de baz):

.0,5 ,7

,8 ,1 ,9

32222111

3331

231312

======

===

xxxxxx

xxx

Valoarea minim a funciei obiectiv: fmin = 70.

BISP_ID_UI_4

Documents

Transcript of BISP_ID_UI_4