C3

A C2

C1 C4

C5

C6

20

50

60

30

40

2080

40

20

50

30

Drumuri în grafuri (Networks - Minimum Spanning Tree)

Se dă un graf neorientat având m noduri şi n arce. Pentru arce se

defineşte o măsură (de exemplu: cost, distanţă). Se pune problema conectării

tuturor nodurilor astfel încât suma totală a valorilor arcelor utilizate să fie

minimă.

Se obţine astfel – arborele drum minim.

Date de intrare:

- numărul de arce [2 ... 100];

- pentru fiecare arc se indică:

1. numărul nodului de start;

2. numărul nodului final;

3. valoarea măsurii arcului (distanţă, cost);

Observaţie:

Graful fiind neorientat nu contează ordinea în care sunt indicate

extremităţile arcelor.

Exemplu:

O firmă de instalaţii electrice studiază posibilitatea de legare a 6

consumatori (C1, ..., C6) la punctul de alimentare (A). Condiţiile tehnice de

instalare permit stabilirea unui număr de 11 legături, date împreună cu

costurile aferente în graful de mai jos.

Rezolvare:

Se numerotează nodurile A → 1, C1 → 2, ..., C6 → 7 şi se introduc

informaţiile necesare celor 11 arce de exemplu: - arcul 1 :(1, 2) cu valoarea

20.

Este indiferentă ordinea de introducere a informaţiilor despre arce.

Metoda drumului critic(Project management [PERT/CPM])

Analiza drumului critic este o metodă modernă de conducere a

proiectelor complexe, permiţând planificarea pe termen mediu şi scurt ,

programarea operativă a execuţiei precum şi actualizarea periodică a acestor

proiecte în funcţie de factorul timp, cost şi resurse.

Au fost dezvoltate independent două tehnici în managementul ştiinţific al

firmelor:

PERT - Program Evaluation and Review Tehnique

CPM – Critical Path Method

Modulul PERT / CPM permite asistarea factorilor de decizie răspunzând

următoarelor întrebări:

1. Care este durata totală a proiectului?

2. Care sunt datele de început şi sfârşit pentru fiecare activitate?

3. Care sunt activităţile critice?

4. Care este intervalul cu care poate fi amânată o activitate critică?

Modulul poate fi utilizat pentru analiza proiectelor cu un număr de

activităţi cuprins în intervalul [2, 90].

Utilizatorul trebuie să stabilească lista activităţilor şi pentru fiecare

activitate lista activităţilor imediat precedente.

Activităţile sunt identificate printr-o literă, iar activităţile imediat

precedente ale unei activităţi vor fi identificate prin litere care preced în

alfabet litera respectivă. De exemplu activitatea :”E”nu poate avea ca

predecesori decât activităţile identificate prin literele „A”, „B”, „C” sau „D”.

Ne propunem să prezentăm în continuare doar două dintre cele cinci

cazuri cu care operează modulul Project management (PERT/CPM)

1. Activităţile au durate cunoscute (Single time estimate)

2. Activităţile au durate aleatoare ( Triple time estimate)

Cazul 1. Single Time Estimate

Date de intrare:

- numărul de activităţi [2 ... 90];

- pentru fiecare activitete se indică:

numărul de activităţi imediat precedente;

literele care identifică activităţiile precedente;

durata activităţii.

Exemplu:

Se consideră un proiect complex, compus din 9 activităţi. Condiţionările

dintre activităţi şi duratele acestora sunt date în tabelul de mai jos:

Activitatea

Activităţi precedente Durata

A - 5B - 6C A 4D A 3E A 1F E 4G D, F 14H B, C 12I G, H 2

Programul indică drumul critic, durata totală de execuţie a proiectului,

precum şi intervalele de fluctuaţie şi marginile libere pentru activităţile

necritice.

Soluţia este prezentată in pagina Error: Reference source not found.

Cazul 2. Triple Time Estimate

Datele de intrare rămân aceleaşi, însă pentru durata activităţii se dau 3

perioade de timp:

- durata minimă a activităţii (estimarea optimistă);

- durata maximă a activităţii (estimarea pesimistă);

- durata cea mai probabilă.

Comentariu:

În practică, duratele activităţiilor sunt insuficient cunoscute şi nesigure.

Există două cazuri: sau activităţiile nu sunt noi şi se cunoaşte aproximativ

legea de repartiţie a duratei de execuţie, sau activităţile sunt în întregime noi

sau foarte puţin cunoscute. Prin chestionarea specialiştilor responsabili cu

fiecare activitate se pot determina cele trei durate (minimă, maximă şi cea mai

probabilă)

Exemplu:

Se consideră un proiect complex compus din 10 activităţi. Condiţionările

dintre activităţi şi cele trei durate estimate pentru fiecare activitate sunt date în

tabelul de mai jos:

Activitatea Activităţi precedente Durata Optimistă Cea mai probabilă Pesimist

ăA - 4 5 12B - 1 1.5 5C A 2 3 4D A 3 4 11E A 2 3 4F C 1.5 2 2.5G D 1.5 3 4.5H B, E 2.5 3.5 7.5I H 1.5 2 2.5J F, G, I 1 2 3