Exam Cercetari Operationale
1. Modelul de alegere optimă a
coşului de consum. Analiza modelului. Consecinţele principale şi sensul lor
economic. Funcţii de cerere la bunuri.
Fiecare
sistem de consum consuma bunuri si nomenclatorul acestora consta din n
denumiri. Aceste bunuri se considera amplasate in spatiul piata, cantitatile
care pot fi oferite sunt marginite. Se va notaxj cantitatea bunului j pe care
consumatorul ar putea sa o procure de pe piata respectiva. Consumatorul are o
anumita relatie de preferinta x>y – x preferabil in raport cu y, x~y – la
fel de preferabile, xmax, Suma pj xj<=M, xj>=0. Geometric
setul preferabil de bunuri e prezentat de punctu de tangenta a unei linii de
indiferenta cu dreapta bugetara – set optim de bunuri. Solutionarea prin
Lagrange. Se alcatuieste functia L (x, lambda) = u +lambda(m – suma pj xj).
Lambda – utilitatea marginala a bunurilor. Consecintele: in punctul de
echilibru utilitatea marginala e proportionala pretului bunului dat cu coeficientul
de proportionalitate lambda. Utilitatea marginala care revine unei unitati de
pret este o marime constanta care coincide cu lambda si e aceeasi pentru orice
bun. Pentru procurarea bunurilor cu cantitatile punctului de echilibru se vor
cheltui toti banii. Utilitatea marginala a doua bunuri se comporta la fel ca
preturile acestor bunuri. Lambda – utilitatea suplimentara care o aduce o
unitate suplimentara de venit. Functia de cerere la bunuri – acelasi model, in
loc de U e V. xj – xj(p,m) – functia de cerere la bunul j. problema e reactia
consumatorului la modificarea venitului sau pretului: consum normal – consum
creste odata cu cresterea venitului, bun de prima necesitate – consumu e
constant venitul creste, bun de lux- consum creste venitul creste.
1. Etapele principale ale cercetării operaţionale.
Obiectivele şi criteriile de eficienţă a problemelor decizionale.
CO – studiul proceselor complexe ce tin de aspecte decizionale
care include solutii, strategii si factori contribuabili. Etape: 1. formularea problemei (scop, resurse, coeficienti
tehnici), 2. elaborarea modelului matematic (functie scop / obiectivul,
restrictii), 3. rezolvarea problmei (determinarea metodei de rezolvare), 4. verificarea,
testarea modelului, validitatii (datele prelucrate / obtinute de catre
decident), 5. aplicarea modelului / implementare. Problema de cercetari operationale se caracterizeaza prin: scop
(maximizarea profitului, performantei, randamentului; minimizarea pierderii,
costului, riscului), constrangeri (restrictii), solutii admisibile, optimale
(decizii, strategii, factori de control), functia obiectiv (criterii de
eficienta, performanta),decident sau grup decizional, etc. Decizia se defineste prin hotarârea de a alege o
anumita varianta de actiune din mai multe posibile. Pentru ca o decizie sa fie eficienta trebuie sa îndeplineasca
urmatoarele conditii: sa fie fundamentata stiintific; sa fie
luata de organul sau persoana autorizata; sa fie luata la timp; sa fie simpla
si clara; sa nu fie contradictorie. Criteriile
de apreciere a variantelor pot fi: tehnice (consum de materii prime, durata
ciclului de productie); economice (profitul, pretul, durata de recuperare a
investitiilor); sociale (forta de munca, importanta produselor în cadrul
pietei). Functia
f – e functia obiectiv a problemei de optimizare, ea reprezinta criteriul de
performanta urmarit: maximizarea beneficiului, productiei marfa, gradului de
incarcare al utilajelor, veniturilor, minimizarea costului productiei, timpului
de tsationare a utilajelor, etc.
2. Clasificarea problemelor
cercetării operaţionale: probleme decizionale de certitudine, risc şi
incertitudine. Regulile decizionale în condiţii de incertitudine şi risc.
Clasificari: 1. Continut: organizarea
optima a procesului de productie, gestiunea stocurilor, transport, de
distribuire optima a resurselor; 2. Raport
cu timpul: statice, dinamice. 3. Numarul de funcții obiectiv. 4. Caracter informational: determinist,
probabilist, incertitudine.
Sistem {X =
(x1, x2,…,xn) – factori contribuabili; C = marime vectoriala / matrici – marimi
constante}. Q = (q1,q2,…,qn) – vector.
De certitudine sau determinista – problema e pe deplin determinata pe grupul de factori X, C; X – solutia
se ia in conditii de certitudine, factorii C sunt cunoscuti si nu pot fi
modificati de decident. De risc sau
probabilista – prezenta celor 3 grupuri de factori X, C, Q. Q – element aleatoriu
– starea naturii. Se cunoaste legea de repartitie. De incertitudine – X,C – ca in determinist, Q – factor necunoscut
(incert) care apartine unui domeniu.
Cele mai
cunoscute instrumente folosite pentru
problema de risc sunt: punctul critic, matricea rezultatelor si arborele
decizional. Punctul critic surprinde relatia dintre volumul productiei si nivelul costului,
profitului si încasarilor din vânzarea unui produs, sau a unui grup de produse.
Punctul critic e cel în care costul total si încasarile din vânzari sunt egale.
Punctul critic este cel care marcheaza volumul productiei dincolo de care firma
înregistreaza profit. Punctul de echilibru = prag de rentabilitate – se gaseste
egalând ecuatiile costului total si a veniturilor din încasari: V=q*p; Ct=Cf+Cd;
V=Ct. Matricea rezultatelor se prezinta ca o lista
bidimensionala de cifre sau simboluri aranjate pe linii si coloane care
identifica starile (conditii) posibile ale naturii N, probabilitatea P si
rezultatul Q fiecarei strategii S. Criteriile pe baza carora decidentul
evalueaza strategiile pot fi: criteriul valorii asteptate; criteriul
rationalitatii (criteriul Laplace, aplicabil deciziilor în conditii de
incertitudine); criteriul probabilitatii maxime (pe baza caruia este aleasa
starea naturii cu probabilitate maxima). Astfel, în cazul criteriului valorii
asteptate, decidentul are de calculat valoarea asteptata a fiecarei strategii (V.A.), care este o
medie aritmetica ponderata a rezultatului sau o suma a valorilor conditionale
ponderate cu probabilitatea producerii lor: VA1=p1*Q11+…+pn*Q1n. Arborele decizional se utilizeaza în
deciziile de grup, in conditii de risc si incertitudine. Scheletul arborelui
este format din noduri si linii. Nodurile sunt momente decizionale: cele care
reprezinta deciziile în conditii de certitudine au forma patrata, iar cele ce
sugereaza deciziile în conditii de risc sau incertitudine au forma de cerc.
Liniile reprezinta activitatile sau alternativele posibile. Rezolvarea consta
in calculul sperantei matematice a fiecarei consecinte si alternative decizionale, utilizând
formula: Sm = suma (pi*Ri), 1
3. Modele liniare ale problemelor de cercetare
operaţională: exemple de probleme, modele matematice ale lor.
Structura
generala a modelului liniar se constituie prin multimea de activitati A1…An,
resursele R1…Rn, relatiile tehnico-economice dintre acestea. Legatura dintre
activitati si resurse e determinata de tehnologia de fabricatie pentru
activitatea Aj (1
a11 x1 +
a12 x2 + … + a1n xn <= b1…………………….
am1 x1 +
am2 x2 + … + amn xn <= bm
sau A * x
<= b … (1)
Fiecare
restrictie incorporeaza 2 afirmatii: cantitatea conusmata dintr-o resursa nu
poate depasi volumul disponibil; consumul total Rij din resursa Ri pentru
efectuarea activitatii Aj este proportional cu intensitatea acesteia, adica cu
xj, Rij=aij xj.
Modelul
liniar mai contine un criteriu de performanta, care permite evaluarea
eficientei fiecarei activitati – indicator ce masoara efortul, altul ce masoara
rezultatul, sau unul care e raportul intre acestea doua. Eficienta maxima
inseamna minimizarea efortului si maximizarea rezultatului; optim este un
program xce apartine Rn care minimizeaza sau maximizeaza o functie obiectiv si
satisface toate restrictiile. Daca fiecare componenta a vectorului linie c =
(c1…cn) masoara eficienta unei unitati din rezultatul activitatii Aj atunci
functia liniara care evalueaza performanta oricarui program x este: f(x)=c1 x1
+ … + cn xn.
Structura
concreta a unei aplicatii in economie e determinata de obiecivul urmarit. In
cazul problemei determinarii structurii
de sortimente optime a productiei se cunosc cantitatile disponibile din
fiecare materie prima bi, coeficientii tehnologici aij (cantitatea de materie
prima i necesara fabricarii uneiunitti de produs j), cantitatile maxime xj si
minime xj, profiturile de unitare pj ale fiecarui tip de produs. Se cere
gasirea acelor cantitati xj care trebuie fabricate din fiecare tip de produs
astfel incat sa se obtina profitul maxim. f(x) = p1 x1+…+pn xn ->max; ai1
x1+…+ain xnx
j<=xj<xj, j=1…n, xj<=0. In
unele probleme in loc de profituile pj se cunosc veniturile unitare vj sau
costurile unitare cj scopul fiind maximizarea venitului, minimizarea
costurilor. Pot lipsi restrictiile sau poate exista si alele. La problema de
programare operativa a productiei restrictiile se refera la o serie de masini
cu care se executa produsele, bi fiind disponibilul de timp al utililajului i
pe perioada analizata, aij timpul necesar prelucrarii unui produs de tipul j la
utilajul i, scopul fiind maximizarea productiei. Modelul are forma:
x1+…+xn->max, ai1 x1 +…+ ain xn <= bi, i=1…m, xj>=0. Daca se doreste
obtinerea unui meniu care sa asigure necesarurile bi dintr-un numar de m
substante avand la dispozitie n alimente cunoscand cantitatile aij din fiecare
substanta pe care le contine o unitate de masura din fiecare aliment si
costurile cj unei unitati de masura din fiecare aliment putem scrie modelul: c1
x1 +...+ cn xn -> min, ai1 x1 + … + ain xn >=bi, x>=0. Variabilele x
inacest caz reprezinta cantitatea din fiecare aliment ce va intra in meniu iar
f(x) e costul total al retetei definite de x. Modelul amestecului optim de produse – n tipuri de benzine, amestecul lor
obtine o benzina cu m caracteristici impuse, la pret minim posibil. O serie de
caracteristici trebuie sa fie indeplinite cu o limita inferioara, altele
superioara, altele cu egalitate. De asemenea trebuie de tinut cont de
cantitatile disponibile din fiecare benzina di. Se cunosc caracteristicile
fiecarei benzine dispozibile date intr-o matrice unde aij e valoarea
caracteristicii i pentru benzina j si preturile unitare ale fiecarei benzine,
pj, xj – cantitati de benzina care vor forma amestec optim.
4. Probleme de programare liniară (PPL); formele de
prezentare. Noţiune de soluţie (soluţie admisibilă; soluţie de bază; soluţie de
reper şi soluţie optimă).
Situatiile
economice total diferite sunt aplicatii in sfera activitatii a urmatoarei
probleme de optimizare: max sau min f(x1,…,xn), gi(x1,…,xn)<=bi, x1,…,xn
apartin omega se includ in Rn in care functiile f, gi: Rn -> R pot avea
orice forma si proprietati (liniare, convexe, continui, diferentiabile), omega
poate fi orice submultime din Rn (continua sau discreta, marginita sau
nemarginita, convexa sau neconvexa, finita sau infinita, etc) in care dorim sa
gasim minimul sau maximul functiei f in variabilele xi care indeplinesc
restrictiile. O astfel de problema e de programare
matematica. Dacă într-o problemă de programare matematică funcţia obiectiv
f şi funcţiile gi, din restricţiile 1.2, sunt funcţii liniare atunci problema
se numeşte problemă de programare liniară.
O problemă de programare liniară este, deci, un caz particular al problemelor
de programare matematică. Functia f – e functia obiectiv a problemei de
optimizare, ea reprezinta criteriul de performanta urmarit: maximizarea
beneficiului, productiei marfa, gradului de incarcare al utilajelor,
veniturilor, minimizarea costului productiei, timpului de stationare a
utilajelor, etc. Inegalitatile in care gi sunt funcții de n variabile iar bi
sunt constante – restrictii ale problemei de optimizare – traduc in limbaj
matematic conditiile de natura economica in care se desfasoara procesul
modelat: nedepasirea stocurilor disponibile de resurse, indeplinirea sau
depasirea unor indicatori economici. Omega de cele mai multe ori e multimea
vectorilor x apartin Rn cu toate componentele nenegative. In dependenta de
natura problemei studiate variaza conditiile impuse variabilelor. Forma
standard: {min sau max f = c1 x2 + … + cn xn; ai1 x1 + … + a1n xn = bi,
i=1,…,n; x1,…xn >=0.} Forma canonica de minim: {min f = c1 x1 + … + cn xn;
ai1 x1 + … + a1n xn >= bi, i=1,…,n; x1,…xn >=0.} Forma canonica de maxim:
{max f = c1 x1 + … + cn xn; ai1 x1 + … + a1n xn <= bi, i=1,…,n; x1,…xn
>=0.} Proprietatile solutiei unei astfel de probleme: verifica restrictiile
1.2, verifica restrictiile directe 1.3, optimizeaza functia obiectiv pe multimea
vectorilor care indeplinesc p1 si p2. Solutie
– un vector x apartine Rn care verifica restrictiile 1.2; solutie admisibila – un vector x apartine Rn care verifica
rstrictiile 1.2, 1.3; solutie optima –
un vector x apartine Rn care verifica restrictiile 1.2, 1.3 si optimizeaza
functia obiectiv pe multimea tuturor vectorilor cu aceasta proprietate. O
soluţie de bază care are toate componentele nenule strict pozitive se va numi soluţie de bază admisibilă. Dintre toate
alegerile posibile de solutii este remarcabilă (prin simplitatea ei) soluţia x=0,
care duce la soluţia particulară numită soluţia de
bază. O soluţie optimă care este de bază se va numi soluţie optimă de bază. Se observă că o soluţie de bază are cel
mult m componente diferite de 0. Din cauza importanţei lor în rezolvarea
problemei, vom evidenţia soluţiile de bază care au mai puţin decât m componente
nenule, numite soluţii degenerate şi
pe cele care au fix m elemente nenule, numite soluţii nedegenerate.
5. Proprietăţile fundamentale ale PPL (teoremele
principale). Interpretarea geometrică a PPL.
Metoda grafică de soluţionare a PPL.
T1. Dacă
problema de programare liniară are soluţii admisibile atunci are şi soluţii de
bază admisibile. T2. Dacă problema de programare liniară are soluţii optime
atunci are şi soluţii optime de bază. T3. Mulţimea soluţiilor admisibile
(optime) este închisă şi convexă. Dacă este şi mărginită atunci punctele
extremale ale acesteia sunt chiar soluţiile admisibile (optime) de bază ale
problemei. Restrictiile – dreapta. Functia scop – gradient. Domeniul de
solutii este poligonul format de
restrictii. Metoda grafica consta in
determinarea tuturor varfurilor poligonului de restrictii care e descris de
relatiile 2, 3. Acest poligon reprezinta toate solutiile admisibile inclusiv si
cele optimale. Se foloseste teorema fundamentala T3 in care se mentioneaza ca
solutia optima a unui model liniar este unul dintre varfurile poligonului de
restrictie. Daca am cunoaste toate varfurile poligonului, atunci prin calculul
direct al valorilor functiei am determina aceste valori pentru toate varfurile
selectand varful pe care ia maxim. Se cer reprezentari foarte exacte a
desenului ce prezinta poligonul de restrictii si gradientul functiei scop.
6. Metoda simplex de soluţionare a PPL.
Se
construieste o solutie initiala de baza, solutie admisibila: de regula se ia in
calitate de solutie de baza punctul (0, 0) daca aceasta e admisibila. Caracter
iterativ: la fiecare iteratie are loc trecerea de la o solutie de baza la alta
imbunatatind de fiecare data functia scop. Fiecarei iteratii ii corespunde un
tabel simplex. Trecerea de la un tabel la altul are loc conform metodei
excluderii Jordan Gauss luand in considerare respectarea cirteriului de
optimalitate.
7. Dualitatea în programarea liniară. Teoremele fundamentale
ale teoriei dualităţii.
W(u)=Suma
bi ui -> min; {a11 u1 + … + am1 um>=c1; … ; a1n u1 + … + amn um>=cn.}
modelul dual e problema de minimizare a costurilor materiei prime / resurselor:
se cauta asa preturi u la resurse pentru care costul total al resurselor
disponibile ar fi minimal cu conditia ca costul unei unitati de produs j nu e
mai mic decat pretul unei unitati de produs j. u – este pret umbra a resursei
si e o marime variabila: la cresterea cu o unitate a resursei i bi=>bi+1, ui
corespunzator pt unele situatii va arata cu cat poate creste valoarea maximala
a functiei de venit. Modelul primal si dual sunt reciproce – corespund strict
unui altuia. Primal: z(x)=(x,c)->max, A*x<=b. Dual: w(u)=(b,u)->min,
At*u>=c. T1 (LEMA). U – solutie admisibila in model dual, x – solutie
adimisibila in model primal; z(x)<=w(u). Daca z(x)=w(u) atunci x – solutie
optima in primal si u – solutie optima in dual. T2. Daca una din probleme are
solutie optimala atunci si cealalta problema tot are. T3 (kuhn tacker).
Criteriul dualitatii: fie x – solutie admisibila in primal, u – in dual;
acestea sunt optimale daca se respecta n+m identitati. Primele n: xj(suma aij *
ui - cj)=0, i=1…m. Celelalte m: ui(suma aij * xj - bi)=0, j=1…n. Daca x*>0
(rentabil) atunci resurse totale in costuri Suma aij ui estimate prin pret
umbra coincide cu pretul de vanzare cj. Daca suma >cj => x*<0 -="" nerentabil.="" u="">0 => deficit, u<0> excendent. T4. Uj = dz(x)/dbi –
utilitatea marginala a resursei i; xj = df(u)/dcj – cost marginal a produsului
j.
8. Interpretarea economică a dualităţii în programarea
liniară. Preţurile umbră ale factorilor de producţie şi rolul lor în analiza
modelelor liniare.
Modelul
dual e problema de minimizare a costurilor materiei prime / resurselor: se
cauta asa preturi u la resurse pentru care costul total al resurselor
disponibile ar fi minimal cu conditia ca costul unei unitati de produs j nu e
mai mic decat pretul unei unitati de produs j. u – este pret umbra a resursei
si e o marime variabila: la cresterea cu o unitate a resursei i bi=>bi+1, ui
corespunzator pt unele situatii va arata cu cat poate creste valoarea maximala
a functiei de venit. Uj = dz(x)/dbi – utilitatea marginala a resursei i; U>0
=> resursa deficit, u<0> res excendent.
9. Reoptimizarea, formularea problemei. Soluţionarea
problemei de optimizare în cazul modificării: a) termenilor liberi ai
restricţiilor; b) coeficienţilor funcţiei obiectiv.
Reoptimizarea
are ca scop pastrarea valorii solutiei optimale la variatia unor factori; se
presupune ca deja s-a rezolvat primul model. Factorii care pot varia: preturile
cj, cantitatile de resurse bi, coeficientii tehnologici aij. a) Modificarea
termenilor liberi poate insemna modificarea posibilitatilor de procurare a
materiilor prime prin pierderea unor furnizori sau relizarea de contracte cu
noi furnizori. b) Modificarea coeficientilor functiei obiectiv poate insemna o
reevaluare a profiturilor unitare sau schimbarea obiectivului propus. Z dc =
Suma (cj+dcj) xj -> max. se rezolva modelul primal. Trebuie sa aflam cu cat
se poate modifica pretul unui produs ca solutia sa ramana nemodificata.
10. Problema de transport: probleme echilibrate (închise)
şi dezechilibrate (deschise), modele matematice. Reducerea modelelor deschise
la modelul închis.
Caracteristicile
unei probleme de transport clasice sunt: fiecare sursă aprovizionează cel puţin
o destinaţie şi fiecare destinaţie este aprovizionată de la cel puţin o sursă;
pot exista perechi sursă-destinaţie între care nu se poate face transfer (rute
blocate); nu există limitări în ceea ce priveşte cantitatea transportată pe
fiecare rută; se cunosc cantităţile disponibile în fiecare sursă şi cantităţile
necesare în fiecare destinaţie; fiecărei rute i s-a asociat un cost care nu
depinde de sensul de parcurgere. Scopul problemei este găsirea acelor cantităţi
care trebuie transportate pe fiecare rută astfel încât să se asigure necesarul
fiecărei destinaţii, în limitele cantităţilor aflate la surse, cu costul minim
posibil. Datele problemei sunt: m = numărul de surse (furnizori); n = numărul
de destinatari (consumatori); {Ai, i = 1,...,m} = cantităţile disponibile în
fiecare sursă; {Bj, j = 1,...,n} = cantităţile necesare la fiecare sursă; {cij,
i = 1,...,m; j = 1,...,n} = costurile unitare pe fiecare rută (costul
transportării unei unităţi de măsură de la sursa i la destinaţia j). xij
cantitatea care va fi transportată de la sursa i la destinaţia j. Problema:
Suma cij xij -> min; Suma xij <=Ai (disponibil total), Suma cij >=Bj
(cerere totala); 1. Disponibilul > cererea; xij = Ai Bj / Suma Ai – solutie admisibila;
se va transporta doar necesarul pentru a avea costuri minime. Problema are soluţie optimă, iar cantitatea în exces
faţă de cerere va rămâne la furnizori, fiind reprezentată de variabilele de abatere
din primele m restricţii. Aceste cantităţi pot fi privite ca nişte cereri ale
unui consumator fictiv şi ţinând cont că, de fapt, aceste cantităţi nu sunt
transportate nicăieri, costurile unitare pe rutele care ar lega furnizorii de
acest consumator sunt 0. 2. Chiar dacă disponibilul este mai mic decât
necesarul, nu înseamnă că nu se va mai transporta nimic, ci doar că unora
dintre consumatori nu li se va satisface toată cererea. Această cerere
nesatisfăcută poate fi privită ca disponibilul unui furnizor fictiv şi ţinând
cont că, de fapt, această cantitate nu există, costurile unitare pe rutele care
ar lega consumatorii de acest furnizor sunt 0. Orice problemă poate fi
transformată într-o problemă de tipul disponibil = cerere. Acest tip va fi ales
pentru formalizarea problemei. O astfel de problemă se numeşte problemă de transport echilibrată. Forma
stadard echilibrata: Suma cij xij -> min; Suma xij =Ai, Suma cij =Bj.
11. Soluţionarea problemei de transport prin metoda
potenţialelor.
Daca
modelul e neechilibrat se defineste un furnizor imaginar m+1 (<) cu
cantitatea de oferta imaginara egala cu diferenta dintre am+i=bj-ai sau se
defineste un consumator imaginar n+1 (>) cu cantitatea de cererea imaginara
bn+1=ai-bj. O soluţie nedegenerată
are m+n–1 componente diferite de 0. Rezolvarea
problemei de transport se face în două etape: 1. Găsirea unei soluţii iniţiale
de bază dupa una din metodele nord-vest, minim pe linie, minim pe coloana,
costul minim, diferente maxime; 2. Găsirea soluţiei optime.
12. Modele de probleme ale programării liniare în numere
întregi (programarea discretă). Exemple de probleme ale programării discrete.
Metoda „Ramifică şi Mărgineşte” (Branch and Baund).
In CO se inainteaza cerinta ca solutia propusa sa
se exprime in numere intregi. In alte cazuri o parte din componentele
vectorului optim e nevoie sa fie in numere intregi, celelalte se pot exprima ca
valori nenegative R. Initial au fost propuse cateva metode de rezolvare a
problemelor de tip liniar in numere intregi de cercetatori Gomory, Land,
Danzig. Metoda Gomory a fost propusa doar pentru rezolvare modelului liniar si
se bazeaza pe metoda simplex si pe ideea definirii unor hiperplane ce sepata
subdomenii admisibile care nu contin solutii exprimate in numere intregi. Tehnicile
respective sunt relativ simple si dupa un numar finit de iteratii de tabele
simplex se obtine solutia finala componentele careia sunt numere intregi. Al
doilea tip de metode propuse de Land, Danzig initial pentru modele liniare mai
tarziu generalizate pentru probleme cu caracter general. In litaratura are
denumirea de „ramificari si frontiere / estimatii”. Exemple de probleme care se
exprima in numere intregi: 1. Modelul clasic de productie cu n produse si m
resurse, 4 conditii, maximizarea venitului. 2. Problema transportului –
minimizarea costurilor de transpoprt, ai, bj sunt numere intregi cererea si
oferta in orice punct va fi un numar intreg, la fel si solutia optima cu toate
componentele ei. 3. Problema determinarii unui post de lucru – n specialitati,
n persoane. Daca persoana i va ocupa postul j atunci castigul respectiv ca fi
vij. E necesar: fiecare persoana i sa fie numit intr-un j; fiecare post j sa
fie ocupat de un i; distribuire persoanelor pe posturi trebuie sa fie realizata
astfel incat vij sa fie maximal. Modelul: z(x)= suma vij xij -> max; suma
xij = 1, i=1…n – o pers ocupa un j; suma xij = 1, j=1…n – fiecare post sa fie
ocupat de un j; xij = {1 – i ocupa j; 0 – i nu ocupa j}. Se rezolva problema
prin metoda grafica sau simplex. Daca solutia gasita nu este din numere intregi
se ia coordonata care nu este un numar intreg si se ia numaru intreg de la
capetele numarului…se cauta soluti inafara acestor numere pentru ca intre ele
nu exista nici un numar intreg. Xnumaru ntreg de
sus – acestea sunt 2 restrictii. Termenul ramifica se refera la faptul ca din
problema initiala rezulta 2 probleme noi prin adaugarea la restrictii a uneia
din cele 2 restrictii. Aceste 2 probleme se rezolva prin metoda simplex.
Marginirea se refera la faptul ca valoarea variabilelor care nu erau numere
intregi este marginita superior sau inferior. Solutia optima estea cea solutie
care confera funtiei obiectiv valoarea cea mai mare la probleme.
13. Probleme multicriteriale ale programării liniare.
Metode de soluţionare.
Modelele cu
mai multe criterii – solutii pentru care s-ar realiza maximu sau minimu pentru
cel putin 2 funcții scop. Venit -> max, cost -> min, profit -> max. in
cazul in care toate expresiile din model reprezinta funcții liniare modelul
multicriterial poarta numele de liniar multicriterial. Acelasi x va realiza val
maxima in primul citeriu si minima in al doilea. Fara a limita generalizarea am
putea considera ca toate sunt de maxim, simetria lui z->min in plan, solutia
ramane aceeasi. Exista cateva moduri de solutionare a acestor probleme: 1. „Compozitie”
/ compunere / sinteza – se determina un sir de numere numite prioritati alfa
L1,…,Lr care determina gradul de importanta a criteriului dat astfel incat suma
lor sa fie 1. Se rezolva modelul prin metoda grafica. Se gaseste valoare maxima
in ambele funcții obiectiv. Se defineste o noua functie obiectiv impreuna cu
functiile obiectiv initiale si ponderile cunoscute Z(x)=Li*zi(x)->max. Se
calculeaza valoarea functiei noi in punctele poligonului. Valoarea maxima va fi
solutia. 2. „Includerii criteriilor in restrictii” – criteriul de baza e cel de
maxim, celelalte devin restrictii cu un plafon de considerare Zi(i)>=Zi. 3.
„Concesiilor” / caderilor succesive – z1(x)->max, fie z1* - valoarea maxima
al lui z1. Se determina o cedare de la aceasta valoare de exemplu 10%:
z2(x)->max, z1(x)>=z1*-cedarea. Urmatorul pas e similar cu precedentul.
Solutia de la ultimal pas e considerata optima. 4. Z1(x)->max, x apartine D,
fie x1* - multimea solutiilor, daca e un singur punct e sol optima.
Z2(x)->max, x apartine x1*, x2*-multimea de solutii…etc.
14. Probleme de optimizare pe reţea: problema arborelui
minim , problema drumului minim (maxim) în reţea fără circuite; problema
drumului minim în reţea cu circuite şi metode de soluţionare.
Problema arborelui minim – avem n orase care trebuie
unite intre ele si cunoastem costul Cij; sa selectam graful pentru care costul
este minim (lungimea totala a muchiilor sa fie minima); contine n-1 muchii si
nu are cicluri; metoda de solutionare este algoritmul Kruskal si algoritmul
Prim. Alg. Kruskal – initierea matricii
costurilor; urmeaza n-1 pasi: la fiece pas se selecteaza cite o muchie, astfel
incit costul selectat s fie minim din celelalte din matrice si sa nu formeze
ciclu. Alg. Prim – se alege un nod S
initial, de la el se alege muchia s, j si de pe muchia respectiva (coloana) se
alege valoarea minima Csj; muchia (i,j) unde i € M (muchii selectate), j € M
(neselectate).
Problema drumului minim (maxim) în reţea fără circuite – se da un graf orientat
(cu arce) fara circuite, fiecarui arc i se asociaza un numar Cij. Nodul 1 este
nod cu gradul de incidenta 0 si este nod de intrare in graf; nodul final are
doar arce de sisire. Sa identificam toate retelele d lungime minima ce pornesc
de la nodul 1 pina la toate celelalte noduri. Metoda de solutionare este
algoritmul Ford: se numeroteaza
corect graful prin suprimarea consecutiva a arcelor astfel incit pentru orice
muchie (i,j) i
Problema drumului minim în reţea cu circuite – metode de rezolvare:
alg. Ford (imperfect), alg. Dijkstra (rezolva si problema drum in retea fara
circuite). Alg. Dijkstra – se da un
graf cu circuite, cu arce in ambele sensuri; sa se selecteze rute de lungime
minima ce pornesc dintr-un nod arbitrar S. Se constituie 2 multimi: M cu noduri
selectate si M cu noduri neselectate. Se selecteaza pe rind nodurile
incepind cu un nod de pornire i0=S pentru care ruta optima a fost selectata:
P0: i0=S € M; Ui0=0; Pr(j)=i0; orice j=[1,n]; Ui=Uj, i=j, - distanta optima;
min {Ui0,j}, orice j=[1,n]; j !€ M, j!=S; MuM=|Un|=n; j€M;
Uj1=min{Ui0j} => urmatorul nod. P1: se verifica pentru toate nodurile j€M
pentru Uj>Ui+Cij, i€M, j€M; daca Uj>Ui+Cij=>Uj=Ui+Cij; daca
Uj<=Ui+Cij=>Uj. P2: min{Uj}=Uj; Pr(j) pentru orice j€M; i2=j2€M;…n-1
pasi.
15. Metoda drumului critic (Critical Path of Method).
Graful-reţea şi regulile principale de construire.
Drumul critic şi determinarea lui. Calcularea
caracteristicilor de timp al grafului-reţea. Semnificaţia şi importanţa
caracteristicilor de timp pentru analiza grafului-reţea.
Principiul
analizei drumului critic constă în divizarea unui proiect (acţiuni complexe) în
părţi componente. Ia naştere un tabel care conţine activităţile proiectului,
intercondiţionările între activităţi şi duratele acestora. Un astfel de tabel
trebuie să conţină cel puţin următoarele elemente: activităţi; condiţionări: se
precizează, pentru fiecare activitate, activităţile imediat precedente, prin
simbolurile lor; durata: pentru fiecare activitate se precizează durata de
execuţie, într-o anumită unitate de măsură. Durata unei activităţi este o
constantă. Modelele de analiză a drumului critic se bazează pe reprezentarea
proiectului printr-un graf, elementele tabelului asociat acestuia fiind
suficiente pentru a construi graful corespunzător. Metoda CPM este un procedeu
de analiză a drumului critic în care singurul parametru analizat este timpul şi
în reprezentarea graficului reţea se ţine seama de următoarele convenţii:
fiecărei activităţi i se asociază un segment orientat numit arc, definit prin
capetele sale, astfel fiecare activitate identificându-se printr-un arc;
fiecărui arc i se asociază o valoare egală cu durata activităţii pe care o
reprezintă; condiţionarea a două activităţi se reprezintă prin succesiunea a
două arce adiacente. Nodurile grafului vor reprezenta momentele caracteristice
ale proiectului, reprezentând stadii de realizare a activităţilor (adică
terminarea uneia sau mai multor activităţi şi/sau începerea uneia sau mai
multor activităţi). Pentru reprezentarea corectă a proiectului, cât şi pentru o
standardizare a reprezentării în desenarea grafului se respectă următoarele
reguli: fiecare activitate se reprezintă printr-un arc a cărui orientare
indică, pentru activitate, desfăşurarea ei în timp; un arc este limitat prin
două noduri care simbolizează momentele de început şi de sfârşit ale executării
activităţii corespunzătoare; lungimea fiecărui arc, în general, nu este
proporţională cu lungimea activităţii; deoarece respectarea tuturor regulilor
nu se poate face doar cu arce care corespund doar activităţilor proiectului,
vor exista şi arce care nu corespund nici unei activităţi, care vor fi
reprezentate punctat şi care, pentru unitatea prezentării, vor fi numite
activităţi fictive, ele neconsumând resurse şi având durata 0. In graf nu sunt admise. Nodurile vor fi numerotate,
numerotarea făcându-se în aşa fel încât, pentru fiecare activitate, numărul
nodului de început să fie mai mic decât numărul nodului de final al
activităţii. graful are un singur nod
iniţial ("începerea proiectului") şi un singur nod final
("sfârşitul proiectului"); orice
activitate trebuie să aibă cel puţin o activitate precedentă şi cel puţin una
care îi succede, exceptând bineînţeles activităţile care încep din nodul
iniţial al proiectului şi pe cele care se termină în nodul final al
proiectului; deşi există activităţi
care se execută în paralel, care pot începe în acelaşi moment şi se pot termina
în acelaşi moment, este interzis ca cele două arce corespunzătoare să aibă
ambele extremităţi comune; nu trebuie introduse dependenţe nereale. să se
folosească, pe cât posibil, numărul minim de activităţi fictive, pentru a nu
complica excesiv desenul. Analiza grafului retea: Calculam caracteristicile de
timp: cel mai devreme termen de realizare a evenimentului i: td(i) = maxim care
vine in nod i; cel mai tarziu termen de realizare a ev j: tt(j) = minim care
pleaca din j. SD = td; FT = tt; ST = tt-tij; FD = td+tij; rezerve de timp: Rtot
= FT-FD=ST-SD; Ri = td(j)-tt(i)-tij. Durata critica = termen de realizare cel
mai devreme a ultimului eveniment n, - cel mai mic interval de timp necesar
pentru realizarea intregului proiect.
Daca td=tt se alege drumul critic. Activitatile drumului critic sunt
numite activitati critice. Caracteristicile de timp sunt importante in analiza
grafului retea pentru ca ele duc la determinarea drumului critic.
16. Teoria firelor de aşteptare (teoria cozilor).
Clasificarea sistemelor de servire (aşteptare). Exemple. Fluxul de sosire al
cererilor (comenzilor). Fluxul elementar, testul Pearson(x2) de validare a
legii de repartiţie a probabilităţilor de tip exponenţial (Poisson) a fluxului
de sosire a cererilor şi a timpului de servire.
Teoria
firelor de aşteptare (teoria cozilor) – scop: abonatii sa nu astepte prea mult.
Pentru analiza acestor sisteme se utilizeaza: caracteristicile fluxului de
cereri solicitate sistemului, timpul de servire. Flux de sosire a cererilor –
variabila x(t) – numarul cererilor solicitate sistemului in intervalul de timp
t – variabila aleatoare discreta. Tabelul pentru reprezentare: x(t): 0,1,…,k,…;
p. Legea de distribuire / repartitie a probabilitatii este diferita pentru
fiecare sistem. Distingem: Sisteme deschise: cu sursă infinită de staţii unde
n-numărul staţiilor, iar m –numărul locurilor de aşteptare=0(cu refuz). Sisteme
deschise unde ninf. Sisteme închise, în care sursa este partea
componentă a sitemului de aşteptare, n –numărul staţiilor de servire. Pentru
toate sistemele, fluxul de sosire a cererilor este elementar, adică satisface
următoarele proprietăţi: 1) ordinar; 2) staţionar; 3) independent. Ordinar –
probab solicitarii mai mult de o cerere intr-un interval mic de timp este
infinit mica de ordin superior. Stationar – probab ca in intervalul de timp t
vor sosi k cereri depinde numai de marimea k si t. Independent – probab nu depinde
de nr de cereri solicitate pina la momentul inceperii intervalului t. Fluxul
elementar se mai numeşte flux de tip Poisson – exprima probabilitatea
intimplarii unui numar de evenimente intr-un interval fixat de timp daca aceste
evenimente se intimpla cu o frecventa stiuta si independent de timpul de la
ultimul eveniment. Lambda – intensitatea fluxului de solicitare a sistemului. O
variabila aleatoare discreta are distributie Poisson cu parametrul lambda>0
daca pntru orice k=0,1,2… probabilitatea ei este definita de formula: f(k;
lamda) = P(X=k) = (lambda^k * e^-lambda)/k!.
17. Procese Markov continui după timp şi discrete după
stări. Sistemul de ecuaţii diferenţiale de tip Kolmogorov. Regim de tranziţie
şi de echilibru (staţionar).
In cazul in
care sistemul analizat are un numar finit de stari, iar timpul de observare
este continuu, se obtine un proces markov. Probabilitatea tranzitiei dintr-o
stare in alta la un anumit moment de timp este nula. Deoarece variabila
aleatoare de timp este continua se utilizeaza densitati ale probabilitatii de
tranzitie.
Proces care
se poate afla in una din stari S1…Sn si care in orice moment de timp T poate
trece dintr-o stare in alta. Pi(t) – probab ca in momentul de timp t procesul
poate trece din orice stare Si in starea Sj a procesului fiind influientat de
un flux de evenimente. Pij(t) – probab ca-n momentul de timp t procesul se afla
in starea Si. Pi(dt) – probab ca in
intervalul de timp dt procesul va trece din Si in Sj. Pi(dt) = lambdaij * dt
(elementar Poisson). Lamda – intensitatea de trecere a procesului din o stare
in alta; = nr de treceri / unitate de timp. Procesul Markov poate fi
reprezentat print-un graf „marcat” orientat. Nodurile grafului sunt starile,
trecerile dintr-o stare in alta sunt sagetile. De exemplu: daca avem o retea de
2 calculatoare sunt posibile starile: S0 – ambele calc lucreaza; S1 – s-a
defectat primul; S2 – s-a defectat al doilea; S3 – s-au defectat ambele.
Variabila lambda in acest caz este intensitatea de defectare a compului; miu –
intensitatea de reparare. Sagetile care pleaca dintr-o stare sunt lambda, cele
care vin spre ele e Miu.
Sistemul de
ecuaţii diferenţiale de tip Kolmogorov
– derivata probabilitatilor care
conduc de la orice stare in starea considerata din care se scade suma tuturor
probabilitatilor care conduc din starea considerata in alte stari. pentru
fiecare stare se alcatuieste o ecuatie. Cele care vin in S0 se iau cu + cele
care pleaca – cu minus. Po’(t)=P1Miu1+P2Miu2-P0Lambda1-P0Lambda2.
Se egaleaza cu 0. Po+P1+P2+P3=1; Teoria de rezolvare a sistemului demonstreaza
ca Pk(t) e suma a 2 solutii fk(t) – solutia ecuatiilor omogene si fik(t) –
solutia particulara care verifica conditiile intitiale (solutia de echilibru).
Functionarea sistemului e divizata in 2 etape: de tranzitie si finala de
stabilitate. O stare Si e neesentiala sau de tranzitie daca exista o stare Sj
si un numar n astfel incat Pij(n)>0, Pji(m)=0, pentru orice m. Cand timpul
este continuu in locul numarului de pasi n se poate considera intervalul de
timp dt. O stare neesentiala poate fi atinsa in sistem dar cand este parasita
nu se mai revine in ea. O stare Si e esentiala daca nu exista o alta stare Sj
in care sa se ajunga pe un drum oarecare din Si fara ca sistemul sa mai poate
reveni in Si. Daca Si si Sj sunt esentiale, pentru cazul discret, exista 2
numere naturale m si n pentru care Pij(n)>0, Pji(m)>0, atunci starile se
numesc comunicate. Aceasta relatie e tranzitiva. Ergodic – sistem pentru care
exista limitele probabilitatilot starilor pentru t tinzand la infinit. Pentru
un sistem cu numar finit de stari conditia necesara si suficienta pentru
ergodicitate este ca toate starile esentiale sa fie comunicante. Pentru starile
neesentiale limitele probab starilor sunt 0. Daca un sistem e ergodic limitele
starilor se pot obtine din ecuatiile Kolmogorov in care toate derivatele se
anuleaza. Se obtine un sistem liniar de n ecuatii cu n necunoscute si suma
probabilitatile = 1.
Jordan gauss – un algoritm de rezolvare a sistemelor de ecuatii
liniare. Este inteles ca o secventa de operatii efectuate asupra unei matrici
de coeficienti. Sunt 3 tipuri de operatii elementare efectuate asupra liniei:
schimbare cu locul a doua linii, multiplicarea unei linii cu un numar diferit
de zero, adunarea unui multiplu a unei linii la alta linie pana cand matricea
nu contine cat mai multe zerouri. Sau se foloseste pivotul pentru transformare.
18. Procese „moarte şi renaştere”. Formulele Eurlang.
Caz
particular Kolmogorov. Lant Markov. Se considera un sistem care poate avea un
nr finit de stari S0…Sn In intervalul de timp unic dt, sistemul aflat in starea
Sk poate trece in starea Sk+1 cu probabilitatea Lambdak dt, poate trece in
starea Sk-1 cu probabilitatea miuk dt sau poate ramane in starea Sk cu
probabilitatea 1-(lambdak+miuk)dt. Robabilitatea ca sistemul sa treaca in alte
stari dect cele specificate e neglijabila. E un proces Markov. Lambdak si miuk
sunt dependenti de k, independenti de t, ceea ce inseamna ca e un proces markov
omogen. Acest proces poarta numele de moarte renastere. Daca starea Sk
reprezinta o nastere, iar o tranzitie in starea Sk-1 reprezinta o moarte. Miui
= 0 atunci e un proces de nastere pura. Lambda i = 0 atunci proces de moarte.
Forumele lui Eurlang – 1903 –
P1 = λ01/λ10
* P0.
P1 =
λ12/λ21 * P1.
Pn= P0 * (λ01
* λ12 * … * λn-1 n)/ (λ10 * λ21 * … * λn n-1).
Po=[(1+λ01/λ10)+…+(
λ01 * λ12 * … * λn-1 n)/( λ10 * λ21 * … * λn n-1)^(-1).
19. Sisteme de aşteptare cu refuz deschise şi calcularea
caracteristicilor principale necesare pentru analiză.
20. Sisteme de servire (aşteptare) deschise cu coadă
finită şi infinită; caracteristicile
principale necesare pentru analiza acestor sisteme.
21. Sisteme de aşteptare închise; caracteristicile
necesare pentru analiza acestor sisteme.
