c12

Cercetari operationale

Barbacioru Iuliana Carmen

CURSUL 12

Cursul 12

2

Cuprins

2 Programare liniara 52.1 Modelul matematic al unei

probleme de programare liniara . . . . . . . . . . . . . . . . . . . . 62.2 Forme de prezentare a modelului matematic . . . . . . . . . . . . . 62.3 Clasicarea solutiilor unei probleme de

programare liniara. Proprietati . . . . . . . . . . . . . . . . . . . . 62.4 Metode pentru obtinerea unui program de baza si a unei baze

ortonormate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.5 Algoritmul simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.6 Metode pentru obtinerea unui program de baza initial . . . . . . . 62.7 Dualitatea n programarea liniara . . . . . . . . . . . . . . . . . . . 62.8 Algoritmul simplex dual . . . . . . . . . . . . . . . . . . . . . . . . 62.9 Algoritmul simplex revizuit . . . . . . . . . . . . . . . . . . . . . . 62.10 Modele liniare de tip transport . . . . . . . . . . . . . . . . . . . . 6

2.10.1 Probleme standard de transport . . . . . . . . . . . . . . . 62.10.2 Generalizari ale problemei transporturilor . . . . . . . . . . 62.10.3 Probleme de transport cu capacitati limitate . . . . . . . . 72.10.4 Probleme de transport cu centre intermediare . . . . . . . . 15

Index 17

3

Cursul 12

4

Cursul 12

Capitolul 2

Programare liniara

2.1 Modelul matematic al uneiprobleme de programare liniara

2.2 Forme de prezentare a modelului matematic

2.3 Clasicarea solutiilor unei probleme deprogramare liniara. Proprietati

2.4 Metode pentru obtinerea unui program de bazasi a unei baze ortonormate

2.5 Algoritmul simplex

2.6 Metode pentru obtinerea unui program de bazainitial

2.7 Dualitatea n programarea liniara

2.8 Algoritmul simplex dual

2.9 Algoritmul simplex revizuit

2.10 Modele liniare de tip transport

2.10.1 Probleme standard de transport

2.10.2 Generalizari ale problemei transporturilor6

Cercetari Operationale Barbacioru Iuliana Carmen

2.10.3 Probleme de transport cu capacitati limitate

Fie ij cantitatea maxima dintr-un anumit produs care poate transportatape ruta (i; j). Modelul problemei de transport constrnsa sa respecte limitareacapacitatii rutelor este:

min

24Xi2M

Xj2N

cijxij

35 (10.14)Xj2N

xij = ai; i 2M (10.15)Xi2M

xij = bj ; j 2 N (10.16)

0 xij ij ; i 2M; j 2 N (10.17)

Problema (10.14)-(10.17) admite solutii daca sunt satisfacute conditiile:

ai 0; bj 0; ij 0;Xi2M

ai =Xj2N

bj (10.18)Xi2M

ij bj ; j 2 N (10.19)Xi2M

ij ai; i 2M (10.20)

Determinarea unei solutii realizabile de baza.

Pentru rezolvarea problemei de transport cu capacitati limitate se folosesc tabelede aceeasi forma cu cele utilizate n problemele standard de transport, dar necare celula a tabelului se nregistreaza si ij , cantitatea maxima de produsecare poate transportata pe ruta (i; j). Pentru determinarea solutiei initiale sealege cpq = min

(ij)fcijg si se atribuie variabilei xpq valoarea maxima compatibila cu

restrictiile, deci:xpq = min fap; bq; pqg

Daca pq < ap si pq < bq , variabila xpq nu este considerata variabila debaza.

Daca pq = ap < bq sau pq = bq < ap, xpq este variabila de baza. Deasemenea xpq apartine bazei daca min fap; bq; pqg este ap sau bq.

7

Cursul 12

Vectorul x determinat prin acest algoritm nu constituie totdeauna o solutie.Se poate ntmpla ca unele diponibilitati sa nu e complet epuizate si unele cererisa nu e integral satisfacute din cauza conditiilor xij ij .

Daca sunt satisfacute conditiile (10.18)-(10.20), problema admite solutii.

O solutie realizabila de baza se poate determina prin modicarea vectoruluix.

Pentru expunerea modului n care trebuie modicat x, sa admitem ca ndepozitul k a ramas neexpediata o cantitate de marfa K si ca n punctele deconsum h si l mai sunt necesare cantitatile H si L. Deoarece

Pi2M

ai =Pj2N

bj ,

vom avea H + L = K.Algoritmul pentru transformarea vectorului x ntr-o solutie realizabila de

baza consta n:

pasul 1 : se completeaza linia k cu o celula n care variabila este xk;0 = K sicoloanele h si l cu cte o celula cu x0;h = H;x0;l = L. Se nlocuiesc costurilecij prin dij = 0 si se atribuie celulelor adaugate costurile dk;0 = 1; d0;h =1; d0;l = 1 ;

pasul 2 : se calculeaza multiplicatorii simplex din sistemul de ecuatii:

uk = 1; vh = 1; vl = 1

ui + vj = dij pentru xij 2 B; i 6= k; j 6= h; l

pasul 3 : se cauta solutia pentru care suma:

= xk;0 + x0;h + x0;l

este minima.Daca min 6= 0 , problema (10.14)-(10.17) nu are solutii realizabile, decinu sunt satisfacute conditiile (10.18)-(10.20).Daca min = 0, solutia care s-a determinat este o solutie realizabila debaza pentru problema (10.14)-(10.17).Revenim la problema initiala, stergnd din tabel celulele adaugate sinlocuind dij prin cij .

8


Criteriu de optimalitate.

Fie x solutia realizabila de baza obtinuta n pasul 3.Se calculeaza multiplicatorii simplex din sistemul:

cij = ui + vj pentru toti (ij) 2 B

si costurile comparative:

cij = cij (ui + vj)

Solutia este optima daca:

cij = 0 pentru toti 0 < xij < ijcij 0 pentru toti xij = 0 (10.21)cij 0 pentru toti xij = ij

adica daca toate costurile comparative asociate variabilelor cu valori nule suntnegative, iar cele asociate variabilelor care nu apartin bazei si au valori egalecu capacitatea maxima a rutei sunt nepozitive. Exemplele (2.10.1) si (2.10.2)sunt exemple de organizare optima a transporturilor n cazurile n care rutele aucapacitati limitate.O alta metoda de optimizare a transporturilor cu capacitati limitate, care va expusa ulterior, se bazeaza pe transformarea problemei ntr-o problema cu treiindici.

Exemplul 2.10.1 Se cere organizarea optima a transporturilor necesare aprovizionariicentrelor Cj ; j = 1; :::; 4 cu o marfa depozitata n punctele Di; i = 1; :::; 3, cunoscndca pe unele rute capacitatea de transport este limitata. n tabelul 10.20 numerelenscrise n coltul din dreapta sus a celulei (i; j) reprezinta capacitatea maxima atransportului pe ruta (i; j) : De exemplu, 13 = 100 nseamna ca din depozitulD1 nu pot expediate centrului C3 dect cel mult 100 de unitati. Daca unor ijnu li se atribuie nici o valoare, capacitatea de transport pe acea ruta este practic

9

Cursul 12

nelimitata. Daca o ruta (r; p) nu poate folosita, rp = 0:

Tabelul 10.20

C1 C2 C3 C4 aiui

D15010

5015

100 + ...

100 7

50 ...

505

2007

D2 1502006

100 10010

...100

12

...150 +

7500

0

D312 15

10010

508

10010

bjvj

1506

1508

3000

2005

Solutie: Se verica n primul rnd daca problema admite solutii realizabile,

adica daca3Pi=1ij bj si

4Pj=1

ij ai: n exemplul din tabelul 10.20, ecarelinie si coloana are cel putin un ij > M; M ind un numar pozitiv, arbitrar demare, deci este asigurata existenta solutiilor realizabile. Pentru obtinerea solutieiinitiale avem:

min cij = c14 = 5

x14 = min fa1; b4; 14g = min f200; 200; 50g = 50deci x14 nu este o variabila din baza. n continuare gasim:

mini6=1j 6=4

cij = c21 = 6;

x21 = 150

deci x14 apartine bazei.Pentru a marca deosebirea dintre variabilele cu valori nenule care apartin bazeisi cele care nu fac parte din baza, acestea din urma vor trecute n tabel cu cifrebarate. Cel mai mic cost din tabelul 10.20 n care s-a suprimat prima coloanaeste c13 = c24 = 7; deci x13 = 100 (nu apartine bazei) si x24 = 150 (apartinebazei). Eliminnd din tabel coloana a patra, gasim c22 = c33 = 10 si x22 = 100(nu apartine bazei), iar x33 = 100 (apartine bazei), c23 = 12; deci x23 = 100:Prin aceasta atribuire este satisfacuta integral cererea n C3; dar concomitenteste lichidat si disponibilul din D2: Aceasta situatie face ca solutia obtinuta sa e

10


degenerata. ntr-adevar, dupa ultima atribuire, x13 = 50 se gaseste o solutie carecontine n baza cinci valori nenule, n timp ce dimensiunile tabelului cer o solutiecu sase variabile de baza. Deoarece att n linia a doua, ct si n coloana a treiavariabilele au valori diferite de zero, nu se poate aplica metoda perturbatiilorpentru completarea solutiei de baza si aceasta se completeaza transformnd unadin variabilele x13; x22 n variabila de baza. Vom alege pe x13 marcnd aceastadecizie prin bararea valorii ei. Se observa ca s-a ajuns la o solutie realizabila, decivom testa optimalitatea ei calculnd multiplicatorii simplex si costurile compar-ative. Atribuind lui v3 valoarea zero, ceilalti multiplicatori simplex se calculeazacu usurinta. Valorile lor au fost trecute n tabelul 10.20.Calculnd costurile comparative, le mentionam numai pe acelea care arata casolutia nu este optima. Astfel avem:

c14 = 5 (7 5) = 3 > 0; x14 ind la limita superioara,c32 = 15 (10 + 8) = 3 < 0; x23 = 0

deci solutia poate mbunatatita.Sa admitem ca vrem sa mbunatatim solutia micsornd valoarea variabilei x14: Ci-clul transferului cantitatilor transportate trebuie construit utiliznd numai vari-abile care apartin bazei. Acest ciclu, pentru exemplul studiat, este nscris ntabelul 10.20.

Tabelul 10.21

C1 C2 C3 C4Disponibil

aiui

D15010

5015

100 1007

50 505

2002

D2 1502006

100 10010

10012

1507

5000

D312 15

10010

508

1002

Necesarbjvj

1506

15017

30012

2007

Se observa ca nu poate lua dect valoarea zero, deoarece x13 este la limitasuperioara.Modicarea facuta astfel nu schimba planul transporturilor, iar din punct devedere matematic consta numai n transformarea variabilei x14 n variabila apartinnd

11

Cursul 12

bazei si a lui x13 n variabila la limita superioara.Costurile comparative asociate solutiei din tabelul 10.21 satisfac conditiile de op-timalitate, deci soluta este optima. Observnd ca c32 = 0 si x32 = 0; putemcauta o alta solutie optima care, evident, va conduce la aceeasi valoare a functieiobiectiv, dar din tabelul 10.21 se constata ca ciclul care trebuie format are unvrf de ordin par n x14, variabila a carei valoare este la limita superioara, deci nu poate lua dect valoarea zero.n concluzie problema admite o singura solutie optima.

Exemplul 2.10.2 Ne propunem sa rezolvam problema de transport cu capacitatilimitate pe unele rute, datele ind continute n tabelul 10.22.

Tabelul 10.22

C1 C2 C3 C4Disponibil

aiui

D1 5010

503 5 4

50

D26 5

70 1003

50 502

120

D3 1508100 100

130 30

450 100

3400

D45 6

1802

502

180

Necesarbjvj

200 150 300 100

Solutie: Construind solutia initiala n acest tabel, se ajunge la urmatoareasituatie: n depozitul D3 ramn 70 de unitati neexpediate, n timp ce C2 si C3sunt aprovizionate sub necesar, cu 50 si respectiv 20 de unitati.Pentru transporturile necesare se construieste tabelul 10.23, care se obtine dintabelul 10.22 adaugnd liniei a treia o celula cu variabila x3;0 si coloanelor doi sitrei celulele cu variabilele x0;2 si x0;3.Toate costurile cij ; i = f1; :::; 4g ; j = f1; :::; 4g se nlocuiesc prin dij = 0; i= f1; :::; 4g ; j = f1; :::; 4g iar costurile corespunzatoare celulelor adaugate suntd3;0 = d0;2 = d0;3 = 1.Folosind acest tabel se cauta

min fx3;0 + x0;2 + x0;3g

12


n tabelul 10.23 s-au construit doua cicluri, din care rezulta ca, lund = 50; ' =20, se obtine min fx3;0 + x0;2 + x0;3g = 0.

Tabelul 10.23

C1 C2 C3 C4 aiui

50...1

20...1

D1 50-...

0

...2500 2

...

...0 0

501

D2......0 0

...70+'

100 0

250 '...

500

1201

D3 70--' 1

...150+

0100100 0

3030: : :0

...50 + ' 100

0400

1

D40 0

1800

500

1801

bjvj

2001

1501

3001

1001

Solutia din tabelul 10.24 este realizabila si este o solutie de baza daca una dinvariabilele la limita superioara este transformata n variabila de baza.

Tabelul 10.24

C1 C2 C3 C4 aiui

D1 8...

2

50 ...

503 15 14

502

D2 1......6

...

...5

90 1003

30 502

1201

D3

...200 ...

8

...

100 + 1001

30 304

70 1003

4000

D4 15 6180

2

502

1802

bjvj

2008

1501

3004

1003

13

Cursul 12

Vom considera ca x32 = 100 apartine bazei. Lund u3 = 0, se calculeazamultiplicatorii simplex si costurile comparative.S-au nscris n tabelul 10.24 numai costurile comparative care indica posibilitatilede mbunatatire a solutiei. Deoarece c1;1 = 8 , se ia x1;1 = dar, formnd ciclul,se observa ca = 0, deoarece valoarea variabilei x3;2 nu poate marita. Aceastaiteratie introduce n baza variabila x11 cu valoarea zero si transforma din nou pex32 n variabila la limita superioara.Solutia din tabelul 10.25 nu este optima i printr-o noua iteratie se obtine solutiadin tabelul 10.26 care satisface criteriul de optimalitate, deci nu mai poate mbunatatita.

Tabelul 10.25

C1 C2 C3 C4 aiui

D1 0 + 2

50 503 5 4

500

D2 16 35

90 1003

30 502

1205

D3 200 8

100 1001

30 304

70 + 1003

4006

D4 15 16180

2

502

1804

bjvj

2002

1503

3002

1003

Tabelul 10.26

C1 C2 C3 C4 aiui

D1 302

20 503 5 4

503

D26

305

90 1003

502

1205

D3 1708

100 1001

30 304

100 1003

4009

D45 6

1802

502

1804

bjvj

2001

1500

3002

1006

14


2.10.4 Probleme de transport cu centre intermediare

Sub acest titlu se trateaza problemele n care marfurile produse n unitatile Pi;i = 1; :::;m sunt transportate n depozitele Dk; k = 1; :::; p, care au sarcina dea satisface cererile consumatorilor Bj ; j = 1; :::; n.Depozitele Dk sunt numite centre intermediare. Problema consta n deter-minarea planurilor de transport de la producator la depozite si de la depozite laconsumatori astfel nct cheltuielile de transport necesare aprovizionarii consuma-torilor sa e minime. Pentru formularea problemei folosim urmatoarele notatii:

ai; i 2M = f1; :::;mgproductia n Pi; dk; k 2 P = f1; :::; pgcapacitatea depozitului Dk; bj ; j 2 N = f1; :::; ngcererea consumatorului Bj ; xik; i 2M; k 2 P cantitatea transportata din Pi n Dk; ykj ; k 2 P; j 2 Ncantitatea transportata din Dk n Bj :

Cu aceste notatii, problema se scrie:

min

24Xi2M

Xk2P

cik xik +Xk2P

Xj2N

qkj ykj

35 (10.22)Xk2P

xik = ai; i 2M (10.23)Xi2M

xik = dk; k 2 P (10.24)Xj2N

ykj = dk; k 2 P (10.25)Xk2P

ykj = bj ; j 2 N (10.26)

xik 0; ykj 0; i 2M; k 2 P; j 2 N

daca s-au notat cu cik si qkj costurile de transport ale unei unitati de produsrespectiv din Pi n Dk si din Dk n Bj . Problema are solutii daca sunt satisfacuteconditiile:

ai 0; dk 0; bj 0;Xi2M

ai =Xk2P

dk =Xj2N

bj (10.27)

15

Cursul 12

Variabilele xik si ykj sunt independente, astfel, problema de transport cucentre intermediare se descompune n doua probleme succesive:

minXi2M

Xk2P

cik xik

pe multimea solutiilor nenegative a sistemului (10.23)-(10.24);

minXk2P

Xj2N

qkj ykj

pe multimea solutiilor nenegative a sistemului (10.25)-(10.26).

Exemplul 2.10.3 Productia de gru a opt gospodarii agricole dintr-o regiune sedepoziteaza n trei silozuri care vor alimenta doua mori. Se cere planul de repar-tizare a productiei gospodariilor n silozuri si planul de aprovizionare a morilorastfel nct costul total al transporturilor ntregii productii de gru la mori sa eminim.

Solutie: Datele numerice ale problemei sunt cele date n tabelele 10.27 si10.28.

Tabelul 10.27

GospodariiSilozuri

G1 G2 G3 G4 G5 G6 G7 G8

Capacit:

silozuri

{^n mii tone

S1 5 4 //// 3 2 6 //// //// 10

S2 3 2 4 5 //// //// 5 1 8

S3 //// //// 6 5 4 4 3 2 7,5

Produse(mii tone)

3 1,5 4 2 2,5 6 3,5 3

Tabelul 10.28

Silozurimori

S1 S2 S3Capacit:

mori

M1 6 5 7 15,5

M2 4 7 4 10Capacitate

siloz 10 8 7,5

16


Patratele hasurate n tabelul 10.27 arata ca productia unor gospodarii nu poate transportata n anumite silozuri.De exemplu gospodariile G7 si G8 nu pot expedia gru n silozul S1.Numerele nscrise n patratele tabelelor reprezinta costul transportului a 1 000 tde la o sursa la o destinatie, unitatea monetara ind 10 000 lei.Fie xij ; i = 1; :::8; j = 1; 2; 3 variabilele care reprezinta cantitatile transportatedin Gi n Sj si yjk; j = 1; 2; 3; k = 1; 2 variabilele care reprezinta cantitatiletransportate din Sj n Mk.Modelul problemei este de forma (10.22)-(10.26), conditiile (10.27) sunt ndepli-nite si solutia se obtine rezolvnd cele doua probleme de transport ale carordate sunt continute n tabelele 10.27 si 10.28. Costurile asociate variabilelor caretrebuie sa ia valori nule n solutie indca transporturile pe acele rute nu suntngaduite se noteaza cu M , M ind un numar pozitiv arbitrar de mare.Solutia optima a problemei de transport gospodarii-silozuri este data n tabelul10.29, costul corespunzator ind C1 = 31; 5:Solutia optima a problemei de transport silozuri-mori se obtine foarte usor, costulminim ind C2 = 125. Costul minim de transport al ntregii productiii de grula mori este C = C1 + C2 = 216; 5.

Tabelul 10.29

G1 G2 G3 G4 G5 G6 G7 G8

S1 5 4 M 23

2;52

5;56

M M 10

S2 33

1;52

3;54 5 M M 5 1

8

S3M M

0;56 5 4

0;54

3;53

32

7,5

3 1,5 4 2 2,5 6 3,5 3

17

Index

Criteriude optimalitate, 9

Modeleliniare de tip transport, 6

Probleme de transportcu capacitati limitate, 7cu centre intermediare, 15

18

Programare liniaraModelul matematic al unei probleme de programare liniaraForme de prezentare a modelului matematicClasificarea solutiilor unei probleme de programare liniara. ProprietatiMetode pentru obtinerea unui program de baza si a unei baze ortonormateAlgoritmul simplexMetode pentru obtinerea unui program de baza initialDualitatea n programarea liniaraAlgoritmul simplex dualAlgoritmul simplex revizuitModele liniare de tip transportProbleme standard de transportGeneralizari ale problemei transporturilorProbleme de transport cu capacitati limitateProbleme de transport cu centre intermediare

Index

c12

Documents

Transcript of c12