METODE CANTITATIVE ÎN MANAGEMENT -...

Conf. univ. dr. Liviu Mihăescu

METODE CANTITATIVE ÎN MANAGEMENT

Cursul are la bză lucrarea

MODELAREA ŞI SIMULAREA DECIZIILOR MANAGERIALE

optimizare prin metode cantitative

ISBN 973-739-003-2Editura Universităţii „Lucian Blaga“

Descrierea CIP a Bibliotecii Naţionale a RomânieiModelarea şi simularea deciziilor manageriale- optimizare prin metode cantitative -

Mihăescu, Liviupp. ; 21 x 14,5Bibliogr.ISBN 973-739-003-2

Copyright © 2004Toate drepturile sunt rezervate autorului

CUPRINS

CAPITOLUL 1ANALIZA CANTITATIVĂ, CALITATIVĂ ŞI PROCESUL DE LUARE A DECIZIEI ..................................................................................................1.1 Procesul de analiză cantitativă ..........................................................

CAPITOLUL 2MODELAREA PROBLEMELOR DE TRANSPORT .................................2.1 Problemă de transport .......................................................................2.2 Problema de transport: o problemă de programare liniară ................2.3 Problema de transport. procedură practică de rezolvare ...................2.3.1 Găsirea unei soluţii iniţiale fezabile. Metoda Costului Minim ..........2.4 Metoda Stepping-Stone .....................................................................2.5 Situaţii speciale care apar în problema de transport .........................

CAPITOLUL 3MODELAREA PROBLEMELOR DE DISTRIBUŢIE PRIN MODELE DE REŢEA .....................................................................................................3.1 Problema celei mai scurte rute ..........................................................3.1.1 Algoritmul celei mai scurte rute .......................................................3.2 Problema arborelui de acoperire minimală ........................................3.2.1 Algoritmul arborelui de acoperire minimală (Greedy) .....................3.3 Problema de flux maxim ....................................................................3.3.1 Algoritmul pentru flux maxim ..........................................................

CAPITOLUL 4MODELE DE STOCARE .........................................................................4.1 Modelul de stocare cu cerere constantă ...........................................4.2 Modelul de stocare a producţiei fabricate pe loturi ............................4.3 Model de stocare cu cerere constantă şi lipsă de stoc ......................4.4 Model de stocare cu cerere variabilă ................................................

77

20202430314049

53535465666970

79829095

100

CAPITOLUL 5FIRE DE AŞTEPTARE ............................................................................5.1 Fir de aşteptare cu o singură unitate de deservire ............................5.1.1 Distribuţia sosirilor ..........................................................................5.1.2 Distribuţia timpilor de deservire ......................................................5.1.3 Regula de deservire .......................................................................5.2 Fir de aşteptare cu sosiri poissoniene şi timpi de deservire exponenţiali .............................................................................................

CAPITOLUL 6SIMULAREA PROCESELOR ECONOMICE ...........................................6.1 Simularea unui proces de stocare .....................................................

BIBLIOGRAFIE ........................................................................................

104106107109111

112

115115

120

CAPITOLUL 1

ANALIZA CANTITATIVĂ, CALITATIVĂ ŞI PROCESUL DE LUARE A DECIZIEI

1.1 Procesul de analiză cantitativă

În studiul metodelor cantitative pentru luarea deciziei se consideră procedura bazată pe parcurgerea următoarelor cinci etape: (1) definirea problemei, (2) dezvoltarea modelului, (3) pregătirea datelor, (4) generarea soluţiei şi (5) întocmirea raportului.

1. Definirea problemei. Definirea problemei este considerată ca fiind cea mai critică etapă a procesului de analiză cantitativă. De cele mai multe ori este necesară imaginaţie, lucru în echipă şi un considerabil efort de a transforma cel mai adesea o problemă descrisă la modul general într-o problemă dine definită în care se pot aplica metode de management cantitativ. De exemplu, o problemă descrisă prin „exces de stoc“ poate fi clar definită în termenii privind obiectivele specifice şi restricţiile de operare, înainte ca un analist să parcurgă următoarea etapă a procesului de analiză cantitativă. Implicarea utilizatorului este aici esenţială, analistul trebuie aici să lucreze în colaborare cu managerul sau cu utilizatorul rezultatelor.

A N A L I Z A C A N T I T A T I V Ă , C A L I T A T I V Ă Ş I P R O C E S U L D E L U A R E A D E C I Z I E I8

2. Dezvoltarea modelului. Modelele reprezintă reprezentări ale obiectelor sau situaţiilor reale. Aceste reprezentări, modele, pot fi făcute în forme variate. De exemplu, un avion real poate fi reprezentat printr-o machetă, un model al unui avion la scară redusă, numită „model fizic“. Acest model reprezintă replica fizică a obiectului real. În terminologia modelării, aceste replici fizice ale obiectelor reale poartă denumirea de „machete“.

Există, de asemenea, modele care sunt fizice în formă, dar nu au reprezentarea fizică a obiectului modelat. Asemenea modele sunt denumite „modele analoage“1.

O altă categorie de modele, care vor fi studiate in continuare, este cea care include acele reprezentări ale problemelor în simboluri şi expresii matematice sau relaţii. Asemenea modele sunt numite „modele matematice“ şi reprezintă elementul critic, cu o importanţă semnificativă, în abordarea cantitativă a procesului decizional. De exemplu profitul generat de vânzarea unui produs (P) poate fi determinat prin multiplicarea profitului unitar cu numărul de unităţi vândute (x). Dacă profitul unitar este de 10 u.m., atunci următoarea relaţie defineşte profitul total obţinut prin vânzarea a x unităţi de bun:

P = 10x (1.1)

Scopul, valoarea unui model este determinată de posibilitatea de a trage concluzii despre o situaţie reală, prin studierea şi analizarea modelului. De exemplu, un constructor de avioane testează, sub forma unei machete, un nou avion în tunelul aerodinamic, pentru a cunoaşte potenţialul de zbor al avionului la mărimea reală. În mod asemănător, un model

1 Un termometru este un model analog. Poziţionarea indicatorului termometrului pe scala de măsurare indică temperatura.

A N A L I Z A C A N T I T A T I V Ă , C A L I T A T I V Ă Ş I P R O C E S U L D E L U A R E A D E C I Z I E I 9

matematic poate fi utilizat pentru a oferi concluzii privind profitul obţinut prin vânzarea unei anume cantităţi de produs vândute. În corelaţie cu relaţia (1.1) se va obţine un profit de 40 u.m. prin vânzarea a 4 unităţi de bun.

În general, experimentarea cu ajutorul modelelor necesită mai puţin timp şi este mai puţin costisitoare decât experimentarea cu obiecte la scara 1:1, sau, în situaţii concrete reale. Experimentarea cu ajutorul modelului avionului la scară redusă este mai rapidă şi mai puţin costisitoare decât experimentarea cu un avion la mărimea reală. În mod identic, modelul matematic prezentat anterior permite o rapidă determinare a profitului posibil fără a fi necesară decizia managerului de a produce şi a vinde x unităţi de bun. Modelele, de asemenea, prezintă avantajul că reduc riscul asociat cu experimentarea în situaţii reale. În particular, se poate aprecia că un design neadecvat, sau o decizie nepotrivită, pot cauza prăbuşirea avionului proiectat, iar un proiect care poate avea o pierdere potenţială mare (de exemplu 50.000 u.m.) poate determina decizia de a nu fi aplicat în situaţia reală.

Acurateţea concluziilor şi a deciziilor luate pe baza studierii unui model sunt în corelaţie cu cât de bine, acesta,reprezintă situaţiile reale. Astfel, modelul avionului va putea reprezenta un avion real, iar concluziile vor determina caracteristicile şi comportamentul real al avionului în timpul zborului. La fel, modelul matematic ce descrie relaţia profitului cu cantitatea vândută, determinat la nivelul firmei, va arăta cu mai mare acurateţe care vor fi predicţiile profitului.

În continuare se va aprofunda procesul de modelare matematică. Rezolvarea problemei manageriale trebuie să treacă în mod uzual prin etapa definirii problemei care să conducă spre un obiectiv specific, precum maximizarea profitului sau minimizarea costurilor, şi determinarea


restricţiilor (de exemplu capacitatea de producţie). Succesul modelului matematic şi al abordării cantitative va depinde direct de acurateţea cu care au fost determinate funcţia (funcţiile) obiectiv şi restricţiile modelului, de modalitatea în care acestea au fost reprezentate în modelul matematic ecuaţional.

Denumim în continuare funcţie obiectiv acea expresie matematică ce descrie obiectivul problemei. De exemplu, ecuaţia profitului P = 10x poate fi funcţie obiectiv pentru firma care doreşte să-şi maximizeze profitul. O restricţie relativă la capacitatea de producţie poate fi necesară dacă, de exemplu, sunt necesare 5 ore pentru producerea unei unităţi de bun şi sunt disponibile pe parcursul săptămânii de lucru doar un total de 40 de ore. Dacă x reprezintă numărul de unităţi produse, restricţia relativă la timpul de lucru poate fi:

5x 40

Valoarea 5x reprezintă timpul necesar pentru a produce x unităţi de bun. Simbolul „“ arată că timpul necesar pentru producţie trebuie să fie mai mic sau egal cu disponibilul de 40 de ore.

Problema decizională decurge din întrebarea: Câte unităţi de produs trebuie programate a fi realizate în fiecare săptămână pentru a maximiza profitul? Modelul matematic complet pentru această problemă simplă de producţie este:

max P = 10x funcţie obiectiv

0x

405xrestricţii

Restricţia x 0 se referă la producţia care urmează a fi realizată, care poate fi zero sau mai mare decât zero, dar, se


consideră astfel că producţia nu poate lua valori negative. Soluţia modelului poate fi uşor calculată şi este x=8 având un profit asociat de 80 u.m.. Acest model este un exemplu, simplu, de programare liniară.

În modelul anterior, profitul unitar (10 u.m.), timpul de producţie al unei unităţi (5 ore) şi capacitatea de producţie (40 ore) reprezintă factori care nu se află sub controlul managerului sau al decidentului. Asemenea factori pot influenţa deopotrivă funcţia obiectiv şi restricţiile şi sunt denumite „factori necontrolabili“ ai modelului. Intrările care sunt controlate, saudeterminate de decident, sunt denumite „intrări controlabile“în model. Intrările controlabile reprezintă decizii alternative specificate de manager, ele fiind de asemenea denumite şi „variabile de decizie“ ale modelului.

Figura nr. 1. 1 Reprezentarea procesului de transformare a intrărilor în ieşiri prin procesul de transformare modelat

Odată ce toate variabilele controlabile şi necontrolabile au fost stabilite, funcţia obiectiv şi restricţiile pot fi evaluate, iar output-ul modelului determinat. În acest sens, output-ul modelului reprezintă o simplă proiecţie a ceea ce s-ar întâmpla

Intrări necontrolabile

Intrări controlabile(Variabile de

decizie)

Modelul matematic

Ieşiri(Rezultate proiectate)


dacă aceşti factori particulari şi decizia se vor întâlni într-o situaţie reală. O reprezentare a modului în care factorii controlabili şi cei necontrolabili sunt transformaţi de modelul matematic din intrări în ieşiri este cea din Figura nr. 1.1.

Figura nr. 1. 2 Reprezentarea modelului de producţie

În Figura nr. 1.2 este realizată o reprezentare similară cu cea anterioară în care sunt punctate detaliile specifice modelului de producţie. Aşa cum s-a arătat înainte, inputurile necontrolabile sunt acelea care nu pot fi influenţate de decident. Inputurile controlabile şi necontrolabile ale unui model depind de problema particulară analizată sau de situaţia decizională. În problema de producţie anterioară, timpul de producţie necesar, 40 de ore, este un input necontrolabil. Dacă este posibil să fie angajate alte persoane, sau să se presteze ore

Intrări necontrolabile

Intrări Modelul matematic

profit unitar 10$timp lucru unitar 5 orecapacitate de producţie

40 ore

Nivelul cantităţii

produse (x)

max P = 10x

0x

405x

Ieşiri

Profitul proiectat şi respectarea restricţiei

timpului de


suplimentare, numărul de ore de producţie va deveni un input controlabil şi, desigur, o variabilă de decizie în model.

Inputurile necontrolabile, sau nu pot fi cunoscute cu exactitate, sau sunt incerte, şi, în consecinţă, au valori variabile. Dacă toate inputurile necontrolabile ale unui model sunt cunoscute şi nu pot varia, modelul respectiv este denumit „model deterministic“. Nivelul ratelor taxelor şi impozitelor nu se află la discreţia managerului şi astfel ele constituie un input necontrolabil în multe modele de decizie. Dacă aceste rate sunt cunoscute şi fixe, cel puţin pe termen scurt, un model matematic cu rate ale taxelor şi impozitelor ca fiind singurele inputuri necontrolabile, va fi un model deterministic. Caracteristica principală a modelului deterministic este aceea că valorile inputurilor controlabile sunt cunoscute dinainte.

Dacă unul din inputurile necontrolabile este variabil, atunci modelul este numit „model stochastic“. Un input necontrolabil în toate modelele de producţie este cererea pentru acel produs. Dacă cererea posibilă viitoare este încadrată între două valori pe un interval, un model matematic ce tratează cererea în condiţii de incertitudine este un model stochastic. În modelul de producţie, numărul total mediu de ore necesare pentru realizarea unui produs, timpul total disponibil şi profitul mediu unitar sunt toate inputuri necontrolabile. Dacă toate inputurile necontrolabile iau valori cunoscute şi fixe, modelul este deterministic. Dacă numărul total mediu de ore necesare pentru realizarea unui produs poate varia între 3 şi 6 ore, în funcţie de calitatea materiei prime, modelul este stochastic. Caracteristica unui model stochastic este că nu poate fi determinată valoarea output-ului, chiar dacă valoarea input-ului controlabil este cunoscută, din cauza valorilor specifice ale inputurilor necontrolabile, care nu sunt cunoscute. Din aceste


considerente, modelele stochastice sunt, adesea, mult mai dificil de analizat.

3. Pregătirea datelor. A treia etapă în analiza cantitativă este pregătirea datelor necesare modelului. În acest sens sunt necesare datele care reprezintă valori ale inputurilor necontrolabile din model. Toate inputurile necontrolabiletrebuie să fie specificate înainte de a putea să se analizeze modelul şi de a selecta decizia bazată pe soluţia problemei.

În modelul de producţie, valorile inputurilor necontrolabile sunt: 10 u.m. profitul unitar, 5 ore necesare pentru realizarea unei unităţi de produs şi 40 de ore pentru capacitatea de producţie. În dezvoltarea modelului, acestevalori sunt cunoscute şi sunt încorporate în modelul care a fost creat. Dacă modelul este relativ mic, şi numărul valorilor de input necontrolabile (a datelor) necesare este redus, analistul, probabil că va combina etapa de dezvoltare a modelului cu cea de pregătire a datelor. În acest moment sunt introduse datele valorice şi sunt determinate ecuaţiile matematice ale modelului.

În multe situaţii de modelare, datele sau valorile necontrolabile nu sunt prezentate pentru a fi introduse ca atare. În aceste situaţii, managerul poate determina că modelul necesită date relative la: profit unitar, timp de producţie şi capacitate de producţie, dar valorile nu pot fi luate direct din evidenţele contabile ale firmei, din compartimentul de producţie sau proiectare. Adesea, în încercarea de a colecta datele, modelul este dezvoltat, iar analistul va folosi o notaţie generală pentru etapa de dezvoltare a modelului şi va trece,apoi, la etapa de pregătire a datelor, pentru a obţine valorile inputurilor necontrolabile.

Se foloseşte următoarea notaţie:c = profit unitar;a = timpul de producţie în ore pe unitate produsă;


b = capacitatea de producţie în ore,iar în etapa de dezvoltare a modelului, acesta se va

reprezenta în modul următor:

0 x

ba·x

c·xopt

Apoi se vor identifica valorile corespunzătoare pentru a, b şi c pentru a defini corespunzător modelul.

O parte din analiştii neexperimentaţi presupun că odată ce problema a fost definită şi modelul general dezvoltat, problema este în esenţă rezolvată. Aceştia cred că etapa de pregătire a datelor este o etapă cu o mică importanţă. În special modelele mari care au numeroase valori de input afirmaţia anterioară nu poate fi departe de adevăr. De exemplu, în modele de dimensiuni moderate, cu 50 de variabile de decizie şi 25 de restricţii sunt necesare peste 1300 de date care trebuie identificate şi pregătite pentru a fi introduse în model. Timpul necesar pentru pregătirea acestor date şi posibilitatea de a greşi, arată că etapa de pregătire a datelor este critică în procesul de analiză cantitativă. Adesea este necesară o bază de date care să furnizeze modelului matematic informaţiile necesare, iar specialiştii vor fi astfel implicaţi în etapa de pregătire a datelor.

4. Generarea soluţiei. Odată ce modelul a fost dezvoltat şi etapa de pregătire a datelor este completată, se poate trece la următoarea etapă. Acum, analistul va încerca să identifice valorile de decizie care conferă cel mai bun output pentru model. Valorile variabilelor specifice de decizie, sau valorile care oferă cel mai bun output, poartă denumirea de „soluţie optimală“ a modelului. Pentru problema de producţie,


generarea soluţiei este etapa care implică găsirea valorii cantităţii de produs, respectiv variabila de decizie x, care maximizează profitul, fără însă a determina nerespectarea restricţiilor modelului relative la capacitatea de producţie.

Procedura de evaluare şi selectare care trebuie folosită în această etapă presupune încercări în care modelul este folosit pentru a testa şi evalua diferite variante de decizie alternative. În modelul de producţie, aceasta înseamnă testarea şi evaluarea modelului considerând valori pentru producţia x, variabile. Se consideră modelul din Figura nr. 1.2 şi se calculează pentru valori diferite ale lui x şi se verifică dacă acestea generează profit corespunzător şi, totodată, respectă restricţiile capacităţii de producţie. Dacă o decizie alternativă nu satisface una sau mai multe din restricţiile modelului, decizia alternativă este respinsă ca nefezabilă relativă la valoarea funcţiei obiectiv. Dacă toate restricţiile sunt satisfăcute, decizia alternativă este fezabilă şi este candidată la „cea mai bună soluţie“ sau decizie recomandată.

Tabelul nr. 1. 1 Reprezentarea procedurii de evaluare şi selecţieAlternativa de

decizie(Cantitatea de

produs) x

Profitul proiectat

Total ore de

producţie

Soluţie fezabilă?(capacitatea =40)

0 0 0 Da2 20 10 Da4 40 20 Da6 60 30 Da8 80 40 Da10 100 50 Nu12 120 60 Nu


Folosind această procedură de evaluare şi selectare a deciziilor alternative, decidentul poate identifica o bună – şi posibil cea mai bună – soluţie fezabilă a problemei. Această soluţie este cea care va determina decizia optimă pentru problemă. În Tabelul nr. 1.1 sunt prezentate rezultatele procedurii de evaluare şi selectare pentru problema prezentată în Figura nr.1.2. Decizia recomandată se referă la o cantitate produsă de 8 unităţi, iar soluţia fezabilă, cu cel mai mare profit, corespunde aceleiaşi cantităţi produse.

Dacă procedura de evaluare şi selecţie poate fi aplicată relativ uşor şi poate să ofere informaţii de valoare managerului, atunci, ea va fi folosită pentru selectarea deciziei optime. Dacă ea necesită calcule foarte laborioase, este posibil să nu mai poată fi aplicată această procedură. Totuşi analiştii chiar au dezvoltat proceduri pentru multe modele care sunt mai eficiente chiar decât procedura de evaluare şi selecţie1. De remarcat că pentru modelele de mici dimensiuni calculele pot fi efectuate manual, pentru cea mai mare parte a aplicaţiilor practice este necesară folosirea unui computer.

Este important de ştiut că etapele de dezvoltare a modelului şi cea de generare a soluţiei nu pot fi complet separate. Atunci când analistul va dori să dezvolte un model de mare acurateţe care să transpună în relaţii matematice problema, el va dori să poată obţine soluţia problemei. Dacă modelul va fi foarte extins, complex, atunci va fi poate chiar imposibil de a se cunoaşte soluţia acestuia. În această situaţie, un model simplificat, uşor de înţeles, cu p procedură care să conducă spre cunoaşterea soluţiei va fi preferat, chiar dacă soluţia determinată prin acesta este doar o aproximare a celei mai bune decizii. Pe măsură ce analiştii acumulează cunoştinţe

1 Sunt introduse în aceastălucrare proceduri de căutare a soluţiilor pentru mai multe tipuri de modele matematice care vor fi formulate.


despre metodele cantitative, modelele generate de aceştia vor fi mai uşor dezvoltate şi rezolvate.

După ce soluţia modelului a fost obţinută, managerul împreună cu analistul vor fi interesaţi să afle cât de bună este soluţia determinată. După generarea modelului, analistul trebuie să verifice acurateţea modelului, pentru a cunoaşte gradul de confidenţă a soluţiilor generate de acesta, ceea ce presupune rezolvarea modelului.

Testarea şi validarea modelului sunt etape care presupun confruntarea rezultatelor generate de model cu rezultatele economice obţinute în situaţia reală modelată. Dacă modelul generează soluţia identică cu cea obţinută în situaţia reală, atunci modelul ar putea fi folosit pentru rezolvarea problemei pentru care a fost formulat. Totuşi, în situaţia în caresunt identificate probleme determinate de lipsa de acurateţe a modelului, pot fi realizate acţiuni corective relative la modificarea modelului sau a datelor de intrare ale acestuia. Chiar şi după acţiunea corectivă, soluţia modelului nu va fi folosită în practică până când modelul nu va trece corespunzător de testare şi validare.

5. Întocmirea raportului. Etapa finală în procesul de analiză cantitativă este reprezentat de pregătirea rapoartelor manageriale bazate pe soluţia modelului. Referitor la procesul de luare al deciziei în problema supusă analizei cantitative, managerul va menţiona în raportul său soluţia generată de modelul cantitativ într-o modalitate care să determine înţelegerea acesteia şi la alte niveluri ierarhice. Raportul va conţine decizia recomandată, dar şi alte informaţii pertinente despre rezultatele modelului care pot fi utile.

Implementarea modelului. Generarea raportului managerial este ultima etapă în procesul de analiză cantitativă


bazată pe soluţia obţinută prin intermediul modelului. Astfel, rămâne la latitudinea managerului dacă va include soluţia cantitativă, cu consideraţiile calitative pentru a face ca decizia luată să fie cea mai bună posibilă. După aceasta, managerul trebuie să urmărească implementarea şi să realizeze evaluarea deciziei. În timpul implementării, dar şi după aceasta, managerul trebuie să continue să monitorizeze contribuţia modelului. În acest moment, se poate ridica problema extinderii şi a creşterii acurateţei modelului care vor determina managerul să se întoarcă la etapele de început ale procesului de analiză cantitativă.

Implementarea cu succes a rezultatelor este de mare importanţă atât pentru analist cât şi pentru manager. Dacă rezultatul procesului de analiză cantitativă nu este implementat, întregul efort depus a fost în zadar.

Adesea implementarea necesită ca angajaţii care vor aplica soluţiile modelului să trebuiască să realizeze activitatea într-un mod diferit, cu eficienţă sporită, iar managerul poate să se lovească de rezistenţa acestora la schimbare. Una dintre cele mai eficiente modalităţi de implementare este să se implice cât mai mulţi angajaţi în procesul de modelare. Dacă angajaţii simt că şi-au adus aportul la identificarea problemei şi la dezvoltarea soluţiei, ei vor fi mai entuziaşti în aplicarea rezultatelor. Succesul implementării rezultatelor ştiinţei managementului în practică este mare pentru acele proiecte care au antrenat cât mai mulţi angajaţii1.

1 Brabb J. George, Introduction to Quantitative Management, Holt, Reinhart and Winston Inc., New York, 1968, pg. 13.

CAPITOLUL 2

MODELAREA PROBLEMELOR DE TRANSPORT

2.1PROBLEMĂ DE TRANSPORT

Problemele de transport pot să apară adesea în planificarea distribuţiei de bunuri şi servicii, din mai multe locaţii, unde există disponibilitate, spre locaţiile unde se află cererea. De obicei, cantitatea de bunuri disponibile în fiecare locaţie de ofertă (origine) este fixă sau limitată, un anumit nivel al cererii fiind

înregistrat la destinaţie.De obicei firmele dispun de mai multe rute care leagă

sursele de destinaţie şi pe acestea sunt asignate costuri diferite de transport.

Tabelul nr. 2. 1

Origine Unitatea de producţieCapacitatea d producţie

lunară (buc)1 Braşov 5.0002 Cluj 6.0003 Oradea 2.500

TOTAL 13.500

Obiectivul acestei rezolvări este determinarea a cât de multe unităţi de produs vor fi transportate, din origini (surse)spre fiecare destinaţie, astfel încât toate cererile la destinaţie să

MODELAREA PROBLEMELOR DE TRANSPORT 21

fie satisfăcute cu condiţia ca şi costul total de transport să fie minim.

Fie ilustrarea următoarei probleme de transport pe care o are de rezolvat firma G.M. care produce generatoare de curent electric. Această problemă implică transportul produselor de la trei unităţi de producţie spre patru centre de distribuţie. G.M. dispune de centre de distribuţie în Braşov, Cluj, Oradea, iar capacităţile de producţie ale firmei în decurs de o lună sunt cele din Tabelul nr. 2.1.

Tabelul nr. 2. 2

Destinaţie Centru de distribuţieCerere lunară previzionată

(buc.)1 Bucureşti 6.0002 Craiova 4.0003 Constanţa 2.0004 Iaşi 1.500

TOTAL 13.500

Se presupune că firma distribuie generatoarele prin patru centre regionale de distribuţie situate în Bucureşti, Craiova, Constanţa şi Iaşi. Cererea lunară corespunzătoare pentru centrele de distribuţie este prezentată în Tabelul nr. 2.2.

Managerul firmei G.M. vrea să determine cât din producţia realizată în fiecare centru de producţie va fi transportat spre fiecare centru de distribuţie. Figura următoare reprezintă grafic legăturile posibile dintre centrele de producţie şi cele de distribuţie.

În Figura nr. 2.1 prin cercuri sunt reprezentate noduri(surse sau destinaţii) iar liniile care unesc aceste noduri se

MODELAREA PROBLEMELOR DE TRANSPORT22

numesc arce. Graful care corespunde nodurilor interconectate se numeşte reţea.

Figura nr. 2. 1 Reţea de transport

O problemă de transport poate fi reprezentată grafic ca o reţea. Din acest motiv problema este numită şi problemă de flux în reţea. Bunurile transportate de la origine spre destinaţie reprezintă fluxul din reţea.

Oferta Rute Cererea


Tabelul nr. 2. 3 Costul transportuluiDestinaţii

Surse Bucureşti Craiova Constanţa IaşiBraşov 3 2 7 6Cluj 7 5 2 3Oradea 2 5 4 5

Costul de producţie este considerat, aici, identic pentru cele trei unităţi de producţie, costul care este variabil fiind numai cel de transport. Astfel, se pune problema să se determine rutele care vor fi folosite şi cantitatea ce va fi transportată pe acestea, astfel încât toată cererea să poată fi satisfăcută cu un cost de transport minim. Costurile pentru fiecare unitate transportată pe fiecare rută sunt prezentate în Tabelul nr. 2.3.


2.2PROBLEMA DE TRANSPORT: O PROBLEMĂ DE PROGRAMARE LINIARĂ

Se poate folosi un program de programare liniară pentru a rezolva problema de transport a firmei G.M. Se vor folosi variabile precum x11 care reprezintă cantitatea de produse transportate din sursa 1 (Braşov) în destinaţia 1 (Bucureşti); x12

reprezintă cantitatea de produse transportate din sursa 1 (Braşov) în destinaţia 2 (Craiova) etc.

Variabilele de decizie pentru problema de transport care are m origini (surse) şi n destinaţii pot fi notate prin xij şi vor reprezenta numărul de unităţi transportate din sursa i la destinaţia j, cu i =1,…,m şi j =1,…,n.

Folosind notaţia de mai sus, pentru x24 = 500, ea corespunde unui transport de 500 bucăţi de produs din sursa 2 (Cluj ) la destinaţia 4 (Iaşi).

Pe baza costurilor de transport din Tabelul nr. 2.3, se poate determina costul transporturilor pe baza următoarelor expresii:a) costul transportului dinspre Braşov = 3x11+2x12+7x13+6x14

b) costul transportului dinspre Cluj = 7x21+5x22+2x23+3x24

c) costul transportului dinspre Oradea = 3x31+5x32+4x33+5x34

Suma expresiilor de mai sus reprezintă funcţia obiectiv care calculează nivelul costului total de transport al G.M.

Restricţiile problemei sunt determinate, la sursă, de nivelul limitat al producţiei iar la destinaţie de nivelul cererii. În cazul producţiei din fiecare fabrică avem numărul total de bunuri oferite mai mic sau egal cu numărul de bunuri produse într-un centru de producţie. Astfel se poate scrie pentru fiecare furnizor:

x11+x12+x13+x14 ≤ 5000 oferta furnizorului din Braşovx21+x22+x23+x24 ≤ 6000 oferta furnizorului din Clujx31+x32+x33+x34 ≤ 2500 oferta furnizorului din Oradea


Firma dispune de patru centre de distribuţie unde trebuie să se asigure că întreaga ofertă va fi satisfăcută. Pentru fiecare centru se deduce:

x11 + x21 + x31 = 6000 cererea în Bucureştix12 + x22 + x32 = 4000 cererea în Craiovax13 + x23 + x33 = 2000 cererea în Constanţax14 + x24 + x34 = 1500 cererea în Iaşi

Combinând funcţia obiectiv cu cele trei restricţii privind oferta şi cele patru restricţii privind cererea se obţine oproblemă de programare liniară cu 12 variabile şi 7 restricţii liniare astfel:

max f = 3x11+2x12+7x13+6x14+7x21+5x22+2x23+3x24+3x31+5x32+4x33+5x34

x11+x12+x13+x14 ≤ 5000 x21+x22+x23+x24 ≤ 6000

x31+x32+x33+x34 ≤ 2500x11 +x21 +x31 = 6000 x12 +x22 +x32 = 4000

x13 +x23 +x33 = 2000 x14 +x24 +x34 = 1500

xij 0, pentru i =1,…,3 şi j = 1,…,4

Soluţia optimă pentru problema de transport a GM este o soluţie în care toate valorile sunt numere întregi. Acest fapt reprezintă o cerinţă obiectivă în rezolvarea problemelor de transport. Datorită structurii speciale a restricţiilor problemelor de transport întotdeauna se obţin soluţii numere întregi dacă nodurile sursă şi cele destinaţie prezintă oferta şi respectiv cererea în numere întregi.

Varietatea de probleme de bază de transport se potîncadra în una sau mai multe din situaţiile următoare:


1. Oferta totală nu egalează cererea totală.2. Fiecare obiectiv poate fi de maximizare.3. Unele rute pot să prezinte restricţii relative la capacitatea

minimă sau maximă de transport.4. Unele rute nu pot fi lua te în considerare fiind considerate

inacceptabile.Cu unele modificări în PPL de transport, aceste situaţii

pot fi luate în considerare în atingerea soluţiilor.Cea mai întâlnită situaţie este cea în care oferta totală

nu este egală cu cererea totală. Când cantitatea oferită este peste nivelul cererii nu apar modificări în formularea modelului PPL. Excesul de ofertă va introduce variable de relaxare în rezolvarea PPL. Relaxarea poate fi interpretată prin ofertă neutilizată sau prin cantităţi oferite care sunt transportate, din surse spre centrul de distribuţie.

Dacă oferta totală este mai mică sau egală cu cantitatea cerută, modelul PPL nu va avea o soluţie fezabilă pentru că restricţiile impuse de cerere nu vor fi satisfăcute. În acest caz, o modificare în restricţiile PPL devine necesară pentru a permite rezolvarea problemelor de transport şi obţinerea soluţiei acesteia. Se va introduce, astfel, o sursă fictivă a cărei ofertă (fictivă) reprezintă chiar excesul de cerere peste nivelul ofertei. Se va asocia costul nul pentru transportul de la această sursă fictivă spre fiecare nod al cererii, ceea ce în funcţia obiectiv va însemna costul transportului doar pe rutele care au cost asociat diferit de 0, deci soluţia optimă a problemei nu se modifică (nu vor mai efectuate practic transporturi de bunuri pe rutele cu cost asociat zero dinspre sursa fictivă).

Odată introdusă sursa fictivă, oferta totală egalează cererea totală, iar modelul PPL poate fi folosit să genereze o soluţie. Pentru valoarea optimă obţinută, destinaţiile care primesc transporturi dinspre sursa fictivă vor fi cele pentru carecererea nu poate fi satisfăcută în totalitate. Prin introducerea


sursei fictive în modelul PPL se va genera un program de transport cu cost minim pentru toată oferta disponibilă şi se vorindica în plus acele destinaţii pentru care există cerere nesatisfăcută.

În unele formulări de probleme este posibil (sau este de dorit) să se considere profitul sau venitul pentru fiecare unitate transportată decât să se ia în considerare costul unitar. Folosirea venitului sau a profitului unitar în coeficientul funcţiei obţinute va impune rezolvarea unei probleme de maxim şi nu de minim (criteriul costului în modelul PPL). Restricţiile vor fi afectate de această modificare.

Formularea problemelor de transport poate fi modificată pentru a lua în considerare capacitatea de transport pentru una sau mai multe rute. De exemplu presupunem că pe ruta Oradea-Bucureşti (sursa 3, destinaţie 1) capacitatea de transport este de 1000 unităţi din cauza spaţiului disponibil de transport limitat, restricţie care este impusă de mărimea vehiculului de transport. Această limitare a capacităţii de transport pe rută poate fi reprezentată în modelul PPL prin adăugarea unei restricţii care corespunde cu limitarea superioară a variabilei de decizie. Pentru x31 (care corespunde cantităţii de bun transportat între Oradea şi Bucureşti) în problema GM se introduce restricţia relativă la capacitatea de transport:

x31≤1000La fel, o rută pentru care nivelul minim de unităţi de

marfă transportate este specificat poate fi x22≥2000, ceea ce va garanta că numărul unităţilor transportate de la Cluj la Craiova va fi de cel puţin 2000 unităţi.

Ca o situaţie particulară, cu ajutorul modeleului PPL este posibil să nu se poată obţine o rută de la fiecare sursă spre (A) destinaţie. Aceasta înseamnă că unele rute sunt


„inacceptabile”. Pentru a rezolva această situaţie, se elimină din problemă variabilele de decizie corespunzătoare acestei rute incluse în modelul în modelul PPL. Rezolvarea problemei în situaţia în care se consideră inacceptabilă ruta Braşov şi Constanţa va conţine 11 variabile, 7 restricţii, ceea ce va oferi soluţia optimă în care ruta specificată nu este utilizată.

Modelul general al problemelor de transport în reprezentarea unei PPL. Se folosesc următoarele notaţii care apar în modelul general al problemelor reprezentate printr-o PPL:

i = numărul de surse, i = m,1 ;

j = numărul destinaţiilor, j = n,1 ;xij = cantitatea transportată din sursa i spre destinaţia j;cij = costul de transport asociat rutei dintre sursa i spre destinaţia j;si = cantitatea de bun sipoanibilă în sursa i;dj = cantitatea de bun cerută în destinaţia j.

Modelul general pentru probleme de transport în care sunt m surse şi n destinaţii este:

min

m

1j

ijij

n

1i

xc

m1,isx i

m

1i

ij

oferte

n1,jdx j

n

1i

ij

cereri

xij ≥ 0 () i, j


Dacă în problema de transport – problemă de

programare liniară oferta totală (

m

1i

is ) este mai mică sau egală

cu cererea totală (

n

1j

id ), o sursă fictivă va oferi exact cantitatea

de bun care reprezintă excesul de cerere. Această sursă fictivă poate fi notată prin m+1, iar cantitatea oferită (fictiv) de această sursă este determinată ca:

sm+1 =

m

1i

i

n

1j

j sd

Pentru a fi siguri că soluţia optimă obţinută în urma acestui artificiu va reprezenta costul total de transport, toţi coeficienţii din funcţia obiectiv asociaţi surselor fictive vor fi nuli (nu se va efectua nici un transport dinspre sursele fictive).

Dacă unele rute au restricţii fictive la capacitatea de transport se vor adăuga restricţii de forma xij≤Lij, unde Lij

reprezintă limita superioară sau capacitatea maximă de transport a rutei ce leagă sursa i de destinaţia j. Dacă, similar, nivelul minimal acceptat pentru transport pe o rută există, atunci se adaugă restricţia de forma xij≥Lij. Aici Lij corespunde nivelului minim de marfă ce poate fi transportat de la o sursă i spre destinaţia j.


2.3PROBLEMA DE TRANSPORT. PROCEDURĂ PRACTICĂ DE REZOLVARE

Dacă problema de transport are 100 de surse şi 500 de destinaţii, aceasta implică 100500=50000 de variabile de decizie în problema de transport – problemă de programare liniară. Acest fapt a determinat realizarea de proceduri practice de rezolvare a problemei de transport care să nu necesite rezolvarea unei probleme de programare liniară asociate problemei de transport. Structura specială a problemei de transport - problemă de programare liniară a permis managerilor să folosească o procedură foarte simplificată pentru realizarea facilă a calculelor.

În problemele GM avem 12 variabile de decizie şi 7 restricţii. Este clar că rezolvarea problemelor GM ca problemă de transport - problemă de programare liniară necesită un efort de calcul considerabil prin rezolvarea folosind Algoritmului Simplex. Prin procedura practică de rezolvare pot fi uşor rezolvate probleme de transport de mărime mică.

Tabelul nr. 2. 4Destinaţii

SurseBucureşti Craiova Constanţa Iaşi

Oferta sursei

3 2 7 6Braşov 5000

7 5 2 3Cluj 6000

2 5 4 5Oradea 2500

Cererea destinaţiei

6000 4000 2000 1500 13500

Celulă corespunzătoare transportului de la Oradea la Bucureşti

n

1j

id =

m

1i

is

cerere = oferta


Aplicarea procedurii practice de rezolvare în problema GM presupune găsirea unei soluţii iniţiale fezabile şi apoi prin interaţii succesive care aduc îmbunătăţiri soluţiei se va determina soluţia optimă şi se va folosi o reprezentare tabelară care va conţine datele problemei şi este utilă în efectuarea calculelor, Tabelul nr. 2.4, unde sunt 12 celule care corespund celor 12 rute de transport (arce) reprezentate în Figura nr. 2.1.

Fiecare celulă de tabel corespunde unei rute transport de la o sursă spre un centru de distribuţie. Cifrele din colţul dreapta sus al fiecărei celule reprezintă costurile de transport asociate fiecărei rute.

În partea dreaptă a tabelului sunt trecute cantităţile disponibile în fiecare sursă, iar în linia de jos sunt reprezentatevalorile cererii la destinaţie. În colţul dreapta jos al tabelului se trece nivelul cererii = nivelul ofertei.

După realizarea tabelului, se trece la rezolvarea problemei de transport care presupune determinarea unei soluţii iniţiale fezabile.

2.3.1 Găsirea unei soluţii iniţiale fezabile. Metoda Costului Minim

Metoda costului minim pentru identificarea unei souţii iniţiale fezabile presupune alocarea a cât mai multe unităţi spre a fi transportate pe rutele de cost minim.

Paşii de parcurs în aplicarea Metodei costului minim pentru obţinerea soluţiei iniţiale fezabile a problemei de transport sunt:

Pasul 1: Identificarea în tabelul de transport a celulei cu costul minim, şi apoi se asigură cât mai multe unităţi de transportat în respectiva celulă. Dacă există mai multe celule cu cost minim identic se ia în considerare celula în care se pot transporta un


număr maxim de unităţi. Dacă mai există alte celule candidate cu cost identic se va alege în continuare dintre acestea.

Pasul 2: Se reduce în rândul ofertei şi în coloana cererii cantitatea de bun asigurată la pasul 1.

Pasul 3: Dacă toate rândurile cu ofertă şi coloanele cu cerere au fost tăiate, atunci s-a obţinut soluţia iniţială fezabilă. În caz contrar se continuă cu pasul 4.

Pasul 4: Dacă pe rândul ofertei este acum un disponibil nul, se elimină linia respectivă prin tăietură. Dacă pe coloana cererii nivelul acesteia este nul, se elimină coloana prin tăietură. Dacă atât linia cât şi coloana sunt tăiate se va face o nouă alocare de zero unităţi pe una din celulele deja tăiate de o linie, pe coloană sau rând.

Pasul 5: Se continuă cu pasul 1 până sunt „tăiate” toate rândurile şi coloanele.

În Tabelul nr. 2.4 se observă că rutele Braşov-Craiova, Cluj-Constanţa şi Oradea-Bucureşti au costul minim de 2 u.m.

Dacă în problemă apar mai multe rute cu cost minim, este practic, util, să se aloce transportul pe ruta care are capacitatea de transport cea mai mare. În problema de faţă, cantitatea maximă - 4000 unităţi - poate fi transportată de la Braşov la Craiova. Aceasta va reduce cantitatea disponibilă la Braşov de la 5000 la 1000, valoarea iniţială a ofertei la Braşov va fi de 1000 iar valoarea cererii nesatisfăcute în Craiova va fi de 4000-4000=0 unităţi. Valoarea iniţială a cererii de 4000 va fi înlocuită pentru Craiova cu 0. Acum se poate elimina coloana corespunzătoare destinţiei Craiova pentru că cererea a fost aici complet satisfăcută.


Tabelul nr. 2. 5Destinaţii


Oferta sursei

3 2 7 6Braşov4000

50001000

7 5 2 3Cluj 6000

2 5 4 5Oradea 2500


60004000

02000 1500 13500

Acum se vor urmări doar celulele care nu au fost „tăiate” cu o linie pentru a identifica noua rută de cost minim. Aceasta este între Cluj – Constanţa şi Oradea – Bucureşti.

Tabelul nr. 2.6Destinaţii


Oferta sursei

3 2 7 6Braşov4000

50001000

7 5 2 3Cluj 6000

2 5 4 5Oradea

25002500

0


60003500

40000

2000 1500 13500

Se alege ruta Oradea – Bucureşti pentru că poate fi satisfăcută o cerere de 2500 unităţi (în comparaţie cu Cluj –Constanţa care permite o satisfacere a cererii cu doar 2000 unităţi). Astfel, oferta din Oradea devine nulă prin alocarea întregii cantităţi disponibile care va fi transportată în Bucureşti. Oferta de 2500 din Oradea va fi înlocuită cu 0 şi cererea în


Bucureşti se va reduce de la 6000 la 3500. Linia corespunzătoare ofertei din Oradea va fi eliminată prin „tăiere”.



Oferta sursei

3 2 7 6Braşov4000

50001000

7 5 2 3Cluj

200060004000

2 5 4 5Oradea

25002500

0


60003500

40000

20000

1500 13500

Următorul cost minim din tabel este pe ruta Cluj –Constanţa. Acum poate fi satisfăcută cererea de 2000 de unităţi în Constanţa, din totalul disponibil în Cluj de 6000 unităţi, iar în Constanţa cererea este satisfăcută integral, valoarea iniţială va fi înlocuită cu valoarea 0, iar valoarea corespunzătoare cererii din Constanţa va fi „tăiată”.



Oferta sursei

3 2 7 6Braşov4000

50001000

7 5 2 3Cluj

2000 1500

600040002500

2 5 4 5Oradea

25002500

0


60003500

40000

20000

15000

13500


În continuare costul minim este de 3 u.m. pe rutele Braşov-Bucureşti şi Cluj-Iaşi. Pe prima rută pot fi transportate 1000 unităţi iar pe a doua 1500 unităţi. Conform regulii adoptate, se vor aloca 1500 unităţi de la Cluj la Iaşi. Cererea în Iaşi se satisface complet, coloana corespunzătoare se va elimina din tabel, iar oferta din Cluj scade de la 4000 la 2500 unităţi ce au rămas disponibile.



Oferta sursei

3 2 7 6Braşov

1000 4000

50001000

07 5 2 3

Cluj2000 1500

600040002500

2 5 4 5Oradea

25002500

0


600035002500

40000

20000

15000

13500

Următorul nivel minim al costului este 3 pe ruta Braşov – Bucureşti. Cerea rămasă nesatisfăcută în Bucureşti are nivelul de 3500 unităţi. Din acest total pot fi satisfăcute 1000 unităţi disponibile în Braşov. Noul disponibil, aici, devenind nul, ceea ce presupune eliminarea liniei corespunzătoare surseiBraşov.

Se constată că rămân 2500 unităţi disponibile în Cluj, iar cererea din Bucureşti este de 2500, ceea ce conduce la satisfacerea cererii din Bucureşti cu disponibilul rămas în Braşov. Valorile de 2.500 unităţi disponibil şi respectiv cerere, respectiv în Cluj şi Bucureşti devin nule, linia corespunzătoare


sursei Cluj şi coloana corespunzătoare destinaţiei Bucureşti se „taie”.

Tabelul nr. 2.10

De la La Cantitatea

transportatăCost unitar Cost total

Braşov Bucureşti 1 000 3 3 000Braşov Craiova 4 000 2 8 000

Cluj Bucureşti 2 500 7 17 500Cluj Constanţa 2 000 2 4 000Cluj Iaşi 1 500 5 4 500

Oradea Bucureşti 2 500 2 5 000TOTAL 13500 - 42 000

Întrucât s-au alocat toate cele 13.500 unităţi cerute din totalul de 13.500 disponibile, s-a determinat o soluţie. Această soluţie este fezabilă pentru că toată cererea este satisfăcută de toată oferta disponibilă. Datele corespunzătoare acestei soluţii obţinute prin Metoda Costului Minim sunt trecute în Tabelul nr. 8.10.Observaţie: Aşa cum se poate deduce, această soluţie nu este soluţia optimă.

În continuare, această metodă va presupune trecerea acestei soluţii fezabile spre soluţia optimă. Metoda costului minim poate fi folosită doar de soluţia iniţială fezabilă a problemei cu m surse şi n destinaţii foloseşte exact m+n-1 rute de transport. Astfel, problema GM trebuie să folosească 3+4-1=6 rute de transport în soluţia iniţială. Pentru problema GM soluţia iniţială fezabilă satisface această condiţie.

Pentru a garanta că metoda costului minim va genera întotdeauna o soluţie iniţială fezabilă cu m+n-1 rute pe care vor fi folosite la transport trebuie efectuate unele modificări.

Ultima alocare de la Cluj la Bucureşti de 2500 unităţi a


presupus alocarea întregului disponibil rămas de 2500 unităţi pentru a satisface cererea din Bucureşti.

În determinarea soluţiei iniţiale fezabile, ultima alocare reduce întotdeauna atât o linie a ofertei cât şi o coloană a cererii, astfel încât cererea şi oferta nesatisfăcute devin zero. În această situaţie se obţine o soluţie iniţială fezabilă cu mai puţin de m+n-1 rute de transport folosite. Pentru a preveni acea situaţie în care atât cererea cât şi oferta se reduc simultan la valoarea zero se poate proceda la:1. Eliminarea liniei şi a coloanei prin „tăierea” acestora.2. În plus se va adăuga unei celule aflate la intersecţia

rândului „tăiat“ şi a coloanei, un transport de zero unităţi, fie pentru linia, fie pentru coloana „tăiată“. Această celulă va fi tratată la fel ca şi cele pentru care s-a asociat o cantitate de transportat.

Pentru a urmări cum se aplică această procedură se ia în considerare următoarea problemă care are 3 surse şi 4 destinaţii. Reprezentarea iniţială este următoarea:


SurseD1 D2 D3 D4

Oferta

6 8 3 10S1 30

2 9 5 7S2 15

7 8 6 4S3 15

Cererea 10 25 10 15 60

Prin aplicarea Metodei Costului Minim se alocă pe ruta S2-D1 cu costul minim asociat (=2) un transport de 10 unităţi. Se trece la următoarea reprezentare:



SurseD1 D2 D3 D4

Oferta

6 8 3 10S1 103020

2 9 5 7S2 10

155

7 8 6 4S3 0

15

Cererea 100

25100

15 60

Corespunzător, următoarea alocare este pe ruta S1-D3 cu 10 unităţi transportate. Apoi pe ruta S3-D4 care are costul minim (=4) se constată că se reduc simultan linia lui S3 şi coloana lui D4 pentru care oferta şi cererea devin simultan zero. Dacă se elimină această linie şi respectiv coloană, singurele celule care mai rămân „netăiate” sunt corespunzătoare lui S1-D2 şi S2-D2. Astfel, ar trebui asigurată o valoare de 0 unităţi transportate de la S2 la D1 sau zero unităţi transportate de la S3

la D4. Prin asigurarea valorii pentru celula S3-D1 se obţine următorul tabel de transport.


SurseD1 D2 D3 D4

Oferta

6 8 3 10S1 103020

2 9 5 7S2 10

155

7 8 6 4S3 0 15

150

Cererea 100

25100

15 60

Flux de 0 unităţi creat artificial

Ambele se reduc, simultan la 0


În continuare se obţine tabelul în care soluţia1 va fi:S1 - D2 : 20S1 - D3 : 10S2 - D1 : 10S2 - D2 : 5S3 - D1 : 0 S3 - D4 : 15

unităţi transportate, şi se folosesc m+n-1=3+4-1=6rute de transport.

Soluţia astfel determinată este optimă.

1 O altă metodă care poate conduce la obţinerea unei soluţii iniţiale fezabile este metoda costului de NV.


2.4METODA STEPPING-STONE

Această metodă oferă o procedură iterativă care permite deplasarea de la soluţia fezabilă iniţială spre o soluţie optimă. Ea este folosită pentru a evalua transportul pe acele rute care nu fac parte din soluţia problemei de transport. Dacă se găsesc rute cu costuri mai mici, atunci soluţia curentă este înlocuită (îmbunătăţită) prin efectuarea de transporturi pe aceste noi rute. Corespunzător, dacă acele rute (care au costuri asociate) care nu sunt înlocuite în soluţia curentă vor determina creştereacosturilor, nu vor fi acceptate la determinarea soluţiei optime.

Pentru ilustrare, se va folosi problema iniţială a GM pe care s-a aplicat metoda costurilor şi s-a determinat soluţia iniţială fezabilă.



Oferta sursei

3 2 7 6Braşov1000 4000

5000

7 5 2 3Cluj

2500 2000 15006000

2 5 4 5Oradea

25002500


6000 4000 2000 1500 13500

Se presupune că se alocă o unitate în celula aflată la intersecţia coloanei 2 cu rândul 2 (ruta Cluj-Craiova). Astfel, pentru a satisface cererea din Craiova la nivelul stabilit, trebuie redus transportul de la Braşov la Craiova la 3999 unităţi transportate, cantitatea de la Braşov la Bucureşti va fi crescută cu o unitate, la 1001, astfel încât oferta din Braşov să fie


menţinută la 5000 şi se va reduce cantitatea transportului de la Cluj la Bucureşti cu o unitate, de la 2500 la 2499 pentru ca cererea din Bucureşti să fie în continuare tot la 6000 unităţi.

În Tabelul nr. 2.15 de mai jos sunt reprezentate efectele induse de aplicarea metodei la nivelul costului.

Tabelul nr. 2.15Ruta Modificări Efect în cost

Cluj-Craiovatransport suplimentar 1 unitate

+5

Braşov-Craiova transport redus cu 1 unitate -2

Braşov-Bucureştitransport suplimentar 1 unitate

+3

Cluj-Bucureşti transport redus cu 1 unitate -7Efect net -1

Din analiza tabelului rezultă că se reduce costul de transport cu 1 u.m. pentru fiecare unitate transportată suplimentar de la Cluj la Craiova cu modificările corespunzătoare în celelalte rute.

Înainte de a adăuga această rută se consideră procedura generală de evaluare a costurilor asociate cu o nouă rută (sau celulă) şi apoi se verifică toate rutele neutilizate pentru a îmbunătăţi soluţia problemei de transport. Metoda constă în evaluarea efectului unei modificări în alte rute care fac parte din soluţia curentă a problemei de transport, soluţie care constă din „celulele ocupate”. Deplasarea se face între celulele care constituie parte a soluţiei curente, pe orizontală şi verticală astfel încât se va ajunge la celula de unde s-a pornit iniţial. Deplasarea între celule este reprezentată prin linia punctată,precum se observă în tabelul următor, pentru evidenţierea modificărilor: Cluj-Craiova, Braşov-Craiova, Braşov-Bucureşti


şi Cluj-Bucureşti, care presupune o reprezentare a parcurgeriiîn sens antiorar în tabel.



Oferta sursei

3 2 7 6Braşov1000 4000

5000

7 5 2 3Cluj

2500 2000 15006000

2 5 4 5Oradea

25002500


6000 4000 2000 1500 13500

În continuare se consideră modificări pe ruta Braşov-Constanţa cu efect şi pe rutele Cluj-Constanţa şi respectiv Braşov-Bucureşti.



Oferta sursei

3 2 7 6Braşov1000 4000

5000

7 5 2 3Cluj

2500 2000 15006000

2 5 4 5Oradea

25002500


6000 4000 2000 1500 13500

Celulă ocupată care a intrat în iteraţia metodei

Celulă neocupată

Celulă ocupată care nu a intrat în iteraţia metodei


Modificările induse pe cele 4 rute considerate în tabelul anterior sunt evidenţiate în Tabelul nr. 2.17.

Modificarea precedentă a soluţiilor induce un cost unitar suplimentar de 9 u.m. fapt ce denotă că această rută nu este atractivă pentru că alegerea sa conduce la creşterea costului total.

Tabelul nr. 2.18Ruta Modificări Efect în cost

Braşov-Constanţatransport suplimentar 1 unitate

+7

Cluj-Constanţa transport redus cu 1 unitate -2

Cluj-Bucureştitransport suplimentar 1 unitate

+7

Braşov-Bucureşti transport redus cu 1 unitate -3Efect net +9

Găsirea fiecărei noi posibile „celule candidate” ajută la identificarea efectului unei noi rute asupra costului total. Evaluarea efectului pentru toate rutele posibile este reprezentat în tabelul următor unde modificările în costul unitar sunt reprezentate prin valorile încercuite:



Oferta sursei

3 2 7 6Braşov1000 4000

5000

7 5 2 3Cluj

2500 2000 15006000

2 5 4 5Oradea

25002500


6000 4000 2000 1500 13500

+4

+9 +7

+7+7

-1


Din Tabelul nr. 2.18 se constată că cea mai bună modificare a costului în sensul reducerii acestuia este reprezentată în celula Cluj-Craiova. Pe această nouă rută se poate transporta un maxim de 2500 unităţi, care nu vor mai fi alocate de la Cluj la Bucureşti, ci de la Cluj la Craiova. Aceasta determină o reducere a cantităţii transportate de la Braşov la Craiova cu 2500 unităţi şi renunţarea la ruta Cluj-Bucureşti.

Toate modificările făcute au păstrat restricţiile asupra cererii în Bucureşti şi Craiova şi restricţiile asupra ofertei la Braşov şi Cluj. Noua soluţie este reprezentată în Tabelul nr. 2.19. În acest tabel este reprezentată prima modificare indusă de metoda Stepping Stone care presupune o reducere a costului total din soluţia iniţială fezabilă cu 2500 u.m. de la 42 000 u.m. la 39 500 u.m. Dacă se evaluează acum modificările induse în cost la noua soluţie, toate rutele neutilizate vor determina o creştere a cheltuielilor cu transportul.

În acest caz, prezentat în Tabelul nr. 2.19, s-a obţinut situaţia optimă, care reprezintă chiar soluţia problemei de transport problemă de programare liniară.



Oferta sursei

3 2 7 6Braşov3500 1500

5000

7 5 2 3Cluj

2500 2000 15006000

2 5 4 5Oradea

25002500


6000 4000 2000 1500 13500

Soluţia problemei este prezentată în Tabelul nr. 2.20.


Tabelul nr. 2.21

De la la Cantitatea

transportatăCost unitar Cost total

Braşov Bucureşti 3 500 3 10 500Braşov Craiova 1 500 2 3 000

Cluj Craiova 2 500 5 12 500Cluj Constanţa 2 000 2 4 000Cluj Iaşi 1 500 3 4 500

Oradea Bucureşti 2 500 2 5 000TOTAL 13500 - 39 500

Determinarea modificărilor în costuri, induse de schimbarea rutelor de transport se realizează prin următoarea procedură:a) se stabileşte un index ui pentru fiecare rădăcină din tabel;b) se stabileşte un index vj pentru fiecare rădăcină din tabel;c) se asociază un coeficient cij pentru fiecare celulă ocupată din

tabelul de transport unde cij= ui+vj. dacă cij reprezintă costul transportului din sursa i către destinaţia j;

d) se constituie un sistem de m+n-1 ecuaţii cu m+n necunoscute care se rezolvă pentru un u=0.



Oferta sursei

3 2 7 6Braşov3500 1500

5000

7 5 2 3Cluj

2500 2000 15006000

2 5 4 5Oradea

25002500


6000 4000 2000 1500 13500

+4

+8

+6

+6

+6

-1


Pe exemplul GM unde trebuie să dispunem de m+n-1, adică 3+4-1=6 rute de transport în soluţia iniţială pentru ca aceasta să fie fezabilă, aşa cum se reprezintă în tabelul următor:



Oferta sursei

3 2 7 6Braşov1000 2500

3500

7 5 2 3Cluj

2500 2000 15006000

2 5 4 5Oradea

25002500


6000 2500 2000 1500 12000

Celulele ocupate sunt:Braşov – Bucureşti: u1 + v1 = 3Braşov – Craiova: u1 + v2 = 2 Cluj – Bucureşti: u2 + v1 = 7Cluj – Constanţa: u2 + v3 = 2Cluj – Iaşi: u2 + v4 = 3Oradea – Bucureşti: u3 + v1 = 2

Pentru u1=0 se obţin: v1=3v2 = 2u2 + v1 = 7 u2 = 4u2 + v3 = 2 v3 = -2u2 + v4 = 3 v4 = -1u3 + v1 = 2 u3 = -1

e) modificările nete unitare în costul de transport se determină pe baza relaţiei eij = cij –ui –vj. Acestea sunt trecute în tabelul următor ca valori încercuite:


Tabelul nr. 2.24vjui

3 2 -2 -13 2 7 60

1000 25007 5 2 3

42500 2000 1500

2 5 4 5-1

2500

Tabelul nr. 2.24 indică prin valoarea –1, aflată la intersecţia rândului 2 cu coloana 2, o scădere a costului cu o u.m. pentru fiecare unitate transportată pe această rută, singura care permite „îmbunătăţirea” soluţiei. Dacă se consideră soluţia îmbunătăţită după aplicarea metodei Stepping Stone reprezentată în Tabelul nr. 2.25.


3 2 -2 -13 2 7 60

1000 25007 5 2 3

42500 2000 1500

2 5 4 5-1

2500

se obţine următorul sistem de 6 ecuaţii cu 7 necunoscute:u1 + v1 = 3u1 + v2 = 2 u2 + v2 = 5u2 + v3 = 2u2 + v4 = 3u3 + v1 = 2

iar pentru u1=0 se obţine următorul sistem echivalent:

v1 = 3v2 = 2u2 + v1 = 5 u2 = 3u2 + v3 = 2 v3 = -1u2 + v4 = 3 v4 = 0u3 + v1 = 2 u3 = -1

+4

+9 +7

+7+7

-1

+4

+9 +7

+7+7

-1


Soluţia acestui sistem este:u1 = 0 v1 = 3u2 = 3 v2 = 2u3 = -1 v3 = -1

v4 = 0

Se asociază valorile soluţiei liniilor şi se calculează eij

pentru celulele care nu sunt incluse în soluţia problemei:


3 2 -1 03 2 7 60

3500 15007 5 2 3

42500 2000 1500

2 5 4 5-1

2500

Se observă că valorile lui eij obţinute corespund cu cele din tabelul 2.22, tabel care conduce spre soluţia optimă.

În Tabelul nr. 2.26, obţinut anterior:e13 = ci3–u1–v3 = 7 - 0 - (-1)=8

reprezintă schimbarea netă în costul total determinat de folosirea rutei de la sursa 1 spre destinaţia 3.

Folosirea metodei distribuţiei modificate (MDM) generează aceleaşi modificări nete ca şi metoda Stepping Stone, fapt ce ajută la rezolvarea mai facilă a problemei.

+4

+8 +6

+6+6

-1


2.5SITUAŢII SPECIALE CARE APAR ÎN PROBLEMA DE TRANSPORT

În practică pot să apară situaţii speciale ale problemei de transport precum:

1. cererea totală nu egalează oferta totală;2. problema de rezolvat conţine funcţia obiectiv de

maximizat;3. rute de transport care nu pot fi folosite (rute blocate).

Prima situaţie se rezolvă prin introducerea unei destinaţii fictive sau a unei surse fictive. Dacă oferta depăşeşte cererea se introduce o destinaţie fictivă cu o cerere reprezentând excesul de ofertă. Dacă cererea este excedentară ofertei, se introduce o sursă fictivă cu o ofertă reprezentând exact cererea excedentară. În ambele situaţii costurile asociate transporturilor spre sau dinspre destinaţiile fictive vor fi nule.

Dacă problema de transport implică obiectiv de maxim, singurele modificări care apar în rezolvare se referă la „celulele neocupate”. În locul alegerii acelor valori eij negative, minime, se vor alege cele acele valori ale eij cu cea mai mare valoare pozitivă, pentru că acestea vor determina creşterea funcţiei obiectiv.

În situaţia în care există rute de transport inacceptabile (blocate), atunci se vor ataşa acestora niveluri ale costului cu valori foarte mari (M) pe unitate de bun transportată, iar în acest caz costul total va creşte foarte mult. În problemele de maxim, coeficienţii din funcţia obiectiv pentru cantităţile ce (nu) vor fi transportate pe aceste rute vor fi valori negative foarte mari, –M.

Se consideră în continuare un exemplu practic: se presupune că sunt trei producători (surse) care au următoarele capacităţi de producţie:


Tabelul nr. 2.27Producător Capacitate de producţie

P1 50P2 40P3 30

Total disponibil 120

Cererea previzionată înregistrată pentru aceste produse la vânzătorii detailişti este prezentată în tabelul următor:

Tabelul nr. 2.28Detailist Cerere previzionată

V1 45V2 15V3 30

Total cerere 90

Costurile de producţie variază de la un producător la altul, iar preţurile de vânzare sunt diferite de la un vânzător la altul. Prin luarea în considerare a acestor preţuri de producţie şi de transport, profitul obţinut pentru o unitate de bun realizat de producătorul i şi vândut de detailistul j este prezentat în Tabelul nr. 2.29.

Tabelul nr. 2.29 Profit unitar al producătorilorDetailist

ProducătorV1 V2 V3

P1 2 8 10P2 6 11 6P3 12 7 9


Se observă că disponibilul depăşeşte cererea cu 120–90=30 unităţi. Aceasta determină introducerea unui consumator fictiv care va consuma surplusul de 30 de unităţi. Profitul unitar asociat şi cantitatea consumată de consumatorul fictiv vor fi nule, deoarece bunurile respective nu sunt nici produse şi nici transportate.


SurseV1 V2 V3 V4

Oferta

2 8 10 0P130 20

5020

6 11 6 0P2 15 15 10

402510

12 7 9 0P3 30

300

Cererea 45150

150

300

30

Pentru a obţine o soluţie iniţială fezabilă se foloseşte o procedură similară cu metoda costului minim în condiţiile unei probleme de maximizare a profitului. Soluţia iniţială fezabilă este prezentată în Tabelul nr. 2.30.

Consumatorul V4, este cel fictiv, el are un profit unitar asociat nul. Soluţia iniţială fezabilă foloseşte m+n–1=3+4–1= 6 rute.

În tabelul următor se asociază valorile ui şi vj pentru determinarea eij=cij–ui–vj, unde cij reprezintă profitul unitar asociat transportului unei unităţi de bun de la producătorul i spre vânzătorul j, pentru toate celulele neocupate:



SurseV1 V2 V3 V4

Oferta

2 8 10 0P1 30 2050

6 11 6 0P2 15 15 1040

12 7 9 0P3 30

30

Cererea 45 15 30 30

Se rezolvă sistemul:

u1 + v1 = 2u1 + v2 = 8 u2 + v3 = 6u3 + v2 = 7u3 + v3 = 9u3 + v4 = 0

pt. v4 = 0 u1 + v1 = 2 u1 + v2 = 8u2 + v3 = 6u3 + v2 = 7u3 + v3 = 9u3 + v4 = 0

u1 = 1u2 = -3u3 = 0v1 = 1v2 = 7v3 = 9

Deoarece toate eij induc o modificare cu 0 unităţi de profit se deduce că soluţia iniţială fezabilă este optimă.

00

0

000

CAPITOLUL 3

MODELAREA PROBLEMELOR DE DISTRIBUŢIE PRIN MODELE DE REŢEA

Multe probleme manageriale care apar curent în designul sistemelor de transport, în designul sistemelor informaţionale şi programarea proiectelor, pot fi rezolvate cu ajutorul modelelor de reţea şi prin tehnicile de analiză a reţelelor. În rezolvarea problemelor de transport, reţeaua de transport constă în noduri şi arce. Aici, vor fi prezentate trei tipuri mari de probleme de reţea: problema rutei cele mai scurte, problema arborelui de acoperire maximală şi problema de flux maxim. În fiecare caz se va dezvolta un model de reţea care va fi rezolvat pentru obţinerea soluţiei optime a problemei.

3.1 Problema celei mai scurte rute

Se consideră reţeaua din perspectiva proiectării şi desemnării unui sistem de transport, unde principalul scop este de a determina cea mai scurtă rută în reţea. Se va dezvolta şi rezolva problema celei mai scurte rute pe cazul aplicativ al Nord Construct (NC). NC operează în prezent mai multe proiecte de construcţii localizate în judeţe diferite. Şantierele sunt uneori la peste 20 km distanţă de sediul firmei.

M O D E L A RE A P R O B L EM E L O R DE D I S T R I B U Ţ I E P R I N M O D E L E D E R E Ţ E A5 4

Cheltuielile firmei cu transportul zilnic al personalului, al echipamentelor şi al materialelor spre şi dinspre şantiere sunt considerabile. Pentru fiecare şantier, drumurile alternative pot fi reprezentate ca în drumuri sau străzi în reţeaua de transport. În figura următoare sunt reprezentate alternativele de transport de la şantiere şi de la sediul NC.

Figura nr. 3. 1 Reţeaua de drumuri pentru problema NC

Arcurile (nodurile) din reţea corespund locaţiilor şantierelor. Drumurile şi străzile apar reprezentate prin arce de reţea. Distanţa dintre şantiere este reprezentată prin valori asociate fiecărei rute. Lungimea rutei nu este proporţională cu reprezentarea arcelor în reţeaua de transport. Dacă NC doreşte să minimizeze distanţa totală de transport de la sediul firmei spre fiecare şantier, atunci care este cea mai scurtă rută în reţea, spre fiecare locaţie?

3.1.1 Algoritmul celei mai scurte rute

Pentru a determina cea mai scurtă rută în cazul problemei NC trebuie stabilită cea mai scurtă de la sediul NC (nodul 1) la fiecare dintre celelalte noduri din reţea. Algoritmul

M O D E L A RE A P R O B L EM E L O R DE D I S T R I B U Ţ I E P R I N M O D E L E D E R E Ţ E A 5 5

folosit ataşează fiecărui nod o etichetă. Prin procedura de etichetare se ataşează la fiecare nod o etichetă formată din două valori incluse între paranteze drepte. Prima valoare indică distanţa de la nodul 1 la nodul etichetat, iar a doua valoare arată nodul precedent din care s-a ajuns în nodul curent.

În orice moment al aplicării procedurii de etichetare vor exista noduri etichetate şi/sau noduri neetichetate. Un nod etichetat este un nod pentru care s-a identificat drumul cel mai scurt dinspre nodul 1, iar cel neetichetat nu a fost încă evaluat. Reprezentarea următoare prezintă un exemplu de etichetă:

Figura nr. 3. 2 Etichetă asociată unui nodValoare care arată că distanţa de la nodul iniţial până la nodul curent este 10

[10, 7]

Valoare care indică faptul că nodul precedent celui curent este nodul 7

Un nod odată etichetat, poate fi considerat etichetat definitiv sau etichetat temporar. Atunci când un nod este etichetat definitiv, algoritmul a generat ruta cea mai scurtă la acel nod, iar pentru etichetele temporare, încă nu s-a stabilit ruta cea mai scurtă.

În continuare se procedează la etichetarea nodurilor reţelei. Prin convenţie, nodului 1 i se asociază eticheta permanentă [0, S]. Valoarea 0 denotă că nodul 1 este nodul de start iar distanţa de la nodul 1 spre el însuşi este 0. S arată că nodul 1 este nodul se start. Pentru a recunoaşte un nod etichetat permanent, tot prin convenţie, acesta va fi reprezentat haşurat. În plus, o săgeată va fi folosită pentru a reprezenta care este nodul investigat la fiecare pas al algoritmului. Figura următoare arată că doar nodul 1 a fost etichetat permanent.


Figura nr. 3. 3

Pentru a considera primul pas, sau iteraţia ca algoritm de etichetare, trebuie considerat fiecare nod în care poate ajunge direct dinspre nodul 1. Se observă că „noduri candidate” sunt 2 şi 3. Pentru nodul 2 se remarcă distanţa asociată pe arc egală cu 15. Nodul 2 va fi etichetat ca temporar cu eticheta [15, 1]. Din nodul 1 se parcurg 15 km până în nodul 2. Apoi pentru nodul 3 se observă că distanţa asociată rutei de la nodul 1 spre nodul 3 este 10, fapt care determină etichetarea temporară a nodului 3 cu [10, 1]. Figura 3.4 arată rezultatul acestei iteraţii cu etichetele temporare.

Pentru a continua se ia în considerare nodul care are drumul de cost minim asociat dintre nodurile etichetate temporar.

Figura nr. 3. 4


Dintre cele două noduri se alege nodul 3 cu distanţa faţă de nodul de start egală cu 10. În nodul 3 se poate ajunge din nodul 1 cu parcurgerea distanţei 15 + 3=18 km parcurgerea distanţei 10 + 3=13.

Pentru nodul 3 se determină minimul dintre 10 şi 13, ceea ce înseamnă că nodului 3 i se poate stabili eticheta permanentă ca în Figura 3.5 şi se va reprezenta haşurat nodul 3.

Figura nr. 3. 5

Odată ce nodului 3 i-a fost determinată eticheta permanentă, se va asocia acum o săgeată precum în Figura nr. 3.5.

Acum se vor lua în considerare toate nodurile care nu au etichetă permanentă şi la care se poate ajunge din nodul 3. Acestea sunt nodurile 2 şi 5.


Figura nr. 3. 6

Se calculează distanţa la aceste noduri pornind din nodul 3 şi se ataşează etichetele corespunzătoare. Practic se observă din figura următoare că nodul 2 are asociate două etichete. Dintre acestea se alege cea care indică distanţa minimă.

Deoarece în nodul 2 se poate alege între două posibile rute, pentru un drum minim la nodul 2, este preferată ruta care porneşte din nodul 1 şi trece prin nodul 3. În consecinţă eticheta [15, 1] este înlăturată şi înlocuită cu [13, 3].

Figura nr. 3. 7


În nodul 2 nu se mai poate ajunge pe o rută mai scurtă. Acestui nod i se consideră eticheta permanentă [13, 3], iar nodul va fi reprezentat haşurat şi se va reprezenta săgeata de marcaj în dreptul nodului 2 (Figura nr. 3.7).

Se calculează apoi distanţele şi se ataşează etichetele pentru toate nodurile care au arce adiacente cu nodurile 2 şi 5. acestea sunt nodurile 4 şi 3. Etichetele sunt în nodul 4, [19, 2] (13+6=19 km privind nodul 2) şi respectiv în nodul 7 eticheta este [30, 2]. În nodul 4 se poate ajunge din nodul 5, distanţa parcursă fiind 14+4=18 km, eticheta temporară asociată fiind [18, 5]. Comparând etichetele [19, 2] şi [18, 5] se constată că distanţa minimă spre nodul 4 este parcursă dinspre nodul 5. Se renunţă la eticheta temporară asociată nodului [19, 2] şi se barează. Eticheta [18, 5] asociată nodului 4 devine permanentă. De asemenea pentru nodul 5 care are eticheta [14, 3], aceasta devine permanentă. Nodul 5 va fi reprezentat haşurat, iar săgeata de marcaj va fi reprezentată în dreptul nodului 5 (Figura 3.8).

Figura nr. 3. 8

De asemenea, se ataşează eticheta [16, 5] nodului 6 pentru care distanţa dinspre nodul 5 este 14+2=16. Acum nodul 4 devine nod cu etichetă permanentă [18, 5]. Se va reprezenta


acest nod haşurat, iar săgeta de marcaj va fi în dreptul său (Figura 3.9).

Figura nr. 3. 9

Din nodul 4 se determină distanţa dinspre nodul 3. Eticheta asociată nodului 7 este [23, 4] (18 + 5 = 23 km dinspre nodul 4). Nodul 6 devine nod căruia i se asociază etichetă permanentă [16, 5]. El va fi reprezentat haşurat şi se va muta săgeata de marcaj în nodul 6 Figura 3.10).

Figura nr. 3.10


Se calculează pentru nodul 7 distanţa dinspre nodul 6 şi se adaugă eticheta [22, 5]. Această etichetă va fi considerată permanentă şi vor fi eliminate etichetele [30, 2] şi [23, 4] care conferă o soluţie mai puţin convenabilă.

Nodul 7 fiind ultimul din reţea neetichetat cu etichetă permanentă, va fi acum considerat ca etichetat permanent. Astfel reţeaua de transport a NC cu rutele de distanţe minime vor fi reprezentate precum în Figura 3.11.

Figura nr. 3. 11

Etichetele permanente asociate fiecărui nod furnizează informaţia relativă la distanţa minimă de la sediul NC spre orice destinaţie. De exemplu de la nodul 6 se poate ajunge parcurgând minim 16 km, trecând prin nodurile 5, 3 şi 1, ruta de parcurs de la sediul firmei fiind: nodul 1, nodul 3, nodul 5 şi destinaţia, nodul 6.

În Tabelul nr. 3.1 sunt sintetizate rutele care trebuiesc parcurse astfel încât să se parcurgă o distanţă minimă în km de la sediul firmei spre fiecare punct de lucru:


Tabelul nr. 3.1Nod Ruta cea mai scurtă Distanţa (km)

2 1 – 3 – 2 133 1 – 3 104 1 – 3 – 5 – 4 185 1 – 3 – 5 146 1 – 3 – 5 – 6 167 1 – 3 – 5 – 6 – 7 22

O problemă de asemenea dimensiuni ar putea fi rezolvată şi doar prin încercări, deoarece numărul mic de rute permite „rezolvarea prin inspectarea situaţiilor posibile”. Acest lucru este posibil şi deoarece 7 noduri permit puţine rute alternative. Dacă problema ar avea 20 – 25 noduri, ar fi necesar destul de mult timp pentru rezolvarea prin inspecţie. De fapt, datorită numărului crescut de rute alternative, într-o reţea mare este destul de uşor să fie omise unele rute, iar soluţia problemei să nu fie cea potrivită, optimă. Pentru o problemă de dimensiuni mari se impune utilizarea procedurii sistematice folosite la rezolvarea problemei NC. Chiar şi în situaţia în care se foloseşte procedura de etichetare, pentru rezolvarea problemelor de mari dimensiuni, devine utilă folosirea unui algoritm corespunzător.

În determinarea rutei celei mai scurte prin procedura de etichetare vom considera o reţea formată din N noduri. Poate fi folosită următoarea procedură pentru determinarea celui mai scurt drum de la nodul 1 spre fiecare nod al reţelei:

Pasul 1: Se ataşează nodului 1 eticheta permanentă [0,S], unde S arată că nodul 1 este nodul de start, iar 0 arată că distanţa de la acest nod la el însuşi este 0.


Pasul 2: Se determină etichetele candidate pentru toate nodurile în care se poate ajunge direct din nodul 1. Prima valoare din etichetele candidate este chiar distanţa de la nodul 1 la fiecare dintre noduri. Se poate numi valoare a distanţei prima parte din etichetă. A doua valoare din etichetă reprezintă nodul precedent, în speţă nodul 1. În acest pas nodul precedent poate fi doar nodul 1.

Pasul 3: Se identifică dintre nodurile candidate la eticheta permanentă acel nod care are cea mai mică valoare a distanţei, şi se declară nod cu etichetă permanentă. Dacă toate nodurile sunt cu etichete permanente, se trece la pasul 5.

Pasul 4: Se consideră toate nodurile care nu au etichetă permanentă identificate la pasul 3. Se calculează etichetele candidate pentru nodurile în cauză, astfel:a) dacă un nod care nu are etichetă permanentă are o etichetă

candidată, se determină prin însumare valoarea distanţei dinspre nodul cu etichetă permanentă spre noul nod. Dacă suma este mai mică decât valoarea distanţei înainte calculată, noua valoare a distanţei este minima celor două. În plus, se va modifica nodul precedent din etichetă corespunzător nodului care determină distanţa cea mai mică. Se trece la pasul 3.

b) Dacă un nod cu etichetă temporară nu a mai avut o altă etichetă candidată, aceasta este creată cu o valoare a distanţei egală cu suma dintre valoarea distanţei de la nodul cu etichetă permanentă spre nodul în discuţie. Simbolul nodului precedent este schimbat cu cel al nodului dinspre care ruta parcursă este minimă. Se trece la pasul 3.

Pasul 5: etichetele permanente identifică distanţele cele maiscurte dinspre nodul 1 spre fiecare nod al reţelei precum şi


precedenţa în parcurgerea nodurilor în reţea. Cea mai scurtă rută spre un nod din reţea poate fi determinată prin parcurgerea drumului în sus invers, de la nodul respectiv spre nodul 1, prin citirea etichetelor care arată precedenţa. Se continuă parcurgerea în sus invers a nodurilor din reţea până la nodul 1 pentru fiecare nod al reţelei, generând astfel parcursul celei mai scurte rute de la nodul 1 spre fiecare nod din reţea.

Paşii procedurii vor determina soluţia problemei rutei de distanţă minimă în reţeaua de transport. Sunt necesari N – 1 iteraţii pentru acest algoritm pentru determinarea soluţiei optime. Dacă trebuie determinată doar cea mai scurtă distanţă spre un anumit nod, algoritmul se poate opri imediat ce nodului respectiv îi este asociată o etichetă permanentă. De asemenea, se poate determina care este drumul cel mai scurt de la un nod k din reţea spre celelalte noduri ale reţelei. În acest scop, nodului k îi va fi asociată eticheta permanentă [0, S]. după aplicarea paşilor algoritmului poate fi găsită cea mai scurtă rută de la nodul k spre toate celelalte noduri din reţea.

În problema NC s-a folosit ca măsură de prim interes distanţa, dar pot fi folosite şi alte criterii precum: timpul necesar pentru deplasare, costul transportului, etc. Uneori analistul poate să întâlnească reţele în care arcele asociate au valori negative1. Această situaţie poate fi întâlnită în acele reţele în care se doreşte minimizarea costului, unde valoareaasociată arcului va indica profitul pentru acea rută.

1 Algoritmul de etichetare folosit aici foloseşte doar valori pozitive.


3.2 Problema arborelui de acoperire minimală

În terminologia de specialitate, problema arborelui de acoperire minimală presupune folosirea ramurilor (arce) în reţea pentru a ajunge în toate nodurile reţelei, astfel încât lungimea totală a tuturor ramurilor folosite pentru a ajunge la toate nodurile să fie minimă.

Pentru o mai bună înţelegere a situaţiei se va considera problema de determinare a reţelei de comunicaţii pentru firmă, de la sediul regional al acesteia. Firma de telefonie Est Telecom trebuie să dispună la sediul său regional de un computer care să fie conectat prin antenă de satelit cu un computer central. Compania de telefonie va instala noua reţea de comunicaţii. Instalarea reţelei este o operaţiune foarte costisitoare. Pentru a reduce costurile, echipa managerială doreşte ca noile linii de comunicaţie instalate să însumeze o lungime minimă posibilă. Computerul central poate fi legat direct la fiecare utilizator, dar pentru firmă este mai economic să instaleze linii directe pentru unii utilizatori şi să-i lase pe ceilalţi utilizatori să se conecteze la sistem prin intermediul utilizatorilor deja conectaţi la sistem.

Figura nr. 3. 12


Determinarea reţelei de comunicaţie cu lungimea cea mai mică este un exemplu de problemă a arborelui de acoperire minimală. Reţeaua pentru problema de mai sus permite conexiuni alternative, pe arce fiind asociate distanţele dintre noduri.

3.2.1 Algoritmul arborelui de acoperire minimală (Greedy)

Algoritmul folosit în problema arborelui de acoperire minimală poartă denumirea de „Greedy” şi constă în alegerea celei mai bune variante, la fiecare pas al algoritmului, fapt care conduce rapid la obţinerea soluţiei optime a problemei. Acest algoritm este unul dintre puţinii algoritmi folosiţi în ştiinţa managementului care este „ cel mai economic“ la fiecare pas şi generează direct evoluţia optimă. Paşii algoritmului Greedysunt:

Pasul 1: În mod arbitrar se porneşte din orice nod şi se realizează legătura cu nodul cel mai apropiat. Cele doua noduri se numesc noduri conectate iar celelalte se numesc neconectate.Pasul 2: Se identifică un nod neconectat care este situat cel mai aproape de un nod conectat. Dacă apare o situaţie de egalitate se alege arbitrar unul dintre ele ca fiind cel mai apropiat nod. Acesta va fi adăugat mulţimii nodurilor conectate. Se repetă pasul doi până când toate nodurile sunt conectate.

Algoritmul este uşor de aplicat prin realizarea conectărilor direct pe graful asociat reţelei. Dacă luăm spre rezolvare problema Est Telecom vom alege arbitrar un nod de start, de exemplu nodul 1. Cea mai mică distanţă de la acest nod este 20 km până la nodul 2. Se conectează cele două


noduri printr-o linie punctată (practic, linia poate fi dublată prin îngroşare) precum în Figura 3.13.

Figura nr. 3. 13

În pasul doi al algoritmului se caută nodul neconectat cel mai apropiat de nodurile conectate 1 sau 2. Nodul 4 este situat la 30 km de nodul 1. Nodul 4 se adaugă la lista nodurilor conectate, iar pe reţea se reprezintă cu linie punctată arcul dintre nodurile 1 şi 4 precum în Figura nr. 3.14.

Figura nr. 3. 14


Se repetă pasul 2 şi se include nodul 3 în lista nodurilor conectate. Se reprezintă punctat arcul dintre nodurile 3 şi 4, apoi se include în lista nodurilor conectate şi nodul 6 şi se reprezintă punctat arcul dintre nodurile 4 şi 6. Ulterior se include nodul 5 în lista nodurilor conectate, se reprezintă punctat arcul dintre nodurile 3 şi 5 şi se obţine soluţia. Arborele de acoperire minimală are lungimea totală dată de suma valorilor asociate arcelor dintre nodurile conectate.

Figura nr. 3. 15

Lungimea minimă a reţelei care acoperă minimal întreaga reţea este 20 + 30 + 10 + 20 + 30=110 km de conexiuni de la sediul central spre oricare nod al reţelei.

Aici, sunt reprezentate pe arce distanţele în km, dar pot fi asociate arcelor, costuri, timp etc. În aceste situaţii arborele de acoperire minimală va determina costul minim, timpul minim etc. în raport de criteriul considerat.


3.3 Problema de flux maxim

Se consideră o reţea cu un nod sursă (nod intrare, input) şi cu un nod de ieşire (nod de output). Problema de flux maxim constă în determinarea cantităţii de flux (vehicule, fluid, mesaj etc.) care pot fi introduse şi scoase din sistemul de reţea într-o perioadă de timp. În această problemă fluxul care circulă în reţea poate folosi toate ramurile (arcele reţelei) cât mai eficient posibil. Capacitatea transportată este limitată (superior) prin restricţiile de capacitate care pot să existe pe fiecare dintre ramurile reţelei. De exemplu, există limitări ale fluxului de autovehicule care pot să parcurgă o autostradă, sau conductele de transport petrolier nu pot să depăşească un anumit nivel determinat de limita constructivă a sistemului de conducte.

Capacitatea minimă sau maximă de transport este denumită şi capacitate de flux pe arc/rută. Dacă nu se specifică capacitatea pentru un nod, se presupune că fluxul de ieşire este egal cu fluxul de intrare.

Un exemplu de problemă de flux maxim este cel al TransGaz. Fluxul de gaz metan intră în conductele din Mediaş prin partea de nord şi ies din reţeaua de conducte în partea de sud a oraşului. Fluxul de gaz este maxim în perioadele iarnă cu temperaturi scăzute. Conductele pot să fie solicitate, acum, la a transporta 13000 mc pe oră.

În timpul efectuării reviziilor şi verificărilor, se presupune un sistem de rute alternative. Rutele alternative prezintă restricţii. Reţeaua alternativă propusă, pentru a prelua cantitatea curentă şi cea suplimentară, care în mod normal ar fi tranzitat prin alte conducte, este reprezentată în Figura nr. 3.16.


Figura nr. 3. 16

Capacitatea de transport este direcţionată, funcţie de cerinţe. De exemplu pe ruta de la 1 la 4 se pot transporta 5000 mc/h dar în sens invers nu se poate transporta nimic.

Este de dorit ca să nu existe situaţii de suprasolicitare (loc îngust) pentru nici una din conductele utilizate. Poate firma TransGaz să transporte prin reţeaua din Figura 3.16 o cantitate de 15000 mc/h? Care este capacitatea maximă de transport, pe oră a reţelei? Care este cantitatea maximă ce poate fi transportată pe fiecare conductă (ramură) din reţea?

3.3.1 Algoritmul pentru flux maxim

La întrebările de mai sus se poate răspunde după aplicarea Algoritmului de flux maxim, care va folosi următoarele specificaţii:

1. poate fi folosită orice rută dinspre nodul de intrare spre nodul de ieşire în sensul/direcţia pentru care fluxul este mai mare decât 0 pentru toate conductele parcurse;


2. se poate creşte fluxul pe o rută la nivelul maxim posibil;3. trebuie căutate rutele dinspre intrare spre ieşire care mai

suportă creşterea cantităţii transportate (dispun de rezervă de capacitate) în direcţiile în care fluxul are valoare mai mare decât 0, pentru toate ramurile, şi apoi se va creşte fluxul pe aceste rute cât de mult posibil;

4. algoritmul se opreşte când nu mai este posibil să fie găsită o nouă rută, dinspre intrare spre ieşire, cu capacitatea de flux orientată, cu valoarea mai mare sau egală cu 0, pentru toate ramurile din rută.

Înainte de a prezenta detaliile algoritmului de flux maxim, se prezintă pe scurt procedura care va determina dacă paşii parcurşi vor conduce spre soluţia optimă a problemei şi va găsi fluxul maxim ce poate fi transportat de la intrare spre ieşire.

Procedura permite ca fluxul anterior asigurat să fie condus pe rute alternative, prin posibilitatea de a avea şi în direcţie inversă fluxuri fictive. De exemplu, se consideră ruta de la 1 la 6 astfel:

Figura nr. 3. 17

Fluxul iniţial ce poate fi propagat în reţea de la nodul 1 spre nodul 6 este de 6000 mc/h. Dacă în reţea sunt propagaţi 4000 mc/h de la nodul 1 spre nodul 6, se vor revizui capacităţile ce flux astfel:

Figura nr. 3. 18


Se observă că s-a redus capacitatea de flux dinspre nodul 1 spre nodul 6 de la 6000 mc/h la 2000 mc/h, deoarece în reţea mai există disponibilitatea de a transporta de la nodul 1 spre nodul 6 de numai 2000 mc/h (6000–4000=2000). Această reducere determină simultan o creştere a fluxului dinspre nodul 6 spre nodul 1 egală cu cantitatea propagată în reţea, de la 0 la 4000 mc/h (0+4000=4000). Această revizuire a capacităţii fluxului dinspre nodul 6 spre nodul 1 arată că dinspre nodul 6 se pot transporta (fictiv) 4000 mc/h. Acest flux fictiv arată că nu este posibil transportul dinspre nodul 6 spre nodul 1, ci arată doar faptul că a scăzut cantitatea care mai poate fi transportată de la nodul 1 spre nodul 6. De fapt, fluxul fictiv dinspre nodul 6 spre nodul 1 provine acum din fluxul iniţial dinspre nodul 1 spre nodul 6 care a fost propagat pe alte ramuri ale reţelei.

Procesul descris anterior prezintă importanţă în problemele de flux maxim atunci când într-o iteraţie se poate propaga flux pe o ramură, iar apoi după ce se observă fluxul propagat pe altă ramură este mai avantajos, se va recurge la reducerea fluxului propagat iniţial. Această procedură, descrisă mai înainte, va identifica o extensie spre care decizia originală poate fi revizuită pentru a propaga flux pe o ramură de reţea cu scopul de a creşte fluxul total propagat în reţea.

Paşii algoritmului de flux maxim:

Pasul 1: Se identifică orice rută care pleacă din nodul de intrare şi ajunge la nodul de ieşire şi care prezintă capacitate de flux mai mare decât 0 pentru toate ramurile de pe rută. Dacă o asemenea rută nu există, soluţia optimă a fost obţinută.

Pasul 2: Se identifică cea mai redusă capacitate de transport, Pm de pe arcele care compun ruta identificată la pasul 1. S


creşte fluxul propagat în reţea prin transportarea a Pm unităţi de-a lungul rutei identificată la pasul 1.

Pasul 3: Pentru ruta identificată la pasul 1 se reduc toate capacităţile de transport dinspre sursă spre destinaţie cu cantităţile Pm şi se cresc toate capacităţile de transport dinspre destinaţie spre sursă cu cantitatea Pm. Se trece la pasul 1.

Procedura poate varia funcţie de alegerea iniţială a analistului efectuată în pasul 1, iar algoritmul va genera probabil, soluţia fluxului maxim. Calculele efectuate aici sunt următoarele:

Iteraţia 1. Pasul selectat este 1 – 3 – 6 – 7, Pm = min(6,7,7) = 6 care corespunde drumului de la 1 la 3. Reţeaua revizuită(Figura 3.19) este:

Figura nr. 3. 19

În reţea se propagă un flux iniţial de 6000 mc.

Iteraţia 2. Pasul selectat este: 1 – 2 – 5 – 3. Pm = min(5, 3, 8)=3 valoare care corespunde drumului de la 2 la 5. Reţeaua revizuită este prezentată în Figura nr. 3.20.


Figura nr. 3. 20

În reţea se propagă suplimentar încă 3000 mc/h. Fluxul total este acum de 9000 mc/h. Fluxul total propagat în reţea se determină prin însumarea valorilor Pm pentru fiecare instalaţie.

Iteraţia 3. Pasul selectat este 1 – 2 – 3 – 5 – 3. Pm= min(2, 2, 3, 5) = 2, valoarea lui Pm corespunde ramurilor de la 1 la 2 şi respectiv de la 2 la 3.

Figura nr. 3. 21

Fluxul total este acum de 11000 mc/h.


Iteraţia 4. Ruta aleasă este 1 – 4 – 6 – 7. Pm=min(5,5,1) = 1 care corespunde drumului de la nodul 6 la 3.

Figura nr. 3. 22

Fluxul total propagat este acum de 12000 mc/h.

Iteraţia 5. Ruta aleasă acum este: 1 – 4 – 6 – 5 – 7, Pm=min(4, 4, 1, 3)=1. Pm corespunde drumului de la 6 la 5.

Figura nr. 3. 23

Fluxul total transportat în reţea este acum de 13000 mc/h.


Iteraţia 6. Mai există, oare, o altă rută dinspre nodul 1 spre nodul 7 care să permită propagarea suplimentară a cantităţii de flux mai mare decât 0? Dacă se foloseşte ruta 1 – 4 – 6 – 3 – 5 – 7 pentru care Pm = min (3, 3, 6, 1, 2) care corespunde drumului de la nodul 3 la nodul 5. Această nouă rută poate să crească fluxul total la 14 000 mc/h.

Figura nr. 3. 24

După cum se observă, din reţeaua revizuită, nu mai sunt drumuri care să permită un transport suplimentar (flux propagat mai mare decât 0) prin ramurile reţelei. Astfel fluxul total maxim pe care îl permite reţeaua de transport este de 14000mc/h.

În iteraţia 6, fluxul de 1000 mc/h a fost posibil de realizat dinspre nodul 6 spre nodul 3, chiar dacă în reţea nu este permis transportul dinspre nodul 6 spre nodul 3. Acest flux propagat în iteraţia 6 este un flux fictiv. Efectul real indus de acest flux fictiv este determinat de faptul că fluxul original de 1000 mc/h dinspre nodul 3 spre nodul 6 din iteraţia 1 este de fapt dirijat dinspre nodul 3 spre nodul 5, ceea ce permite transportul a încă 1000 mc/h prin reţea. Acum se va determina


cantitatea şi direcţia fluxurilor propagate pe fiecare ramură din reţea astfel încât fluxul maxim total propagat să fie de 140000 mc/h.

Fluxurile corespunzătoare fiecărei ramuri care conduce la soluţia optimă pot fi implicate prin compararea capacităţilor de flux finale cu cele iniţiale. În cazul în care capacitatea de flux finală este mai mică decât capacitatea iniţială, prin ramura respectivă se propagă un flux de cantitate egală cu diferenţa dintre capacitatea de flux iniţială şi cea finală. De exemplu se consideră ramura 3 – 6 pe care capacitatea de flux iniţial era:

Figura nr. 3. 25

cu capacitatea de flux finală:

Figura nr. 3. 26

Deoarece capacitatea de flux finală dinspre 3 spre 6 este mai mică decât capacitatea iniţială, ramura are un flux propagat de 7–2=5 dinspre nodul 3 spre nodul 6. Acest flux va fi reprezentat prin:

Figura nr. 3. 27


Prin compararea fluxurilor de capacitate iniţiale pe toate ramurile cu fluxurile de capacitate finală, se determină următorul flux de reţea:

Figura nr. 3. 28

Rezultatul analizei fluxului maximal indică faptul că reţeaua de conducte TransGaz nu poate să transporte un flux de 15000 de mc/h. În consecinţă va fi necesară extinderea capacităţii de transport pentru a face faţă perioadelor din an cu cerere mare de gaz.

Dacă reţeaua se va extinde, sau va fi modificată, trebuie să fie realizată o nouă analiză, care să determine noul nivel al fluxului în reţea.

CAPITOLUL 4

MODELE DE STOCARE

Stocurile pot fi definite ca fiind acele cantităţi de bunuri sau materiale care sunt păstrate în scopul de a fi utilizate. Pentru foarte multe firme, cheltuielile asociate cu finanţarea şi păstrarea stocurilor constituie o parte substanţială a costurilor afacerii. În companiile mari, în special în acelea în care produc cantităţi mari de bunuri, sau bunuri scumpe, costurile asociate cu materiile prime care sunt procesate şi stocurile de produse finite pot să ajungă la valori mari. Pentru a realiza nivelurile valorice la care pot să ajungă aceste stocuri, se va considera în continuare situaţia firmei DrinkCo.

DrinkCo este un distribuitor de sucuri, vin şi bere. De la depozitul central al firmei, se livrează marfă la peste 1000 de beneficiari, magazine de vânzare en-detail.

Stocul valoric al firmei este reprezentat şi de ambalaje a căror valoare este de aproximativ 40% din valoarea stocurilor. Aceasta reprezintă aproximativ 50000 de lăzi. Costul mediu al unei lăzi este de aproximativ 5 unităţi monetare. Firma estimează astfel că valoarea ambalajelor pentru sucuri este de 250000 de unităţi monetare.

Există unele costuri asociate cu menţinerea şi manipularea unui nivel dat al stocurilor. Luate împreună, aceste costuri poartă numele de costuri de stocare. În primul rând, este implicat aici costul finanţării. Dacă firma împrumută bani

M O D E L E D E S T O C AR E8 0

pentru a-şi menţine investiţia în stocuri, o dobândă va majora aceste costuri. Dacă firma foloseşte capitalul propriu pentru a păstra stocuri, ea nu va fi capabilă să folosească acest capital pentru alte investiţii. În fiecare caz există o cheltuială legată de nivelul capitalului imobilizat în stocuri.

De obicei, costul capitalului este exprimat în procente din suma investită. Dacă firma estimează că acest cost este reprezentat de o rată a dobânzii de 18% anual atunci dobânda

pentru costurile de stocare este 100

18·250000=45000 unităţi

monetare/an. Există un număr de alte costuri asociate precum:

cheltuieli cu asigurările, taxe casare, pierderi, depozitare, care de asemenea depind de valoarea stocului. Firma estimează aceste costuri la un nivel de aproximativ 7% din valoarea stocului.

Costul total de stocare este 100

718 ·250000 = 62500

unităţi monetare/an.Dacă se apreciază că sucurile reprezintă doar 40% din

nivelul total al stocurilor, se poate deduce că, pentru menţinerea stocurilor, costurile necesare sunt apreciabile.

Managerii au de ales între (a) a dispune de stocuri suficiente care să satisfacă cererea de bunuri şi (b) de a investi cât mai puţin în activitatea de menţinere a stocurilor. De fapt, managerii trebuie să rezolve problema prin alegerea celei mai bune decizii care să ia în considerare următoarele:

1. Care trebuie să fie cantitatea comandată astfel încât nivelul stocului să fie readus la nivelul iniţial?2. Când trebuie să fie luată decizia prin care să dispună refacerea stocului?

M O D E L E D E S T O C AR E 8 1

Scopul acestui capitol este de arăta cum modelarea cantităţii poate folosi ca suport în luarea deciziilor. În majoritatea sistemelor de stocare chiar dacă există similarităţi, totuşi fiecare sistem este particular.

În prima parte se discută despre modelele deterministede stocare unde se presupune că cererea este cunoscută şi are o valoare constantă. Apoi se discută despre modele probabilistede stocare, unde cererea are o valoare fluctuantă, descrisă în termeni probabilistici.


4.1 Modelul de stocare cu cerere constantă

Acest model este aplicabil pentru situaţiile în care cererea este constantă sau relativ constantă. Aceasta înseamnă că cererea satisfăcută cu ajutorul stocului înregistrează valori similare în intervalul de timp. De exemplu 5 bucăţi/săptămână sau 1000kg/lună.

Tabelul nr. 4. 1Săptămâna Cererea (lăzi)

1 20002 20253 19504 20005 21006 20507 20008 19759 190010 2000

TOTAL lăzi 20000Cererea medie săptămânală 2000

Se aplică acest model pentru firma DrinkCo. La nivelul firmei s-a efectuat o analiză preliminară privind costurile de stocare şi s-a decis realizarea unui studiu detaliat care să ofere informaţii despre cât şi când comandă beneficiarii pentru ce să se aducă la nivelul cel mai scăzut costul de stocare. Cererea pentru săptămânile viitoare pentru SoftDrink, o băutură


răcoritoare produsă de DrinkCo este prezentată în Tabelul nr. 4.1.

Cererea prezentată nu este strict constantă, dar prezintă variaţii foarte mici de la o săptămână la alta. Furnizarea săptămânală a 2000 de lăzi de băutură răcoritoare pare o aproximare rezonabilă.

În practică, se constată că stocul real chiar satisface propunerea realizată prin model. Astfel în situaţiile reale managerul sau analistul vor determina care modele sunt cele mai apropiate de reprezentarea reală.

În cazul în care cererea variază între 1900 şi 2100 de lăzi pe săptămână, nivelul stocului de 2000 de lăzi reprezintă o valoare rezonabilă, iar decidentul poate realiza un compromis între: (a) păstrarea unui stoc redus şi existenţa unor comenzi frecvente şi (b) păstrarea unui stoc mare care să satisfacă comenzile mai puţin frecvente, dar cu o cantitate furnizată mai mare.

Prima situaţie are ca efect cheltuieli considerabile cu pregătirea comenzii, în timp ce în situaţia a doua vor fi mai mari cheltuielile de stocare. Soluţia optimă va combina cele două situaţii, în aşa mod, încât să determine un cost total minim.

Costul de stocare şi manipulare este cel care depinde de nivelul stocului. Un nivel al stocului ridicat va determina un cost de stocare ridicat.

Dacă DrinkCo estimează că nivelul costului anual de stocare reprezintă 25% din valoarea stocului, iar costul unei lăzi este de 5 unităţi monetare, costul de stocare şi manipulare pentru o ladă de SoftDrink pe o perioadă de un an este 0,25·5=1,25 unităţi monetare.

În continuare, trebuie determinat costul de lansare a unei noi comenzi. Pentru DrinkCo, pregătirea unei comenzi constă în aprox. 45 de minute de procesare a documentelor şi manipulare a produselor. Costurile salariale pentru plata


angajaţilor sunt de 16 unităţi monetare pe oră, deci plata corespunzătoare pentru 45 minute=(45/60)·16=12 unităţi monetare pe oră. Cheltuielile cu documente, poştă, telefon, transport şi recepţie sunt de 8 unităţi monetare/comandă. Astfel, cheltuielile de lansare a unei noi comenzi sunt 12+8=20 unităţi monetare/comandă. Astfel, firma DrinkCo plăteşte 20 unităţi monetare pe comandă, indiferent de volumul acesteia.

Costul de stocare şi costul de lansare al comenzii, precum şi informaţiile privind cererea pot fi folosite în modelul de stocare cu cererea constantă.

Cantitatea Q reprezintă nivelul comenzii. Astfel, decizia de a produce cantitatea Q presupune determinarea acestei valori Q care va minimiza suma dintre costul de stocare şi costul de lansare al comenzii.

Figura nr. 4. 1

Nivelul inventarului pentru SoftDrink va avea maxim valoarea Q atunci când unul dintre detailişti va avea o comandă cu cantitatea Q. DrinkCo va satisface cererea clienţilor până când stocul de produse se epuizează. În acel moment un alt transport de 2000 lăzi va fi primit. În ipoteza unei cereri constante de 2000 de lăzi/săptămână, (cu 5 zile lucrătoare),

Nivel maximal stocului Q

Nivel mediu al stocului ½ Q

Nivel minim al stocului 0 t

T Timp mediu necesar pentru epuizarea stocului


poate fi satisfăcută o cerere medie de 400 lăzi/zi (reprezentarea grafică Figura nr. 4.1)

Nivelul mediu al stocului în intervalul de timp este (stocul iniţial + stocul final)/2 şi se bazează pe faptul că stocul descreşte de la nivelul Q spre 0 în intervalul de timp T.

Figura nr. 4. 2

Figura nr. 4.2 arată evoluţia activităţii de stocare pe un interval de timp mai mare. Stocul este alimentat ciclic la fiecare sfârşit de perioadă T.

Stocul satisface o cerere constantă de 2000 lăzi/săptămână.

Dacă stocul mediu este ½Q pentru fiecare ciclu, stocul mediu pentru un număr (întreg ) de cicluri este tot ½Q.

Cheltuielile de stocare pot fi determinate folosind stocul mediu. Acestea rezultă din multiplicarea stocului mediu cu costul unitar de stocare pentru perioada de stocare.

Perioada de stocare poate fi considerată 1 săptămână, o lună, un an sau mai mult. De obicei, se foloseşte costul de stocare unitar anual.

Dacă se notează:I = procentul din valoarea produsului care reprezintă costul anual unitar de stocare (25 % pentru DrinkCo)C = cost unitar al unei lăzi de produs (Cs) este determinat de: Cs = I·C

Q

½Q

0t

T 2T 3T

Nivel de stoc mediu


Pentru produsul SoftDrink se obţine 0,25·5 = 1,25Costul anual de stocare se determină prin multiplicarea

stocului mediu cu costul unitar anual de stocare.Cost anual de stocare = ½Q·Cs

Pentru completitudine, în costul total trebuie introduse şi cheltuielile cu lansarea comenzilor. Dacă se notează cu D cererea anuală de produse, atunci numărul anual de comenzi va

fi determinat de raportul Q

D.

Astfel, costul total anual cu lansarea comenzilor va fi: Cost anual cu

lansarea produsului

=nr. anual

de comenzi

·costul unitar de lansare

= Q

D· Co

unde costul de lansare este notat prin Co.Astfel, costul total anual (costul de stocare + costul de

lansare) poate fi determinat prin:

TC = 2

1·Q·Cs +

Q

D·Co

Dacă în cazul DrinkCo avem Cs=1,25 unităţi monetare şi Co=20 unităţi monetare, atunci cererea anuală este calculată prin: D=52(săpt.)·2000 (lăzi)=104000 (lăzi anual), şi atunci:

TC=2

1·Q·1,26+

Q

104000·20 = 0,265·Q +

Q

2080000

Relaţia anterioară descrie costul total în funcţie de Q. Valoarea minimă a costului se poate determina pentru acea valoare Q care minimizează funcţia costului total. Pentru a determina minimele funcţiei costului, derivata acesteia în raport cu cantitatea trebuie să fie egală cu zero.


Q

TC

= hC2

1-

2o

Q

CD =0. De aici se deduce că:

sC2

1=

2o

Q

CD Q2=

s

o

C

C2D

Q*=s

o

C

C2D ,

unde Q* reprezintă cantitatea optimă care poate fi stocată dacă se foloseşte modelul cu cerere constantă.

Dacă deja sunt determinate D=104000 lăzi, Co=20 unităţi monetare şi Cs=1,25 unităţi monetare, atunci:

Q=1,25

201040002 =1824.

Astfel cantitatea optimă este Q*=1824 lăzi/săptămână.Dacă se reprezintă pe acelaşi grafic costurile implicate,

atunci se deduce:

Figura nr. 4. 3

cantitate Q*=1824

cost anual total

cost anual de stocare

cost anual de lansare


Astfel costul total minim devine:

TC* = 2

1Q*·Cs +

*Q

DCo

TC*=s

o

C

C2D

2

1 Cs+

s

o

o

C

C2D

CD

=2

CCD so +

2

CCD so

TC*= so CC2D În problema prezentată TC* devine:

TC*= 1,25201040002 = 2280,35 u.m.

Acum, managerii ştiu că nivelul stocului optim este Q* (în cazul DrinkCo Q* = 1824 lăzi) şi trebuie să determine care este momentul în care trebuie să lanseze comanda astfel încât stocul să fie realimentat. Managerii trebuie să stabilească şi

calendaristic zilele în care să reaprovizioneze. Expresia Q

D

arată numărul de comenzi care se fac într-un an. Cu datele

problemei, *Q

D=

1824

104000= 57,02 ceea ce înseamnă că pentru

un an se efectuează aproximativ 57 de comenzi. Pentru că săptămâna lucrătoare are doar 5 zile, numărul de zile total lucrate pe parcursul anului este:

52 săptămâni · 5 zile/săptămână = 260 zile lucrătoare. Dacă se repartizează cele 57 comenzi pe an la 260 zile

lucrătoare se deduce:

T =

*Q

D260

= D

*Q260 =

104000

1824260 = 4,56 zile.

Rezultatul asigură că, o reaprovizionare la 4,56 zile conferă o satisfacţie optimă a cerinţelor. Totuşi nu poate fi


practic folosită valoarea optimă a lui T*=4,56 zile lucrătoare, fapt care denotă că pot fi lansate comenzile la 4 zile, dar stocul creşte şi implicit cheltuielile sau se lansează comenzile la interval de 5 zile, dar poate să apară situaţia lipsei stocului, fapt care poate conduce la costuri de penalizare.

Tabelul nr. 4. 2 Analiza senzitivităţii pentru modelul de stocare cu cerere constantă.

Cost TotalValoare Cs

(%)

Valoare Co

Q* Pe baza Q*

Pe baza Q = 1824

23 19 1792,5 2204,76 2205,0923 20 1839,1 2262,03 2262,1123 21 1884,5 2317,90 2319,1324 19 1785,2 2213,70 2214,2124 20 1831,6 2271,21 2271,2324 21 1876,9 2327,30 2328,2525 19 1778,1 2222,61 2223,3325 20 1824,3 2280,35 2280,3525 21 1869,3 2336,66 2337,3726 19 1771,0 2231,48 2232,4526 20 1817,0 2289,45 2289,4726 21 1861,9 2345,99 2346,49

Pe baza analizei senzitivităţii se deduce că valoarea optimă (teoretică) a stocului conduce la nivelul costului total minim.

Dacă se înregistrează variaţii în Cs şi Co se deduce din Tabelul nr. 4.2, pe baza costurilor totale proiectate, că volumul costului total variază între 2200 şi 2400 unităţi monetare/an. În acest caz se recomandă decidentului de a alege o valoare a lui Q apropiată de 1824 lăzi.


4.2 Modelul de stocare a producţiei fabricate pe loturi

Următorul model suport decizional pentru activitatea de stocare este similar cu modelul de stocare cu cerere constantă. De asemenea, se consideră ipoteza unei cereri constante, dar bunurile nu mai aprovizionează depozitul în transporturi de Q unităţi ci se consideră că depozitul este aprovizionat continuu câteva zile sau câteva săptămâni (de exemplu, din producţie proprie fabricată).

Oferta cu rată constantă, presupusă aici, semnifică faptul că este furnizată aceeaşi cantitate de produse în fiecare unitate de timp (de exemplu 20 unităţi în fiecare zi, 100 pe săptămână etc.). Acest model este destinat situaţiilor în care odată o comandă făcută, începe producţia unui număr constant de produse (un lot de fabricaţie) care se adaugă la stocul existent până când lotul respectiv este realizat în totalitate.

Dacă se consideră un sistem de producţie care produce 50 de unităţi pe zi şi se programează 10 zile de producţie se va realiza un lot de 50·10=500 unităţi. Problema principală în acest model constă în determinarea mărimii optime Q a lotului care va minimiza costul total.

O condiţie care trebuie menţionata este că modelul se aplică în situaţiile în care rata producţiei este mai mare decât rata cererii, iar sistemul trebuie să prezinte capacitatea de a satisface cererea. De exemplu, dacă nivelul cererii este de 2000 unităţi pe săptămână, nivelul producţiei trebuie să fie cel puţin de 2000 unităţi pe săptămână pentru ca oferta să satisfacă cererea. Cu această condiţie suplimentară, practic, în fiecare zi se produce mai mult decât se livrează spre beneficiar. Excesul de producţie va fi, astfel, stocat, stocul înregistrând o creştere graduală pe perioada în care se produc bunurile. Atunci când producţia încetează (s-a produs întreg lotul), stocul va începe să


înregistreze o scădere progresivă până când este lansat în producţie noul lot. Reprezentarea evoluţiei stocului este prezentată în Figura nr. 4.4.

Figura nr. 4. 4

Sunt utilizate costurile de stocare şi costurile de lansare la fel ca la modelul de stocare cu cereri constantă, cu costul de stocare variabil, funcţie de nivelul stocului. Costul de lansare, însă, este un cost care include: ore de muncă, materiale, costulrebuturilor, fiind de fapt un cost fix pentru fiecare lot produs, care este totuşi dependent de mărimea costului de fabricaţie.

Determinarea costului total

Fie notaţia Q pentru mărimea lotului de producţie. Trebuie determinat nivelul mediu al stocului şi costul unitar de stocare. Se consideră o durată de un an şi corespunzător costul unitar anual de stocare. Folosind notaţiile:d = cererea zilnică pentru produs;p = producţia zilnică;t = durata (în zile) pentru un ciclu de fabricaţie şi reprezentareadin Figura nr. 4.4 se determină valoarea medie a stocului.

cost

Stoc maxim Q

Stoc mediu ½ Q

Stoc minim 0

t

Faza de creştere a stocului (producţie) Faza de reducere a stocului (non-producţie)

t


Dacă se presupune p>d, atunci diferenţa p-d arată nivelul zilnic al excesului de cerere, care va alimenta stocul. Dacă se stochează zilnic p-d unităţi timp de t zile, nivelul maxim al stocului este:

Nivel maxim stoc = (p-d)· t

Dacă un lot de produse are Q unităţi care sunt produse în t zile, iar producţia zilnică este de p bucăţi, atunci Q = p·t. De aici se deduce că durata unui ciclu de fabricaţie este de:

t = p

Qzile

Nivelul maxim al stocului devine:

(p-d)·t = (p-d)· p

Q = (1-

p

d)·Q

Stocul mediu se determină ca medie aritmetică a nivelului maxim şi a celui minim astfel:

Stocul mediu = 2

0Q)p

d-(1

= Q)p

d-(1

2

1

Dacă costul de stocare unitar anual este Cs = I·C, atunci costul anual de stocare devine:

Cost anual de stocare

=stoc

mediu·

cost unitar anual de stocare

= )p

d-(1

2

1Q·Cs

Dacă D este cererea anuală pentru produs şi Co este costul pentru un ciclu de fabricaţie, iar numărul de cicluri de


fabricaţie pe an este Q

D, costul anual de producţie se determină

prin:Cost anual

de producţie

=nr. cicluri

de fabricaţie pe an

·cost de producţie

pe ciclu de fabricaţie

=Q

D·Co

Astfel, costul total de operare (TC) al modelului devine:

TC = )p

d-(1

2

1Q·Cs +

Q

D·Co (4.1)

Dacă firma lucrează 250 zile/an (şi 115 sunt zile libere şi nelucrătoare), atunci cererea zilnică d poate fi determinată

prin: d = 250

D, iar dacă prin P se notează producţia anuală,

producţia zilnică este p = 250

P, atunci numărul de zile de

producţie (250) coincide cu numărul de zile care se manifestă cererea pentru produs:

p

d =

250

P

250

D=

P

D

Pe baza relaţiei de mai sus se poate scrie costul total anual ca:

TC = )P

D-(1

2

1·Q·Cs +

Q

D·Co (4.2)

Ecuaţiile (4.1) şi (4.2) sunt echivalente. Analistul va alege care dintre acestea este preferabil să fie folosită.


Determinarea nivelului optim al lotului de producţie. Când se doreşte obţinerea costului minim, derivata costului total în raport cu cantitatea va genera după egalare cu zero soluţia nivelului optim al lotului de producţie Q*:

Q

TC

= )P

D-(1

2

1·Cs - o2

CQ

D =0

Q2=s

o

C

C

P

D1

2D

Q*=

s

o

C)PD-(1

C2D

,

Pe baza acestei valori se deduce nivelul minim al costului total:

TC* = )P

D-(1

2

1·

s

o

C)PD-(1

C2D

·Cs +

s

o

C)PD-(1

C2D

D

·Co

TC*= so CCD)P

D(1

2

1 + so CCD)

P

D(1

2

1

TC*= so CCD)P

D2(1

De asemenea, durata unui ciclu de producţie optim este:

t*=P

*Q=

2

s

o

P

1

C)P

D(1

C2D

.


4.3 Model de stocare cu cerere constantă şi lipsă de stoc

În multe situaţii practice nivelul stocului nu poate satisface cererea. Chiar dacă nu este o situaţie dorită, ea trebuie evitată pe cât posibil.

Uneori este foarte costisitor să fie păstrate în stoc bunuri, aşa că managerii preferă lipsa de stoc. Pentru un dealer, de exemplu, de autoturisme nu este neobişnuit să nu deţină în stoc un tip de vehicul, iar clientul este dispus să aştepte să-şi primească maşina după câteva săptămâni.

Modelul de stocare cu cerere constantă şi lipsă de stoc ia în considerare faptul că un client poate comanda un produs, acest produs poate să nu fie în stoc, clientul nu renunţă la cererea sa şi aşteaptă să sosească un nou transport de produse pentru ca să-şi satisfacă cererea. De obicei, clientul este dispus să aştepte dacă perioada cu lipsă de stoc este scurtă, iar acesta este asigurat de ofertant că cererea sa va fi satisfăcută cu prioritate imediat ce bunul este disponibil. Dacă clientul consideră că amânarea intrării în posesia bunului îi poate cauza prejudicii, atunci el ar putea renunţa la achiziţionarea bunului de la furnizor şi eventual ar cere despăgubiri pentru prejudiciul cauzat.

În modelul de stocare cu cerere constantă introducem următoarele ipoteze:1. Există S cereri de produs nesatisfăcute din cauza lipsei stocului atunci când un nou transport Q de produse aprovizionează stocul. Cele S cereri rămase neonorate sunt satisfăcute imediat, iar în stoc vor rămâne Q-S produse. 2. Q-S va fi nivelul maxim al stocului. 3. Durata dintre două aprovizionări succesive T va fi împărţităîn două faze: t1 zilele în care cererea poate fi satisfăcută din stoc şi t2 zilele în care este lipsă de stoc.


Figura nr. 4. 5

Reprezentarea grafică a acestui model este făcută în Figura nr. 4.5. Aici, cererile nesatisfăcute sunt considerate stoc negativ (-S).

Pentru determinarea costului total se însumează toate cheltuielile de stocare obişnuite şi cheltuielile de lansare. În plus, va apărea un cost suplimentar datorită lipsei stocurilor, cheltuieli cu munca şi livrările directe asociate cu procesarea şi prelucrarea comenzilor în aşteptare. De asemenea, ar putea să apară costuri de penalizare datorită insatisfacţiei clienţilor. Costul de penalizare poate fi în corelaţie directă cu timpul de aşteptare al clienţilor, el va fi astfel calculat similar cu costul depozitării. Se calculează, astfel, costul de penalizare anual pe baza unei medii a cererii nesatisfăcute şi pe baza costului unitar.

Pentru determinarea costului mediu se foloseşte o medie ponderată cu frecvenţe, unde frecvenţele reprezintă zilele de stocare.

Se notează cu t1 perioada în care stocul este pozitiv (0) şi cu t2 perioada lipsei de stoc.

t1 t2

T

D1 D E

Stoc maxim Q-S

0Cerere nesatisfăcută -S

A

B C

timp

Nivel stoc


Din Figura 4.5 se deduce că timp de t1 zile, nivelul stocului scade de la Q-S la 0 unităţi, fapt care conduce la stabilirea stocului pe aceasta perioadă la:

2

0S)-(Q =

2

S)-(Q.

În perioada t2 nu există stoc, ea reprezintă perioada corespunzătoare lipsei de stoc. Deoarece un ciclu de stocare are T = t1+t2 zile, stocul mediu pe acest interval de timp este:

Stoc mediu = 21

21

tt

t0t2

S)-(Q

=

T

tS)-(Q

2

1 1 .

Se exprimă t1 şi T în funcţie de Q, S şi d. Întrucât nivelul maxim al stocului este Q-S iar d reprezintă cererea

zilnică (constantă) se poate scrie t1 =d

SQ zile1. Astfel, stocul

maxim de Q-S unităţi va fi epuizat în d

SQ zile. Deoarece

sunt aduse în stoc la fiecare comandă Q unităţi, lungimea unui ciclu, a duratei între două reaprovizionări trebuie să fie

determinată de: T =d

Q zile2.

1 Această valoare se deduce în triunghiul ABC pe baza determinării

tangentei unghiului tg =1t

SQ = d cererea zilnică t1 =

d

SQ .

2 Această valoare se deduce din triunghiul ADE, prin calculul valorii

tg = T

Q = d = cererea zilnică T =

d

Q.


Astfel, se înlocuiesc valorile lui t1 şi T în nivelul mediu al stocului şi se calculează:

Stoc mediu = S)-(Q2

1·

d

Qd

SQ

= Q

S)-(Q

2

1 2

Se observă că nivelul mediu al stocului este exprimat doar în funcţie de două variabile de decizie: nivelul lotului de reaprovizionare (Q) şi numărul maxim de cereri nesatisfăcute (S) acceptate.

Dacă D reprezintă cererea anuală, numărul total de loturi de reaprovizionare (a câte Q unităţi) este:

Numărul anual de reaprovizionări = Q

D.

Numărul mediu de comenzi nesatisfăcute este variabil, de la 0 la nivelul maxim S. În intervalul de timp T, stocul poate să satisfacă toate comenzile în t1 (nu există cereri nesatisfăcute) iar în t2 exisă cerere nesatisfăcută.

Nivelul mediu al cererilor neonorate la timp

=T

·t2

S00·t 21

=T

t·

2

S 2

Deoarece numărul maxim de comenzi neonorate este S,iar cererea zilnică este d, lungimea perioadei cu lipsă de stoc se determină ca:

t2 = d

S

Înlocuim pe t2 şi T în ecuaţia nivelului mediu al comenzilor neonorate şi se obţine:


Nivelul mediu al comenzilor neonorate la timp

=

d

Qd

S·

2

S

=2Q

S2

În continuare se consideră: Cs = cost de stocare unitar anual;Co = cost de lansare comandă;Cp = cost de penalizare unitar anual.

Expresia costului total în nivelul de stocare cu cerere constantă şi lipsă de stoc devine:

p

2

os

2

·C2·Q

S·C

Q

D·C

2·Q

S)-(QTC

Dacă se estimează nivelul costurilor Cs, Co şi Cp, se poate determina costul minim pentru nivelurile stabilite ale lui Q şi S.

Prin derivarea expresiei TC în funcţie de Q şi în funcţie de S şi prin egalarea derivatelor cu 0 se obţine un sistem de două ecuaţii cu două necunoscute (în Q şi S) care are ca soluţie:

p

ps

s

o*

C

CC

C

2·D·CQ şi

ps

s**

CC

C·QS

,

valori care constituie soluţia optimă a modelului de stocare cu cerere constantă şi lipsă de stoc.

M O D E L E D E S T O C AR E1 0 0

4.4 Model de stocare cu cerere variabilă

Firma FiatLux vinde becuri de iluminat economice. Ea se aprovizionează de la producător. FiatLux vrea să determine nivelul optim de reaprovizionare al stocului şi să îşi formuleze politica de stoc cu scopul de a avea un stoc minim.

Costul de lansare al comenzii este de 24 u.m. Un bec costă 6 u.m. Costul de stocare anual reprezintă 20% din valoarea produsului Cs=0,26=1,2 u.m./an.

Cererea variază de la o săptămână la alta, de la o zi la alta. Astfel, nu se poate estima cererea săptămânală. Firma estimează, pe baza cererii trecute, un nivel al cererii pentru anul în curs de 4000 de becuri.

Pentru a determina nivelul reaprovizionării se calculează:

Q*=s

o

C

2·D·C=

1,2

2·4000·24= 400 buc.

Acest nivel de 400 de bucăţi generează un cost total minim. Însă variaţia lui Q în jurul nivelului său optim, Q*, nu determină o foarte mare variaţie în costul total.

Chiar dacă cererea anuală este de 3000 de bucăţi sau 5000 de bucăţi, totuşi, un nivel de reaprovizionare de 400 buc. determină un nivel redus al costului total. Dacă Q*=400 buc.,

firma anticipează că: *Q

D=

400

4000= 10 reaprovizionări pe an.

Dacă se lucrează 250 de zile pe an, intervalul de timp între

două reaprovizionări este10

250= 25 zile lucrătoare. Acest

rezultat este convenabil dacă se mizează pe o cerere constantă.Managerul trebuie să stabilească şi momentele în care

este nevoie de a se lansa o nouă comandă de reaprovizionare.

M O D E L E D E S T O C AR E 1 0 1

Se ştie că furnizorul are nevoie de o săptămână pentru a livra transportul. Dacă se ia în considerare că necesarul de 4000 bucăţi trebuie vândut într-un an, nivelul necesar săptămânal este de 4000 buc./52 săpt. 77 buc./săpt. Cu această medie, în situaţia în care cererea este simetric distribuită faţă de medie, cererea poate fi mai mare de 77 buc./săpt. în 50% din cazuri şi respectiv mai mică de 77 buc./săpt. în 50% din cazuri.

Dacă firma va avea o cerere mai mare de 77 buc./săpt.,se va înregistra o lipsă de stoc datorată excesului de cerere în 5 din situaţiile de reaprovizionare, care reprezintă 50% din totalul de 10 anual, când lipsa stocului va fi înregistrată înainte de reaprovizionare.

Această situaţie este de neacceptat pentru FiatLux şi impune ca firma să stabilească probabilitatea de distribuţie pentru datele de aprovizionare, şi să analizeze probabilistic situaţiile cu exces de cerere pentru intervalul de timp considerat. Trecutul statistic al cererii în anul anterior prezintă o distribuţie normală cu media de = 77 becuri pe săptămână şi cu o dispersie =25 buc.

Figura nr. 4. 6

Folosind datele din trecutul statistic privind cererea, analistul este în măsură să determine dacă distribuţia normală, sau alte distribuţii de probabilitate sunt cele mai adecvate pentru datele reale.

77 buc.

=77 =25

M O D E L E D E S T O C AR E1 0 2

Fiind dată o distribuţie de probabilitate a cererii, se poate determina aceea probabilitate de lipsă de stoc, care permite calculul distribuţiei de probabilitate a cererii care are o anumită valoare r.

Se poate aprecia momentul care determină lansarea unei noi comenzi şi se poate folosi un cost de penalizare pe unitatea de produs care lipseşte din stoc. Managerul va aprecia un număr mediu de situaţii în care există lipsă de stoc care ar putea fi permise pe parcursul unui an. Dacă cererea pentru produs înregistrează o distribuţie probabilistă, managerul va accepta şi niveluri crescute ale cererii, dar şi niveluri reduse, asociate cu costuri mari de stocare, sau cu costuri scăzute.

Dacă se presupune că managerul firmei acceptă o singură situaţie de lipsă de stoc, media lipsei de stoc fiind egală cu 1, atunci un număr de 10 reaprovizionări pe an, managerul poate face ca cererea să depăşească posibilitatea sa

de ofertă o singură dată din 10 cazuri (10

1100= 10%) anual.

Aceasta înseamnă că, la atingerea unui nivel al stocului egal cu r, distribuţia cererii poate în 10% din cazuri să depăşească acest nivel. Această situaţie se regăseşte în reprezentarea din Figura nr. 4.7.

Figura nr. 4. 7

Pentru distribuţia normală se caută valoarea lui z în Tabela distribuţiei normale astfel:

lipsă de stoc (cererea > r) în 5% din cazuricererea oferta

cererea r în 95% din cazuri

M O D E L E D E S T O C AR E 1 0 3

σ

μrz

r = +z

Dacă analistul dispune de valorile =77, =25, iar pentru z=1,25, corespunde valoarea tabelată f(z)=0,3944,atunci:

r =77+1,2525= 77+31,25= 108,25109

Astfel, decizia relativă la stocul recomandat se referă la menţinerea unui stoc de siguranţă de 109-77=32 bucăţi din care să poată fi satisfăcute eventualele cereri care depăşesc cererea medie.

CAPITOLUL 5

FIRE DE AŞTEPTARE

Un fir de aşteptare reprezintă un număr de clienţi care aşteaptă să fie deserviţi (la casa magazinului, la ghişeul băncii, la un semafor etc.). În cele mai multe situaţii clienţii acceptă şi trebuie să aştepte pentru a fi deserviţi. Se poate întâmpla ca unii dintre clienţi să nu fie dispuşi să aştepte mult timp pentru a fi deserviţi. Managerul realizează că aceste nemulţumiri pot îndepărta clienţii, iar cei care aşteaptă, la coadă, nu pot fi serviţi cu promptitudine. Dacă managerul doreşte să rezolve această situaţie, el va fi nevoit să instaleze mai multe case sau să scurteze timpul de deservire din sistem.

Prima soluţie presupune o creştere a costurilor cu personalul şi echipamentul suplimentar necesar. Aceasta determină managerul să pună în balanţă beneficiile suplimentare şi costurile implicate.

Modelele cantitative pot să ajute managerii să înţeleagă şi să ia deciziile cele mai bune privind funcţionarea liniilor de aşteptare. Teoria firelor de aşteptare presupune studierea comportamentului clienţilor şi a celor care oferă servicii în sistemul de deservire.

Pentru un număr dat de linii de deservire, sistemele de aşteptare pot să fie caracterizate prin:1. procentaj de timp, sau probabilitate, pentru care clientul

este servit;2. probabilitate de a avea un număr specific de clienţi în

sistem;

F I R E D E A Ş T E P T A R E 1 0 5

3. numărul mediu de unităţi (clienţi) în sistem;4. timpul mediu petrecut de fiecare client în sistem (timp de

aşteptare plus timp de deservire);5. numărul mediu de unităţi (clienţi) în firul de aşteptare;6. timpul mediu petrecut de fiecare client în firul de aşteptare;7. procentaj de timp, sau probabilitate ca un client nou sosit să

fie nevoit să aştepte pentru a fi deservit.

Dacă managerul va dispune de aceste informaţii el va fi în mai bună măsură informat pentru a lua deciziile care vor avea în vedere o îmbunătăţire a serviciului existent raportat la costurile suplimentare.

F I R E D E A Ş T E P T A R E1 0 6

5.1 Fir de aşteptare cu o singură unitate de deservire

S.C. Meteor este un lanţ de magazine cu reprezentare regională. Firma s-a dezvoltat în ultima perioadă foarte mult, datorită vânzărilor sporite.

Unitatea de încărcare-descărcare a unuia dintre magazinele S.C. Meteor a fost proiectată pentru a permite încărcarea sau descărcarea exclusivă a unui singur camion. Cererea crescută a clienţilor determină o creştere a nivelului activităţii la unitatea de încărcare-descărcare. Managerul trebuie să ia în considerare alternativele care pot să conducă la o creştere a operativităţii la unitatea de încărcare-descărcare.

O alternativă ar fi ca încărcarea şi descărcarea mai rapidă a camioanelor să se realizeze prin folosirea unei benzi rulante. O altă alternativă este cea a construirii unei noi unităţi de încărcare-descărcare, pentru ca simultan să poată fi operate două camioane în paralel.

Pentru a lua decizia potrivită, managerul are nevoie de informaţii necesare să îşi fundamenteze decizia. El vrea să ştie în ce măsură fiecare dintre cele două alternative pot să aducă îmbunătăţiri şi care sunt costurile asociate acestora.

Dacă se ia prima alternativă în calcul, managerul va trebui să identifice câteva caracteristici esenţiale ale sistemului de deservire:1. distribuţia sosirilor pentru camioane;2. distribuţia timpului de servire pentru încărcarea şi

descărcarea camioanelor;3. regula de deservire aplicată în firul de aşteptare.


5.1.1 Distribuţia sosirilor

Definirea distribuţiei sosirilor pentru o linie de aşteptare presupune determinarea numărului de unităţi care sosesc şi determinarea frecvenţiei sosirilor într-un interval de timp (de exemplu într-o oră). Trebuie determinată aici distribuţia de probabilitate a sosirilor camioanelor.

Pentru cele mai multe sisteme de aşteptare, sosirile au o distribuţie aleatoare. Aceasta înseamnă că sosirile sunt independente de alte sosiri, şi nu poate fi prognozată următoarea sosire. În asemenea situaţie, managerii pot să se bazeze pe distribuţia Poisson care oferă o bună descriere a distribuţiei sosirilor.

Prin utilizarea distribuţiei de probabilitate Poisson, probabilitatea ca să existe x sosiri într-un interval de timp este

definită de realţia: P(x)=x!

eλ λx

pentru x natural,

unde:x = numărul de sosiri în unitatea de timp; = media sau numărul de sosiri în unitatea de timp;e = 2,71828 este baza logaritmului natural.

În cazul de faţă, se determină că sosirile au o medie de trei camioane pe oră ( = 3). Astfel, se deduce că:

P(x)=x!

e3 3x

.

Deoarece x poate lua valorile 0, 1 sau 2 şi e-3=0,0498, probabilităţile ca să sosească zero, unul sau două camioane în sistem sunt:

P(x=0 camioane) = 0!

e3 30

= 0,0498

P(x=1 camion) =1!

e3 31

= 0,1494


P(x=2 camioane) =2!

e3 32

= 0,2241.

Tabelul nr. 5. 1 Probabilitatea de distribuţie a sosirilorNumăr de camioane

x

Probabilitate de distribuţie

P(x)0 0,0497870681 0,1493612052 0,2240418083 0,2240418084 0,1680313565 0,1008188136 0,0504094077 0,0216040318 0,0081015129 0,002700504

10 0,000810151

Se pot calcula valorile lui P(x) precum în Tabelul nr. 5.1. Reprezentarea grafică a funcţiei P(x) este prezentată în Figura nr. 5.1.

Figura nr. 5. 1

0,00

0,05

0,10

0,15

0,20

0,25

1 2 3 4 5 6 7 8 9 10 11Nr. camioane

Probabilitate


Distribuţia de probabilitate Poisson descrie sosirile camioanelor la S.C. Meteor S.A. şi ajută la simplificarea analizei firului de aşteptare. Este important ca după urmărirea sosirilor în sistem pentru o perioadă de timp să se observe dacă distribuţia Poisson reprezintă o bună aproximare a situaţiei reale a sosirilor camioanelor.

5.1.2 Distribuţia timpilor de deservire

O distribuţie de probabilitate trebuie să arate cât timp este necesar pentru încărcarea sau descărcarea unui camion. Deoarece fiecare camion poate transporta produse diferite, în cantităţi diferite, timpul de încărcare şi descărcare pentru fiecare camion poate varia foarte mult. Din practică se deduce că cea mai bună aproximare pentru distribuţia de probabilitate a timpilor de deservire este distribuţia exponenţială. Pe baza acesteia, se deduce că probabilitatea ca serviciul să fie realizat într-un interval specific de timp (t), se determină prin:

P(timpul de deserviret) = 1-e-t

unde: = media numărului de unităţi pe care le poate deservi sistemul în unitatea de timp.

Dacă se determină că unitatea de încărcare-descărcare poate deservi în medie 4 camioane pe oră, atunci pentru = 4 se deduce:

P(timpul de deserviret) = 1-e-4t

Probabilităţile de deservire din Tabelul nr. 5.2 au următoarea interpretare: pentru t=0,5 ore care au corespondent la 30 minute, P(timpul de deservire 30 minute) = 0,86466, în 86,4% din cazuri timpul de aşteptare este mai mic sau egal cu 30 minute, iar pentru t=0,4 ore care au corespondent la 12 minute, P(timpul de deservire 12 minute) = 0,7981, în 79,8%


din cazuri timpul de aşteptare este mai mic sau egal cu 12 minute.

Tabelul nr. 5. 2 Probabilitate de distribuţie exponenţialăTimp de deservire

în ore (t)Timp de deservire

în minute Probabilitatea de distribuţie P(t)

0,0 0 0,000000,1 6 0,329680,2 12 0,550670,3 18 0,698810,4 24 0,798100,5 30 0,864660,6 36 0,909280,7 42 0,939190,8 48 0,959240,9 54 0,972681,0 60 0,98168

Funcţia de distribuţie de probabilitate ia valorile din Tabelul nr. 5.2 şi este reprezentată grafic în Figura nr. 5.2.

Figura nr. 5. 2 Reprezentare a probabilităţii de distribuţie exponenţiale

0,000,200,400,600,801,001,20

0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0

timp de deservire (ore)

probabililate


Practic, funcţia exponenţială reprezintă o însumare a frecvenţelor relative a timpilor de deservire.

5.1.3 Regula de deservire

În firul de aşteptare trebuie să existe o regulă de deservire. De obicei aceasta este de tip FIFO1, ceea ce înseamnă că deservirea se face în ordinea sosirilor, primul sosit fiind primul servit.

Alte tipuri de reguli pot asocia niveluri de importanţă clienţilor şi deservirea prioritară a unora dintre aceştia în defavoarea clienţilor consideraţi de o mai mică importanţă.

1 First Input First Output


5.2 Fir de aşteptare cu sosiri poissoniene şi timpi de deservire exponenţiali

Acest tip de fir de aşteptare cu o singură unitate de deservire, cu sosiri poissoniene şi timpi de deservire exponenţiali se caracterizează prin: un singur fir de aşteptare; sosirile urmează o distribuţie de probabilitate Poisson; timpii de deservire urmează o distribuţie de probabilitate

exponenţială; regula de deservire este FIFO.

Dacă firma S.C. Meteor S.A. se încadrează în acest tip de fir de aşteptare atunci se consideră că numărul de sosiri în unitatea de timp =3 camioane/oră şi media numărului de unităţi deservite în sistem în unitatea de timp este =4 camioane/oră. Pe baza presupunerilor anterioare, s-au elaborat următoarele relaţii definitorii:

1. Probabilitatea ca unitatea de încărcare-descărcare să fie liberă (probabilitatea de a avea 0 camioane în

sistem) este: P0 = 1-μ

λ = 1-;

2. Probabilitatea de a avea n unităţi în sistem:

Pn =n

μ

λ

P0;

3. Numărul mediu de unităţi care aşteaptă să fie deservite

(lungimea cozii): Lq=λ)-μ(μ

λ2

;

4. Numărul mediu de unităţi în sistem (în curs de deservire

plus cei care aşteaptă în fir): L= Lq + μ

λ=

λ-μ

λ;


5. Timpul mediu de aşteptare până la deservire:

Wq= λ

Lq =λ)-μ(μ

λ;

6. Timpul mediu de aşteptare în sistem (aşteptare plus

deservire): W = Wq+μ

1=

λ-μ

1;

7. Probabilitatea ca o unitate sosită să aştepte în sistem:

Pa = μ

λ = .

Această probabilitate =μ

λ se numeşte factor de

utilizare a firului de aşteptare. Sistemul de deservire cu o singură linie de aşteptare

poate fi aplicat doar dacă μ

λ<1. Această relaţie este echivalentă

cu o medie a servirilor () mai mare decât media sosirilor ().

În cazul S.C. Meteor S.A. se deduc:

1. P0 = 1-4

3 = 0,25, probabilitatea ca unitatea de încărcare-

descărcare să fie liberă arată că în sistem sunt 0 camioane în 25% din cazuri;

2. Lq=λ)-μ(μ

λ2

=3)-4(4

32

= 2,25. Numărul mediu de camioane

din coadă este 2,25;

3. L= Lq + μ

λ=

λ-μ

λ =

3-4

3=3. Numărul mediu de unităţi în

sistem, în curs de deservire plus cei care aşteaptă în fir, este de 3 camioane;


4. Wq= λ

Lq =3

2,25= 0,75. Timpul mediu de aşteptare în fir

până la deservire pentru un camion este de 0,75 ore (45 minute);

5. W = Wq+μ

1= 0,75+0,25 =1. Timpul mediu de aşteptare în

sistem (aşteptare plus deservire) este de o oră pentru fiecare camion;

6. Pa = μ

λ = = 0,75. Probabilitatea arată că în 75% din

cazuri camioanele vor aştepta deservirea.

Modelul acesta furnizează informaţii relative la caracteristicile de operare ale sistemului de deservire. Dacă managerul va dori să introducă modificări în sistem, el poate să previzioneze care sunt rezultatele acestora.

Modelele firelor de aşteptare pot fi combinate, situaţiile reale în care ele sunt întâlnite pot fi mult mai complexe. De exemplu un singur fir de aşteptare şi mai multe staţii de deservire, pot să apară restricţii privind orarul de deservire al staţiilor etc.

Se pot de asemenea realiza simulări pentru activitatea de deservire şi se poate determina un comportament stochastic pentru unităţile de deservire.

CAPITOLUL 6

SIMULAREA PROCESELOR ECONOMICE

6.1 Simularea unui proces de stocare

Un en-gross-ist cumpără marfă pe care o stochează o anumită perioadă de timp, până în momentul în care o vinde. Se presupune că cererea se satisface la începutul zilei. S-a observat că cererea de marfă (r) a fost determinată printr-un studiu statistic. Cererea de marfă este aleatoare. În tabelul de mai jos este prezentată probabilitatea asociată unui anumit nivel al cererii.

Tabelul nr. 6. 1Nr.crt.

Valoarea cererii (r)P(r) = probabilitatea de a avea

nivelul cererii egal cu r 1 sub 100 0,002 100 0,063 150 0,114 200 0,205 250 0,126 300 0,037 350 0,108 400 0,089 450 0,12

10 500 0,18

S I M U L A R E A P R O C E S E L O R E C O N O M I C E1 1 6

En-gross-istul trebuie să determine densitatea de repartiţie a funcţiei P(r) notată aici prin F(r). Densitatea de repartiţie reprezintă probabilitatea cumulată pentru fiecare dintre valorile asociate cererii. Valoarea funcţiei densităţii de repartiţie se determină astfel: pentru o cerere sub 100 de unităţi, este egală cu

F(r<0)=P(r<0)=0; pentru F(r<100)= P(r<100) + P(r=100)=0+0,06=0,06 şi

arată că o cerere mai mică sau egală cu 100 de unităţi poate să apară cu probabilitatea de 0,06;

pentru F(r<150)=P(r<100)+P(r=100)+P(r=150)=0+0,06+0,11==0,06 şi arată că o cerere mai mică sau egală cu 150 deunităţi poate să apară cu probabilitatea de 0,11 ş.a.m.d.Valorile funcţiei densităţii de repartiţie sunt prezentate în

Tabelul 6.3 împreună cu mulţimile asociate valorilor acestei funcţii.

Tabelul nr. 6. 2

Nr. crt.

F(r)Densitatea de

repartiţie

Mulţimi asociate

1 0,00 02 0,06 0,00-0,053 0,17 0,06-0,164 0,37 0,17-0,365 0,49 0,37-0,486 0,52 0,49-0,517 0,62 0,52-0,618 0,70 0,62-0,699 0,82 0,70-0,81

10 1,00 0,82-0,99

S I M U L A R E A P R O C E S E L O R E C O N O M I C E 1 1 7

Durata de reaprovizionare este o variabilă aleatoare care are valorile posibile τ, determinate printr-un studiu statistic anterior şi care a returnat următoarele rezultate.

Tabelul nr. 6. 3

Nr. crt.

Durată dereaprovizionare τi

(zile)

P(τi) = probabilitatea de a realiza aprovizionarea în τi zile

1 sub 1 0,202 1 0,403 2 0,144 3 0,155 4 0,036 5 0,057 6 0,03

Pentru distribuţia descrisă în Tabelul nr. 6.3 se determină densitatea de repartiţie F(τi) şi mulţimile asociate.

Tabelul nr. 6. 4

Nr. crt.

F(r)Densitatea de

repartiţie

Mulţimi asociate

1 0,00 02 0,20 0,00-0,193 0,60 0,20-0,594 0,74 0,60-0,735 0,89 0,74-0,886 0,92 0,89-0,917 0,97 0,92-0,968 1,00 0,97-0,99

S I M U L A R E A P R O C E S E L O R E C O N O M I C E1 1 8

Se presupune că en-gross-istul se reaprovizionează cu o cantitate constantă Q= 800 unităţi de produs. De asemenea se cunosc următoarele informaţii:- costul de reaprovizionare CQ= 50000 u.m. (cheltuieli de

lansare comandă, transport, cheltuieli fixe);- costul unitar este c= 2000 u.m./buc. produs;- stocul iniţial este S0= 800 buc. produs.

Pot fi întâlnite următoarele situaţii:1. stocul cererea, fapt care nu determină probleme deosebite

distribuitorului;2. stocul < cererea, situaţie care poate fi rezolvată prin:

a. comandă specială cu costuri suplimentare cs= 30 u.m./buc. produs. Comanda poate fi primită cu o probabilitate de 0,7 în ziua următoare şi cu o probabilitate de 0,3 peste două zile de la lasarea comenzii.

b. nu există posibilitatea de a realiza o comandă specială şi se înregistrează pierderi datorate nesatisfacerii cererii prin cheltuielile de penalizare Cp=100 u.m./buc. produs lipsă/zi.

Se cere determinarea nivelului optim de stoc, prin modificarea unora dintre ipotezele de lucru (stoc iniţial,politică de reaprovizionare etc.)

Se poate introduce un nivel al stocului de siguranţă SS=500 buc., iar politica de reaprovizionare poate fi bazată pe comparaţia stocului existent astfel:- S< un nivel al stocului R, situaţie care implică efectuarea

unei comenzi speciale;- S< SS, situaţie care conduce la realizarea unei comenzi

obişnuite.

S I M U L A R E A P R O C E S E L O R E C O N O M I C E 1 1 9

Se simulează valori uniform distribuite pe intervalul închis [0, 1], pentru variabile aleatoare pe care le implică modelul:

Tabelul nr. 6. 5 Simulare variabile aleatoare

CerereDurată

reaprovizionareZile sosire

comandă specialăxi Si yi τi ti di

0,83 500 0,45 2 0,49 10,95 500 0,30 2 0,91 20,41 250 0,06 1 0,02 10,57 350 0,27 2 0,26 10,67 400 0,96 7 0,11 10,40 250 0,38 2 0,90 20,49 300 0,91 5 0,52 10,64 400 0,46 2 0,42 10,75 450 0,69 3 0,66 10,10 150 0,04 1 0,85 20,33 200 0,06 1 0,01 10,42 250 0,29 2 …0,61 350 0,77 40,59 350 0,97 70,85 500 0,50 20,45 250 …0,14 1500,42 2500,83 5000,44 250…

Folosind date din tabelele de numere aleatoare se determină care este nivelul optim al stocului şi al cantităţii de aprovizionat.

BIBLIOGRAFIE

Blezu Dorin, Boncuţ Mioara

Matematici aplicate în economie, Editura „Alma Mater“, Sibiu

Brabb J. George Introduction to Quantitative Management, Holt Inc., 1968

Charnes A. (coord.) Management Models and Industrial Applications of Linear Programming, John Wiley & Soons, Inc., NY, 1961

Dinescu Constantin, Fătu Ioan

Matematici pentru economişti, vol. I, II, III, E.D.P., Bucureşti, 1995

Dobre Ioan, Mustaţă Floarea

Simularea proceselor economice, Curs ASE Bucureşti

Gagsdale Cliff Spreadsheet Modelling and Decision Analysis, South-Western College Publishing, 1998

Mitruţ Dorin Culegere de probleme de Bazele Cercetării operaţionale, ASE Bucureşti

Mustaţă Floarea, Mărăcine Virginia

Cercetări operaţionale, Curs ASE Bucureşti

Naylor H. Thomas, Vernon M. John

Microeconomics and decision models of the firm, Harcourt Brace & World Inc., 1969

Nădejde Ileana (coord.)

Probleme de cercetare operaţională -programare matematică -, Editura Academiei RSR, Bucureşti, 1971

Nica Vasile, Mustaţă Floarea, Ciobanu Gheorghe, Mărăcine Virginia

Cercetări operaţionale I, Programare liniară, Problema de transport, Teoria jocurilor, Curs ASE Bucureşti

Popescu Octavian (coord.)

Matematici aplicate în economie, E.D.P.,Bucureşti, 1999

Roşca Liviu Modelare şi simulare, Editura „Alma Mater“, Sibiu

Wagner M. Harvey Principles of Operations Research, With Applications to Managerial Decisions, Prentice Hall, 1969

*** Information for Decision Making, Prentice Hall, New-Jersey, 1970

METODE CANTITATIVE ÎN MANAGEMENT -...

Documents

Transcript of METODE CANTITATIVE ÎN MANAGEMENT -...