zi im anul 3 sem 1 cercetari operationale azp0i21x734g

8/18/2019 Zi Im Anul 3 Sem 1 Cercetari Operationale Azp0i21x734g

1/41

CERCETĂRI OPERAŢIONALE

Tematică – CURS

I. PROGRAMARE LINIARĂ

1.1. Forme de prezentare ale unei probleme de programare liniară

1.2. Trecerea de la o formă de prezentare la alta

1.3. Soluţiile unei probleme de programare liniară

1.4. Rezolvarea unei probleme de programare liniară

1.5. Dualitate în programarea liniară

II. PROBLEME DE OPTIMIZARE ÎN REŢELE DE TRANSPORT

2.1. Modelarea problemelor de transport

2.2. Adaptarea metodei simplex la rezolvarea problemei de transport

2.3. Variante ale problemei de transport

III. MODELE MATEMATICE PENTRU GESTIUNEA STOCURILOR

3.1. Noţiuni generale

3.2. Modele deterministe

3.3. Modele probabiliste

IV. ELEMENTE DE TEORIA GRAFURILOR

4.1. Concepte de bază

4.2. Matrici asociate unui graf

4.3. Găsirea drumurilor într -un graf orientat

4.4.

Determinarea drumurilor hamiltoniene

4.5. Drumuri de valoare optimă într-un graf

V. TEST PENTRU EVALUAREA CUNOŞTINŢELOR.

ANALIZA REZULTATELOR


2/41

Tematică - SEMINAR

1. Probleme economice care conduc la modele de optimizare liniară

-

folosirea eficientă a resurselor limitate - alocarea optimă de fonduri băneşti

- probleme de nutriţie

2. Rezolvarea unei probleme de programare liniară

- metoda grafică

- algoritmul simplex

3. Dualitate în programarea liniară.

4. Interpretarea economică a dualităţii

5. Rezolvarea problemei de transport

6. Variante ale problemei de transport

7. Modele matematice pentru gestiunea stocurilor

-

modele deterministe

- modele probabiliste

8. Determinarea drumurilor într-un graf orientat; drumuri hamiltoniene

- algoritmul lui Chen

- algoritmul lui Kaufmann

9.

Drumuri de valoare optimă într -un graf- algoritmul Bellman-Kalaba


3/41

I. PROGRAMARE LINIARĂ

1.1. Forme de prezentare ale unei probleme de programare liniară

FORMA GENERALĂ

Se spune că o problemă de programare liniară (P.P.L.) este prezentată sub forma generală

dacă este scrisă astfel: [] ⋯ ⋯ , 1 ⋯ , 1 ⋯ ≥ , 1

≥ 0 , 1 0 , 1 ∈ ℝ , 1 Deci o P.P.L. este dată sub forma generală dacă, indiferent de scopul optimizării (min sau

max), aceasta are restricţii de toate felurile şi variabile de toate semnele.

Observaţie. Când se spune că ∈ ℝ ( x are semn oarecare) înseamnă că oricare dinrezultatele > 0 sau < 0 sau 0 poate fi acceptat.FORMA STANDARD

O problemă de programare liniară este prezentată sub forma standard dacă este scrisă astfel:

[] = = , 1 ≥ 0 , 1 sau matricial:

[]

≥ 0


4/41

unde: ()≤≤≤≤ ∈ ℳ×ℝ, , , … , ∈ ℝ ,

⋮ ∈ ℝ

,

⋮ ∈ ℝ

Deci o P.P.L. este dată sub forma standard dacă aceasta are toate restricţiile egalităţi şi toate

variabilele nenegative.

FORME CANONICE

Forma canonică de max. [] ∑ = = , 1 ≥ 0 , 1

sau matricial:

[]

≥ 0 Forma canonică de min. [] ∑ =

≥ = , 1

≥ 0 , 1

sau matricial: [] ≥ ≥ 0


5/41

1.2. Trecerea de la o formă de prezentare la alta

Trecerea de la forma generală la forma standard

Procedura de trecere comportă două etape:

Etapa I Pozitivitatea variabilelor problemei - se obţine printr -o schimbare de variabilă

sau transformare liniară, astfel:

, , + , ≥ 0 , ≥ 0 , ≥ 0, + ≥ 0 ,

ă ≥ 0ă 0ă ∈ ℝ , ∈ 1, ̅ Observaţie. Orice număr real se poate scrie ca diferenţa a două numere reale pozitive.

Etapa a-II-a Transformarea inegalităţilor în egalităţi - se face prin introducerea unor

variabile de compensare (egalizare, ecart ) nenegative, prin adunarea la membrul cel mic al

fiecărei inegalităţi:

dacă ∑ = , atunci ∑ = , ≥ 0 dacă ∑ ≥ = , atunci ∑ = , ≥ 0 sau

echivalent ∑ = , ≥ 0 Obsevaţie. Nu există nici o legătură între variabilele de la transformarea de semn şi cele de

compensare. Pot fi aceleaşi litere sau nu, dar cu alţi indici. Variabilele de compensare intră în

funcţia obiectiv cu coeficienţii zero.

Trecerea de la forma canonică la forma standard

Deoarece în ambele forme de prezentare (canonică, standard) variabilele sunt nenegative,

trecerea de la forma canonică la forma standard înseamnă transformarea inecuaţiilor în ecuaţii

prin introducerea variabilelor de compensare.


6/41

Trecerea de la forma generală la forma canonică

Procedura de trecere comportă 2 etape:

Etapa I Pozitivitatea variabilelor problemei

Etapa a-II-a Transformarea tuturor restricţiilor în inegalităţi de acelaşi sens, operaţiune care

are la bază următoarele echivalenţe:

⟺ ≥ ⟺

≥ şi înmulţirea uneia dintre ele cu (-1).

1.3. Soluţiile unei probleme de programare liniară

Soluţii posibile

Fără a diminua generalitatea problemei, vom presupune că aceasta este prezentată subforma standard:

[]

(*) ≥ 0 unde: ()≤≤≤≤ ∈ ℳ×ℝ, , , … , ∈ ℝ ,

⋮ ∈ ℝ , ⋮ ∈ ℝ.Definiţia 1. Se numeşte soluţie posibilă (admisibilă, realizabilă) a P.P.L. (*), orice

vector ∈ ℝ care satisface simultan restricţiile problemei precum şi condiţiile de semn. Mulţimea soluţiilor posibile se va nota cu:

∈ ℝ ⁄ ş ≥ 0


7/41

Pentru o P.P.L. se poate ca mulţimea soluţiilor posibile să se afle într -una din situaţiile:

1. Ø (este mulţimea vidă), caz în care se spune că restricţiile problemei suntcontradictorii;

2. se reduce la un singur punct , caz în care nu există posi bilitatea alegeriicelei mai bune soluţii pentru că soluţia posibilă fiind unică ea este şi cea mai bună şi

cea mai rea;

3. are cel puţin 2 elemente, caz în care există posibilitatea alegerii celei mai bunesoluţii, printr -un procedeu sau algoritm specific.

Din punct de vedere practic, primele două cazuri sunt lipsite de interes.

Teorema 1. Mulţimea soluţiilor posibile este convexă, adică odată cu oricare două puncte ale sale, segmentul care le uneşte aparţine, de asemenea, mulţimii:∀ , ∈ , segmentul [, ] 1 ∕ ∈ [0,1] ⊂ .

Teorema 2. Dacă o P.P.L. (în variabile continue) admite mai mult de o soluţie posibilă,atunci ea admite o infinitate de soluţii posibile.

Soluţii de bază

Fie , , … , ∈ ℳ×ℝ matricea restricţiilor problemei, unde coloana conţine coeficienţii necunoscutei a sistemului de restricţii, 1 .

Sistemul de restricţii, scris desfăşurat, poate fi pus sub forma:

⋯ (**)unde:

⋮ ∈ ℝ, 1 .

Deci, vectorul b poate fi exprimat ca o combinaţie liniară a vectorilor

(

)∈,̅ din

acelaşi spaţiu liniar ℝ.


8/41

Având în vedere compatibilitatea sistemelor de ecuaţii liniare, pentru programarea

liniară prezintă interes cazul în care sistemul de restricţii (**) este compatibil nedeterminat,

ceea ce are loc dacă:

, < Din acest motiv, să presupunem că:

, < .Observaţie. Dacă , < < , atunci se poate renunţa la (m-r )restricţii, deoarece prezenţa sau absenţa lor nu influenţează asupra existenţei soluţiei

problemei.

Definiţia 2. O soluţie posibilă a P.P.L. (*) se numeşte soluţie de bază dacă îndeplineşteurmătoarele condiţii:

1. are cel mult m componente strict pozitive, iar celelalte sunt nule.2. coloanele matricei A corespunzătoare componentelor strict pozitive sunt vectori liniar

independenţi (din ℝ).Definiţia 3. O soluţie de bază a P.P.L. (*) se numeşte:

nedegenerată - dacă are exact m componente strict pozitive;

degenerată – dacă are mai puţin de m componente strict pozitive.

Vom nota cu mulţimea soluţiilor de bază; ⊂ . Dacă ≠ ∅ , atunci ≠ ∅ .Avem dacă ∅ sau se reduce la un punct.

Teorema 3. Dacă , < , atunci numărul soluţiilor de bază aleP.P.L. (*) satisface condiţiile:0

Teorema 4. Orice soluţie de bază a P.P.L. (*) este vârf al mulţimii soluţiilor posibile ale problemei şi reciproc.

Deci ≡ ţ â


9/41

Observaţie.

Un punct ∈ se numeşte punct extrem sau vârf al mulţimii convexe ⊂ ℝ dacă nuexistă nici o pereche de puncte , ∈ şi ∈ 0,1 astfel încât 1 . Geometric, este vârf al lui C orice punct care nu se poate afla pe nici un segment de dreaptăîn interiorul segmentului.

Soluţii optime

Definiţia 4. O soluţie posibilă ∈ a problemei P.P.L. (*) se numeşte soluţie optimă dacă satisface şi cerinţa de optim:

[opt]∈

Notăm cu: ∈ ⁄ [opt]∈ } ⊆ mulţimea soluţiilor optime. Avem dacă ∅ sau se reduce la un punct.Definiţia 5. Se spune că o P.P.L. admite:

optim unic – dacă conţine un singur element; optim multiplu – dacă conţine cel puţin 2 elemente. Teorema 5. Mulţimea soluţiilor optime a unei P.P.L. este mulţime convexă. Prin urmare, dacă problema admite două soluţii optime distincte, atunci aceasta admite o

infinitate de soluţii optime.

Teorema 6. Soluţia optimă a P.P.L. (*) se află printre vârfurile mulţimii soluţiilor posibile ale problemei. ⊆ ⊆ Dacă P.P.L. are optim finit, atunci acesta se află într-un vârf al lui (tronson sau

poliedru convex).

Dacă P.P.L. are optim infinit, putem admite că acesta este atins în punctul de la infinit (care aparţine lui numai când este nemărginită).


10/41

1.4. Rezolvarea problemei de programare liniară

METODA GRAFICĂ comportă următoarele etape:

1. se determină grafic mulţimea soluţiilor posibile ;2. se determină mulţimea soluţiilor de bază , adică mulţimea vârfurilor lui ;3. se determină mulţimea soluţiilor optime , calculând valoarea funcţiei obiectiv în

fiecare vârf al lui şi alegând, după caz, valoarea cea mai mică sau cea mai mare. Observaţii.

1. Metoda grafică este limitată ca aplicare la probleme cu două şi, uneori, cu treivariabile.

2. Este însă utilă pentru a putea ilustra grafic mulţimile , şi , având astfel o bază de discuţii pentru problemele cu mai multe variabile.

METODA ALGEBRICĂ comportă următoarele etape:

1.

se determină toate soluţiile de bază ale sistemului de restricţii;

2. se determină soluţia optimă, calculând valoarea funcţiei obiectiv pentru fiecare soluţiede bază şi alegând, după caz, valoarea cea mai mică sau cea mai mare.

Prin urmare, atât metoda grafică, cât şi metoda algebrică, presupun parcurgerea a două etape:

Etapa I - etapa de enumerare a soluţiilor de bază

Etapa a-II-a - etapa de evaluare a soluţiilor de bază.

De fapt, aceasta este metoda de enumerare şi evaluare a soluţiilor, întâlnită şi în alte clasede probleme de optimizare.


11/41

METODA SIMPLEX

Scopul metodei simplex este de a alege soluţia optimă pornind de la un vârf oarecare al lui

, adică de la o soluţie de bază, şi trecând apoi la un alt vârf care să fie o soluţie mai bună

decât precedenta (în sensul optimului).

Algoritmul simplex va lua sfârşit în două situaţii şi anume:

s-a ajuns la cea mai bună soluţie, constatându-se dacă problema are optim unic saumultiplu;

nu se poate ajunge la cea mai bună soluţie (pentru că nu există) şi se ia decizia că problema nu are optim finit (problema are “optim infinit”).

Întrebările la care trebuie să răspundă orice metodă de rezolvare a unei probleme deoptimizare, în particular şi metoda simplex, sunt următoarele:

Cum pornim?

Cum trecem de la o soluţie la alta?

Cum ne oprim?

Presupunem că problema de programare liniară (P.P.L.) este prezentată (adusă)

la f orma standard: [] ≥ 0 unde: ∈ ℳ×ℝ, ∈ ℝ, ∈ ℝ, ∈ ℝ.Observaţie. Deoarece [] [], este neesenţială alegerea unei problemecare cere maximizarea funcţiei obiectiv. Presupunem < ; rezultă că are cel puţin 2 elemente. Cum este mulţime convexă,rezută că are o infinitate de elemente, situaţie în care P.P.L. prezintă interes din punct devedere practic.

Notăm matricea sistemului de restricţii , , … , , unde este coloanacoeficienţilor necunoscutei

,

∈ ℝ,

∈ 1, ̅.


12/41


13/41

Observaţie. În practică se urmăreşte ca baza iniţială să fie formată din vectorii unitari, adică

să fie baza canonică , , … , ⊂ ℝ.Fie

∈ ℝ soluţia de bază a P.P.L. corespunzătoare bazei B:

> 0, 1 0, 1 Deci ∈ ℝ, unde: − ∙ ∈ ℝ.În practică se lucrează doar cu componentele > 0.Valoarea funcţiei obiectiv în soluţia de bază este:

∙ ∙ ∙ ∙ ∙ .

Prin urmare, de interes în continuare vor fi: , şi .

Notăm: ∙ ∙ − ∙ , 1 ∙ − ∙ , 1 şi cu Δ 0, 1 , 1 .

Prin urmare, diferenţele corespunzătoare coloanelor vectorilor bazei curente sunt nule.


14/41

Macheta de început a tabloului simplex (tabel informaţional care uşurează derularea

calculelor) este:

…

…

+

…

…

… … + … … 1 … 0 … 0⋮ ⋮ ⋮ ⋮ … ⋮ … ⋮ −

0

… 1

… 0

⋮ ⋮ ⋮ ⋮ … ⋮ … ⋮ 0 … 0 … 1 0 … 0 … 0 Δ+ … Δ … Δ

CRITERIUL DE OPTIM

Dacă toate diferenţele Δ 0, 1 , atunci problema de programare liniară admiteoptim finit şi e soluţie optimă.

Pentru ca acest criteriu de optim să poată fi folosit indiferent de scopul optimizării ( max sau

min), diferenţele se calculează:

Δ , 1 , pentru , 1 , pentru


15/41

ÎMBUNĂTĂŢIREA SOLUŢIEI

CRITERIUL DE INTRODUCERE ÎN BAZĂ

Dacă există un indice nebazic , 1 pentru care Δ > 0 , atunci se poate găsio nouă soluţie de bază cel puţin la fel de bună ca şi vechea soluţie de bază (în sensul

optimului).

Dacă există mai multe diferenţe Δ > 0, atunci se poate alege oricare vector corespunzător,fără a influenţa soluţia finală.

De regulă, se alege pentru care:Δ max≤≤Δ Δ⁄ > 0}

CRITERIUL ELIMINĂRII DIN BAZĂ

Dacă există un indice nebazic , 1 pentru care Δ > 0, atunci se poateobţine o nouă bază şi, deci, o nouă soluţie de bază, eliminând din vechea bază B vectorul, 1 pentru care:

min≤≤

> 0

unde: ⋮ sunt coordonatele (în baza B) vectorului determinat la criteriul de

intrare în bază.

Deci vectorul

părăseşte baza, iar în locul lui va intra vectorul

. Cu alte cuvinte, nu

stricăm baza în totalitate.


16/41

Observaţie. Efectuând rapoartele de la criteriul eliminării din bază, se poate întâmpla ca:

1. Să existe două sau mai multe rapoarte minime egale, caz în care poate părăsi baza

B oricare dintre vectorii care conduc la acest rezultat fără să fie afectată soluţia

optimă.

2. Să nu existe nici un > 0 (adică 0, 1 ), caz în care algoritmul iasfârşit cu decizia de “optim infinit ”

CRITERIUL DE OPTIM MULTIPLU

Dacă , şi există măcar un indice , pentru care , atunci problema poate admite optim multiplu: admite optim multiplu - dacă măcar un element al coloanei este strict pozitiv,

necesar determinării vectorului care părăseşte baza;

nu admite optim multiplu – dacă 0, 1 .


17/41

1.5. Dualitate în programarea liniară

Definiţia 1. Fiind dată problema de programare liniară:

[] (P)

≥ 0 (1)se numeşte duală a acesteia, problema:

[]

(D) ≥ ≥ 0 (2)Problema (1) se numeşte primala, iar problema (2) se numeşte duala şi reciproc. Perechea de

probleme (1) – (2) se numeşte cuplu dual sau cuplu de probleme duale.

Teoremă. Duala dualei unei probleme de programare liniară este chiar problema de optimizare dată.

Altfel spus, duala dualei coincide cu primala.

Definiţia 2. Se spune că o problemă de programare liniară are restricţiile concordante cu funcţia obiectiv, dacă aceasta are forma de prezentare:

[]

sau[]

≥

indiferent ce semne au variabilele problemei.

Observaţie.

Cel mai frecvent definiţia dualităţii sau a cuplului de probleme duale este dată prin

intermediul cuplului (P) – (D) din definiţia 1. În acest caz se introduce aşa numitul concept de

dualitate simetrică. Pornind de la dualitatea simetrică se poate deduce apoi orice cuplu de

probleme duale, cupluri de dualitate nesimetrică.


18/41

Între problemele unui cuplu primal-dual există anumite legături precise a căror cunoaştere

înseamnă posibilitatea scrierii dualei oricărei probleme de programare liniară:

dacă problema primală cere maximizarea funcţiei obiectiv, atunci în problema duală

se va cere minimizarea funcţiei obiectiv şi reciproc;

numărul de restricţii ale primalei indică numărul de variabile ale problemei duale şi

reciproc;

numărul de variabile ale primalei indică numărul de restricţii ale dualei şi reciproc;

termenii liberi din primală devin coeficienţi ai funcţiei obiectiv din duală şi reciproc;

coeficienţii funcţiei obiectiv din primală devin termeni liberi în duală şi reciproc;

dacă primala are matricea A a coeficienţilor necunoscutelor sistemului de restricţii,

atunci duala va avea ca matrice

;

dacă primala are restricţii:

inegalităţi concordante,

inegalităţi neconcordante,

egalităţi,

acestora le corespund în duală, respectiv:

variabile ≥ 0,

variabile ≤ 0,

variabile de semne oarecare (∈ ℝ. dacă primala are:

variabile ≥ 0,

variabile ≤ 0,

variabile de semne oarecare (∈ ℝ,acestora le corespund în duală, respectiv:

inegalităţi concordante,

inegalităţi neconcordante,

egalităţi.


19/41

Teorema fundamentală a dualităţii

Pentru orice cuplu de probleme duale este adevărată întotdeauna una şi numai una dinafirmaţiile următoare:

1.

dacă una din probleme are optim infinit, atunci cealaltă nu are soluţii posibile;2. niciuna din probleme nu admite soluţii posibile;

3. dacă una din probleme are optim finit, atunci şi cealaltă are optim finit şi valorile

optime ale celor două funcţii obiectiv coincid.

Teorema ecarturilor complementare

Fie şi două soluţii posibile ale cuplului dual:(P) [] ≥ 0 (D) [] ≥ ≥ 0 Condiţia necesară şi suficientă ca şi să fie soluţii optime este aceea ca ele să satisfacărelaţiile: 0 şi 0 Pe componente, relaţiile anterioare devin:

=

= 0 şi

= 0

=

Prin urmare:

dacă soluţia optimă

a primalei satisface cu inegalitate strictă restricţia i a

problemei, atunci 0, ∈ 1,̅ ; dacă soluţia optimă a dualei satisface cu inegalitate strictă restricţia j a problemei,

atunci 0, ∈ 1, ̅ ; dacă o componentă a soluţiei optime a dualei este strict pozitivă, atunci soluţia

optimă a primalei satisface cu egalitate restricţia i a problemei, ∈ 1, ̅ ; dacă o componentă a soluţiei optime a primalei este strict pozitivă, atunci soluţia

optimă a dualei satisface cu egalitate restricţia j a problemei, ∈ 1, ̅ .


20/41

Evident că fiecare dintre cele două probleme ale cuplului dual (P) – (D) poate fi soluţionată

direct cu algoritmul simplex.

Într-un astfel de context, se pun două întrebări:

1. poate fi dedusă soluţia uneia dintre probleme pe baza rezolvării celeilalte?

2. dacă răspunsul la prima întrebare este afirmativ, care dintre probleme poate fi

soluţionată mai rapid (mai eficient)?

Teoremă.

Dacă una din problemele duale (P) – (D) are soluţie optimă, atunci soluţia optimă a celeilate

este dată de diferenţele

Δ corespunzătoare variabilelor de compensare ale problemei

rezolvate, considerate în valoare absolută (|Δ|).În practică nu se dă un cuplu dual, ci doar o problemă de programare liniară care poate fi

rezolvată direct sau prin intermediul dualei sale. De regulă, se alege problema de maximizare

deoarece soluţionarea este mai rapidă.


21/41

II. PROBLEME DE OPTIMIZARE ÎN R EŢELE DE TRANSPORT

2.1. Modelarea problemelor de transport

Într-o mare varietate de contexte se pune problema deplasării unei cantităţi Q dintr-un

produs omogen ce poate fi materie, energie, informaţie etc., din unele locuri numite surse

(depozite, furnizori) în alte locuri numite destinaţii (centre de consum), această deplasare

realizându-se pe anumite rute de legătură.

Presupunem că produsul omogen este disponibil în depozitele , , … , şi estecerut în centrele de consum

, , … , .

Se cunosc:

disponibilul depozitelor (oferta);

necesarul centrelor de consum (cererea);

costurile unitare de transport de la fiecare deposit la fiecare centru de

consum.

Din punct de vedere economic, se pune problema satisfacerii cererii în centrele de

consum la un cost total de transport minim.

Notăm cu:

– disponibilul depozitului , ∈ 1,̅ ; - necesarul centrului de consum , ∈ 1, ̅ ;

- costul unitar de transport pe ruta

( , ), ∈ 1, ̅ , ∈ 1, ̅.

Notăm cu - cantitatea transportată de la depozitul la centrul de consum , ∈ 1, ̅ , ∈ 1, ̅ .


22/41

Pentru a evita explicaţii şi scrieri numeroase, în prezentarea unei probleme de transport, se

recurge la sintetizarea tuturor informaţiilor legate de ofertă, cerere, costuri unitare, într -un

tabel.

DEPOZITE CENTRE DE CONSUM Disponibil … … … … … … ⋮ ⋮ ⋮ … ⋮ … ⋮ ⋮

⋮ ⋮ ⋮ … ⋮ … ⋮ ⋮ … … Necesar … … Din punct de vedere matematic, se pune problema:

Să se stabilească ce cantităţi trebuie transportate de la fiecare depozit la fiecarecentru de consum astfel încât costul total al transportului să fie minim.

Modelul matematic al problemei clasice de transport este:

Să se determine ∗ , ∈ 1, ̅ , ∈ 1, ̅ care satisfac:

[] == , ∈ 1,̅= , ∈ 1, ̅= > 0, ∈ 1,̅ , ∈ 1,̅


23/41

Remarcăm faptul că problema de transport (P.T.) este o problemă de programare liniară în

forma standard, cu restricţii şi × variabile.Se demonstrează că:

1 Prin urmare, orice soluţie de bază a P.T. are cel mult componente nenule. Distingem:

solu ţie de bază nedegenerată - are exact 1 componente nenule; soluţie de bază degenerată - are mai puţin de 1 componente nenule.

Conceptul de “soluţie de bază nedegenerată” este foarte important în soluţionarea

problemei de transport.

Se spune că o problemă de transport este:

echilibrată - dacă oferta totală este egală cererea totală, adică:

== neechilibrată - dacă oferta totală este diferită de cererea totală, adică:

≠

=

=

Conceptul de echilibrare este fundamental pentru algoritmul de căutare a soluţiei optime.


24/41

2.2. Adaptarea metodei simplex la rezolvarea problemei de transport

Rezolvarea problemei de transport se face în ipoteza de echilibrare (P.T.E.), adică:

== Fiind o problemă de programare liniară, P.T.E. se poate rezolva cu ajutorul metodei

simplex (volum mare de calcule).

Datorită proprietăţilor matricei A, (generate de forma acesteia, elementele sunt 0 şi 1),

algoritmul simplex are în acest caz o descriere specifică cunoscută în literatura de specialitate

sub denumirea de metoda potenţialelor .

Pasul 1. Se determină o soluţie iniţială de bază prin:

metoda colţului de N -V (simplă, însă, neţinând cont de criteriul economic al

costurilor, conduce la soluţii cu cost ridicat);

metoda minimului pe linie, metoda minimului pe coloană, metoda

minimului din tabel - acordă prioritate rutelor „mai ieftine”, prin urmare,

dau soluţii mai apropiate de soluţia optimă;

metoda diferenţelor maxime (Vogel) – mai elaborată, însă, foarte eficientă

(uneori dă chiar soluţia optimă).

Pasul 2. Se testează soluţia de bază nedegenerată cu ajutorul unui criteriu de optim:

dacă soluţia este optimă - STOP.

dacă soluţia nu e optimă - se îmbunătăţeşte (pasul 3)

Pasul 3. Îmbunătăţirea soluţiei de bază: 3.1. se determină o variabilă dintre variabilele nebazice care urmează

să devină variabilă bazică (nenulă);

3.2. se determină o variabilă dintre variabilele bazei curente

care părăseşte baza.

Astfel, se obţine altă soluţie de bază care se testează (pasul 2).


25/41

Rezolvarea problemei de transport neechilibrate

În vederea soluţionării, problema de transport neechilibrată trebuie adusă la o

problemă de transport echilibrată. Distingem următoarele situaţii:

dacă ∑ > ∑ == (oferta depăşeşte cererea), atunci, pentru echilibrare, seintroduce un consumator fictiv, +, al cărui necesar este + ∑ ∑ == şi ale cărui costuri unitare sunt nule, adică: ,+ 0, ∈ 1, ̅ ;

dacă

∑


26/41

III. MODELE MATEMATICE PENTRU GESTIUNEA STOCURILOR

3.1. Noţiuni generale

Prin stoc înţelegem o rezervă de bunuri materiale destinate vânzării sau folosirii în procesul

de producţie. Constituirea stocurilor presupune:

cheltuieli de aprovizionare sau producţie;

cheltuieli de stocare (depozitare, întreţinere etc.);

pierderi pentru deprecierea mărfurilor şi altele.

Orice gestiune de stoc presupune intrări în stoc sau aprovizionări şi ieşiri din stoc, acestea

putând avea un caracter determinist sau aleator.

Deciziile ce se iau în organizarea ştiinţifică a stocurilor au la bază un criteriu de optim,

determinat de politica economică, acesta fiind de obicei costul total minim.

Politica optimă reprezintă activitatea de management a stocurilor care implică un cost total

minim. Elementele unei politici optime sunt:

nivelul optim al stocurilor;

volumul optim al unei comenzi de reaprovizionare;

perioada optimă de reaprovizionare;

numărul optim de reaprovizionări etc.

3.2. Modele deterministe

Modelul 1. Gestiunea (stoc) cu perioadă fixă, cerere constantă şi fără posibilitatea lipsei de stoc.

Considerăm gestiunea unui stoc de cantitatea Q, pe un interval de timp θ, cu aprovizionări la perioade fixe (T ), de cantitate conform cererii constante( q).

Presupunem cunoscute: cantitatea Q; perioada de gestiune θ ; costul unitar de stocare , pe unitatea de cantitate şi pe unitatea de timp; costul de lansare a unei comenzi , pentru volumul întregii comenzi.

Presupunem că lansarea comenzii se face în timp util şi aprovizionarea se realizează înmomentul în care s-a epuizat stocul s; de asemenea, presupunem că stocul se consumăuniform (variaţie liniară) şi nu se admite lipsa de stoc.

Criteriul de optim va fi costul total minim.


27/41

Pentru fiecare perioadă T avem următoarele cheltuieli:

1

2∙ ∙ ∙

Numărul aprovizionărilor este:

Costul total al gestiunii cantităţii Q pe perioada va fi:

12 ∙ ∙ ∙ ∙ 12 ∙ ∙ ∙ ∙ Înlocuind corespunzător, putem exprima costul total doar în funcţie de variabila q, astfel:

1 ∙ ∙ 12 ∙ ∙ ∙ Determinăm: min

determinăm punctele staţionare ale funcţiei , adică soluţiile ecuaţiei:′ ∙ ∙ ∙ ∙ 0 ⟹ ∙∙ ⟹ ∙∙ punct critic pentru ; din considerente economice,

luăm pentru numai valori pozitive. ′′ ∙ ∙ . Cum ′′ > 0 rezultă este punct de minim pentru .

Deci elementele unei politici optime sunt:

2

ˆ

s

l

c

cQq

volumul optim al unei comenzi

2ˆˆ

l

s

c

cQ

q

Qv

numărul optim de aprovizionări

2

ˆ

ˆ

s

l

cQ

c

vT

perioada optimă de aprovizionare

2ˆ sl ccQC gestiunea optimă


28/41

Modelul 2. Gestiunea (stoc) cu perioadă fixă, cerere constantă şi cu posibilitatea lipseide stoc.

Considerăm gestiunea de la modelul 1, cu modificarea că se admite lipsa de stoc, dar penalizată cu un cost unitar de penalizare

.

Perioada constantă T o împărţim în două subperioade:

- în care stocul satisface cererea > ; - în care stocul nu mai satisface cererea > .

Criteriul de optim este costul total minim.

În perioada se va plăti pentru stocul mediu ∙ costul unitar , adică cheltuielile mediide stocare:

∙ ∙ .În perioada avem lipsă de stoc penalizată cu costul unitar , deci se vorînregistra cheltuielile medii de penalizare:

− ∙ ∙ Costul total al gestiunii va fi:

, 2 ∙ ∙ 2 ∙ ∙ ∙ Din relaţiile:

, − ⇓ ⇓

∙ − ∙ Înlocuind

şi

în expresia funcţiei cost total, obţinem:

, ∙ 2 ∙ ∙ ∙ 2 ∙ ∙ ∙ Punctele de extrem ale funcţiei , se vor găsi printre punctele staţionare, adică soluţiilesistemului:

, 0, 0

⟹

,̂ punct staţionar

Se demonstrează că acesta este şi punct de minim pentru , .


29/41

Deci o politică optimă presupune:

∙∙∙ ∙

⟹ volumul optim al unei comenzi,

unde: + se numeşte factor de penalizare.̂ ∙ ∙∙∙ ∙ √ ⟹ stocul optim

∙∙

∙

∙ √

⟹ numărul optim de aprovizionări

∙∙∙ ∙ ⟹ perioada optimă de aprovizionare √ 2 ∙ ∙ ∙ ∙ ∙ ⟹ gestiunea optimă

3.3. Modele aleatoare

Gestiune (stoc) cu cerere aleatoare, cu pierderi în cazul surplusului de stoc, cu cheltuielisuplimentare în cazul lipsei de stoc şi cu cost de stocaj neglijabil.

Notăm cu s stocul la un moment dat dintr-un anumit tip de marfă şi cu X variabila aleatoarece reprezintă cererea din această marfă, având repartiţia:

: , 0,1,2,…,, pentru cerere discret ă unde: < ≥ 0, ∀ 0,1, … , ∑ = 1 sau : , ∈ [0, ∞], pentru cerere continuă unde: este densitatea de repartiţie a variabilei aleatoare X ,

< ∫ − este funcţia de repartiţie a v.a. X


30/41


31/41

Aplicând penalizările unitare şi mediilor şi , putem determina valoareamedie a cheltuielilor :

∙ ∙ ∙ ∙

=+

=

Criteriul de optim va fi costul total minim:

min Cum este o funcţie discretă, rezultă că minimul ei va fi atins în punctul ̂ pentru care:

̂ 1 > ̂̂ 1 > ̂

Prin urmare, pentru a determina stocul optim ̂ trebuie să rezolvăm sistemul de inecuaţii: 1 > 1 >

Stocul optim ̂ este acea valoare a lui s care satisface relaţia: 1 < < (*)

unde: ∑ = este funcţia de repartiţie a variabilei aleatoare cerere X , + este raport de penalizare.Observaţii.

1. Deoarece funcţia de repartiţie este nedescrescătoare, din relaţia (*) rezultă că ̂ este un minim absolut pentru funcţia cost mediu.

2.

Dacă 1 < , atunci ̂ ̂ 1, deci minimul funcţiei costmediu are loc pentru două valori ̂ şi ̂ 1.3. Dacă 1 < , atunci ̂ 1 ̂, deci minimul funcţiei cost

mediu are loc pentru două valori ̂ 1 şi ̂.Gestiunea optimă este:

̂ ∙ ̂ ∙ ̂

= ∙ ̂

= +̂ ∙


32/41

Cazul continuu

Variabilele aleatoare excedent de stoc şi lipsă de stoc au repartiţiile:

∶ , ∈ [0, ]

∶ , ∈ [, ∞] unde: este densitatea de repartiţie a variabilei aleatoare cerere X .Mediile lor sunt: ∙

∙ iar funcţia valoarea medie a cheltuielilor este:

∙ ∙ ∙ ∙ Punem condiţia de minim:

′ 0 Stocul optim ̂ este soluţia ecuaţiei:

unde: ∫ este funcţia de repartiţie a variabilei aleatoare cerere X ,iar + este raport de penalizare.

Observaţii.

1. ′′̂ > 0 ⟹ este punct de minim pentru funcţia . 2. Cum este funcţie nedescrescătoare, rezultă că ̂ este minim unic (absolut).

Gestiunea optimă (costul total minim) va fi:

̂ ∙ ̂ ∙ ̂

∙ ̂ ∙

̂


33/41

IV. ELEMENTE DE TEORIA GRAFURILOR

4.1. Concepte de bază

Definiţia 4.1. Un graf orientat este o pereche de forma , unde X este o mulţimefinită şi , ⁄ , ∈ ⊂ × . Elementele lui X se numesc vârfuri sau noduri alelui G, iar perechile , se numesc arce ale grafului G: x este extremitatea iniţială (sursă),

y extremitatea finală (destinaţie) pentru arcul , .Graful , admite o reprezentare geometrică în plan, obţinută astfel: vârfurile se plasează în plan în poziţii distincte oarecare;

pentru fiecare arc

, , punctele x şi y se unesc printr-un segment orientat.

Exemplu. Considerăm graful orientat , dat de: , , 3, 4 , 3, , 4, , , 3, , 3, 4

Definiţia 4.2. Dacă arcele

, , … , ∈ au proprietatea că extremitatea finală a arcului

coincide cu extremitatea iniţială a arcului +, ∀ ∈ 1, 1̅ , atunci mulţimea ordonată , , … , formează un drum în graful , .Echivalent, drumul mai poate fi definit şi ca o mulţime ordonată de vârfuri , , … , } ⊂ pentru care avem proprietatea , ∈ , ∀ ∈ 1, ℎ 1̅ .Definiţia 4.3. Drumul , , … , cu proprietatea că extremitatea finală a arcului coincide cu extremitatea iniţială a arcului , se numeşte circuit în graful G.

3 4


34/41

Distingem:

drum elementar – un drum în care fiecare nod apare o singură dată;

drum neelementar - un drum care trece de două sau mai multe ori prin acelaşi nod.

Un drum elementar care trece prin toate nodurile grafului se numeşte drum hamiltonian.

Lungimea unui drum este egală cu numărul arcelor care îl formează.

Numărul de noduri la care se poate ajunge din nodul se numeşte puterea de atingere anodului ∈ şi se notează .4.2. Matrici asociate unui graf

Fie , un graf orientat având , , … , .Definiţia 4.4. Matricea (),∈,̅ dată de relaţiile:

1, ă ( , ) ∈ 0, ă ( , ) ∉ , ∀ . ∈ 1, ̅ .se numeşte matricea arcelor (matricea de adiacenţă, matricea conexiunilor directe)

a grafului G.

Pentru exemplul anterior avem:

0 01 0 1 10 00 10 0 0 10 0


35/41

Definiţia 4.5. Matricea (),∈,̅ dată de relaţiile:

1, ă î ă ţ

0, î

,

∀ . ∈ 1,̅

se numeşte matricea drumurilor (matricea conexiunilor totale) a grafului G.

Remarcăm faptul că

două grafuri care au aceeaşi mulţime de vârfuri şi aceeaşi matrice a arcelor coincid;

nu este obligatoriu ca două grafuri având aceeaşi mulţime de vârfuri şi aceeaşi matrice

a drumurilor, să aibă şi aceleaşi arce.

4.3. Găsirea drumurilor într-un graf orientat

Fie , un graf orientat cu n noduri: , , … , .În vederea elaborării unor algoritmi de determinare a matricii drumurilor, vom introduce

operaţiile de adunare şi înmulţire booleană:

̇ 0 10 0 1

1 1 1

× ̇ 0 10 0 0

1 0 1


36/41

Algoritm 1.

Pas 1. Se construieşte matricea arcelor A.

Pas 2. Se calculează succesiv puterile matricei A până la

−.

Pas 3. Se calculează matricea drumurilor:

⋯ − − Observaţie. Dacă ne interesează doar existenţa drumurilor dintre noduri, nu şi numărul lor,

atunci vom folosi înmulţirea şi adunarea booleană.

Algoritm 2.

Pas 1. Se construieşte matricea arcelor A.

Pas 2. Pentru fiecare linie i, se adună boolean la aceasta toate liniile j pentru care 1.Pas 3. Se reia pasul 2 până când, după o aplicare a acestuia, matricea rămâne aceeaşi.

Ultima matrice obţinută este matricea drumurilor D.

Observaţie. Aceşti algoritmi sunt destul de lenţi în ceea ce priveşte aplicarea pe calculator.

Ambele procedee ne arată existenţa sau nu a unui drum între două noduri, eventual celungime are ( – existenţa drumurilor de lungime k , dacă s-au folosit operaţiile algebrei

booleene) şi câte sunt de această lungime ( – numărul drumurilor de lungime k , dacă s-aufolosit operaţiile obişnuite).

Totuşi, în problemele practice cel mai important este să ştim care sunt efectiv aceste drumuri.


37/41

Pentru exemplul anterior se obţine:

3 1 11 1

1 11 11 10 0 1 10 0

Matricea drumurilor (),∈,̅ a grafului G poate indica prezenţa sau absenţacircuitelor în graful G, astfel:

dacă 0, ∀ ∈ 1, ̅ , atunci graful G nu are circuite dacă ∃ ∈ 1, ̅ pentru care 1, atunci în G există un circuit care are ca vârf

iniţial şi final nodul

.

De asemenea, matricea drumurilor D ne ajută să calculăm puterile de atingere ale fiecărui

nod din G, astfel:

= numărul elementelor egale cu 1 de pe linia i din matricea D, ∈ 1, ̅ .4.4. Determinarea drumurilor hamiltoniene

Fie , un graf orientat, fără circuite, cu n noduri: , , … , .Presupunem că am calculat matricea drumurilor D şi puterile de atingere ale tuturor

nodurilor.

Teoremă (Chen) Un graf orientat, fără circuite, cu n noduri conţine un drum hamiltonian

dacă şi numai dacă ∑ = − Teoremă

Dacă într -un graf orientat, fără circuite există un drum hamiltonian, atunci acesta este unic.


38/41

Algoritmul lui Chen

Pas 1. Se scrie matricea arcelor A

Pas 2. Se calculează matricea drumurilor D

Pas 3. Dacă ∃ ∈ 1, ̅ pentru care 1, atunci graful are circuite,algoritmul lui Chen nu se poate aplica ⟹ STOP

Dacă 0, ∀ ∈ 1, ̅ , atunci graful G nu are circuite ⟹ se trece la pasul 4.Pas 4. Se calculează puterile de atingere ale tuturor nodurilor

Pas 5. Dacă ∑ = ≠ − , atunci graful G nu are drum hamiltonian.Dacă ∑ = − , atunci se trece la pasul 6.

Pas 6. Se ordonează nodurile grafului în ordinea descrescătoare a puterilor de atingere

⟹ drumul hamiltonian căutat. Algoritmul lui Kaufmann (înmulţirii latine)

Pas 1. Se scrie matricea (),∈,̅ , similară matricei arcelor A,unde: ( , ), ă ( , ) ∈ ∗ ă ( , ) ∉ , ∀ , ∈ 1, ̅ .

Pas 2. Din matricea - matricea latină, prin suprimarea primei litere,se obţine matricea - matricea destinaţiilor posibile.

Pas 3. Se calculează: + & , ∈ 1, 1̅ .


39/41

Operaţia de concatenare (&) (înmulţire latină) respectă regulile din înmulţirea obişnuită a

matricelor, cu următoarele precizări:

dacă una din componentele participante la calcul este *, atunci rezultatul este *;

în caz contrar, rezultatul compunerii constă în scrierea în continuare a vârfurilor

componente ale simbolurilor participante.

- conţine lista tuturor drumurilor formate din m arce în graful dat.Observaţie. Drumurile hamiltoniene, dacă există, se vor afla în matricea

−,

unde n = numărul vârfurilor grafului dat.

4.5. Drumuri de valoare optimă într-un graf

În marea majoritate a problemelor care pot fi modelate prin grafuri nu ne interesează numai

dacă există sau nu legături între componentele reprezentate prin nodurile grafului, ci şi

intensitatea acestora. Această intensitate are semnificaţia unei valori numerice (pozitive sau

negative) asociate arcului corespunzător legăturii a cărei intensitate o măsoară.

În aplicaţiile economice această valoare poate fi:

lungimea drumului dintre două localităţi;

costul parcurgerii rutei reprezentate prin arcul corespunzător ;

durata parcurgerii rutei respective;

cantitatea transportată pe ruta respectivă etc.

Una din problemele care poate apărea în aceste situaţii este găsirea, pentru o anumită pereche

de noduri sau mai multe perechi, a drumului optim între acestea.

Pentru formalizarea problemei vom introduce noţiunea de:

valoare a unui drum

≝ suma valorilor arcelor care îl compun.


40/41

În aceste condiţii putem enunţa problema drumului optim:

Dat fiind un graf , şi o funcţie: ⟶ ℝ

( , ) ⟶ ( , ), ∀ ( , ) ∈ care asociază fiecărui arc o valoare reală, să se găsească, pentru o pereche dată de noduri,

drumul (drumurile) de valoare optimă (minimă sau/şi maximă) între cele două noduri şi

valoarea acestuia (acestora).

Deoarece majoritatea problemelor economice se modelează prin grafuri cu număr finit de

noduri, ne vom limita în continuare doar la acestea.

Din cauza varietăţii nelimitate a grafurilor posibile, nu există un algoritm care să rezolve

orice problemă, în timp util, dar s-au elaborat o mulţime de algoritmi, fiecare fiind cel mai

eficace în anumite cazuri.

Algoritmul lui Bellman – Kalaba

Algoritmul se aplică în grafuri finite care nu au circuite de valoare negativă (pentru o

problemă de minim) sau care nu au circuite de valoare pozitivă (într -o problemă de maxim) şi

găseşte drumurile de valoare minimă (maximă) de la toate nodurile grafului la un nod

oarecare, fixat.

Dacă dorim să cunoaştem drumurile de valoare minimă (maximă) între oricare două noduri,

vom aplica algoritmul, pe rând, pentru fiecare nod al grafului.

Fie , un graf orientat, finit, , , … , .Presupunem, fără a restrânge generalitatea, că am numerotat nodurile astfel încât nodul spre

care căutăm drumurile de valoare minimă (maximă) de la celelalte noduri să fie .


41/41

Pasul 1. Se construieşte matricea pătratică (),∈,̅ , cu dimensiunea egală cunumărul de noduri ale grafului, ale cărei elemente sunt:

( , ) , ă ∃ ( , ) ş ≠ 0 , ă ∞ ,∞ , î ă . , ă ∄ ( , )î ă . , ă ∄ ( , )

unde ( , ) este valoarea arcului ( , ), ∀ ( , ) ∈ .Pasul 2. Se adaugă succesiv liniile

la matricea M , elementele acestora calculându-se prin

relaţiile de recurenţă: , ∈ 1, ̅ (−,,min∈,̅ ( −,)) .(−,,max∈,̅ ( −,)) . , ∈ 1, ̅ .

Pasul 3. După calcularea fiecărei linii noi, se compară elementele ei cu cele ale precedentei:

dacă −, , ∀ ∈ 1, ̅ , atunci se opreşte recurenţa şi ultima linie calculatăconţine valorile optime ale drumurilor de la celelalte noduri la nodul .

dacă ≠ −, , pentru cel puţin un indice j, se trece la calcularea noii linii +. Pasul 4. Pentru găsirea drumului care dă valoarea minimă de la un nod la nodul ,se găsesc, începând înapoi de la ultima linie, pe care s-au obţinut valorile finale, nodurile

, , … , care formează drumul căutat, unde: , , iar fiecare alt indice+ este cel pentru care s-a obţinut minimul (maximul) de pe poziţia al liniei .Observaţie. Pentru grafuri foarte mari, algoritmul necesită un volum mare de memorie, prin

necesitatea memorării matricei M , care este greu de manipulat. Chiar dacă, din cele arce posibile, graful ar avea doar un procent foarte mic, matricea grafului va avea tot poziţii dememorat şi analizat

zi im anul 3 sem 1 cercetari operationale azp0i21x734g

Documents