12-13_me_curs pl extended gp si jocuri 18042013

M o d e l a r e a E c o n o m i c ă a n . u n i v . 2 0 1 2 - 2 0 1 3

1

Modulul II.

Modelele de alocare optimală a unor resurse limitate Cuprins:

Aplicatii ale PL in teoria jocurilor strategice

I. STUDIUL SOLUTIEI OPTIME A PROBLEMEI DE PROGRAMARE LINIARA ......... 4

1. Modelarea structurii de fabricaţie a unei organizaţii (cazul în care variabilele sunt

continue) ..................................................................................................................................... 5 2. Analiza de senzitivitate şi reoptimizarea ............................................................................. 6 2. Parametrizarea ...................................................................................................................... 8

Studiu de caz din culegere .............................................................................................. 10

3. Modelarea structurii de producţie şi a posibilităţilor de dezvoltare ale unei organizaţii

(cazul în care variabilele sunt NUMERE ÎNTREGI) ............................................................. 20

4. Modele liniare stochastice cu vectorii b şi c aleatori ........................................................ 21 4.A. Programarea stochastică cu vectorul c aleatoriu (cj sunt variabile aleatoare) ...... 21 4.B.Programarea stochastică cu vectorul b aleator .......................................................... 22

II. FUZZYFICAREA MODELELOR ....................................................................................... 22

II.1. Metode de trecere de la variabila lingvistică (descriptivă) la cea cantitativă

(algoritmizabilă) .................................................................................................................. 22 II. 2. Necesitatea fuzzyficării modelelor deterministe .......................................................... 23 II. 3. Variabilă fuzzy, relaţie fuzzy ........................................................................................ 23

II.4. Programarea matematică fuzzy (programarea liniara fuzzy PLF) ................................ 25 III. MULTICRITERIALITATEA ÎN ACTIVITATEA DE MANAGEMENT .................... 28

III. 2. Programarea liniară multidimensională (multiobiectiv) .......................................... 29 Metoda maximizării unei funcţii sinteză de utilitate ........................................................ 29

III.3. PROGRAMAREA SCOP ............................................................................................. 30

Modelul de programare liniară cu mai multe funcţii obiectiv ........................................ 31


2

Aplicatii ale modelului de programare liniara. ELEMENTE DE

TEORIA JOCURILOR

Jocurile strategice - modele simplificate de astfel de situaţii conflictuale şi de acţiuni între participanţi ce au

interese contrarii

- modeleazǎ situaţii în care doi sau mai mulţi parteneri folosesc, în mod deliberat şi

raţional, strategii inteligente pentru atingerea unor obiective contrare: maximizarea câştigului,

respectiv minimizarea pierderii.

Jocul = un proces competitiv care se desfǎşoarǎ între mai mulţi participanţi numiţi jucǎtori.

In teoria jocurilor, se postuleazǎ urmǎtoarele ipoteze:

- toţi participanţii au posibilitatea sǎ aplice strategii cu un caracter definit

- toţi participanţii cunosc posibilitǎţile strategice ale adversarilor

- rezultatul oricǎrei partide se manifestǎ printr-o pierdere sau un câştig

- cel puţin un partener are o comportare raţionalǎ (este inteligent şi prudent, adică

poate analiza coerent situaţia şi hotărâ asupra acţiunilor viitoare pentru a-şi atinge obiectivul).

Formularea matriceală a problemei

- fiecare linie/coloanǎ va reprezenta o strategie (fie Ai, i=1,…m, respectiv Bj, j=1,…n

aceste strategii),

- criteriul de decizie va fi dat de o regulǎ de alegere a strategiei.

Considerând un joc cu doi parteneri, forma sa poate apare ca o matrice dreptunghiularǎ (matrice

de “plăţi”) ijcC cu i=1,…,m şi j=1,…n,

cij exprimǎ câştigul jucǎtorului maximizant (obiectiv = maximizarea câştigului propriu –

jucǎtorul A), respectiv pierderea jucǎtorului minimizant (desemnat în continuare prin B) dacǎ sunt

alese strategiile Ai şi Bj cu condiţia ca jocul sǎ fie cu sumǎ nulǎ1.

În ipoteza unui comportament raţional2, jucătorul A va urmări să-şi maximizeze câştigul

aşteptat indiferent de alegerea făcută de concurent.

In cazul general, dacă:

cij: consecinţa alegerii strategiei Ai de către jucătorul A şi a strategiei Bj de către

jucătorul B;

x(i): probabilitatea ca jucătorul A să aleagă strategia Ai; i = 1, ..., m

y(j): probabilitatea ca jucătorul B să aleagă strategia Bj; j = 1, ..., n

v: valoarea jocului.

Jocurile cu sumă nulă sunt considerate jocuri cu informaţie completă: fiecare dintre

partenerii de joc îşi defineşte un set de strategii, cunoaşte strategiile adversarului şi matricea de

plăţi asociată.

1 pierderea jucătorului B (numit jucător minimizant) – cij, egalează câştigul celuilalt + cij.

2 In sistemul axiomatic a lui von Neumann – Morgenstern, se consideră, la nivel individual, că o alegere

între două variante a şi b este raţională atunci când se poate exprima o relaţie de preferinţă, de echivalenţă

sau de non-preferinţă între cele două variante şi în mod suplimentar, se respectă regula tranzitivităţii. La

nivel de grup, cerinţele de raţionalitate sunt mai complexe; J.Arrow, laureat al premiului Nobel pentru

economie în 1972, a definit cinci astfel de condiţii.


3

Scopul jocului formulat astfel este de a stabili ce strategie să aleagă fiecare partener la joc

pentru a-şi atinge obiectivul. Fiecare dintre cei doi jucători foloseşte criterii proprii de decizie:

- jucătorul maximizant va alege strategia care să îi aducă cea mai convenabilă valoare în

condiţiile celei mai agresive acţiuni a adversarului; acesta adoptă o strategie prudentă – cel mai

mare minim sau maxmin (în ipoteza că este raţional, inteligent şi este informat asupra jocului).

Valoarea câştigată de acesta este:

- Aijn,1jm,1i

Vcminmax

- jucătorul B îşi va selecta strategia după un criteriu de tip dual: minmax, iar valoarea câştigată

va fi:

- Bijm,1in,1j

Vcmaxmin.

Utilizarea celor două reguli de decizie va aduce fiecărui jucător cel mai bun posibil rezultat

(cel mai mare câştig pentru A, cea mai mică pierdere pentru B), iar punctul de echilibru al jocului

se numeşte valoarea jocului.

După gradul de informare şi de control asupra intenţiilor celuilalt partener, există două tipuri de

strategii:

- pure – în situaţia în care jucătorii aleg fiecare o singură strategie, dovedită optimă prin faptul

că VA=VB=V (în aceste condiţii, V este chiar valoarea jocului; dacă V>0 câştigă jucătorul

maximizant).

Strategiile pure nu presupun nici un element de hazard în stabilirea lor, fiind însă

limitate de alegerile făcute cu principiile maxmin şi minmax.

- mixte - reprezintă o combinaţie de strategii pure, fiecare având asociată o anumită

probabilitate de alegere atunci când jocul este reluat în mai multe partide. Strategiile

combinate implică rulări succesive ale jocului şi urmărirea modului de a juca al adversarului

(de comutare de la o strategie la alta, astfel ca, pe termen lung, să se atingă o pozitie

avantajoasă).

Strategia mixtă pentru jucătorul A este definită prin determinarea probabilităţilor [x1, x2, ...,

xm] prin rezolvarea problemei de programare liniară:

m,…1,=i 0; x

1 = x + ... + x +x

0 V - x c + ... +x c + x c

...

0 V - x c + ... +x c + x c

0 V - xc + ... +xc + x c

VMax

i

m2 1

mmn22n11n

mm2222112

m m12 21111


4

I. STUDIUL SOLUTIEI OPTIME A PROBLEMEI DE PROGRAMARE

LINIARA

Considerăm cazul a n activităţi competitive, pentru realizarea cărora se folosesc m resurse limitate,

fie x1, x2,...,xn, vectorul care descrie nivelul pe care le poate atinge fiecare din cele n activităţi /

variabilele de decizie (mărimile asupra cărora decidentul poate exercita un anumit control în

vederea realizării obiectivului propus). Vectorul format prin combinarea unor valori atribuite

variabilelor x1, x2,...,xn, reprezintă o soluţie/o alternativă sau o variantă decizională. Dacă

variabilele x1, x2,...,xn, reprezintă mărimi continue, există o infinitate de combinaţii posibile între

valorile variabilelor şi, prin urmare, numărul variantelor decizionale este infinit. In funcţie de

specificul procesului descris, variabilele x pot lua numai valori ne-negative, fie acestea continue

pe spaţiul R (mulţimea numerelor reale), sau în Z (mulţimea numerelor întregi) sau numai valorile

0 şi 1.

Forma generală a modelului de programare liniară este:

Opt f(X) = CX

sau

Funcţia obiectiv sau de eficienţă:

f(X) = j

n

j

j xc1

Supusă sistemului de restricţii: AX b sau AX ≥ b

Cu condiţia de ne-negativitate: X 0

In care:

nxxxX ...21 X = vector coloană cu n componente x1, x2,...,xn, care reprezintă

necunoscutele modelului (şi care constituie variabilele de decizie);

mnmm

n

n

aaa

aaa

aaa

A

...

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

...

...

21

22221

11211

A = matricea coeficienţilor tehnologici sau matricea normelor de consum cu elementele {aij}, i =

1,...,m, j = 1,...,n;

nb

b

b

b...

2

1

b = vector coloană cu componentele b1, b2, ..., bm denumiţi termenii liberi din partea

dreaptă a restricţiilor (sau RHS – Right Hand Side) ce desemnează disponibilul maxim dintr-o

anumită resursă sau nivelul minim care trebuie atins de anumite activităţi;

ncccC ...21 c = vector linie - coeficienţii funcţiei obiectiv (care descrie nivelul de

performanţă a unei soluţii în atingerea obiectivului fixat anterior de către decident) – de exemplu:

costuri unitare, preţuri unitare, profituri unitare sau alţi indicatori de performanţă care

caracterizează variabilele de decizie.

Formatul general al PPL (problema de maxim - problema primală)

Max nn xcxcxcXf ...)( 2211

Cu sistemul de restricţii:


5

mnmnmm

nn

nn

bxaxaxa

bxaxaxa

bxaxaxa

....

....

....

2211

22222121

11212111

Cu condiţiile:

0...,,, 21 nxxx

Transformarea din formă canonică în forma standard (PPL) – se introduc variabilele de

abatere/de compensare sau ecart: y1, y2, …, yi,…ym unde i=1,2,…, m – se transformă inegalităţile

în egalităţi:

Max mnn yyyxcxcxcXf 0....00...)( 212211

mmnmnmm

nn

nn

byxaxaxa

byxaxaxa

byxaxaxa

....

....

....

2211

222222121

111212111

Cu condiţiile de nenegativitate:

0,...,,...,,, 2121 mn yyyxxx

Categorii de soluţii:

- soluţie – vectorul X care satisface sistemul de restricţii:

- soluţie admisibilă – soluţia care satisface condiţiile de nenegativitate;

- soluţia optimă – soluţia admisibilă care realizează cea mai bună valoare a funcţiei obiectiv.

Intepretarea soluţiei (rezultată din aplicarea algoritmului simplex):

Analiza de senzitivitate – studiază stabilitatea componentelor soluţiei la variaţii de mică

amploare a datelor de intrare: matricea A, vectorul termenilor liberi b sau a coeficienţilor funcţiei

obiectiv - C.

1. Modelarea structurii de fabricaţie a unei organizaţii (cazul în care variabilele

sunt continue)

Structura de fabricaţie pentru o anumită perioadă poate fi reprezentată printr-un vector ale

cărui elemente sunt cantităţile de produse de diferite sortimente, care urmează să fie realizate

în perioada considerată de fiecare unitate de producţie (atelier, secţie, filială etc.)

Dacă funcţia obiectiv care maximizează profitul total este funcţie liniară şi restricţiile

referitoare la cerere şi resurse sunt liniare se obţine un model de programare liniară.

Datele de intrare necesare pentru construirea modelului de programare liniară pot fi:

nomenclatorul de produse, preţuri unitare, costuri unitare, profituri unitare, consumuri specifice,

timpi de fabricaţie, norme de muncă, disponibil de resurse, capacităţi de producţie, cerere

contractată sau estimată, standarde de calitate.

Variabilele de decizie sunt cantităţile de produse de diferite sortimente, care urmează să fie

realizate în perioada considerată de fiecare unitate de producţie;

Datele de ieşire obţinute prin rezolvarea modelului de programare liniară sunt următoarele:

structura sortimentală şi de produs, valorile indicatorilor de performanţă în cazul realizării

soluţiei furnizate de model, resursele utilizate şi resursele neutilizate, "locurile înguste" sau

resursele deficitare, preţurile umbră asociate resurselor, analiza senzitivităţii soluţiei la

modificarea preţurilor, costurilor, disponibilului de resurse, analiza parametrică a coeficienţilor

funcţiilor obiectiv sau a disponibilului de resurse.


6

Prin rezolvarea modelului de programare liniară (forma primală) se obţine soluţia optimă -

varianta decizională x*1, x*2,...,x*n care duce la cea mai bună valoare a criteriului de performanţă

specificat prin funcţia obiectiv;

● Preţurile umbră asociate restricţiilor liniare:

- - reprezintă valorile optime ale variabilelor duale;

- Preţul umbră este diferit de zero numai dacă restricţia asociată este verificată cu

egalitate, adică numai dacă resursa respectivă este folosită integral de către soluţia

optimă;

- Preţul umbră asociat unei resurse este valabil pentru un anumit interval de variaţie al

cantităţii disponibile de resursă;

- Preţul umbră arată cu cât s-ar modifica valoarea funcţiei obiectiv dacă s-ar putea mări

cu o unitate disponibilul din resursa respectivă;

- Preţurile umbră sunt folosite la analiza senzitivităţii soluţiei optime la variaţia

vectorului b al termenilor liberi ai restricţiilor liniare.

● Costurile reduse asociate restricţiilor de nenegativitate asupra variabilelor decizionale:

- Costul redus este diferit de zero numai dacă variabila asociată are valoarea zero în

soluţia optimă;

- Costul redus arată cu cât s-ar înrăutăţi valoarea funcţiei obiectiv dacă valoarea

variabilei asociate ar creşte de la 0 la 1;

- Costurile reduse sunt folosite pentru verificarea optimalităţii soluţiilor problemei de

programare liniară.

După obţinerea soluţiei optime, înainte de implementarea practică a acesteia, decidentul

poate efectua:

Analize de senzitivitate

Reoptimizări

Parametrizări

Analiza de senzitivitate studiază senzitivitatea unei soluţii optime la variaţia unui

singur coeficient al modelului de programare liniară, în ipoteza că ceilalţi coeficienţi ai modelului

nu se modifică.

Cele mai multe produse informatice furnizează informaţii pentru analiza de senzitivitate a

soluţiei optime primale la variaţia coeficienţilor funcţiei obiectiv şi pentru analiza de senzitivitate

a soluţiei optime duale la variaţia termenilor liberi ai restricţiilor liniare.

Analiza parametrică:

- Pentru un element al vectorului b al resurselor sau pentru unul dintre elementele

vectorului c al coeficienţilor funcţiei obiectiv

- Parametrizarea întregului vector b sau c.

2. Analiza de senzitivitate şi reoptimizarea

Se referă numai la soluţia optimă curentă (primală sau duală);

Studiază senzitivitatea unei soluţii optime la variaţia unui singur coeficient al

modelului de programare liniară, în ipoteza că ceilalţi coeficienţi ai modelului nu se modifică;

Cele mai multe produse informatice furnizează informaţii pentru analiza de

senzitivitate a soluţiei optime primale la variaţia coeficienţilor funcţiei obiectiv şi pentru analiza

de senzitivitate a soluţiei optime duale la variaţia termenilor liberi ai restricţiilor liniare.

Analiza senzitivităţii soluţiei optime la variaţia coeficienţilor funcţiei obiectiv Furnizează intervalul în care poate varia fiecare coeficient al funcţiei obiectiv, astfel

încât soluţia optimă primală să rămână neschimbată.


7

Intervalul asociat unui coeficient al funcţiei obiectiv pentru care soluţia problemei

rămâne optimă se numeşte interval de optimalitate.

Cunoscând soluţia optimă şi intervalul de variaţie al unui coeficient al funcţiei obiectiv,

în ipoteza că ceilalţi coeficienţi ai modelului nu se modifică, se poate determina variaţia

corespunzătoare a funcţiei obiectiv.

Analiza senzitivităţii soluţiei optime la variaţia termenilor liberi ai restricţiilor

liniare Furnizează intervalul în care poate varia fiecare termen liber, astfel încât soluţia optimă

duală (vectorul preţurilor umbră) să nu se modifice.

Intervalul asociat unui termen liber pentru care preţurile umbră rămân neschimbate se

numeşte interval de admisibilitate pentru soluţia primalei.

Cunoscând preţurile umbră optime şi intervalul de variaţie al unui termen liber, în

ipoteza că ceilalţi coeficienţi ai modelului nu se modifică, se poate determina variaţia

corespunzătoare a funcţiei obiectiv.

Reoptimizarea Constă în determinarea soluţiei optime în cazul modificării unor coeficienţi din matricea A

şi/sau vectorul b şi/sau vectorul c;

Reoptimizarea presupune parcurgerea a două etape:

Verificarea optimalităţii soluţiei curente în noile condiţii;

Determinarea noii soluţii în cazul în care soluţia curentă nu îndeplineşte condiţiile

de optimalitate. Observaţie: Cele mai multe produse informatice pentru rezolvarea problemelor de programare

liniară nu oferă opţiunea de reoptimizare. Această lipsă este compensată de viteza de calcul şi prin

interfaţa prietenoasă care permite utilizatorului modificarea rapidă a coeficienţilor şi rezolvarea

imediată a problemei.

Reoptimizarea în raport cu vectorul b Situaţia practică: după obţinerea soluţiei optime, modificarea disponibilului de resurse a

determinat transformarea vectorului b în vectorul b ;

Etapa I: Se determină dacă soluţia optimă verifică restricţiile ai căror termeni liberi s-au

modificat.

- În caz afirmativ, soluţia optimă rămâne aceeaşi;

- În caz negativ, se trece la Etapa II.

Etapa II: Se aplică următoarea procedură pentru determinarea noii soluţii:

1. Se identifică B-1

, inversa bazei corespunzătoare soluţiei optime pentru vectorul b. (In

tabelul simplex al ultimei iteraţii, în dreptul coloanelor care au făcut parte din baza

iniţială).

2. Se calculează noua soluţie de bază 'b1B'BX

3. Se verifica dacă 'BX 0. În caz afirmativ, '

BX este soluţie optimă a problemei

modificate.

4. Dacă există în vectorul 'BX componente negative, atunci se aplică algoritmul simplex

dual pentru determinarea soluţiei optime.

Reoptimizarea în raport cu vectorul c Situaţia practică: după obţinerea soluţiei optime, modificarea costurilor de producţie a

determinat transformarea vectorului c în vectorul c . Funcţia obiectiv constă în minimizarea

costurilor totale pentru realizarea vectorului de activităţi X.

Etapa I: În ultimul tabel simplex, se determină dacă soluţia optimă verifică condiţiile de

optimalitate: zj – cj ≤ 0, j.

- În caz afirmativ, soluţia optimă rămâne aceeaşi;

- În caz negativ, se trece la Etapa II.


8

Etapa II: Dacă există cel puţin o diferenţă zk – ck > 0, se utilizează algoritmul simplex

primal pentru determinarea noii soluţii optime.

2. Parametrizarea Permite analize de tipul „ce-ar fi dacă?” în cazul în care termenii liberi ai restricţiilor sau

coeficienţii funcţiei obiectiv sunt funcţii liniare de un parametru;

Parametrizarea presupune parcurgerea a două etape:

Rezolvarea problemei pentru o valoare fixată a parametrului;

Studiul senzitivităţii soluţiei la variaţia parametrului.

Parametrizarea vectorului b

Situaţia practică: variaţia disponibilului de resurse este exprimată printr-o funcţie liniară de un

parametru R care transformă vectorul b în vectorul b ( ).

Se pot realiza două tipuri de analiza parametrică:

1. Parametrizarea unui singur element al vectorului b: bi => bi ( ) = bi + şi

menţinerea la nivelul iniţial a celorlalte elemente ale vectorului b.

În acest caz, pentru termenul liber bi specificat:

Se determină toate intervalele de variaţie ale parametrului (- , + ) şi ale

termenului liber bi ( ) = bi + , astfel încât )('b1B)('BX 0;

Pentru fiecare interval de variaţie a lui bi se determină:

- variaţia corespunzătoare a funcţiei obiectiv;

- panta (slope) funcţiei obiectiv = raportul dintre variaţia funcţiei

obiectiv şi variaţia termenului liber bi = preţul umbră ui care rămâne

neschimbat în interval.

2. Parametrizarea întregului vector b: b => b ( ) = b + , unde R, iar este un

vector cu m perturbaţii.

În acest caz:

Se determină toate intervalele de variaţie ale parametrului (- , + ) astfel încât

)('b1B)('BX 0. Fiecărui interval îi corespunde un vector format din m

preţuri umbră care rămân neschimbate în acel interval.

Pentru fiecare interval de variaţie a lui se determină:



obiectiv şi variaţia parametrului .

Din punct de vedere matematic se aplică următoarea procedură:

Etapa I: Se obţine soluţia optimă a problemei pentru o valoare fixată a parametrului (de

exemplu pentru parametrul = 0);

Etapa II: Studiul senzitivităţii soluţiei la variaţia parametrului atribuit vectorului b:

1. Se identifică B-1

, inversa bazei corespunzătoare soluţiei optime;

2. Se calculează noua soluţie de bază )('b1B)('BX ;

3. Se determină intervalul [ 1, 2] astfel încât )('b1B)('BX 0. În acest

interval, vectorul preţurilor umbră u = cBB-1

rămâne neschimbat.

4. Se identifică variabila xj( ) < 0 pentru < 1 sau > 2. Se aplică algoritmul

simplex dual pentru determinarea soluţiei optime şi se reia procedura de la pasul 3.

5. Procedura se termină când s-au analizat toate valorile lui (- , + ).

Parametrizarea vectorului c


9

Situaţia practică: variaţia costului de producţie este exprimată printr-o funcţie liniară de un

parametru R care transformă vectorul c în vectorul c ( ). Funcţia obiectiv constă în

minimizarea costurilor totale pentru realizarea vectorului de activităţi X.

Se pot realiza două tipuri de analiză parametrică:

1. Parametrizarea unui singur element al vectorului c: cj => cj ( ) = cj + şi

menţinerea la nivelul iniţial a celorlalte elemente ale vectorului c.

În acest caz, pentru coeficientul cj specificat:

Se determină toate intervalele de variaţie ale parametrului (- , + ) şi ale

coeficientul cj ( ) = cj + , astfel încât )(c)(z'

j

'

j ≤ 0;

Pentru fiecare interval de variaţie a lui cj se determină:



obiectiv şi variaţia coeficientului cj = valoarea variabilei decizionale

xj care rămâne neschimbată în interval

2. Parametrizarea întregului vector c: c => c ( ) = c + , unde R, iar este un

vector cu n perturbaţii.

În acest caz:

Se determină toate intervalele de variaţie ale parametrului (- , + ) astfel încât

)(c)(z'

j

'

j ≤ 0, j. Fiecărui interval îi corespunde un vector format din n variabile

decizionale xj, j = 1, ...,n, ale căror valori rămân neschimbate în acel interval.

Pentru fiecare interval de variaţie a lui se determină:



obiectiv şi variaţia parametrului .

Din punct de vedere matematic se aplică următoarea procedură:

Etapa I: Se obţine soluţia optimă a problemei pentru o valoare fixată a parametrului (de

exemplu pentru parametrul = 0);

Etapa II: Studiul senzitivităţii soluţiei la variaţia parametrului atribuit vectorului c:

1. Se calculează )()(''

jj cz , pentru j = 1, ...,n;

2. Se determină intervalul [ 1, 2] astfel încât )(c)(z'

j

'

j ≤ 0, pentru j = 1, ...,n (în

cazul problemei de minim). În acest interval, soluţia optimă rămâne neschimbată.

3. Se identifică diferenţa )(ck)(z ''

k > 0 pentru < 1 sau > 2. Se aplică

algoritmul simplex primal pentru determinarea soluţiei optime şi se reia procedura

de la pasul 1.

4. Procedura se termină când s-au analizat toate valorile lui (- , + ).

Cazurile practice posibile de reoptimizare şi parametrizare:

Modificarea simultană a cantităţilor disponibile din diferite resurse duce la reoptimizarea în

raport cu vectorul b sau la parametrizarea vectorului b al termenilor liberi;

Modificarea simultană a mai multor costuri unitare (sau preţuri) duce la reoptimizarea în raport

cu vectorul c sau la parametrizarea vectorului c al coeficienţilor funcţiei obiectiv;

Modificarea consumurilor tehnologice determină modificarea unor elemente ale matricei

coeficienţilor tehnologici şi duce la reoptimizarea în raport cu matricea A;

Asimilarea de produse noi determină introducerea unor variabile noi şi duce la reoptimizarea

în raport cu matricea A şi vectorul c;

Apariţia unor noi resurse limitate determină adăugarea de noi restricţii şi duce la reoptimizarea

în raport cu matricea A şi vectorul b.


10

Studiu de caz din culegere3

Structura de producţie pentru probleme de dimensiuni mari cu variabile

în numere reale. Analiza economică complexă.

Staţia pilot a societăţii comerciale SEROM S.A. a realizat şi testat trei modele noi de pardoseală ceramică: Model1,

Model2, Model3. Din cercetările de marketing pentru aceste produse, rezultă că ele se bucură de succes pe piaţă.

Conducerea societăţii a decis realizarea modelelor noi de pardoseală la trei din filialele sale: Filiala1, Filiala2, Filiala3.

Filialele dispun de materiile prime, utilajele şi tehnologiile corespunzătoare.

Conducerea societăţii comerciale urmăreşte o încărcare uniformă a capacităţii de fasonare a fabricilor sale astfel

încât raportul dintre producţia realizată şi capacitatea de fasonare să fie acelaşi pentru toate fabricile.

Profitul unitar estimat variază în funcţie de tipul modelului, de aceea conducerea societăţii ar dori să determine

structura ofertei pentru fiecare filială astfel încât profitul total să fie maxim.

Baza informaţională • Prin studiul pieţei, compartimentul de marketing a estimat vânzările potenţiale pentru luna următoare

(octombrie a.c.), şi preţurile unitare pentru fiecare model de pardoseală.

• Pe baza reţetelor de fabricaţie, compartimentul cercetare-dezvoltare producţie a stabilit costul unitar de

producţie şi a estimat profitul unitar pentru fiecare model (tabelul 1). Tot pe baza reţetelor de fabricaţie s-au determinat

consumurile specifice de masă preparată (barbotină) pentru fiecare model de pardoseală (tabelul 2).

Tabel 1

Modele pardoseală Vânzări potenţiale (mii m2) Profitul (unit.monetare/1000 m

2)

Model1

Model2

Model3

60

80

50

12

10

9

Tabel 2

Model1 Model2 Model3

Consumul de barbotină (tone / 1000 m2) 4 2,25 1,44

• Pe baza fişei utilajului, secţiile de producţie din fiecare fabrică au determinat capacitatea de preparare a

barbotinei pentru plăcile de pardoseală precum şi capacitatea de fasonare pentru luna următoare (tabelul 3).

Tabel 3

Capacitatea de preparare (tone) Capacitatea de fasonare(mii m2)

Filiala1 81 50

Filiala2 72 60

Filiala3 31,5 30

Specificarea necunoscutelor:

x1 cantitatea din Model1 fabricată la Filiala1

x2 cantitatea din Model1 fabricată la Filiala2

...

X8 cantitatea din Model3 fabricată la Filiala2

X9 cantitatea din Model3 fabricată la Filiala3

Formatul general al PPL (problema de maxim - problema primală)

Max 992211 ...)( xcxcxcXf

Cu sistemul de restricţii:

mnmnmm

nn

nn

bxaxaxa

bxaxaxa

bxaxaxa

....

....

....

2211

22222121

11212111

Cu condiţiile:

3 St. de caz 7 din lucrarea „Modelare economică. Studii de caz, teste”, autori: Raţiu-Suciu C., Luban F.,

Hîncu D., Ciocoiu N., Editura ASE, Bucureşti, 2007


11

0...,,, 21 nxxx

Cu datele numerice:

987654321 999101010121212)(max xxxxxxxxxXf

Restricţiile pentru capacitatea de preparare:

C1: 00.8144.125.200.4 741 xxx

C2: 00.7244.125.200.4 852 xxx

C3: 50.3144.125.200.4 963 xxx

Restricţiile pentru capacitatea de fasonare:

C4: 50741 xxx

C5: 60852 xxx

C6: 30963 xxx

Restricţiile pentru capacitatea de absobţie a pieţei/vânzări potenţiale:

C7: 60321 xxx

C8: 80654 xxx

C9: 50987 xxx

Restricţiile corespunzătoare gradului de încărcare pentru capacităţile de fasonare:

C10:

C11:

PPL - problema de minim - problema duală)

987654321 5080603060505.317281)(min uxuuuuuuuXg

Se foloseşte WINQSB/Linear Programming; se optează pentru începerea lucrului la o problemă

nouă (New problem) cu 9 variabile (variables) şi 11 restricţii (constraints), cu tipul

funcţiei obiectiv – de maximizare (maximize) si cu variabile reale şi non-negative; formatul de

introducere al datelor - matrix spreadsheet form.

Meniul de ntroducere al datelor: Tabel 4

Variable

-->

X1 X2 X3 X4 X5 X6 X7 X8 X9 Direction R. H. S.

Maxim

ize

12 12 12 10 10 10 9 9 9

C1 4 2.25 1.44 <= 81

C2 4 2.25 1.44 <= 72

C3 4 2.25 1.44 <= 31.5

C4 1 1 1 <= 50

C5 1 1 1 <= 60

C6 1 1 1 <= 30

C7 1 1 1 <= 60

C8 1 1 1 <= 80

C9 1 1 1 <= 50

C10 6 -5 6 -5 6 -5 = 0

C11 1 -2 1 -2 1 -2 = 0

LowerBou

nd

0 0 0 0 0 0 0 0 0

UpperBou

nd

M M M M M M M M M


12

Variable

-->

X1 X2 X3 X4 X5 X6 X7 X8 X9 Direction R. H. S.

Variable

Type

Continuo

us

Continuo

us

Continuo

us

Continuo

us

Continuo

us

Continuo

us

Continuo

us

Continuo

us

Continuo

us

Tabel 5. Soluţia optimă – sumar

Decision

Variable

Solution

Value

Unit Cost

or

Profit c(j)

Total

Contribution

Reduced

Cost

Basis

Status

Allowable

Min. c(j)

Allowable

Max. c(j)

X1 0,5714 12,0000 6,8572 0 basic 10,0000 17,7778

X2 0 12,0000 0 -8,9877 at

bound

-M 20,9877

X3 0 12,0000 0 -8,9877 at

bound

-M 20,9877

X4 34,9841 10,0000 349,8413 0 basic 7,8333 12,0000

X5 13,0370 10,0000 130,3704 0 basic 5,9853 19,5759

X6 0,9630 10,0000 9,6296 0 basic 6,6707 29,1518

X7 0 9,0000 0 -4,1600 at

bound

-M 13,1600

X8 29,6296 9,0000 266,6667 0 basic 2,8714 21,4800

X9 20,3704 9,0000 183,3333 0 basic -3,2571 15,2400

Objective Function (Max.) = 946,6984

Constraint

Left Hand

Side

Direction

Right Hand

Side

Slack

or

Surplus

Shadow

Price

Allowable

Min. RHS

Allowable

Max. RHS

C1 81,0000 <= 81,0000 0 1,1429 80,0000 142,2222

C2 72,0000 <= 72,0000 0 6,2787 53,5814 73,8000

C3 31,5000 <= 31,5000 0 6,2787 30,5085 33,3000

C4 35,5556 <= 50,0000 14,4444 0 35,5556 M

C5 42,6667 <= 60,0000 17,3333 0 42,6667 M

C6 21,3333 <= 30,0000 8,6667 0 21,3333 M

C7 0,5714 <= 60,0000 59,4286 0 0,5714 M

C8 48,9841 <= 80,0000 31,0159 0 48,9841 M

C9 50,0000 <= 50,0000 0 4,0857 5,5556 52,2222

C10 0,0000 = 0 0 1,2381 -91,8333 2,6667

C11 0 = 0 0 2,0635 -1,6250 1,6000

Tabel 6. Analiza parametrică pentru termenul liber al restricţiei C1 (resursa critică) - Parametric

Analysis From RHS

of C1

To RHS

of C1

From

OBJ Value

To

OBJ Value

Slope

Leaving

Variable

Entering

Variable

81,0000 142,2222 946,6984 1.016,6670 1,1429 X4 Slack_C1

142,2222 M 1.016,6670 1.016,6670 0

81,0000 80,0000 946,6984 945,5555 1,1429 X1 X7

80,0000 42,6667 945,5555 779,6296 4,4444 X4 Slack_C9

42,6667 38,4000 779,6296 714,4445 15,2778 X8 X2

38,4000 33,6000 714,4445 640,2857 15,4497 X9 X3

33,6000 21,6000 640,2857 453,8571 15,5357 X5 Slack_C2

21,6000 18,9000 453,8571 401,6250 19,3452 X6 Slack_C3

18,9000 0 401,6250 0,0000 21,2500 X2

0 -Infinity Infeasible


13

Figure 1

Tabel 7. Analiza parametrică pentru termenul liber al restrictiei C4 (resursa in exces) From RHS

of C4

To RHS

of C4

From OBJ Value To OBJ Value Slope Leaving

Variable

Entering

Variable

50,0000 M 946,6984 946,6984 0

50,0000 35,5556 946,6984 946,6984 0 Slack_C4 Slack_C9

35,5556 26,6667 946,6984 765,1111 20,4286 X8 X2

26,6667 23,3333 765,1111 696,1905 20,6762 X9 X3

23,3333 20,2500 696,1905 632,0571 20,8000 X4 Slack_C1

20,2500 15,0000 632,0571 498,8571 25,3714 X5 Slack_C2

15,0000 13,1250 498,8571 441,0000 30,8571 X6 Slack_C3

13,1250 0,0000 441,0000 0,0001 33,6000 X2

0,0000 -Infinity Infeasible


14

Figure 2

Tabel 8. Analiza parametrică pentru coeficientul din funcţia obiectiv corespunzător

variabilei x1 From Coeff.

of X1

To Coeff.

of X1

From OBJ

Value

To OBJ Value Slope Leaving

Variable

Entering

Variable

12,0000 17,7778 946,6984 950,0000 0,5714 X4 X7

17,7778 48,1111 950,0000 1.365,2780 13,6905 X8 Slack_C9

48,1111 48,5513 1.365,2780 1.372,6030 16,6406 X9 X2

48,5513 48,7714 1.372,6030 1.376,6790 18,5156 X7 X3

48,7714 M 1.376,6790 M 20,2500

12,0000 10,0000 946,6984 945,5555 0,5714 X1 Slack_C1

10,0000 -M 945,5555 945,5555 0


15

Figure 3

Tabel 9. Analiza parametrică pentru coeficientul din funcţia obiectiv corespunzător lui x2 From

Coeff.

of X2

To Coeff.

of X2

From

OBJ Value

To

OBJ Value

Slope

Leaving

Variable

Entering

Variable

12,0000 20,9877 946,6984 946,6984 0 X5 X2

20,9877 42,4250 946,6984 1.071,5400 5,8235 X9 Slack_C9

42,4250 42,6085 1.071,5400 1.073,8090 12,3750 X4 X3

42,6085 49,3809 1.073,8090 1.171,7140 14,4563 X8 Slack_C1

49,3809 M 1.171,7140 M 18,0000

12,0000 -M 946,6984 946,6984 0


16

Figure 4

Rezolvarea în EXCEL/Solver

Configurarea spatiului de lucru şi introducerea datelor


17

Folosirea opţiunii de Solver pentru rezolvare


18

Raportul de rezultate - Answer report

Cell Name Original Value Final Value

$L$2 valoarea functiei obiectiv 946.6984127 946.6984127

Cell Name Original Value Final Value

$B$18 x1 0.571428571 0.571428571

$C$18 x2 0 0

$D$18 x3 0 0

$E$18 x4 34.98412698 34.98412698

$F$18 x5 13.03703704 13.03703704

$G$18 x6 0.962962963 0.962962963

$H$18 x7 0 0

$I$18 x8 29.62962963 29.62962963

$J$18 x9 20.37037037 20.37037037

Cell Name Cell Value Formula Status Slack

$K$5 c1 LHS 81 $K$5<=$M$5 Binding 0

$K$6 c2 LHS 72 $K$6<=$M$6 Binding 0

$K$7 c3 LHS 31.5 $K$7<=$M$7 Binding 0

$K$8 c4 LHS 35.55555556 $K$8<=$M$8 Not Binding 14.44444444




19



$K$13 c9 LHS 50 $K$13<=$M$13 Binding 0

$K$14 c10 LHS 0 $K$14=$M$14 Not Binding 0

$K$15 c11 LHS 0 $K$15=$M$15 Not Binding 0

$B$18 x1 0.571428571 $B$18>=0 Not Binding 0.571428571

$C$18 x2 0 $C$18>=0 Binding 0

$D$18 x3 0 $D$18>=0 Binding 0

$E$18 x4 34.98412698 $E$18>=0 Not Binding 34.98412698

$F$18 x5 13.03703704 $F$18>=0 Not Binding 13.03703704

$G$18 x6 0.962962963 $G$18>=0 Not Binding 0.962962963

$H$18 x7 0 $H$18>=0 Binding 0

$I$18 x8 29.62962963 $I$18>=0 Not Binding 29.62962963

$J$18 x9 20.37037037 $J$18>=0 Not Binding 20.37037037

Raportul analizei de senzitivitate – Sensitivity Report

Final Reduced Objective Allowable Allowable

Cell Name Value Cost Coefficient Increase Decrease

$B$19 x1 0.571428571 0 12 5.777777774 2

$C$19 x2 0 -8.987654318 12 8.987654318 1E+30

$D$19 x3 0 -8.98765432 12 8.98765432 1E+30

$E$19 x4 34.98412698 0 10 2 2.166666665

$F$19 x5 13.03703704 0 10 9.575892856 4.014705881

$G$19 x6 0.962962963 0 10 19.15178571 3.329268292

$H$19 x7 0 -4.159999997 9 4.159999997 1E+30

$I$19 x8 29.62962963 0 9 12.48 6.128571428

$J$19 x9 20.37037037 0 9 6.239999997 12.25714286

Final Shadow Constraint Allowable Allowable

Cell Name Value Price R.H. Side Increase Decrease

$K$6 c1 LHS 81.00 1.14 81 61.22222221 1

$K$7 c2 LHS 72.00 6.28 72 1.8 18.41860465

$K$8 c3 LHS 31.50 6.28 31.5 1.8 0.991525424

$K$9 c4 LHS 35.56 0.00 50 1E+30 14.44444444

$K$10 c5 LHS 42.67 0.00 60 1E+30 17.33333333

$K$11 c6 LHS 21.33 0.00 30 1E+30 8.666666667

$K$12 c7 LHS 0.57 0.00 60 1E+30 59.42857143

$K$13 c8 LHS 48.98 0.00 80 1E+30 31.01587302

$K$14 c9 LHS 50.00 4.09 50 2.222222222 44.44444444

$K$15 c10 LHS 0.00 1.24 0 2.666666666 91.83333333

$K$16 c11 LHS 0.00 2.06 0 1.6 1.625


20

Raportul Limits

Target

Cell Name Value

$L$2

valoarea functiei obiectiv 946.6984127

Adjustable Lower Target Upper Target

Cell Name Value Limit Result Limit Result

$B$19 x1 0.571428571 0.571428571 946.6984127 0.571428571 946.6984127

$C$19 x2 0 -5.68434E-

15 946.6984127 0 946.6984127

$D$19 x3 0 -3.55271E-

15 946.6984127 -3.55271E-

15 946.6984127

$E$19 x4 34.98412698 34.98412698 946.6984127 34.98412698 946.6984127

$F$19 x5 13.03703704 13.03703704 946.6984127 13.03703704 946.6984127

$G$19 x6 0.962962963 0.962962963 946.6984127 0.962962963 946.6984127

$H$19 x7 0 4.73695E-15 946.6984127 4.73695E-15 946.6984127

$I$19 x8 29.62962963 29.62962963 946.6984127 29.62962963 946.6984127

$J$19 x9 20.37037037 20.37037037 946.6984127 20.37037037 946.6984127

3. Modelarea structurii de producţie şi a posibilităţilor de dezvoltare

ale unei organizaţii (cazul în care variabilele sunt NUMERE

ÎNTREGI)

În cazul produselor indivizibile, pentru determinarea structurii optime de fabricaţie se pot utiliza

modele de programare liniară în numere întregi.

Rezolvarea modelelor liniare cu variabile întregi se efectuează cu metode de enumerare:

- explicită şi implicită

Din categoria metodelor de enumerare implicită face parte metoda „branch and bound” adică

„ramifică şi mărgineşte”.

Procesul iterativ de rezolvare poate fi reprezentat printr-un arbore binar, în care fiecare nod are

un singur ascendent şi doi descendenţi direcţi.

Fiecare nod al arborelui binar reprezintă o problemă de programare liniară fără restricţia ca

variabilele să fie întregi. Problemele asociate nodurilor arborelui binar se rezolvă cu algoritmul

simplex.

Un nod se ramifică dacă soluţia problemei este neîntreagă şi nu există alt nod cu soluţie

întreagă şi cu valoare mai bună a funcţiei obiectiv.

Pentru ramificarea unui nod, din soluţia problemei asociată acelui nod, se alege o componentă

xj cu valoare neîntreagă, xj = .

Pornind de la această variabilă se construiesc două probleme care generează două noduri

descendente:

Problema pentru nodul stâng:

prin adăugarea restricţiei

xj [ ],

unde [ ] este parte întreagă a numărului

Problema pentru nodul drept:

prin adăugarea restricţiei xj [ ] +1.


21

Prin adăugarea de restricţii de ramificare, se reduce domeniul soluţiilor cu valori întregi, iar

valoarea funcţiei obiectiv se înrăutăţeşte. Cea mai bună valoare a funcţiei obiectiv este asociată

nodului iniţial sau nodului rădăcină a arborelui binar.

4. Modele liniare stochastice cu vectorii b şi c aleatori

- modele de programare liniară în care unul sau mai mulţi dintre coeficienţii aij, bi şi cj sunt mărimi

aleatoare cu distribuţia de probabilitate cunoscută se numesc modele stochastice.

- valoarea funcţiei obiectiv a problemei de programare liniară va fi o mărime aleatoare a cărui

distribuţie de probabilitate va fi determinată în funcţie de valorile posibile ale mărimilor aleatoare

de intrare: consumuri tehnologice, disponibil de resurse, preţuri etc.

In general, distribuţia de probabilitate a valorilor funcţiei obiectiv se poate obţine prin simularea

Monte Carlo.

Prin analiza distribuţiei de probabilitate a valorilor funcţiei obiectiv decidentul obţine mai multe

informaţii despre valorile posibile ale indicatorului optimizat şi poate cuantifica riscul asociat

diferitelor variante decizionale.

4.A. Programarea stochastică cu vectorul c aleatoriu (cj sunt variabile

aleatoare)

Modelul de programare liniară:

AX b şi X 0 cu max cX,

Unde:

r

r

n

rr

nn

ppp

cccccccccC

...;;

),...,,(...);,...,,();,...,,(

21

21

22

2

2

1

11

2

1

1

unde 11

r

h

hp , iar h

jc este valoarea coeficientului cj al funcţiei obiectiv care are asociată

probabilitatea de realizare ph, pentru j = 1, ..., n; h = 1, ..., r.

Metoda 1:

a) Se calculează mediile probabiliste ale coeficienţilor funcţiei obiectiv:

r

h

h

jhj cpc1

;

b) Se rezolvă problema de programare liniară deterministă

AX b; X 0 cu max j

n

j

j xc1

se obţine varianta decizională optimă asociată speranţei matematice optime a valorii criteriului de

performanţă.

Metoda 2:

a) Se rezolvă r probleme de programare liniară de forma:

AX b şi X 0 cu max

cu j

n

j

h

j xc1

, pentru h = 1,...,r,

se obţin valorile optime ale funcţiei obiectiv f1*, f2*,...,fr*;


22

b) Se construieşte distribuţia de probabilitate a valorilor funcţiei obiectiv:

r

r

ppp

fffF

...

*...**

21

21*

c) Se determină media valorilor optime, deviaţia standard, coeficientul de variaţie, intervalul de

încredere pentru media valorilor funcţiei obiectiv.

4.B. Programarea stochastică cu vectorul b aleator

Modelul de programare liniară are forma:

AX b

X 0

max cX,

unde b este o mărime aleatoare uniform repartizată în intervalul [ 2

i

1 b ,ib ], pentru i = 1,...,m.

Rezolvarea analitică:

a) Se calculează mediile probabiliste ale elementelor termenului liber al restricţiilor:

2

11

ii

i

bbb , pentru i = 1,...,m

b) Se rezolvă problema de programare liniară deterministă

AX b

X 0

max cX

se obţine varianta decizională optimă asociată speranţei matematice disponibilului.

II. FUZZYFICAREA MODELELOR

II.1. Metode de trecere de la variabila lingvistică (descriptivă) la cea cantitativă

(algoritmizabilă)

Deciziile se bazează pe informaţii. Cel mai adesea, informaţiile disponibile se prezintă sub

forma unui amestec de date precise şi percepţii. Aceste percepţii pot fi exprimate foarte

sugestiv cu ajutorul unor operatori lingvistici cum sunt: poate, oarecum, cald, rece, aproape,

departe, mare, mic, înalt, scund etc. sau de exemplu, „este foarte posibil ca preţul produsului

X să crească semnificativ în viitorul apropiat”.

Percepţiile sunt prin natura lor imprecise, reflectând abilitatea limitată a oamenilor de a reţine

detalii şi de a memora multe informaţii.

Imprecizia este generată de imposibilitatea de a delimita exact graniţele dintre diferite

categorii cum sunt: mare – mic, aproape – departe etc.

Legat de imprecizia percepţiei umane, Lotfi Zadeh (cercetător american) a formulat chiar un

principiu al incompatibilităţii arătând că pe măsura creşterii complexităţii, precizia şi

semnificaţia afirmaţiilor referitoare la comportamentul procesului economic sunt

incompatibile, în sensul că majoritatea afirmaţiilor referitoare la un proces complex sunt

imprecise sau vagi.

De asemenea, L. Zadeh este fondatorul teoriei mulţimilor vagi (fuzzy) prin care se

fundamentează din punct de vedere matematic posibilitatea de a opera cu elemente imprecise.

Astfel, prin definirea noţiunii de mulţimi vagi, elementele unor astfel de mulţimi au grade de


23

apartenenţă cu valori în intervalul [0, 1]. De exemplu, o întreprindere poate aparţine cu gradul

de apartenenţă 0,9 mulţimii întreprinderilor „mici” şi cu gradul de apartenenţă 0,2 mulţimii

întreprinderilor „mijlocii”.

Un asemenea mod de abordare permite definirea conceptelor de optimizare flexibilă şi de

soluţie satisfăcătoare (Herbert Simon).

Prin definirea coeficienţilor unui model de programare liniară ca mulţimi vagi se obţine

programarea robustă (o familie de probleme de programare inexactă).

Trecerea de la exprimarea lingvistică la cea numerică constituie o artă, dificil de algoritmizat.

Necesitatea transformării variabilei lingvistice în variabilă de tip numeric, rezultă din:

- posibilitatea reflectării mai exacte a fenomenelor;

- posibilitatea prelucrării automate a datelor.

Pe parcursul elaborării modelelor are loc permanent convertirea variabilelor lingvistice în

variabile numerice şi invers.

Regulile de transformare sunt, în majoritatea cazurilor, de natură empirică şi intuitivă, dar în

anumite cazuri pot fi folosite proceduri programabile pe calculator prin folosirea statisticii

matematice.

II. 2. Necesitatea fuzzyficării modelelor deterministe

În situaţii complexe, pentru rezolvarea problemelor se apelează la raţionamente exprimate prin

variabile descriptive.

Imprecizia exprimată prin operatorii lingvistici oferă expresivitate şi conţinut informaţional

ridicat comunicării în limbaj natural.

Procesul de fuzzyficare constituie obiectivul unei concepţii caracterizate printr-o capacitate

deosebită de adaptabilitate şi flexibilitate. Prin fuzzyficare, variabilele lingvistice pot fi

transformate în variabile cantitative, care au un caracter deosebit de elastic.

Manevrarea datelor inexacte permite nuanţarea deciziei şi conduce la programarea flexibilă.

Pentru a obţine modele flexibile şi robuste apare necesitatea utilizării toleranţelor pentru

coeficienţii modelelor deterministe.

În cazul relaxării restricţiilor se pot elabora programe flexibile de producţie cu diferite grade

de realizare.

Mărimea toleranţelor admise pentru restricţiile problemei de programare liniară reprezintă

necesarul suplimentar de resurse pentru realizarea obiectivelor propuse.

Este recomandat ca iniţial să se opereze cu variabile şi relaţii deterministe. E baza analizei

rezultatelor, se apreciază care sunt variabilele şi / sau restricţiile care denaturează realitatea

economică. În final, aceste variabile şi restricţii se relaxează prin fuzzyficare.

II. 3. Variabilă fuzzy, relaţie fuzzy

Cercetătorul american Lofti Zadeh propune, în 1965, conceptul de logică fuzzy prin care se pot construi propoziţii

care, în afară de valoarea 1 pentru propoziţia adevărată şi valoarea 0 pentru propoziţia falsă, pot avea valori

intermediare în [0, 1].

Savantul român Grigore Moisil a anticipat, în 1943, conceptul de logică fuzzy în lucrările sale de logică nuanţată

în care propoziţiile au infinitate de valori.

Astăzi abordarea imprecisă a problemelor decizionale beneficiază de rezultate importante care constituie :

- teoria mulţimilor fuzzy

- teoria sistemelor fuzzy

- teoria algoritmilor fuzzy.

Aceste rezultate stau la baza multor sisteme de inteligenţa artificială, în special în robotică.


24

Fie E mulţimea tuturor elementelor x şi A o mulţime inclusă în E, A E. Elementele mulţimii

A se caracterizează prin diferite proprietăţi.

In cazul utilizării cuvintelor (adjective, adverbe, etc.) se spune că mulţimea elementelor se

constituie în universul discursului. În acest caz, se obţine o variabilă lingvistică.

In cazul când mulţimea elementelor este formată din cifre care reprezintă indicatorii ataşaţi

unei caracteristici (cantităţi, lungimi, capacităţi, note etc.) se obţine o variabilă fuzzy sau vagă.

Pentru a indica apartenenţa unui element x E, la o anumită proprietate a mulţimii A E se

defineşte gradul de apartenenţă sau funcţia de apartenenţă μA(x).

Funcţia de apartenenţă este definită pe mulţimea E şi ia valori în mulţimea M, adică μA(x): E

M

Dacă mulţimea M a valorilor funcţiei de apartenenţă este formată din două elemente, adică M

= {0, 1}, atunci A este o mulţime nevagă.

Dacă mulţimea M este intervalul [0, 1], atunci A este o mulţime vagă sau fuzzy. În acest caz

deoarece max μA(x) = 1, mulţimea A este o mulţime vagă normală. In general, se efectuează o

normalizare a gradelor de apartenenţă.

Mulţimea elementelor x pentru care μA(x) 0 se numeşte suportul mulţimii vagi.

Dacă se consideră că gradul de apartenenţă este o mărime deterministă, atunci este vorba de

vaguitate de ordinul I:

Dacă se consideră că gradul de apartenenţă este o mărime vagă ( ca grad de apartenenţă

determinist), atunci este vorba de vaguitate de ordinul II.

Definiţia mulţimii vagi sau fuzzy: Se numeşte mulţime vagă A în E, mulţimea perechilor

ordonate {x, μA(x) x E}, unde μA(x) este funcţia sau gradul de apartenenţă al elementului x

la o anumită proprietate care caracterizează mulţimea A.

Cu ajutorul funcţiilor de apartenenţă, variabilele lingvistice pot fi transformate în variabile

cantitative, deosebit de flexibile.

Funcţiile de apartenenţă au caracter subiectiv. De exemplu, afirmaţia „întreprinderea Y

aparţine în „mare măsură” mulţimii B a întreprinderilor mici” poate fi exprimată cantitativ prin

gradul de apartenenţă μB(Y) = 0,9.

Dacă subiectivismul reprezintă informaţia necuantificabilă deţinută de decidenţ sub forma

intuiţiei şi experienţei atunci abordarea fuzzy permite:

- valorificarea informaţiei comunicabile prin limbajul natural

- asimilarea elementelor specifice intuiţiei umane

Există diferite tipuri de funcţii de apartenenţă. Cele mai utilizate sunt funcţiile de apartenenţă

exponenţiale şi fracţionare.

Între mulţimile vagi se pot defini diverse relaţii. Aceste relaţii sunt definite cu ajutorul gradelor de

apartenenţă. Dacă gradele de apartenenţă sunt mărimi deterministe, atunci relaţia definită este în

sens nevag. Dacă gradele de apartenenţă sunt mărimi vagi, atunci relaţia definită este în sens vag.

Egalitatea a două mulţimi vagi:

- în sens nevag: A = B dacă şi numai dacă μA(x) = μB(x), ( ) x E

- în sens vag: A B dacă μA(x) μB(x), ( ) x E (adică mulţimea A este egală în

sens vag cu mulţimea B dacă μA(x) este egal în sens vag cu μB(x) „aproape pentru

orice” sau pentru majoritatea elementelor x E).

Incluziunea a două mulţimi vagi:

- în sens nevag: A B, dacă şi numai dacă μA(x) μB(x), ( ) x E

- în sens vag: A ~ B, dacă şi numai dacă μA(x) ~ μB(x), ( ) x E.

Mulţimea complementară a unei mulţimi vagi:

- O mulţime A~

se numeşte complementară a lui A, dacă:

μA~ (x) = 1 - μA(x), ( ) x E

Mulţimea complementară a unei mulţimi vagi:


25

- O mulţime A~

se numeşte complementară a lui A, dacă:

μA~ (x) = 1 - μA(x), ( ) x E

Intersecţia nevagă A B a două mulţimi vagi:

- Intersecţia nevagă a două mulţimi vagi este o submulţime inclusă în sens nevag în A

şi B al cărui grad de apartenenţă satisface relaţia:

μA B(x) = min {μA(x), μB(x)}

Intersecţia vagă A B a două mulţimi vagi:

- Intersecţia vagă a două mulţimi vagi este o submulţime inclusă în sens vag în A şi B

al cărui grad de apartenenţă satisface relaţia:

μA B(x) min {μA(x), μB(x)}

Reuniunea nevagă A B a două mulţimi vagi:

- Reuniunea nevagă A B a două mulţimi vagi este o mulţime vagă cu gradul de

apartenenţă determinist:

μA B(x) = max {μA(x), μB(x)}

Reuniunea vagă A B a două mulţimi vagi:

- Reuniunea vagă A B a două mulţimi vagi este o mulţime vagă cu gradul de

apartenenţă definit în sens vag:

μA B(x) max {μA(x), μB(x)}

Produsul algebric nevag A*B a două mulţimi vagi A şi B este o mulţime vagă cu gradul de

apartenenţă determinist: μA * B(x) = μA(x) * μB(x)

Produsul algebric vag A*B a două mulţimi vagi A şi B este o mulţime vagă cu gradul de

apartenenţă definit în sens vag: μA * B(x) μA(x) * μB(x)

Suma algebrică nevagă A+B a două mulţimi vagi este o mulţime vagă cu gradul de apartenenţă

determinist: μA + B(x) = μA(x) - μB(x) * μA(x) + μB(x)

Suma algebrică vagă A+B a două mulţimi vagi este o mulţime vagă cu gradul de apartenenţă

definit în sens vag: μA + B(x) μA(x) - μB(x) * μA(x) + μB(x)

II.4. Programarea matematică fuzzy (programarea liniara fuzzy PLF)

Consecinţele complexităţii şi multitudinii de aspecte importante în studiul proceselor

economice duc la imposibilitatea identificării cu uşurinţă a acelor factori uşor cuantificabili şi

măsurabili impunând anumite rigori în tratarea lor cantitativă.

In unele cazuri nu se pot face aproximări (de exemplu, prin valori medii sau speranţe

matematice) şi, astfel, pentru studiile cu caracter operaţional se folosesc „transcrieri” calitative (în

sensul folosirii unor variabile lingvistice) ale informaţiilor disponibile.

O variabilă lingvistică (V.L.) este descrisă cu ajutorul cuvintelor (nu al numerelor) într-un

limbaj natural sau artificial;

- conceptul a fost introdus de către L. Zadeh pentru a cuprinde într-o teorie

cuprinzătoare exprimări vagi, ambigue, insuficient de precise.

Teoria mulţimilor şi sistemelor fuzzy se constituie începând din deceniul VII al secolului

trecut ca un instrument puternic pentru modelarea şi conducerea sistemelor în condiţii de

imprecizie a datelor.

Imprecizia este opusă acurateţei/exactităţii adică gradului în care datele sunt corecte, de

încredere şi certificate ca fiind lipsite de erori. Alături de acurateţe, actualitatea, completitudinea şi

consistenţa sunt dimensiunile calităţii datelor care se referă, în special, la valorile datelor.

Cel mai adesea, apropierea dintre limbajul natural şi cel matematic se realizează prin

intermediul mulţimilor fuzzy. Abordarea fuzzy este destinată prelucrării unor date numerice

imprecise care nu pot fi tratate probabilistic.


26

O V.L. se caracterizeză prin determinări:

- primare: „mare”, „mic”, „moderat”, „scăzut”

- secundare obţinute prin rafinări ale celor primare cu ajutorul unor operatori lingvistici:

„destul de”, „mai”, „foarte”, „prea”, „accentuat de”, „extrem de” etc.

Pornind de la concepţia clasică cu privire la mulţime şi element al unei mulţimi se poate

susţine că noţiunea de mulţime fuzzy reprezintă o abordare dintr-un unghi diferit al conceptului se

mulţime. Se acceptă ideea că între apartenenţa unui element la o mulţime şi non-apartenenţa există

o serie de situaţii tranzitorii de natură continuă, descrise cu ajutorul gradelor de apartenenţă.

Fie X o mulţime oarecare, se numeşte mulţime fuzzy (pe X) rezultatul unei aplicaţii

]1,0[: XF caracterizată prin funcţia de apartenenţă ]1,0[X:F .

Valorile 0 şi 1 reprezintă cel mai mic, respectiv cel mai mare grad de apartenenţă la F al

unui element Xx .

Pentru descrierea fuzzy a unor fenomene şi procese, aplicaţiile )X(F pot admite

diferite exprimări analitice: forma triunghiulară sau trapezoidală, în formă de „clopot” etc.

Variabilele fuzzy sunt mărimi fuzzy asociate celor deterministe; echivalentul valorii

scalare în sens determinist este asociat gradului sau atributului lingvistic în cazul unei variabile

fuzzy.

Domeniul de valori (de exemplu: „foarte scăzută”, „scăzută”, „suficientă”, „moderată”,

„mare”, „foarte mare”, „extrem de mare”) ale mărimii deterministe „cifra de afaceri” (de

exemplu) se numeşte univers de discurs.

Fiecărui atribut al unei variabile lingvistice îi este asociată o funcţie de apartenenţă a

cărei valoare (în sens determinist) indică nivelul de încredere în asocierea dintre atribut şi valoarea

deterministă. Problema de programare liniara fuzzy - PLF - a asimilat specificul abordării fuzzy în

sensul tratării într-un context fuzzy a restricţiilor şi funcţiei obiectiv (chiar şi a coeficienţilor

tehnologici) din modelul tradiţional al programării liniare

XCFopt

0X

bXA

bXA

22

11

(*)

Intr-o formulare concisă, fiind date restricţiile fuzzy R1, R2, ….Rm şi obiectivele fuzzy

O1,O2, …Op se construiesc funcţiile de apartenenţă:

)X(iR pentru i=1,…m respectiv )X(

kO pentru k=1,…p,

apoi se introduce criteriul de optimizare: )X(maxEX

unde E este mulţimea soluţiilor admisibile şi

}p,1k),X(;m,1i),x(min{)X(ki OR .

Intr-o formă detaliată, modelul de programare liniară (*) se transformă în sens fuzzy (**)

prin relaxarea restricţiilor care modifică termenul liber al acestora şi introduc toleranţe (mărimi

admisibile ale perturbaţiilor posibile în nivelul resurselor).

XCFopt

X

bXgsaubXA

bXgsaubXA

0,0,0

)(

)(

21

21222

11111

(**)


27

Calculul funcţiilor de apartenenţă se face diferit :

• pentru restricţii de tipul „ ”

1111

1

111

111

11

b)x(gbpentru)b()X(g

b)X(gpentru0

b)X(gpentru1

)X(

• pentru restricţii de tipul „ ”

2222

2

222

222

22

)()(

)(0

)(1

)(

bxgbpentruXgb

bXgpentru

bXgpentru

X


28

Fie: E mulţimea soluţiilor admisibile (realizabile);

Xx o soluţie de alocare ....)x,x,x(X 321

Definim prin Si mulţimea vagă inclusă în E asociată obiectivului Oi descrisă prin funcţia

de apartenenţă ]1,0[E:)x(i . Pentru simplificarea calculelor şi în baza modului de

definire a operaţiei de intersecţie cu mulţimi vagi putem considera )}X({min iEx

.

III. MULTICRITERIALITATEA ÎN ACTIVITATEA DE

MANAGEMENT

Procesul decizional presupune evaluarea mai multor variante decizionale în vederea alegerii

uneia dintre ele. De cele mai multe ori, evaluarea variantelor decizionale se face pe baza mai

multor indicatori economici consideraţi criterii de evaluare. Problemele în care se caută

varianta decizională optimă în raport cu mai multe criterii se numesc probleme de optimizare

multicriterială.

În cazul optimizării multicriteriale se tratează distinct:

- optimizarea multiatribut;

- optimizarea multiobiectiv.

În cazul optimizării multiatribut:

- numărul variantelor decizionale este finit;

- fiecare variantă este evaluată prin mai multe criterii exprimate prin atribute (valori)

cantitative şi / sau calitative.

În cazul optimizării multiobiectiv:

- numărul variantelor decizionale este infinit;

- fiecare variantă este evaluată prin mai multe criterii exprimate prin funcţii

matematice.

-

Criteriile de evaluare pot fi exprimate în unităţi de măsură diferite. O altă problemă constă în

faptul că, unele criterii luate în considerare urmăresc maximizarea unor indicatori economici

(de exemplu: venitul total, producţia totală tec.), iar alte criterii urmăresc minimizarea unor

indicatori (de exemplu: costul total, timpul de lucru etc.).

g2 g(X) b2 22b

)X(

1


29

Pentru alegerea variantei decizionale optime este necesară ierarhizarea variantelor decizionale

disponibile în raport cu toate criteriile dorite. Dar, în general, o variantă optimă în raport cu un

criteriu este suboptimală în raport cu celelalte criterii. De aceea, se caută varianta care

realizează cel mai bun compromis pentru toate criteriile. În acest scop este necesară

transformarea valorilor indicatorilor în mărimi care să permită atât compararea variantelor cât

şi agregarea valorilor criteriilor de evaluare. Există diferite metode prin care se poate face

transformarea valorilor criteriilor în mărimi comparabile.

III. 2. Programarea liniară multidimensională (multiobiectiv)

Forma generală a problemei de programare liniară cu mai multe funcţii obiectiv:

Optimum F(X) = CX

Cu restricţiile:

AX b

X 0,

Unde:

X = vector coloană cu n componente x1, x2,...,xn care reprezintă variabilele decizionale ale

problemei. (De exemplu X poate fi vectorul structurii de producţie pentru o anumită

perioadă);

F(X) = vector coloană cu r componente f1(X), f2(X),...,fr(X), care reprezintă funcţiile obiectiv prin

care sunt exprimate criteriile de evaluare a variantelor decizionale. Fiecare funcţie

obiectiv fh(X) = n

1jjxhjc , pentru h = 1,...,r.

C = matrice cu r linii şi n coloane. Este matricea coeficienţilor celor r funcţii obiectiv, chj, h =

1,...,r, j = 1,...,n.

A = matrice cu m linii şi n coloane. Este matricea coeficienţilor tehnologici, aij, i = 1,...,m, j =

1,...,n

b = vector coloană cu m componente b1, b2,...,bm care reprezintă termenii liberi din partea dreaptă

a restricţiilor. Ei reprezintă disponibilul maxim dintr-o anumită resursă sau nivelul

minim care trebuie atins de anumite activităţi.

Metoda maximizării unei funcţii sinteză de utilitate

Pentru determinarea unei soluţii care realizează cel mai bun compromis pentru toate funcţiile

se va construi o funcţie sinteză a tuturor funcţiilor obiectiv numită funcţie sinteză de utilitate.

Funcţia sinteză de utilitate se obţine prin transformarea funcţiilor obiectiv f1(X), f2(X),...,fr(X),

cu semnificaţii economice concrete, în funcţii de utilitate care pot fi însumate. Prin

maximizarea funcţiei sinteză de utilitate în raport cu restricţiile problemei se obţine soluţia de

compromis cu utilitate maximă.

Algoritmul de calcul pentru obţinerea soluţiei de compromis pentru toate funcţiile obiectiv este

următorul:

Pasul 1. Se obţin valorile optimiste şi valorile pesimiste ale tuturor funcţiilor obiectiv.

a) Se rezolvă r probleme de programare liniară cu o singură funcţie obiectiv:

Optim fh(X) = minim de functie este dacã )X(hfmin

maxim de functie este dacã )X(hfmax

Supusă la restricţiile:

AX b


30

X 0,

pentru h = 1,...,r.

Se notează: O1, O2,...,Or valorile optimiste ale funcţiilor obiectiv f1(X), f2(X),...,fr(X)

b) Se rezolvă r probleme de programare liniară cu o singură funcţie obiectiv:

Pessim fh(X) = minim de functie este dacã )X(hfmax

maxim de functie este dacã )X(hfmin

Supusă la restricţiile:

AX b

X 0,

pentru h = 1,...,r.

Se notează: P1, P2,...,Pr valorile pesimiste ale funcţiilor obiectiv f1(X), f2(X),...,fr(X)

Pasul 2. Pe baza axiomelor von Neumann – Morgenstern, se determină utilităţile valorilor

optimiste O1, O2,...,Or şi pesimiste P1, P2,...,Pr:

Valori: O1 ... Oh ... Or P1 ... Ph ... Pr ,

Utilităţi: u1 ... uh ... ur ur+1 ... ur+h ... u2r

astfel încât uh + ur+h = 1 pentru h = 1, ..., r

Pasul 3. Se construiesc funcţiile de utilitate f h(X) = αhfh(X) + βh, unde αh şi βh pentru

h = 1,...,r se obţin prin rezolvarea a r sisteme de două ecuaţii liniare cu două

necunoscute:

hu1hhhP

huhhhO

Pasul 4. Se rezolvă problema de programare liniară cu funcţia sinteză de utilitate de forma:

Max )X(r

1h

'hf = Max

r

1hh

n

1jjxhjch

Supusă la restricţiile: AX b cu X 0,

sau Max )X(r

1h

'hfh

Supusă la restricţiile: AX b cu X 0,

unde π1, π2, ..., πr 0 sunt coeficienţi de importanţă atribuiţi de decident, astfel încât r

1h

1h .

După rezolvarea problemei se obţine soluţia X* de compromis, nedominată de celelalte soluţii

obţinute prin rezolvarea problemei în raport cu fiecare funcţie obiectiv f1(X), f2(X),...,fr(X).

Rezolvarea problemelor de programare liniară cu funcţia sinteză de utilitate se poate face cu

WINQSB/ Lp – ilp.

III.3. PROGRAMAREA SCOP

Programarea scop este o metodă de rezolvare a problemei de programare liniară cu mai multe

funcţii obiectiv. Obiectivul programării scop este găsirea unei soluţii care verifică

restricţiile AX b, X 0 şi care duce la abateri cât mai mici faţă de scopurile propuse

prin funcţiile obiectiv.

Ideea de bază a metodei constă în transformarea tuturor funcţiilor obiectiv în „restricţii scop”

prin:

- specificarea pentru fiecare funcţie obiectiv a unui nivel de aspiraţie sau scop;


31

- definirea pentru fiecare scop a unei perechi de variabile de abatere sau deviaţie:

- deviaţia în plus faţă de scopul propus

- deviaţia în minus faţă de scopul propus.

Nivelurile de aspiraţiile sau scopurile pot fi:

- stabilite de decident;

- obţinute prin optimizarea problemei de programare liniară în raport cu fiecare funcţie

obiectiv.

Forma generală a unui model pentru "programarea scop" este:

minimizează )(1

ii

N

i

ii dd

supusă la restricţiile:

AX b

X 0

şi restricţiile „scop”:

fi(X) = Vi + di+ - di

- => fi(X) - di

+ + di

- = Vi, i = 1,...,N

di+ 0, di

- 0, i = 1,...,N

unde:

di+ : deviaţia în plus faţă de valoarea prestabilită pentru funcţia obiectiv i;

di- : deviaţia în minus faţă de valoarea prestabilită pentru funcţia obiectiv i;

πi şi ρi sunt coeficienţi ai deviaţiilor care fac posibilă însumarea lor;

fi(X) : funcţia obiectiv i;

Vi : valoarea prestabilită (nivelul de aspiraţie) pentru funcţia obiectiv i;

X = vector coloană cu n componente x1, x2,...,xn care reprezintă variabilele decizionale ale

problemei.

AX b: restricţiile care definesc domeniul de admisibilitate al problemei pentru variabilele

decizionale x1, x2,...,xn.

Elementul cheie în utilizarea practică a metodei de programare scop îl constituie specificarea

funcţiei obiectiv, adică definirea coeficienţilor πi şi ρi pentru deviaţiile di+ şi di

-.

Funcţia care minimizează deviaţiile faţă de nivelurile de aspiraţie sau scopurile propuse se

numeşte „funcţie scop”. Dacă deviaţiile se măsoară cu unităţi de măsură diferite, atunci este

necesară definirea unor costuri de penalizare a deviaţiilor astfel încât să se poată minimiza

suma totală a costurilor de penalizare generate de diferite deviaţii.

Funcţiilor scop li se pot asocia diferite priorităţi. În acest caz se poate proceda astfel:

- Se ordonează descrescător scopurile şi se stabileşte prioritatea de satisfacere a fiecărui

scop:

P1 P2 … Pn...

unde înseamnă "mult mai mare".

- Ordonarea prin priorităţi este absolută, astfel că scopul cu prioritatea P2 nu va fi niciodată

atins înainte ca scopul cu prioritatea P1 să fie realizat cu abaterea cea mai mică faţă de

nivelul de aspiraţie propus.

- În acest caz, prin metoda programării scop se rezolvă succesiv un număr de probleme egal

cu numărul priorităţilor. Evident, numărul priorităţilor este mai mic sau cel mult egal cu

numărul funcţiilor obiectiv, iar numărul funcţiilor scop este egal cu numărul priorităţilor.

Deoarece nu toate scopurile pot fi realizate simultan, în cazul funcţiilor scop cu priorităţi

diferite vor apărea conflicte între scopuri. Aceste conflicte pot fi analizate cu ajutorul

„preţurilor umbră” asociate restricţiilor scop.

Rezolvarea modelelor de programare scop se poate face cu WINQSB/ Gp – igp.

Modelul de programare liniară cu mai multe funcţii obiectiv:


32

...

XC)x(f(max)opt

XC)x(f(min)opt

n,...,1j;0x

bAX

22

11

j

Scrierea detaliată a funcţiei obiectiv de tip min:

nn12121111 xc...xcxc)x(fmin

dacă )x(F1 desemnează nivelul optim al criteriului, se evaluează abaterea 1d faţă de

acest nivel:

)x(Fxc...xcxcd 1nn12121111

Transformarea fostei funcţii obiectiv în restricţie:

)x(Fdxc...xcxc 11nn1212111

Forma generală a modelului de programare liniară

minn

1i

ii )dd( - “funcţia scop”

supusă la restricţiile: bXA cu x ≥ 0; 0d i ; 0id , i=1,..,n

şi restricţiile “scop”: fi(x) dd ii = Fi(x)

Dacă obiectivele sunt exprimate în unităţi de măsură diferite, pentru minimizarea

deviaţiilor faţă de nivelurile de aspiraţie este necesară determinarea unor costuri de penalizare»

ale deviaţiilor (prin ponderarea deviaţiilor cu aceste costuri, devine posibilă însumarea şi

obţinerea unei funcţii obiectiv pentru programarea scop). Dacă se notează cu Wi costurile de

«penalizare», “funcţia scop” se scrie: min

n

1i

iiii )dwdw(

În ceea ce priveşte nivelul de importanţă acordat obiectivelor - două alternative:

- se ordonează descrescător scopurile şi se stabileşte prioritatea de satisfacere a fiecărui scop;

P1 >> P2 >> … >>Pn (>> înseamnă «mult mai mare decât»).

- se rezolvă succesiv un număr de probleme egal cu numărul priorităţilor. Acordarea de

priorităţi diferite generează apariţia unor “conflicte” între scopuri, atunci când nu este posibilă

realizarea simultană a tuturor nivelurilor de aspiraţie.

- obiectivele se consideră a fi de importanţă egală, în acest caz ele nu se ordonează (priorităţile

sunt egale).

12-13_me_curs pl extended gp si jocuri 18042013

Documents