cap2 programare liniara

Modelarea proceselor economice 9

Unitatea de învăţare 2

MODELE ECONOMICE REZOLVATE PRIN PROGRAMARE LINIARĂ

[ACKOFF, 1975], [ANDREICA, 1998], [GIARD, 1998], [HILLIER, 2005], [KARMANOV, 1977], [KAUFMANN, 1975], [KAUFMANN, 1987], [KRAJEWSKI, 2005] [IONESCU, 1999], [MALIŢA, 1971+, [MIH0C, 1973+, *RAŢIU, 2001], [RUSU, 2001], [SZABO, 2005], [THIEL, 1990], [ZIDĂROIU, 1983]

Obiectiv Obiectivul acestui capitol este de a defini şi construi modele economice care vor fi rezolvate prin programare liniară. Se prezintă probleme economice clasice, întâlnite în practică, care pot fi rezolvate prin aplicarea modelelor matematice ale programării liniare. Sunt abordate şi modelele de alocare – problema de repartizare şi problema de transport. Modelele sunt rezolvate cu ajutorul produsului software QM (Quantitative Management).

Competenţele unităţii de învăţare Parcurgerea acestei unităţi permite înțelegerea definirii şi construcţiei modelelor economice care conduc la problema programării liniare. Prin studiile de caz prezentate şi aplicaţiile propuse, studenţii vor fi capabili să modeleze un proces sau fenomen din lumea reală care să fie rezolvat apoi prin programare liniară. Aceasta presupune definirea variabilelor modelului, definirea funcţiei obiectiv şi a restricţiilor, iar în final interpretarea economică a rezultatelor obţinute prin aplicarea produsului software QM (modulele Linear Programming, Integer Programming, Mixed Integer Programming, Assignment, Transportation).

Durata medie de parcurgere a acestei unităţi de învăţare este de 8 ore.

O clasă largă de modele de optimizare în economie se rezolvă prin programare liniară. Problema de programare liniară se încadrează în limitele generale ale modelelor programării matematice şi se caracterizează prin faptul că atât funcţia obiectiv cât şi restricţiile sunt exprimate matematic prin funcţii liniare. Rezolvarea matematică a problemei de programare liniară se bazează pe aparatul matematic furnizat de algebra liniară şi elaborarea unor metode eficiente de determinare a soluţiilor problemei. Prima metodă generală de rezolvare a problemei de programare liniară (algoritmul SIMPLEX) este datorată lui G. Dantzig (1951) şi permite determinarea soluţiilor în cazul în care acestea există, sau poate dovedi inexistenţa soluţiilor, degenerarea lor etc. A doua metodă generală de rezolvare a problemei de programare liniară (algoritmul Simplex dual) este datorată lui C.E. Lemke (1953). Elaborarea celor două metode a condus la noi cercetări în acest domeniu şi rezultatele obţinute au devenit capitole legate de

10 Dorin Lixăndroiu

problemele de programare în numere întregi (algoritmii lui R. Gomory, 1958, 1963), problemele de transport, problemele de alocare (repartizare). Ulterior, metodele de rezolvare s-au diversificat în strânsă legătură cu dezvoltarea calculatoarelor. Forma generală a problemei de programare liniară (PPL) este: Max [Min] nn xcxcxcf ...2211

cu retricţiile: 11212111 ... bxaxaxa nn

22222121 ... bxaxaxa nn

.......................................................... (1) mnmnmm bxaxaxa ...2211

şi 0...,,0,0 21 nxxx

În notaţie matriceală forma generală a PPL este:

Max [Min] XCXf t

BXA (2)

0X

unde: nmA , - este matricea coeficienţilor sistemului de restricţii

1,mB - este vectorul coloană al termenilor liberi

1,nX - este vectorul coloană al celor n necunoscute

nC t ,1 - este vectorul coloană transpus ale cărui componente dau

coeficienţii necunoscutelor în funcţia obiectiv. În forma generală a PPL se consideră că variabilele (necunoscutele) sunt numere reale. Există numeroase aplicaţii economice de mare importanţă care conduc la modele în care se pun şi alte condiţii asupra variabilelor. Natura concretă a fenomenelor modelate impune cerinţa ca variabilele supuse restricţiilor problemei să nu poată lua decât valori din anumite mulţimi, cel mai frecvent numere întregi. Distingem următoarele tipuri particulare de probleme de programare liniară: A. Programarea liniară mixtă Există două tipuri de variabile:

Rxxx m,...,, 21

Nyyy n,...,, 21

Modelul presupune maximizarea (minimizarea) formei liniare:

Max [Min]

m

i

n

jjjii ygxfZ

1 1

(3)

cu p restricţii (inecuaţii sau ecuaţii liniare):


m

i

n

jkjkjiki pkcybxa

1 1

,...,2,1,

B. Programarea liniară în numere întregi Toate variabilele sunt numere întregi şi pozitive, adică Nxxx n,...,, 21 . De exemplu, în

construcţia modelului apar ca necunoscute: oameni, tipuri de casuţe de vacanţă, avioane de capacităţi diferite, tipuri de produse etc. şi din analiza realităţii ne aşteptăm ca soluţia optimă să nu fie “mare”. Pentru aceste tipuri de variabile punem condiţia să fie numere întregi. Ar fi greu de interpretat o soluţie optimă, de tipul: 4,35 avioane Airbus 320 şi 6,78 echipaje. Dar, dacă modelul conduce la o soluţie optimă cu valori “mari”, de tipul: produsul P1 – 438,78 bucăţi, produsul P2 – 397,25 bucăţi, atunci se poate rezolva PPL cu variabile reale şi apoi rotunjim soluţiile obţinute.

C. Programarea liniară booleană (0 – 1) Necunoscutele sunt variabile booleene, adică în final soluţiile problemei de programare liniară vor fi de tip 0 / 1. La forma generală a problemei adăugăm restricţiile: Zxxx n,...,, 21 - variabile întregi

şi nixi ,...,2,1,1 (4)

nixi ,...,2,1,0

Evident, singurele numere întregi care aparţin intervalului [0, 1] sunt 0 sau 1. Aceste probleme apar în modelele în care se doreşte, de exemplu, selectarea unor proiecte dintr-o mulţime dată, selectarea unor variante de acţiune dintr-o mulţime dată etc. Variabila 1ix va indica alegerea proiectului i, iar 0ix va arăta că proiectul i nu

este selectat. Prezentăm în continuare câteva probleme economice clasice, întâlnite în practică, care pot fi rezolvate prin aplicarea modelelor matematice ale programării liniare. 1. Programarea producţiei [1] Considerăm un proces de producţie în care se realizează n produse/activităţi. Pentru desfăşurarea procesului există un disponibil de m resurse (materii prime, forţă de muncă, capacităţi de producţie, resurse financiare), limitate superior. Se cunosc:

- cantităţile de resurse necesare pentru producerea unei unităţi din produsul /activitatea j,

- costurile de producţie şi preţurile de vânzare pentru fiecare unitate din produsul /activitatea j.

Notăm: mibi ,...,2,1, - nivelul cunoscut al resurselor

njmiaij ,...,2,1,,...,2,1, - cantitatea din resursa i folosită pentru

producerea unei unităţi din produsul/activitatea j njc j ,...,2,1, - preţul de vânzare al unei unităţi din produsul/activitatea j


njd j ,...,2,1, - costul de producţie al unei unităţi din produsul

/activitatea j njx j ,...,2,1, - nivelul necunoscut al produsului/activităţii j

Se cere să se determine nivelurile celor n produse/activităţi care conduc la un beneficiu maxim. Problema conduce la construcţia următorului model care se rezolvă prin metoda programării liniare. Modelul

Funcţia obiectiv:

n

jjjj xdc

1

)(max

Restricţiile:

n

jijij mibxa

1

,...,2,1, (5)

njx j ,...,2,1,0

2. Programarea producţiei [2] O firmă realizează un produs. Pentru o perioadă de n luni se cunosc cantităţile lunare contractate. Acestea pot fi realizate în avans şi depozitate. Producţia poate fi realizată în orar normal sau suplimentar. Volumul producţiei realizabile este limitat de capacităţile de producţie existente. Costurile de producţie în orar normal, în orar suplimentar, precum şi costurile de stocare diferă de la o lună la alta. Se pune problema determinării cantităţilor ce trebuie realizate lunar în orar normal, în orar suplimentar şi care trebuie stocate, astfel încât costurile de producţie şi stocare să fie minime, în condiţiile în care la începutul primei luni şi la sfârşitul perioadei stocul produsului este 0. Notăm: n - numărul de luni niRi ,...,2,1, - cantităţile lunare contractate

niyi ,...,2,1, - volumul producţiei lunare realizabile în program normal

niy si ,...,2,1, - volumul producţiei lunare realizabile în program suplimentar

nici ,...,2,1, - costul lunar al producţiei realizabile în program normal

nicsi ,...,2,1, - costul lunar al producţiei realizabile în program suplimentar

d - costul unitar de stocare nixi ,...,2,1, - cantităţile ce trebuiesc produse lunar în program normal

nix si ,...,2,1, - cantităţile ce trebuiesc produse lunar în program suplimentar

nisi ,...,3,2, - cantităţile ce trebuiesc stocate lunar.

Se cere să se determine nixi ,...,2,1, , nix si ,...,2,1, şi nisi ,...,2,1, , astfel încât

costurile de producţie şi stocare să fie minime.


Modelul

Funcţia obiectiv:

n

i

ssi

si

siii xcxcsdxcxc

21111min

Restricţiile:

i

k

i

kki

skk niRsxx

1 11 1,...,2,1,

nnsnn Rsxx (6)

niyx ii ,...,2,1,0

niyx si

si ,...,2,1,0

nisi ,...,2,1,0

Modelul se rezolvă prin metoda programării liniare. 3. Problema amestecului Cunoscută şi sub numele de problema dietei sau nutriţiei, problema amestecului este una din primele probleme practice, formulată şi rezolvată ca problemă de programare liniară. Problema constă în determinarea unei diete dintr-un număr dat de alimente, care să satisfacă anumite cerinţe biologice şi să fie în acelaşi timp cât mai ieftină. Astfel de probleme apar în alcătuirea raţiilor pentru animale în zootehnie, pentru calcularea amestecului optim de îngrăşăminte în agricultură, în industria chimică pentru diverse amestecuri, în industria petrolieră pentru amestecuri de benzine etc. Notăm: ,,...,2,1,,...,2,1, njmiaij - cantitatea din principiul nutritiv i,

conţinută într-o unitate din produsul/alimentul j ,,...,2,1, mibi - numărul minim de unităţi din principiul nutritiv i,

pe care trebuie să-l conţină dieta ,,...,2,1, njc j - costul unei unităţi din produsul/alimentul j

,,...,2,1, njx j - cantitatea necunoscută din produsul/alimentul j

care va intra în compoziţia dietei (necunoscutele problemei) Modelul

Funcţia obiectiv:

n

jjj xc

1

min

Restricţiile:

n

jijij mibxa

1

,...,2,1, (7)

njx j ,...,2,1,0

Modelul construit se rezolvă prin metoda programării liniare.


4. Problema reducerii pierderilor la tăierea materialelor În activităţile productive apar probleme de optimizare la tăierea (croirea) unor materiale (rulouri de hârtie, bare metalice, ţevi, scânduri, stofe etc.), prin minimizarea pierderilor rezultate. Presupunem că materialele ce urmează a fi tăiate/croite au aceleaşi dimensiuni. Operaţia de tăiere/croire poate fi efectuată după mai multe modele, rezultând bucăţi de dimensiunile dorite şi un rest ce reprezintă o pierdere. Notăm: ,,...,2,1, mibi - numărul de bucăţi necesare de tipul i

,,...,2,1,,...,2,1, njmiaij - numărul de bucăţi de tipul i care se obţin

din tăierea/croirea conform modelului j ,,...,2,1, njrj - costul restului rezultat prin tăierea/croirea conform

modelului j ,,...,2,1, njx j - numărul de materiale ce urmează a fi tăiate/croite

conform modelului j; Modelul

Funcţia obiectiv:

n

jjj xr

1

min

Restricţiile:

n

jijij mibxa

1

,...,2,1, (8)

njx j ,...,2,1,0 - numere întregi

Modelul construit se rezolvă prin metoda programării liniare cu variabilele numere întregi, deoarece materialele ce urmează a fi tăiate/croite conform unui anumit model se presupun indivizibile. 5. Problema realizării proiectelor O instituţie publică trebuie să realizeze m proiecte (obiective) în n ani. Se pune problema repartizării pe ani a celor m proiecte (obiective), astfel încât beneficiile obţinute să fie maxime, în ipotezele: - realizarea unui obiectiv durează maxim un an - mai multe obiective pot fi realizate în acelaşi an - nu se pot transfera sume din bugetul de finanţare de la un an la altul Notăm:

,,...,2,1, njB j - bugetul anului j

,,...,2,1,,...,2,1, njmibij - beneficiul rezultat din realizarea în anul j a

obiectivului i ,,...,2,1,,...,2,1, njmifij - finanţarea necesitată de realizarea

obiectivului i în anul j ,,...,2,1,,...,2,1, njmixij - variabile booleene, care indică realizarea

1ijx sau non-realizarea 0ijx obiectivului i în anul j


Modelul

Funcţia obiectiv:

m

i

n

jijij xb

1 1

max

Restricţiile:

m

ijijij njBxf

1

,...,2,1, (9)

n

jij mix

1

,...,2,1,1

njmixij ,...,2,1,,...,2,1,1,0

Modelul conduce pentru rezolvare la problema de programare liniară cu variabile booleene (0-1). Observaţie. În cazul a 7 obiective care trebuie realizate în 4 ani, avem un model cu 28 de variabile întregi şi 67 (4 + 7 + 28 + 28) de restricţii ! Conform relaţiilor (4), 56 de resticţii vor asigura condiţia ca variabilele să fie booleene (0-1). STUDIUL DE CAZ Nr. 1 – Sacoşa de golf O firmă realizează un produs (sacoşă de golf) în două variante: standard şi de lux. Procesul de fabricaţie constă în execuţia a 4 operaţii succesive (croit, cusut, finisaj şi control de calitate). Timpii de execuţie pe unitatea de produs (în ore) sunt:

Produsul Operaţia 1 Operaţia 2 Operaţia 3 Operaţia 4

Standard 0.6 0.5 1.1 0.1

De luxe 1 0.8 0.7 0.25

Profitul unitar obţinut este de 10 u.m. pentru varianta standard şi de 9 u.m. pentru cea de lux. Timpii disponibili estimaţi pentru fiecare operaţie sunt:

Operaţia 1 Operaţia 2 Operaţia 3 Operaţia 4

Timpii disponibili

650 h 700 h 750 h 200 h

Determinaţi programul optim de fabricaţie, adică numărul de produse, în cele două variante, care trebuie executat astfel încât profitul total obţinut să fie maxim. Notăm: 1x - numărul de sacoşe standard

2x - numărul de sacoşe de lux


Modelul Funcţia obiectiv: 21 910max xx

Restricţiile: 65016.0 21 xx

7008.05.0 21 xx (10)

7507.01.1 21 xx

20025.01.0 21 xx

0,0 21 xx

Rezolvăm cu modulul Linear Programming din produsul software Quantitative Management (QM).

Figura1

În figura 1 se prezintă soluţia obţinută – programul optim de fabricaţie presupune realizarea a 433.82 sacoşe de golf model standard şi a 389.70 sacoşe de golf model de lux. Valoarea corespunzătoare a funcţiei obiectiv va fi de 7845.59 u.m. Evident, în realitate planul de producţie optim va fi rotunjit la 433 sau 434 pentru modelul standard şi 389 sau 390 pentru modelul de lux. Problemele de programare liniară în care intervin două sau trei variabile se pot rezolva şi pe cale grafică. Geometric, în cazul a două variabile, fiecare restricţie determină un semiplan, care rezultă prin divizarea planului de către dreapta a cărei ecuaţie se obţine prin transformarea inecuaţiei în ecuaţie. În final se obţine un poligon, care reprezintă mulţimea soluţiilor admisibile. Soluţia optimă trebuie căutată în vârfurile poligonului. În figura 2 se prezintă rezolvarea grafică a problemei considerate în QM.


Figura 2

Interpretarea rezultatelor Rezolvarea în QM, permite o analiză aprofundată şi o interpretare economică a soluţiilor obţinute. În figura 3 sunt date rezultatele acestei analize.

Figura 3

Reduced costs - arată cu cât trebuie să se modifice coeficienţii funcţiei obiectiv, pentru ca în soluţia finală valorile variabilelor să fie pozitive. Slack / Surplus - furnizează pentru fiecare restricţie valorile variabilelor auxiliare. În cazul exemplului studiat dă informaţii importante pentru manager, legate de capacităţile de producţie neutilizate. Astfel, avem la operaţia 2 un surplus de 171,32 ore, iar la operaţia 4 un surplus de 59,19 ore.


Dual Value - dă informaţii asupra valorii marginale a resurselor în soluţia optimă. Preţul dual asociat unei restricţii arată cu cât se îmbunătăţeşte valoarea optimă a funcţiei obiectiv la creşterea cu o unitate a valorii membrului drept din restricţia respectivă.

Figura 4

Astfel, dacă mărim cu o oră timpul afectat pentru operaţia 1, de la 650 ore la 651 ore, va rezulta o creştere a valorii funcţiei obiectiv cu 4,26 u.m. de la 7845,59 u.m. la 7849,85 u.m. (figura 4). Evident pentru operaţiile 2 şi 4, Dual Value = 0, deoarece la aceste operaţii am constatat un surplus de ore neutilizate. Objective Coefficient Ranges - pentru variaţia coeficienţilor funcţiei obiectiv în intervalul: (Lower Bound - Upper Bound), soluţia optimă rămâne neschimbată. Din figura 3, deducem că o variaţie a profitului pentru sacoşa de lux în intervalul (6,36 u.m. - 16,67u.m.) nu conduce la modificarea structurii optime de producţie (figura 5).

Figura 5

În schimb, pentru un profit de 16,67 u.m. se renunţă complet la producţia sacoşelor standard şi se vor produce numai sacoşe de lux (figura 6).


Figura 6

Right Hand Side Ranges - preţul dual asociat unei restricţii rămâne valabil dacă valoarea resursei (membrul drept al inegalităţii) variază în intervalul (Lower Bound - Upper Bound). De exemplu, din figura 3 deducem că preţul dual de 4,26 u.m. rămâne valabil dacă timpul afectat operaţiei 1 variază în intervalul (409,09 ore – 846,34 ore). Observaţie. Analiza senzitivităţii se face printr-o singură modificare a unui coeficient la un moment dat.

STUDIUL DE CAZ Nr. 2 – Model de alegere a unui produs software modular Se consideră că un produs software este format din mai multe module şi fiecare modul prin execuţie îndeplineşte o anumită funcţie, necesară utilizatorului. Ipotezele modelului: I1. Pentru fiecare modul se cunoaşte fiabilitatea şi costul; I2. Utilizatorul dispune de o sumă limitată pentru achiziţionarea produsului software; I3. Utilizatorul cunoaşte frecvenţa de utilizare a fiecărei funcţii din produsul software. Să se maximizeze fiabilitatea medie prin alegerea unei mulţimi optime de module fără redundanţă. Datele problemei sunt: - bugetul disponibil = 12 u.m. - pentru funcţia 1 sunt disponibile 4 module - frecvenţa de utilizare = 0.75

Modulul P1 P2 P3 P4

Fiabilitatea 0.90 0.80 0.85 0.95

Costul 6 4 5 8

- pentru funcţia 2 sunt disponibile 3 module


- frecvenţa de utilizare = 0.25

Modulul Q1 Q2 Q3

Fiabilitatea 0.70 0.80 0.90

Costul 2 4 6

Modelul general Notăm: N - numărul de funcţii kF - frecvenţa de utilizare a funcţiei k

km - numărul de module disponibile pentru funcţia k

kjR - fiabilitatea modulului j care execută funcţia k

kjC - costul modulului j care execută funcţia k

B - bugetul disponibil

_R - fiabilitatea medie

,1kjx dacă modulul j a fost ales pentru funcţia k

,0kjx dacă modulul j nu a fost ales pentru funcţia k

Funcţia obiectiv:

N

kkk RFR

1

_max , unde

km

jkjkjk RxR

1

(11)

Restricţiile sunt:

km

jkj Nkx

1

,...,2,1,1 (12)

N

k

m

jkjkj

k

BCx1 1

kkj mjNkx ,...,2,1,,...,2,1,1,0

Constatăm că rezolvarea acestui model conduce la o problemă de programare liniară cu variabile booleene (0-1). Modelul general particularizat pentru datele problemei prezentate mai sus, a fost rezolvat cu modulul Integer Programming din QM. Figura 7 prezintă datele problemei introduse în QM.


Figura 7

Soluţiile obţinute sunt date în figura 8.

Figura 8

Rezolvarea modelului de alegere a unui produs software modular a condus la selectarea modulului P4 pentru funcţia 1 şi a modulului Q2 pentru funcţia 2. S-a obţinut o fiabilitate medie de 0,9125. RESTRICŢII LOGICE ÎN MODELELE DE PROGRAMARE LINIARĂ Considerăm un model general de alegere a unor proiecte de investiţii. Avem n proiecte de investiţii pentru care se cunosc beneficiile ce ar putea rezulta din realizarea acestora. Notăm cu: ,1ix dacă proiectul i se realizează

,0ix dacă proiectul i nu se realizează

Se pune problema de a determina proiectele de investiţii care se vor realiza, astfel încât beneficiul total să fie maxim. Analizăm în continuare introducerea restricţiilor pentru câteva operaţii logice.


A. INCOMPATIBILITATEA Două proiecte sunt incompatibile când nu se pot realiza în acelaşi timp; se poate realiza doar unul sau niciunul (ele presupun utilizarea aceleiaşi resurse limitate, sau sunt variante tehnice cu aceeaşi finalitate).

0jx 1jx

0ix Da Da

1ix Da Nu

Aceasta conduce la restricţia: 1 ji xx (13)

Generalizare:

- din n proiecte, se poate realiza unul sau niciunul:

n

iix

1

1

- din n proiecte, se pot realiza cel mult m proiecte:

n

ii mx

1

B. DISJUNCŢIA (sau) Cel puţin unul dintre proiectele i sau j trebuie să se realizeze.

0jx 1jx

0ix Nu Da

1ix Da Da


Generalizare:

- din n proiecte, cel puţin unul trebuie să se realizeze:

n

iix

1

1

- din n proiecte, cel puţin m trebuie să se realizeze:

n

ii mx

1

C. ALTERNATIVA (sau exclusiv) Presupune să se realizeze, în cazul a două proiecte unul sau altul, dar nu amândouă.

0jx 1jx

0ix Nu Da

1ix Da Nu



Generalizare:

- din n proiecte, unul singur trebuie să se realizeze:

n

iix

1

1

- din n proiecte, m proiecte trebuie să se realizeze:

n

ii mx

1

D. IMPLICAŢIA Dacă proiectul i implică proiectul j, nu se poate realiza i fără a realiza şi j. Dar, dacă i nu se realizează, proiectul j se poate realiza sau nu.

0jx 1jx

0ix Da Da

1ix Nu Da

Aceasta conduce la restricţia: ji xx (16)

Implicaţia poate apare în situaţii mai complexe, de exemplu:

khi xxx realizarea proiectului i implică realizarea cel puţin a unuia din

proiectele h şi k

khi xxx 2 realizarea proiectului i implică realizarea proiectelor h şi k

ikh xxx 2 realizarea proiectelor h sau k implică realizarea proiectului i

STUDIUL DE CAZ Nr. 3 – Model de alegere a unor obiective Modelul general a fost formulat în cadrul Problemei realizării proiectelor (problema 5). Abordăm cazul particular al unei instituţii publice care trebuie să realizeze 6 obiective (O1, O2,..., O6) în 5 ani. Variabilele modelului (variabile booleene) sunt: ,5,...,2,1,6,...,2,1, jixij

care indică realizarea 1ijx sau non-realizarea 0ijx obiectivului i în anul j.

Să stabilim ce restricţii logice trebuiesc adăugate modelului în următoarele ipoteze: I1. Nu se pot realiza mai mult de două obiective într-un an.

6

1

5,...,2,1,2i

ij jx

I2. Nu se pot realiza mai mult de 3 obiective în primii 2 ani. 3...... 622212612111 xxxxxx ,

sau mai concentrat putem scrie:

6

121 3

iii xx


I3. Obiectivul O2 nu poate fi realizat în acelaşi an cu obiectivul O1. - scriem câte o restricţie de incompatibilitate pentru fiecare an: 5,...,2,1,121 jxx jj

I4. Dacă obiectivele O1 şi O2 sunt realizate în acelaşi an, nici un alt obiectiv nu poate fi realizat în acelaşi an. - pentrul anul 1 avem: 211131 2 xxx

211141 2 xxx

211151 2 xxx

211161 2 xxx

- aceleaşi restricţii vor fi adăugate şi pentru anii 2,3, 4 şi 5. Concentrat putem scrie cele 20 de restricţii logice astfel: 5,...,2,1,6,5,4,3,2 21 jixxx jjij

I5. În primul an trebuie realizate obiectivele O1 şi O2 sau obiectivele O3 şi O4. 241312111 xxxx - din cele 4 obiective doar două se vor realiza

2111 xx - cele două vor fi (O1 şi O2) sau (O3 şi O4)

I6. Obiectivul O1 poate fi realizat în primul an numai dacă acesta este anul de realizare al obiectivelor O2 şi O3. - recunoaştem situaţia analizată la implicaţie: “realizarea proiectului i implică realizarea proiectelor h şi k”; deci, vom adăuga restricţia logică: 3121112 xxx

MODELE DE ALOCARE (Distribuirea şi repartizarea resurselor) Modelele de alocare optimizează modul de împărţire a resurselor disponibile între activităţile ce urmează a fi executate. Obiectivul îl constituie alocarea resurselor astfel încât să se minimizeze cheltuielile totale sau se maximizeze beneficiul. Notăm: ,,...,2,1, miRi - resursele

,,...,2,1, njJ j - activităţile

,,...,2,1,,...,2,1, njmicij - cheltuielile (sau beneficiile) care rezultă

din alocarea unei unităţi din resursa iR activităţii .jJ

,,...,2,1, nja j - cantităţile de resurse necesare

,,...,2,1, mibi - cantităţile de resurse disponibile


În figura 9 este dată matricea care defineşte problema de alocare.

Resurse Activităţi Cantitatea de resursă

Disponibilă J1 J2 .... Jn

R1 c11 c12 .... c1n b1

R2 c21 c22 .... c2n b2 .... .... .... .... .... .... Rm cm1 cm2 .... cmn bm

Cantitatea de resursă necesară

a1

a2

....

an

Figura 9 – Matricea problemei de alocare Dacă suma resurselor disponibile este egală cu suma cantităţilor necesare, adică:

m

i

n

jji ab

1 1

(17)

problema de alocare este echilibrată. În cazul unei probleme neechilibrate algoritmii de rezolvare determină şi activităţile ce nu vor fi executate sau resursele ce nu vor fi folosite. În clasa problemelor de alocare distingem: problema de transport şi problema de repartizare. Problema de transport Constă în transportul unui produs care se află în m depozite (centre de aprovizionare, surse) către n consumatori (clienţi, centre de desfacere), astfel încât costul de transport să fie minim. Notăm: ,,...,2,1, miDi - depozitele

,,...,2,1, njC j - centrele de consum

,,...,2,1, nja j - cantităţile de produs solicitate

,,...,2,1, mibi - cantităţile de produs disponibile

,,...,2,1,,...,2,1, njmicij - cheltuielile pentru transportul unei unităţi

de produs de la depozitul iD la centrul de consum jC

,,...,2,1,,...,2,1, njmixij - cantitatea necunoscută de produs care va

fi transportată de la depozitul iD la centrul de consum jC

Modelul

Funcţia obiectiv:

m

i

n

jijij xc

1 1

min (18)

Restricţiile:

n

jiij miax

1

,...,2,1,

m

ijij njbx

1

,...,2,1,

njmixij ,...,2,1,,...,2,1,0

Modelul problemei de transport este rezolvat în QM de modulul Transportation, care tratează şi situaţiile neechilibrate (cererea > oferta sau cererea < oferta). Problema de repartizare Într-o problemă de repartizare fiecare resursă poate fi alocată unei singure activităţi şi fiecare activitate nu poate utiliza decât o singură resursă. Este un caz particular de problemă de transport în care toate cantităţile disponibile sunt egale cu 1 şi toate cantităţile necesare sunt egale tot cu 1. Exemplul tipic de problemă de repartizare: un număr m de persoane trebuie să efectueze un număr n de activităţi. Fiecare persoană are un anumit cost (randament / performanţă) pentru fiecare activitate. Se încearcă formarea de perechi resursă-activitate astfel încât să se optimizeze funcţia obiectiv (minimizarea costurilor sau maximizarea performanţelor). Astfel de probleme apar când trebuie să repartizăm avioanele şi echipajele pe zboruri, camioanele şi şoferii pe anumite rute, personalul dintr-o organizaţie pe anumite funcţii etc. Dacă există mai multe activităţi decât se pot efectua, trebuie precizat ce activitate nu va fi realizată. Dacă există mai multe resurse decât activităţi, se va preciza ce resurse rămân nealocate. Modelul

Funcţia obiectiv:

m

i

n

jijij xc

1 1

min (cost)

sau

m

i

n

jijij xr

1 1

max (randament)

Restricţiile:

n

jij mix

1

,...,2,1,1 (19)

m

iij njx

1

,...,2,1,1

,1ijx dacă resursa i a fost alocată activităţii j

,0ijx dacă resursa i nu a fost alocată activităţii j

Modelul problemei de repartizare este rezolvat în QM de modulul Assignment.


STUDIUL DE CAZ Nr. 4 – Repartizarea echipajelor pe cursele aeriene [ACKOFF, 1975]

O linie aeriană desfăşoară activităţi zilnice în ambele sensuri între două oraşe A şi B. Dacă echipajul are baza (domiciliul) în A şi soseşte în B cu un anumit zbor, atunci el trebuie să se reîntoarcă în A cu unul din zborurile următoare (eventual a doua zi). Compania aeriană doreşte să determine ce perechi de zboruri (dus-întors) trebuie formate astfel încât timpul total de şedere pe aeroportul străin să fie minim. Apare şi problema: fiind date perechile de zboruri, unde trebuie să-şi aibă baza fiecare echipaj? Activităţile zilnice se desfăşoară conform orarului:

Număr zbor Plecare A Sosire B

A-B 1 7 h 8 h

A-B 2 8 h 9 h

A-B 3 13 h 30 min 14 h 30 min

A-B 4 18 h 30 min 19 h 30 min

A-B 5 20 h 21 h

A-B 6 23 h 30 min 0 h 30 min

Număr zbor Plecare B Sosire A

B-A 1 8 h 9 h 15 min

B-A 2 8 h 30 min 9 h 45 min

B-A 3 12 h 13 h 15 min

B-A 4 17 h 30 min 18 h 45 min

B-A 5 19 h 20 h 15 min

B-A 6 22 h 23 h 15 min

Echipajul trebuie să se odihnească între zboruri cel puţin 5 ore. Determinaţi perechile de zboruri pentru care timpul întreg de staţionare pe un aeroport străin să fie redus la minim. Se poate stabili baza echipajelor fie în A, fie în B. Pentru fiecare pereche de zboruri, echipajul va fi repartizat în baza care face posibilă obţinerea unui timp minim de staţionare. Rezolvare Pasul 1. Calculăm timpul de staţionare pe aeroportul străin în ipoteza că baza este în A. Pentru aceasta considerăm toate perechile (A-Bi, B-Aj), cu i=1,2,…,6 şi j=1,2,…,6. Plecare A - Sosire B

Zbor B-A 1 B-A 2 B-A 3 B-A 4 B-A 5 B-A 6

A-B 1 24 24.5 28 9.5 11 14

A-B 2 23 23.5 27 8.5 10 13

A-B 3 17.5 18 21.5 27 28.5 7.5

A-B 4 12.5 13 16.5 22 23.5 26.5

A-B 5 11 11.5 15 20.5 22 25

A-B 6 7.5 8 11.5 17 18.5 21.5


Pasul 2. Calculăm timpul de staţionare pe aeroportul străin în ipoteza că baza este în B. Pentru aceasta considerăm toate perechile (B-Ai, A-Bj), cu i=1,2,…,6 şi j=1,2,…,6. Plecare B - Sosire A

Zbor B-A 1 B-A 2 B-A 3 B-A 4 B-A 5 B-A 6

A-B 1 21.75 21.25 17.75 12.25 10.75 7.75

A-B 2 22.75 22.25 18.75 13.25 11.75 8.75

A-B 3 28.25 27.75 24.25 18.75 17.25 14.25

A-B 4 9.25 8.75 5.25 23.75 22.25 19.25

A-B 5 10.75 10.25 6.75 25.25 23.75 20.75

A-B 6 14.25 13.75 10.25 28.75 27.25 24.25

Pasul 3. Combinăm cele două tabele, alegând baza care oferă timpul de staţionare cel

mai scăzut pentru fiecare pereche. Noua tabelă conţine datele de intrare în modulul Assignment din QM (figura 10).

Figura 10

Soluţia este dată în figura 11.

Figura 11

Pasul 4. Pentru a stabili baza echipajelor identificăm soluţiile de repartizare (Assign) în cele două tabele construite la Pasul 1 şi 2. Rezultă că 3 perechi de zboruri vor avea baza în A şi 3 perechi de zboruri vor avea baza în B, iar durata totală de aşteptare pe aeroporturile străine pentru toate cele 6 echipaje este de 49 ore şi 45 minute (Optimal cost = $49.75).

Baza A : < A - B 2 > < A - B 3 > < A - B 6 > Baza B : < A - B 5 > < A - B 4 > < A - B 1 >

Rezumat

Problema de programare liniară se încadrează în limitele generale ale modelelor programării matematice şi se caracterizează prin faptul că atât funcţia obiectiv cât şi restricţiile sunt exprimate matematic prin funcţii liniare.

Tipuri particulare de probleme de programare liniară: - programarea liniară în numere întregi

- programarea liniară mixtă

- programarea liniară booleană

Rezolvarea în QM permite o analiză aprofundată şi o interpretare economică a soluţiilor obţinute – valoarea marginală a resurselor în soluţia optimă (Dual Value), intervalele de variaţie ale coeficienţilor funcţiei obiectiv pentru care soluţia optimă rămâne neschimbată (Lower Bound - Upper Bound), valorile variabilelor auxiliare (Slack / Surplus) etc.

Utilizarea variabilelor booleene permite introducerea restricţiilor pentru

câteva operaţii logice: incompatibilitatea, disjuncţia (sau), alternativa (sau exclusiv), implicaţia. Modul de utilizare este prezentat în Studiul de caz nr.3 – Model de alegere a unor obiective.

Modelele de alocare (distribuirea şi repartizarea resurselor) optimizează modul de împărţire a resurselor disponibile între activităţile ce urmează a fi executate. Obiectivul îl constituie alocarea resurselor, astfel încât să se minimizeze cheltuielile totale sau se maximizeze beneficiul. În clasa problemelor de alocare distingem: problema de transport şi problema de repartizare.


Test de evaluare a cunoştinţelor – Probleme propuse 1. O persoană doreşte să realizeze depozite bancare în valoare totală de 2000 u.m. la oricare din cele 6 bănci analizate. Informaţiile obţinute sunt:

Banca Dobânda Situaţia Anii

B1 4.5% Excelentă 2009

B2 5% Foarte bună 2011

B3 6% Proastă 2007

B4 5.5% Bună 2006

B5 4.5% Excelentă 2010

B6 5% Foarte bună 2011

Investitorul decide că nu va plasa mai mult de 25% la o singură bancă şi cel puţin jumătate din fonduri vor fi plasate la băncile pentru care are informaţii după anul 2008. Nu va investi mai mult de 30% în băncile care au situaţia financiară mai puţin de foarte bună. Ce sumă va depune în fiecare bancă pentru a maximiza profitul din dobândă ? Construiţi modelul şi rezolvaţi-l utilizând produsul software QM. [RUSU, 2001] 2. Un student în managementul afacerilor la Nowledge College trebuie să se înscrie la 65 de cursuri pentru obţinerea licenţei. El trebuie să aleagă cel puţin 23 de cursuri de specialitate (de afaceri) şi cel puţin 20 de cursuri complementare (nonbusiness courses). Dispune de 3000 $ pentru cumpărarea cursurilor editate. În medie un curs de specialitate necesită 120 de ore de studiu, iar cartea costă 60$. Pregătirea unui curs complementar necesită 200 ore de studiu, iar cartea costă 24$. Ca orice student, îşi pune problema câte cursuri de specialitate şi complementare să aleagă pentru a învăţa cât mai puţin. Construiţi modelul, găsiţi soluţia optimă şi analizaţi rezultatele utilizând produsul software QM. 3. O firmă de prelucrarea lemnului dispune de 69 de scânduri de dimensiuni: 290cmx25cmx4cm. Pentru o lucrare contractată, firma trebuie să livreze câte 100 de scânduri de următoarele dimensiuni: 50cmx25cmx4cm, 70cmx25cmx4cm şi 80cmx25cmx4cm. Cum trebuie tăiate scândurile astfel încât cantitatea totală de deşeuri rezultate să fie minimă? Construiţi modelul şi găsiţi soluţia optimă utilizând produsul software QM. 4. O unitatea comercială trebuie să răspundă unei cereri de 23 unităţi din produsul P, eşalonată pe o perioadă de 4 luni. La începutul fiecărei luni unitatea se poate aproviziona cu orice cantitate din produsul respectiv la un preţ ce variază de la o lună la alta.

luna 1: cerere = 5 pret unitar = 10




luna 4: cerere = 5 pret unitar = 9 Să se definească un model pentru politica optimă de aprovizionare a firmei astfel încât toate cererile să fie satisfăcute, ştiind că în stoc se găsesc la începutul primei luni 4 unităţi din perioada anterioară, capacitatea maximă a depozitului este de 10 unităţi, iar la sfârşitul ultimei luni toate produsele sunt vândute. Determinaţi soluţia optimă utilizând produsul software QM. 5. Într-un model investiţional se poate alege între 5 proiecte şi există o sumă limitată de 1100 u.m., care poate fi investită. Beneficiul rezultat din realizarea proiectelor este:

Proiect 1 Proiect 2 Proiect 3 Proiect 4 Proiect 5

Beneficiul 75 81 85 92 63

Costul 290 250 240 330 220

În ipotezele: I1. Alegerea proiectului 3 implică alegerea a cel puţin două din proiectele 1, 4 sau 5 şi I2. Proiectele 2 şi 3 nu se pot realiza în acelaşi timp, formulaţi modelul care conduce la un beneficiu maxim. Determinaţi soluţia optimă utilizând produsul software QM.

6. O firmă are depozite în 4 filiale şi aprovizionează cu acelaşi produs 9 centre. Cheltuielile de transport pentru o unitate de produs, oferta şi cererea sunt date în tabelul de mai jos:

C1 C2 C3 C4 C5 C6 C7 C8 C9 Oferta

D1 31 43 40 36 37 41 47 29 42 427

D2 19 18 20 47 14 36 13 62 47 3824

D3 57 59 55 64 18 20 53 39 64 4370

D4 28 46 52 60 25 18 42 59 24 1280

Cererea 1500 1000 1000 1500 1000 1000 600 1000 1500

a) a) Să se stabilească planul de transport astfel încât cheltuielile să fie minime. b) b) Centrele cu cererea nesatisfăcută apelează în perioada următoare la un alt

furnizor pentru întreaga cantitate. Stabiliţi planul de transport pentru noua perioadă, în ipoteza că oferta firmei şi cererea centrelor de consum rămase, se păstrează neschimbate. c) Reduceţi oferta pentru perioada a 3-a în filialele (depozitele) cu exces astfel încât să se obţină o problemă de transport echilibrată (cererea rămâne aceeaşi). Rezolvaţi problema utilizând produsul software QM.

7. Reluaţi Studiul de caz nr. 4 – Repartizarea echipajelor pe cursele aeriene în ipoteza că durata dintre zboruri este de cel puţin o oră. Stabiliţi perechile de zboruri pentru care timpul întreg de staţionare pe un aeroport străin să fie redus la minim. Determinaţi soluţia optimă utilizând produsul software QM.

cap2 programare liniara

Documents