modelare ma\atematica in inginerie curs 1

Universitatea POLITEHNICA din Bucureti Facultatea Ingineria i Managementul Sistemelor

Tehnologice

Modelare Matematic n Inginerie

Autor curs: Conf.dr.ing.mat. Ovidiu Bljin

MMI - Cursul 1 2

Capitolul 1

MODELARE I OPTIMIZARE MATEMATIC

(I)

Cap.1. Modelare i optimizare matematic

MMI - Cursul 1 3

1. Introducere 2. Programare liniar


MMI - Cursul 1 4

1. Introducere


MMI - Cursul 1 5

Optimizarea sau programarea matematic const n determinarea unui punct dintr-un spaiu real dat, care realizeaz minimul sau maximul unei funcii reale, cu valori reale, cu respectarea unui sistem de restricii definit de egaliti sau inegaliti algebrice. Modelul matematic general al unei astfel de probleme se poate exprima sub forma:

=

uxlxhxg

xf

00

)()(

)([max]min

unde: nx R , , , . RR: nf mng RR: pnh RR: Cap.1. Modelare i optimizare matematic

MMI - Cursul 1 6

Optimizarea presupune urmtoarele dou activiti: modelarea matematic pentru optimizare; rezolvarea modelului de optimizare. Aceste dou activiti implic fundamente i concepte teoretice diferite, dar s-au dezvoltat ntr-o corelare perfect. Modelarea matematic a unei probleme reale implic reprezentarea realitii studiate. Aceasta necesit elemente de conceptualizare, de identificare a parametrilor i a variabilelor, a relaiilor funcionale care exist ntre variabile i a relaiilor de mrginire a variabilelor. Modelarea matematic pentru optimizare este un proces iterativ care presupune o serie de pai pentru: identificarea parametrilor i variabilelor care caracteri-


MMI - Cursul 1 7

zeaz fenomenul analizat; definirea mulimilor de evoluie a indicilor acestor elemente; precizarea domeniului de definiie a variabilelor; elaborarea funciei obiectiv a modelului; scrierea relaiilor algebrice sau difereniale care leag variabilele i parametrii precizai mai sus; colectarea datelor asociate modelului. Dup modelare are loc rezolvarea modelului, analiza soluiei acestuia i pe baza ei, eventual, reluarea procesului de modelare. n fig.1 sunt artai principalii pai ai procesului de modelare i de rezolvare a modelului obinut.


MMI - Cursul 1 8

Fig.1 Cap.1. Modelare i optimizare matematic

MMI - Cursul 1 9

De obicei, aceti pai se parcurg de mai multe ori, repetndu-se anumite etape pn la definirea complet i minimal a modelului. Cea mai dificil etap const n recunoaterea i definirea problemei, care presupune izolarea poriunii din univers ce trebuie modelat i precizarea restriciilor. Exemplu: Se consider o companie care produce scaune n patru centre de fabricaie F1,..., F4, amplasate n localiti diferite, scaune pe care le vinde n patru magazine M1,..., M4, din alte localiti, cu preurile 20, 15, 20, respectiv, 18 u.m. (uniti monetare). Fiecare centru de fabricaie are propriul su cost de producie al scaunelor i anume 5, 7, 3, respectiv, 4 u.m.


MMI - Cursul 1 10

Costul de transport, exprimat n u.m., de la fiecare centru de fabricaie la fiecare magazin, este: Tab.1

M1 M2 M3 M4F1 1 1 2 0 F2 3 6 7 3 F3 3 1 5 3 F4 8 2 1 4

Cheresteaua necesar fabricaiei scaunelor este achizi-ionat de la dou depozite D1 i D2 aflate n localiti diferite de cele de fabricaie i vnzare, la un pre de 0,1 i, respectiv, 0,075 u.m. Costul de transport al cherestelei de la fiecare depozit la


MMI - Cursul 1 11

fiecare centru de fabricaie este dat n tab.2: Tab.2

F1 F2 F3 F4D1 0,01 0,02 0,04 0,04 D2 0,04 0,03 0,02 0,02

Pentru asigurarea produciei, de la fiecare depozit com-pania se aprovizioneaz cu o cantitate de cherestea care nu este mai mic de 8 u.c. (uniti de capacitate: m3, steri). Cantitatea de cherestea necesar pentru un scaun este de 20 u.c. Numrul minim i numrul maxim de scaune posibil de fabricat la fiecare centru de producie sunt indicate n tab.3 de mai jos:


MMI - Cursul 1 12

Tab.3 F1 F2 F3 F4

min 0 400 500 250 max 500 750 1000 250

Numrul minim i numrul maxim de scaune pe care le poate livra fiecare magazin sunt date n tab.4: Tab.4

M1 M2 M3 M4min 500 100 500 500 max 2000 400 1500 1500

S se stabileasc un plan de aprovizionare, fabricaie i livrare care s maximizeze profitul companiei.


MMI - Cursul 1 13

Elaborarea modelului matematic: 1. Definirea domeniilor de apartenen a indicilor parame-trilor i variabilelor

Nume Valoare Descriere

i [1, nrdep] Domeniul de evoluie a indicilor asociai depozitelor de cherestea; nrdep = 2

j [1, nrfab] Domeniul de evoluie a indicilor asociai centrelor de fabricaie; nrfab = 4

k [1, nrdes] Domeniul de evoluie a indicilor asociai magazinelor; nrdes = 4


MMI - Cursul 1 14

2. Identificarea i definirea parametrilor i variabilelor

Nume Valoare Descriere

spretk[20, 15, 20,

18] Preul de vnzare a scaunelor la magazinele M1,..., M4

pscostj [5, 7, 3, 4] Costul de fabricaie a scaunelor la centrele de fabricaie F1,..., F4

tscostjk[1, 1, 2, 0, 3,

6, 7, 3, 3, 1, 5, 3, 8, 2, 1, 4]

Costul de transport al scaunelor de la fiecare centru de fabricaie Fj la fiecare magazin Mk [u.m.]

tmcostij

[0,01; 0,02; 0,04; 0,04; 0,04; 0,03; 0,02; 0,02]

Costul de transport al cherestelei de la fiecare depozit Di la fiecare centru de fabricaie Fj [u.m.]


MMI - Cursul 1 15

mcosti [0,1; 0,075] Costul cherestelei la depozitele Di

qamini [8; 8] Cantitatea minim de achiziie de cherestea la depozitele Di [u.c.]

qms 20 Cantitatea de cherestea necesar pentru fabricarea unui scaun [u.c./ buc.]

fminj[0; 400; 500;

250]

Numrul minim de scaune posibil de fabricat la fiecare centru de fabricaie Fj [buc.]

fmaxj[500; 750; 1000; 250]

Numrul maxim de scaune posibil de fabricat la fiecare centru de fabricaie Fj [buc.]

smink[500; 100; 500; 500]

Numrul minim de scaune solici-tat de fiecare magazin Mk [buc.]

smaxk [2000; 400; Numrul maxim de scaune soli-


MMI - Cursul 1 16

1500; 1500] citat de fiecare magazin Mk [buc.]

xdfij ? Cantitatea de cherestea achiziio-nat de la fiecare depozit Di de fiecare centru de fabricaie Fj la fiecare magazin Mk [u.c.]

xfsjk ? Numrul de scaune livrate (trans-portate) de la fiecare centru de fabricaie Fj la fiecare magazin Mk

3. Construcia modelului matematic Modelul matematic asociat procesului descris n enun are forma urmtoare:


MMI - Cursul 1 17

=====

==

=

=

=+

= =

=

=

=

= =

= =

(7) ,..., , ,..., Z,(6) ,..., , ,..., , ,..., , ,

(5) ,..., ,

(4) ,..., ,

(3) ,..., ,

(2) ,..., ,

(1) )(

)( max

nrdesknrdepixfsnrdesknrfabjnrdepixfsxdf

nrfabjxfsqmsxdf

nrdeskmaxsxfsmins

nrfabjmaxfxfsminf

nrdepiminqaxdf

xdftcosmtcostm

xfstcoststcospsspret

ik

ikij

nrdep

i

nrdes

kjkij

nrfab

jkikk

nrdes

kjjkj

nrfab

jiij

nrdep

i

nrfab

jijiij

nrfab

j

nrdes

kjkjkjk

1111100

10

1

1

1

1 1

1

1

1

1 1

1 1


MMI - Cursul 1 18

Funcia obiectiv (1) modeleaz maximizarea profitului companiei exprimat ca diferena dintre ctigul obinut din vnzarea tuturor scaunelor i costurile cu cheresteaua cum-prat, transportul de la depozitele de cherestea la centrele de fabricaie, transportul scaunelor de la centrele de fabri-caie la magazine, precum i costul de producie a scaunelor. Restricia (2) se refer la cantitatea de cherestea cump-rat de centrele de fabricaie de la fiecare depozit. Restricia (3) reprezint ncadrarea produciei scaunelor n limitele de producie a fiecrui centru de fabricaie. Restricia (5) modeleaz ncadrarea vnzrii scaunelor n limitele de livrare a fiecrui magazin. Restricia (6) reprezint o balan a cherestelei utilizat de fiecare centru de fabricaie.


MMI - Cursul 1 19

2. Programare liniar 2.1. Modele de programare liniar (I)


MMI - Cursul 1 20

2.1. Modele de programare liniar (I) 2.1.1. Modele de alocare 2.1.2. Modele de asamblare 2.1.3. Modele de dezasamblare 2.1.4. Modele de dezasamblare-asamblare 2.1.5. Modele de producie cu selectarea optim a tehnologiilor 2.1.6. Modele de sisteme cu stocuri 2.1.7. Modele de producie liniar dinamice 2.1.8. Dezvoltarea modelelor de producie


MMI - Cursul 1 21

Aceast seciune conine un numr de modele de programare liniar reprezentative pentru aceast clas de probleme i care constituie o surs de prototipuri ce pot fi imediat reconfigurate pentru a surprinde situaii tehnico-economice reale. Modelele se pot combina sau dezvolta n sensul modelrii practice complexe.


MMI - Cursul 1 22

2.1.1. Modele de alocare

Alocarea resurselor este o problem fundamental a economiei. Alocarea resurselor este deosebit de important, mai ales n contextul existenei din ce n ce mai precare a acestora i a creterii din ce n ce mai pronunate a numrului celor care solicit aceste resurse. Presupunem c avem de executat un numr finit de n activiti (sau produse) care necesit utilizarea unui numr finit m de resurse cunoscute. Activitile se afl ntr-o "competiie" n ceea ce privete accesul la resurse. Se cunosc:

aij numrul de uniti din resursa i cerute pentru produ-


MMI - Cursul 1 23

cerea unei uniti din produsul j; bi cantitatea disponibil din resursa i; cj profitul asociat unei uniti din produsul j.

Se noteaz cu xj numrul de uniti de executat din activitatea (produsul) j. Modelul matematic de alocare a resurselor avnd ca obiectiv maximizarea profitului are forma:

==

=

=

njx

mibxa

xc

j

i

n

jjij

n

jjj

,..., ,

,..., ,

max 1

10

11

(8)


MMI - Cursul 1 24

Modelul dual al modelului (8) se scrie:

==

=

=

miu

njcua

ub

i

j

m

iiij

m

iii

,..., ,

,..., ,

min 1

10

11

(9)

unde ui reprezint numrul de uniti alocate din resursa i pentru fabricarea celor n produse. Se observ c problema dual const n a minimiza cantitatea total a resurselor cu satisfacerea restriciei de ncadrare n limitele de profit impuse.


MMI - Cursul 1 25

2.1.2. Modele de asamblare

Acest tip de modele este ntlnit atunci cnd se pune problema maximizrii profitului n procesul de asamblare a mai multor subansamble (repere, subproduse etc.) n produse finale destinate vnzrii. Se presupune c subansamblele se pot achiziiona la un pre cunoscut. Decidentul urmrete maximizarea valorii produselor finale asamblate, din care se scade costul subansamblelor, cu satisfacerea restriciilor de achiziionare-livrare, precum i de utilizare a capacitilor (resurselor) de asamblare.


MMI - Cursul 1 26

Schema general a unui proces de asamblare este pre-zentat n fig.2, care conine datele modelului.

Fig.2


MMI - Cursul 1 27

Semnificaia elementelor modelului: qk cantitatea achiziionat din subansamblul final k; cj preul unitar de vnzare al produsului final j; dk costul unitar de asamblare pentru subansamblul k; akj cantitatea din subansamblul k utilizat n asamblarea

unei uniti din produsul final j; eij cantitatea din resursa disponibil i utilizat n

asamblarea unei uniti din produsul final j; fik cantitatea din resursa disponibil i utilizat n proce-

sarea unei uniti din subansamblul k; hk stocul disponibil corespunztor subansamblului k; gj numrul de produse finale j care trebuie vndute; bi cantitatea din resursa disponibil i n procesul de

procesare a subansamblelor i de asamblare;


MMI - Cursul 1 28

wk numrul de uniti din subansamblul k coninut n cantitatea qk. Variabilele modelului sunt:

Jjx j , - produsele finale; Kkqk , - subansamblele.

Modelul matematic asociat procesului de asamblare are forma urmtoare:


MMI - Cursul 1 29

+

KkqJjgx

Iibqfxe

Kkhqwxa

qdxc

k

jj

Jjik

Kkikjij

Jjkkkjkj

Jj Kkkkjj

, ,

,

,

max

0

(10)

(11)

(12)

(13) (14)

Funcia obiectiv (10) exprim profitul, ce trebuie maxi-mizat, ca diferen ntre vnzrile produselor finale i costurile cu achiziia subansamblelor.


MMI - Cursul 1 30

Restriciile (11) reprezint balana achiziionare-livrare n care intervin stocurile hk de care dispune firma. Restriciile (12) reprezint limitarea impus de capaci-tile de producie de care dispune firma (timp, suprafee de producie etc.) n privina asamblrii subansamblelor i a procesrii acestora. Restricia (13) impune o limit referitor la numrul minim de produse finale de asamblat. Modelul matematic dual modelului (10)-(14) se poate scrie imediat. De exemplu, restricia dual asociat variabilelor qk este

+

Iikiikkk Kkdzfuw , (15)

unde:


MMI - Cursul 1 31

ui variabilele duale asciate subansamblului k, adic valoarea intern (a firmei) ctigat la achiziionarea unei uniti suplimentare din subansamblul k; zi variabilele duale asociate resursei (capacitii) i, adic valoarea obinut la utilizarea unei uniti suplimen-tare din resursa i. Restricia (15) se poate rescrie sub forma:

+Ii

kkkiik uwdzf

sau nc:

kk

Iikiik

uw

dzf

+ (16)


MMI - Cursul 1 32

Inegalitatea (16) arat c valoarea intern (a firmei) a unei uniti din subansamblul k este cel mult egal cu costul de achiziie a subansamblului plus costul resursei (capacit-ii) utilizate n procesarea acestuia. Observaie: Modelul matematic (10)-(14) se poate dez-volta n sensul de a include preurile resurselor utilizate, restricii privind disponibilitatea acestora, restricii de sto-care a produselor finale sau a subansamblelor, de transport etc.


MMI - Cursul 1 33

2.1.3. Modele de dezasamblare

Problema const n maximizarea profitului n procesul de dezasamblare a unui produs n subansamble (repere, subproduse etc.) destinate vnzrii. Se presupune c produsele se pot achiziiona la un pre cunoscut, sunt suficient de complexe i se pot dezasambla n subansamble bine individualizate. Decidentul urmrete maximizarea valorii subansamblelor vndute, din care se scade costul produselor achiziionate, cu satisfacerea restriciilor de achiziionare-livrare i de utilizare a capacitilor (resurselor) de asamblare. Schema general a unui proces de dezasamblare este


MMI - Cursul 1 34

artat n fig.3, care conine i datele modelului.

Fig.3

Semnificaia elementelor modelului: qk cantitatea vndut din subansamblul k;


MMI - Cursul 1 35

cj costul de achiziie a unei uniti din produsul j de dezasamblat;

dk preul de vnzare a unei uniti din subansamblul k; akj cantitatea din subansamblul k rezultat din dezasam-

blarea unei uniti din produsul j; eij cantitatea din resursa (capacitatea de producie)

disponibil i utilizat n dezasamblarea unei uniti din produsul j;

fik cantitatea din resursa (capacitatea de producie) disponibil i utilizat n procesarea unei uniti din suban-samblul k;

hk cantitatea maxim ce poate fi vndut din subansam-blul k;


MMI - Cursul 1 36

mk cantitatea minim ce poate fi vndut din suban-samblul k;

gj numrul maxim de uniti achiziionate din produsul j de dezasamblat;

bi cantitatea maxim din resursa disponibil i n pro-cesul de dezasamblare; Variabilele modelului sunt:

Jjx j , - produsele achiziionate; Kkqk , - subansamblele.

Modelul matematic asociat unui proces de dezasam-blare este urmtorul:


MMI - Cursul 1 37

++

+

KkhqmJjgx

Iibqfxe

Kkqxa

qdxc

kkk

jj

Jjik

Kkikjij

Jjkjkj

Jj Kkkkjj

, ,

,

,

max

0

(17)

(18)

(19)

(20) (21)

Funcia obiectiv (17) vizeaz maximizarea profitului obinut prin scderea costurilor produselor achiziionate din vnzrile subansamblelor.


MMI - Cursul 1 38

Restriciile (18) reprezint balana achiziionare-livrare n sensul c mrimea cantitii vndute din subansamblul k nu poate fi mai mare dect ceea ce rezult din dezasamblarea produselor achiziionate. Restriciile (19) exprim limitarea impus de capacitile de producie (resursele fizice) implicate n procesul de dezasamblare de care dispune firma. Restriciile (20) i (21) conin marginile simple asupra produselor de dezasamblat i, respectiv, a subansamblelor rezultate.

Observaii: 1) n modelul (17)-(21) se pot include o serie de alte

restricii referitoare la alte cerine ale decidentului n


MMI - Cursul 1 39

procesul de achiziie a produselor de dezasamblat sau a subansamblelor rezultate.

2) La construcia acestui model trebuie stabilit n prealabil nivelul pn la care se execut dezasamblarea, adeseori dictat de pia, de nevoile de subansamble reclamate de aceasta.

3) Modelele de dezasamblare funcioneaz n tandem cu cele de asamblare, aa cum se poate vedea n seciunea urmtoare.


MMI - Cursul 1 40

2.1.4. Modele de dezasamblare-asamblare

Un astfel de model este rezultatul unificrii celor dou tipuri de modele din seciunile anterioare. n acest caz, o firm achiziioneaz anumite suban-samble i produse pe care le dezasambleaz. Subansamblele rezultate sunt asamblate n produse finale. Subansamblele rmase i produsele finale rezultate sunt vndute. Se presupune c subansamblele i produsele de deza-samblat sunt achiziionate la un pre cunoscut. Decidentul este interesat n maximizarea valorii subansamblelor i a produselor finale asamblate din care se scad costurile subansamblelor i a produselor achiziionate,


MMI - Cursul 1 41

cu satisfacerea restriciilor de achiziie-livrare i a utilizrii capacitilor de producie (resurselor) de dezasamblare-asamblare de care dispune firma. Astfel de procese de dezasamblare-asamblare se ntlnesc foarte des n industria constructoare de maini, petrochimic, de prelucrare a lemnului, a crnii etc. Intrrile ntr-un astfel de proces sunt reprezentate de subansamblele i produsele achiziionate n vederea dezasamblrii. Ieirile sunt date de produsele asamblate i subansamblele rmase n respectivul proces. Procesul poate funciona n anumite ipoteze: exist o separabilitate bine definit a subansamblelor; este posibil o anumit interschimbabilitate a subansam-blelor n procesul de asamblare.


MMI - Cursul 1 42

Schema general a unui proces de dezasamblare-asamblare este ilustrat n fig.4.

Fig.4


MMI - Cursul 1 43

Semnificaia elementelor modelului: cj costul unitar de achiziie al produsului j de deza-

samblat; zm numrul de uniti achiziionate din subansamblul m; pm costul unitar de achiziie a subansamblului m; qk numrul de uniti vndute din produsul asamblat k; dk preul de vnzare al produsului asamblat k; tm numrul de uniti vndute din subansamblul m; sm preul de vnzare al subansamblului m; amj cantitatea din subansamblul m rezultat din deza-

samblarea unei uniti din produsul achiziionat j; bmk cantitatea din subansamblul m utilizat n asambla-

rea unei uniti din produsul final k;


MMI - Cursul 1 44

eij cantitatea din resursa (capacitatea) disponibil i utilizat n dezasamblarea unei uniti din produsul achizi-ionat j;

fik cantitatea din resursa (capacitatea de producie) disponibil i utilizat n asamblarea unei uniti din produsul final k;

him cantitatea din resursa disponibil i utilizat n procesarea unei uniti din subansamblul achiziionat m;

gim cantitatea din resursa disponibil i utilizat n proce-sarea unei uniti din subansamblul vndut m;

bi cantitatea din resursa disponibil i de care dispune firma n procesul de dezasamblare-asamblare a produselor i de procesare a subansamblelor.


MMI - Cursul 1 45

Variabilele modelului sunt: Jjx j , - numrul de produse achiziionate n vederea

dezasamblrii; Kkqk , - numrul de produse asamblate destinate

vnzrii; Mmzm , - numrul subansamblelor achiziionate; Mmtm , - numrul subansamblelor vndute.

Modelul matematic asociat unui proces de dezasam-blare-asamblare are forma:


MMI - Cursul 1 46

+++++

++

, , , , , , , , , ,

,

,

max

MmKkJjztqxMmzMmtKkqJjx

Iibzhtgqfxe

Mmztqbxa

zptsqdxc

mmkj

mm

mm

kk

jj

Jji

Mm Mmmimmimk

Kkikjij

Jjmm

Kkkmkjmj

Jj Kk Mm Mmmmmmkkjj

0

0

(22)

(23)

(24)

(25) (26) (27) (28) (29)

Funcia obiectiv (22) exprim profitul ca diferen ntre vnzrile produselor finale asamblate i ale subansamblelor


MMI - Cursul 1 47

rmase i respectiv costurile cu achiziia subansamblelor i ale produselor de dezasamblat. Restriciile (23) reprezint balana achiziionare-livrare a elementelor procesului. Ele indic modul n care sunt dezasamblate produsele achiziionate, precum i felul n care subansamblele sunt asamblate n produse finale. Restriciile (24) exprim limitarea impus de capaci-tile de producie de care dispune firma (ore, suprafee de depozitare etc.). Restriciile (25)-(28) indic limitele superioare n care se poate desfura procesul analizat. Condiiile de nenegativitate (29) ale variabilelor arat limitele inferioare de desfurare a procesului.


MMI - Cursul 1 48

Observaie: Modelul matematic (22)-(29) se poate dezvol-ta, de exemplu, n sensul de a introduce n expresia funciei obiectiv i o serie de costuri referitoare la manopera procesului de dezasamblare-asamblare, preurile utilizrii capacitilor de producie, preurile de stocare ale produselor sau ale subansamblelor etc. Astfel modelul reprezint o component a unui model general asociat unui proces de producie.


MMI - Cursul 1 49

2.1.5. Modele de producie cu selectarea optim a tehnologiilor

Aceste modele se refer la problema optimizrii proce-selor de producie care au la dispoziie mai multe tehnologii. Presupunem c o firm dorete s-i maximizeze profi-tul prin vnzarea unor produse pe care le poate fabrica utiliznd mai multe tehnologii. Fiecare tehnologie poate genera acele produse, utilizeaz aceleai intrri (materii prime, subansamble etc.) la un pre cunoscut i folosete resursele de producie ale firmei n cantiti bine definite. n fig. 5 este ilustrat schema unui proces de producie, care utilizeaz mai multe variante tehnologice n care sunt precizate i mrimile care definesc un astfel de proces. Cap.1. Modelare i optimizare matematic

MMI - Cursul 1 50

Fig.5

Semnificaia elementelor modelului:

ek costul unitar de achiziie a intrrii k; dj costul tehnologiei j; cp preul unitar de vnzare al produsului p;


MMI - Cursul 1 51

rkj cantitatea din intrarea k, achiziionat de firm, utilizat de varianta tehnologic j;

qpj cantitatea produs din produsul final p, destinat vnzrii, corespunztoare variantei tehnologice j;

smj cantitatea din capacitatea m utilizat de varianta tehnologic j;

bm disponibilul firmei din capacitatea m. Variabilele modelului sunt:

Kkzk , - cantitatea din intrarea k achiziionat de firm (materii prime, materiale, subansamble, produse etc.), (va-riabile de achiziionare);

Jjy j , - varianta tehnologic j, (variabile de producie); Ppxp , - cantitatea din cel de-al p-lea produs fabricat i


MMI - Cursul 1 52

vndut de firm, (variabile de vnzare). Modelul matematic al unui proces de producie care dispune de mai multe tehnologii are forma:

MmKkPpzyx

Mmbys

Kkzyr

Ppyqx

zeydxc

kjp

Jjmjmj

Jjkjkj

Jjjpjp

Kkkk

Pp Jjjjpp

, , , , ,

,

,

,

max

0

0

0

(30)

(31)

(32)

(33)

(34)


MMI - Cursul 1 53

Funcia obiectiv (30) exprim profitul obinut de firm ca diferen ntre ncasrile obinute prin vnzarea produ-selor finale i cheltuielile cu achiziiile i utilizarea varian-telor tehnologice. Restriciile (31) arat c, pentru fiecare tip de produs, cantitatea vndut este mai mic sau cel mult egal cu cantitatea generat de diferitele variante tehnologice. Restriciile (32) arat c, pentru fiecare intrare, suma cantitilor utilizate de variantele tehnologice este mai mic sau cel mult egal cu cantitatea achiziionat de firm. Restriciile (33) asigur c variantele tehnologice se ncadreaz n disponibilul fiecrei capaciti cu care este nzestrat firma.


MMI - Cursul 1 54

Modelul dual corespunztor modelului (30)-(34) are forma:

++

MmKkPpuwvKkew

JjduswrvqPpcv

ub

mkp

kk

Ppj

Kk Mmmmjkkjppj

pp

Mmmm

, , , , , ,

, ,

min

0

(35)

(36)

(37)

(38)

(39)

unde vp, wk, um sunt variabilele duale. Funcia obiectiv (35) reprezint valoarea resurselor (capacitile de producie) utilizate de firm, funcie care care trebuie minimizat.


MMI - Cursul 1 55

Restriciile (36) arat c valoarea (intern a firmei) a fiecrui produs final este cel puin egal cu preul su de vnzare; reflect implicaiile variabilelor de vnzare. Restriciile (37) arat c valoarea total a rezultatelor procesului de producie este mai mic sau egal cu valoarea intrrilor utilizate n procesul de producie; . Restriciile (38) arat c valoarea (intern a firmei) a fiecrei intrri (achiziie) nu este mai mare dect preul ei de achiziie; reflect implicaiile variabilelor de achiziie.


MMI - Cursul 1 56

2.1.6. Modele de sisteme cu stocuri

Aceast seciune se refer la modele matematice asociate unui proces care conine stocuri. De altfel, majori-tatea proceselor de producie sunt organizate pe stocuri. Programarea liniar este un instrument foarte potrivit pentru reprezentarea evoluiei stocurilor ntr-un proces de producie. Observaie: De obicei, modelele cu stocuri nu sunt utilizate independent, ci mai degrab constituie un submodel n cadrul unui model general al unui proces de producie. Presupunem c un proces se desfoar pe un orizont de timp de T perioade, n care se urmresc un numr de n pro-


MMI - Cursul 1 57

duse destinate vnzrii. Aceste produse se pot depozita i costurile de depozitare sunt cunoscute pe fiecare perioad de timp. S se determine o politic de vnzare i depozitare care s maximizeze valoarea vnzrilor produselor respective. Semnificaia elementelor modelului:

cjt preul de vnzare al produsului njj ,...,, 1= , n perioada 1] ,[ +tt ;

djt costul de depozitare a produsului njj ,...,, 1= , n perioada 1] ,[ +tt ;

sj cantitatea disponibil n stoc din produsul j de la nceputul orizontului de timp.

mj capacitatea de stocare de care dispune firma pentru


MMI - Cursul 1 58

produsul j; ljt marginea inferioar a cantitii din produsul j de

vndut la momentul t; ujt marginea superioar a cantitii din produsul j de

vndut la momentul t. Variabilele modelului sunt:

xjt - cantitatea din produsul njj ,..., , 1= de vndut la momentul Ttt ,..., , 1= ;

hjt - cantitatea (stocul) din produsul njj ,...,, 1= , depo-zitat n perioada 1],[ +tt . Modelul matematic al problemei formulate mai sus are forma urmtoare:


MMI - Cursul 1 59

====

===

===+

=+

=

= ==

11010

11

101

1

1

1

1

11

1

1 11

TtnjhTtnjx

Ttnjuxlnjmh

njhxTtnjhhx

njshx

hdxc

jt

jt

jtjtjt

jj

jTjT

jtjtjt

jjj

T

t

T

t

n

jjtjt

n

jjtjt

,..., , 1,..., , ,..., , 1,..., ,

,..., , 1,..., , ,..., ,

,..., , ,..., , 1,..., ,

,..., ,

max 1

(40)

(41)

(42) (43)

(44) (45) (46) (47)

Funcia obiectiv (40) este profitul realizat de firm de-a lungul orizontului de T perioade de timp, dat de diferena dintre vnzrile produselor i costurile de depozitare, n care Cap.1. Modelare i optimizare matematic

MMI - Cursul 1 60

s-a presupus c n ultima perioad de timp toate produsele au fost vndute. Restriciile (41) impun ca suma dintre cantitatea vn-dut n prima perioad i stocul din acea perioad s fie cel mult egal cu cu stocul iniial disponibil. Restriciile (42) de tip balan sau de evoluie a stocu-rilor, arat c pentru fiecare produs, cantitatea vndut n fiecare perioad de timp plus cantitatea depozitat n respectiva perioad este cel mult egal cu disponibilul n stoc de la perioada de timp anterioar. Restriciile (43) arat c, pentru fiecare produs, cantita-tea ce se vinde n ultima perioad de timp este cel mult egal cu cantitatea din stoc a produsului respectiv de la perioada anterioar.


MMI - Cursul 1 61

Restriciile (44) arat, pentru fiecare produs, ncadrarea n capacitatea de stocare de care dispune firma. Restriciile (45) exprim ncadrarea n anumite limite a cantitii vndute din fiecare produs, la fiecare perioad de timp. Observaie: Datorit restriciilor (45), modelul matematic nu trebuie s conin limite asupra stocurilor produselor depozitate.


MMI - Cursul 1 62

2.1.7. Modele de producie liniar dinamice

Se consider un proces de producie cu caracter discret, caracteristic industriilor de prelucrare i asamblare, pentru care se dorete s se construiasc un sistem de conducere care s influeneze comportarea acestuia, n sensul de a asigura bunuri i servicii conform anumitor specificaii, n cantitile i la termenele cerute, la un cost de producie minim. Procesul de producie are intrri i ieiri. Intrrile (materii prime, materiale, subansamble etc.) sunt transfor-mate prin operaii tehnologice, specifice pentru fiecare reper, diferite ca secven i numr. Ieirile din proces sunt


MMI - Cursul 1 63

produsele finite. n cadrul procesului de fabricaie a produselor finite se evideniaz stocurile de repere n diferite faze de execuie. Elementele care determin evoluia sistemului de pro-ducie sunt stocurile de materii prime, materiale, repere, subansamble, ansamble i produse finite, care vor fi consi-derate ca variabile de stare. Cantitile de materii prime de aprovizionare i de produse finite de livrare reprezint variabilele exogene. Relaiile fundamentale ntre aceste variabile, care reprezint trecerea reperelor de la o operaie la alta, pot fi reprezentate printr-un model liniar dinamic. Evoluia stocurilor de repere, subansamble, ansamble,


MMI - Cursul 1 64

produse finite sau materii prime, materiale etc. se poate exprima sub forma unei ecuaii de dinamic, care este o ecuaie de balan, aplicabil i n alte modele ale unor pro-cese fizice, energetice, macro-economice. Forma general a ecuaiei de dinamic este:

===

++=+ lacn

mmim

n

kkik

n

jjijii tvdtphtubtxtx

111

1 )()()()()(

(48) unde:

xi(t) stocul de repere, subansamble, ansamble, produse finite sau materii prime, materiale etc. de la momentul t;

uj(t) cantitatea de repere, subansamble etc. lansate n fabricaie la momentul t;


MMI - Cursul 1 65

pk(t) cantitile de aprovizionare de la momentul t; vm(t) cantitile de livrare a reperelor, subansamblelor

sau produselor finite de la acelai moment de timp t; bij consum specific de material, ce reprezint influena

lui uj(t) asupra lui xi(t), cu urmtoarele interpretri: 0< este consumul specific din stocul x

ijbi(t) la o comand unitar

uj(t) numai dac operaia uj(t) este executat din stocul xi(t) i 0> este creterea nivelului stocului xijb i(t) la o comand unitar uj(t) dac operaia uj(t) este cumulat n xi(t);

hik element ce ia valoarea 0 sau +1 cu interpretarea: 0=ikh dac stocul de aprovizionare pk(t) nu particip n

stocul xi(t) i 1=ikh n caz contrar; dim element ce ia valoarea 0 sau -1 cu interpretarea:


MMI - Cursul 1 66

0=imd dac din stocul xi(t) nu se livreaz reperul sau produsul vm(t) i 1=imd n caz contrar;

nc numrul de operaii tehnologice sau de comenzi de fabricaie ale procesului de producie analizat;

na numrul de stocuri cu materialele de aprovizionare; nl numrul de stocuri cu produsele de livrare ale

procesului considerat. Observaie: Relaia (48) exprim faptul c stocul de repere de la momentul 1+t este egal cu stocul de la momentul t plus cantitatea de repere care se proceseaz n intervalul

] ,[ 1+tt , plus cantitatea de materii prime, materiale etc. ce particip la desfurarea procesului de producie n acest interval de timp i influeneaz acest stoc, plus cantitatea de


MMI - Cursul 1 67

repere care se livreaz din stoc n acelai interval de timp. Problema propus se poate interpreta ca una de alocare a materiilor prime, materialelor, subansamblelor etc. precum i a capacitilor de producie. Ca urmare, modelul matema-tic liniar dinamic al unui proces de producie discret cu stocuri reprezint un model liniar dinamic de alocare. Modelul matematic are forma urmtoare:


MMI - Cursul 1 68

====

====

==++

====

+++=+

++

=

==

===

=

= =

= ==

110110

10

1

11

0

111

1

1

11

0

111

1

1 1

1

1 11

TtnktpTtnjtu

Ttnitx

Ttnitgtuf

Ttni

tvdtuetx

nixxTtni

tvdtphtubtxtx

tpctuctxc

ak

cj

i

i

n

jjij

n

mmim

n

jjiji

ii

n

mmim

n

kkik

n

jjijii

T

t

T

t

n

j

T

t

n

kkakjcj

n

iisi

c

lc

lac

c a

,..., , 1,..., ,)( ,..., , 1,..., ,)( ,..., , 1,..., ,)(

,..., , 1,..., ),()(

,..., , 1,...,

,)()()(

,..., ,(0) ,..., , 1,...,

,)()()()()(

)()()(min 1

(49)

(50)

(51) (52)

(53) (54) (55) (56)


MMI - Cursul 1 69

unde: n numrul de stocuri de repere, subansamble etc; csi costul unitar al subansamblelor, ansamblelor sau a

produselor finite de livrat definite de stocul xi(t); ccj costul unitar al manoperei asociat operaiei tehnolo-

gice uj(t); cak costul unitar al materiilor prime, materialelor sau al

subansamblelor etc. cu care se aprovizioneaz procesul de producie;

eij un consum specific al operaiei tehnologice uj(t) din stocul xi(t); 0< ; eije ij sunt de fapt elementele negative bij;

fij timpul de execuie (consumul specific de capacitate) necesar operaiei tehnologice uj(t), din capacitatea de


MMI - Cursul 1 70

producie gi(t), pe care acea operaie tehnologic se execut la momentul t; Funcia obiectiv (49) a modelului presupune minimiza-rea stocurilor cu repere, subansamble, ansamble, produse finite de livrat, a stocurilor cu comenzile lansate n fabricaie, precum i a stocurilor cu materiile prime i materialele de aprovizionat; altfel spus, se caut minimizarea produciei neterminate; Restriciile de succesiune i de livrare (52) exprim faptul c anumite operaii tehnologice nu se pot executa naintea altora, inclusiv livrarea nu se poate efectua nainte de executarea stocului cu produsele de livrat. Restriciile de capacitate (54) sunt scrise pe un orizont de timp dat.


MMI - Cursul 1 71

Observaii: 1) Soluia optim a modelului (49)-(56) determin ce

repere, n ce cantitate, pe ce maini i la ce moment de timp trebuie executate pentru satisfacerea livrrilor impuse i pentru minimizarea stocurilor cu producia neterminat.

2) Planul de producie obinut prin rezolvarea modelului indic minimul necesar de stocuri de producie i stocuri de aprovizionare.


MMI - Cursul 1 72

2.1.8. Dezvoltarea modelelor de producie

a) Pentru nceput vom considera un model standard de

selecie a tehnologiilor:

KkJjx

Jjhx

Mmbxa

xc

jk

jKk

jk

Jjm

Kkjkmjk

Jj Kkjkjk

, ,

,

,

min

0

(57)

unde: J mulimea produselor;


MMI - Cursul 1 73

M mulimea resurselor; K mulimea trhnologiilor; cjk costul de producie a unei unuiti din produsul j

fabricat cu tehnologia k; amjk cantitatea din resursa m utilizat pentru fabricarea

unei uniti din produsul j cu tehnologia k; bm disponibilul din resursa m; hj cererea din produsul j.

Variabilele (necunoscutele) modelului sunt: xjk cantitatea din produsul j fabricat cu tehnologia k.

b) Urmtorul pas pentru dezvoltarea modelului const n introducerea dimensiunii temporale i a stocurilor. Modelul matematic se exprim n acest caz sub forma:


MMI - Cursul 1 74

==

=+=

+

= =

TtJjsTtKkJjx

TtJjhssx

TtMmbxa

sdxc

jt

jkt

jtjtjtKk

jkt

Jjmt

Kkjktmjkt

T

t Jj

T

t Jjjtjt

Kkjktjkt

1,..., , , 1,..., , , ,

1,..., , ,

1,..., , ,

min

00

1

1 1

(58)

unde: T orizontul de timp; cjkt costul de producie a unei uniti din produsul j

fabricat cu tehnologia k la momentul de timp t;


MMI - Cursul 1 75

djt costul de depozitare a stocului din produsul j la momentul de timp t;

amjkt cantitatea din resursa m utilizat pentru fabricarea unei uniti din produsul j cu tehnologia k la momentul de timp t;

bmt disponibilul din resursa m la momentul de timp t; hjt cererea din produsul j la momentul t.

Variabilele (necunoscutele) modelului sunt: xjkt cantitatea din produsul j fabricat cu tehnologia k la

momentul de timp t; sjt stocul produsului j la momentul de timp t.

Semnificaia anumitor notaii: Jjsj0 stocul iniial, .


MMI - Cursul 1 76

n teoria produciei se face o distincie foarte clar ntre capitalul, fora de munc i materialele care sunt utilizate pentru a produce bunuri i servicii. Materialele vor fi consumate, utiliznd resursele de capital i fora de munc.

c) n continuare vom dezvolta modelul prin separarea resurselor n materiale (materii prime, alte materiale nece-sare procesului de producie) i resurse propriu-zise (capital i fora de munc). Introducnd stocuri, pentru acestea vom obine urmtoarea variant de model liniar dinamic de producie:


MMI - Cursul 1 77

==

==

==+==+

=++

+++

=

= = =

TtRryTtMmv

TtJjsTtKkJjx

TtRrpggyy

TtRryxa

TtJjhssx

TtMmbvvxa

yw

vesdxc

rt

mt

jt

jkt

rtrtrtrtrt

Jjrt

Kkjktrjkt

jtjtjtKk

jkt

Jjmtmtmt

Kkjktmjkt

T

t Rrrtrt

T

t Jj

T

t Mmmtmt

T

t Jjjtjt

Kkjktjkt

1,..., , , 1,..., , ,

1,..., , , 1,..., , , ,

1,..., , ,

1,..., , ,

1,..., , ,

1,..., , ,

min

0000

0

11

1

1

1

1 11

(59)


MMI - Cursul 1 78

unde: M mulimea materialelor; R mulimea resurselor; emt costul unitar al materialului m la momentul de timp t

(inclusiv costul de stocare); wrt costul unitar al resursei r la momentul de timp t; amjkt cantitatea din materialul m utilizat pentru produ-

cerea unei uniti din produsul j cu tehnologia k la momentul de timp t;

arjkt cantitatea din resursa r utilizat pentru producerea unei uniti din produsul j cu tehnologia k la momentul de timp t;

grt cantitatea din resursa r achiziionat la momentul de timp t;


MMI - Cursul 1 79

tr ciclul de via al resursei r (dup tr perioade de timp resursa r se retrage din producie);

prt cantitatea din capacitatea r retras din producie la momentul de timp t. Variabilele (necunoscutele) modelului sunt:

xjkt cantitatea din produsul j fabricat cu tehnologia k la momentul de timp t;

sjt stocul produsului j la momentul de timp t. vmt stocul materialului m la momentul de timp t; yrt stocul resursei r la momentul de timp t.

Semnificaia anumitor notaii: sj0 stocul iniial corespunztor produsului j, Jj ; vm0 stocul iniial corespunztor materialului m, Mm ; yr0 stocul iniial corespunztor resursei r, Rr .


MMI - Cursul 1 80

Funcia obiectiv a modelului presupune minimizarea stocurilor cu producia neterminat, precum i a stocurilor de materiale i resurse. Introducerea componentei temporale determin apariia stocurilor care la rndul lor impun ecuaiile de balan, n fapt ecuaii de dinamic, ce exprim evoluia temporal a stocurilor. n model apar trei astfel de ecuaii de dinamic: a stocurilor de materiale, de produse i de resurse. Dac la rndul lor resursele sunt mprite pe clase din ce n ce mai detaliate, atunci pentru fiecare dintre aceste clase, n model va aprea o ecuaie de balan (dinamic) care va exprima evoluia temporal a resursei respective. Modelul mai conine restriciile de ncadrare n limitele date de stocurile resurselor disponibile la un moment dat.


MMI - Cursul 1 81

Resursele existente au o evoluie temporal n strns legtur cu cele achiziionate.

d) n continuare, pentru dezvoltarea modelului vom intro-duce componenta spaial a resurselor. Vom considera c resursele sunt disponibile la anumite centre de aprovizionare de unde sunt transportate la centrele de fabricaie. Pe de alt parte, produsele rezultate n centrele de fabricaie sunt, la rndul lor, transportate la centrele de consum. Aceasta implic replicarea modelului (59) pentru fiecare centru de fabricaie i introducerea ecuaiilor tipice ale unui model de transport pentru materiale i produse. Astfel este necesar a se introduce restriciile de limitare a cantitilor achiziionate de la centrele de aprovizionare,


MMI - Cursul 1 82

precum i cele de limitare a produselor absorbite de centrele de consum. Mai mult, ecuaiile modelului (59) trebuie modificate pentru a ine seama de cantitile de materiale sau de cele de produse transportate ntre centrele de aprovizionare, de producie i de consum care definesc situaia modelat. Modelul matematic are urmtoarea form:


MMI - Cursul 1 83

===+=

==+=+

++

+++ ++

= =

= =

= =

1,..., , , , 1,..., , , ,

1,..., , , ,

1,..., , , ,

1,..., , , ,

min

TtMmAahzTtFfRrpgyy

TtFfRryxa

TtFfJjqssx

TtFfMmvvxaz

zuqu

ywsd

vexc

mFf

amtafmt

rtffrtrtffrt

Jjrtf

Kkjktfrjktf

Dbfbjtjtffjt

Kkjktf

Aamtffmt

Jj Kkjktfmjktfafmt

T

t Ff

T

t Ff Mm Aaafmtafmt

Jj Dbfbjtfbjt

T

t Jj

T

t Rr Ffrtfrtf

Ffjtfjtf

T

t Jj

T

t Mm Ffmtfmtf

Kk Ffjktfjktf

j

m

mj

111

1

1

1 1

21

1 1

1 1

0

0

0


MMI - Cursul 1 84

==

==

==

=

TtJjDbFfqTtMmFfAaz

TtFfRryTtFfMmv

TtFfJjsTtFfKkJjx

TtJjDbhq

jfbjt

mafmt

rtf

mtf

jtf

jktf

jbjtFf

fbjt

1,..., , , , , 1,..., , , , ,

1,..., , , 0, 1,..., , , ,

1,..., , , , 1,..., , , , ,

1,..., , , ,

00

000

2

(60)

unde: F mulimea centrelor de producie; Am mulimea centrelor de aprovizionare corespunzto-

are materialului m; Dj mulimea centrelor de consum corespunztoare pro-


MMI - Cursul 1 85

dusului j; cjktf costul unitar al produsului j fabricat cu tehnologia k,

la momentul de timp t, la centrul de producie f; djtf costul de depozitare a stocului produsului j la

momentul de timp t, la centrul de producie f; emtf costul unitar al materialului m la momentul de timp

t, la centrul de producie f; wrtf costul unitar al resursei r la momentul de timp t, la

centrul de producie f; 1fbjtu costul unitar al produsului j transportat de la centrul

de producie f la centrul de consum b, la momentul t; 2afmtu costul unitar al materialului m transportat de la

centrul de aprovizionare a la centrul de producie f, la mo-


MMI - Cursul 1 86

mentul de timp t; amjktf cantitatea din materialul m utilizat pentru

producerea unei uniti din produsul j, cu tehnologia k, la momentul de timp t, la centrul de producie f;

arjktf cantitatea din resursa r utilizat pentru producerea unei uniti din produsul j, cu tehnologia k, la momentul de timp t, la centrul de producie f;

grtf cantitatea din resursa r achiziionat la momentul de timp t, la centrul de producie f;

prtf cantitatea din resursa r retras din producie la momentul de timp t, la centrul de producie f;

1amth disponibilul de material m la centrul de aprovizio-

nare a, la momentul de timp t;


MMI - Cursul 1 87

2bjth cerina produsului j la centrul de consum b, la

momentul de timp t. Variabilele (necunoscutele) modelului sunt:

xjktf cantitatea din produsul j fabricat cu tehnologia k, la momentul de timp t, la centrul de producie f;

vmtf stocul materialului m la momentul de timp t, la centrul de producie f;

sjtf stocul produsului j la momentul de timp t, la centrul de producie f;

yrtf stocul resursei r la momentul de timp t, la centrul de producie f;

qfbjt cantitatea din produsul j transportat de la centrul de producie f la centrul de consum b, la momentul t;


MMI - Cursul 1 88

afmtz cantitatea din materialul m transportat de la centrul de aprovizionare f la centrul de producie f, la momentul t; Semnificaia anumitor notaii:

sj0t stocul iniial corespunztor produsului j de la centrul de producie f, Jj , Ff ;

vm0f stocul iniial corespunztor materialului m de la centrul de producie f, Mm , Ff ;

yr0f stocul iniial corespunztor resursei r de la centrul de producie f, Rr , Ff . Concluzie: Lucrnd la nivel algebric se pot genera n mod corect modele de programare liniar de dimensiuni mari prin extensia unor modele de dimensiuni mai mici pentru care se poate menine un control al semnificaiei fizice a variabi-


MMI - Cursul 1 89

lelor. Regulile dup care se dezvolt modelul sunt relativ simple i explicite.


1. Introducere 2. Programare liniar 2.1. Modele de programare liniar (I) 2.1.1. Modele de alocare 2.1.2. Modele de asamblare 2.1.3. Modele de dezasamblare 2.1.4. Modele de dezasamblare-asamblare 2.1.5. Modele de producie cu selectarea optim a tehnologiilor 2.1.6. Modele de sisteme cu stocuri 2.1.7. Modele de producie liniar dinamice 2.1.8. Dezvoltarea modelelor de producie

modelare ma\atematica in inginerie curs 1

Documents