FACULTATEA DE ŞTIINŢE ECONOMICECATEDRA DE MANAGEMENT – MARKETINGCURS NR.11

ORDONANŢAREA LANSĂRILOR ÎN FABRICAŢIE (II)

11.1 GRAFURI. DEFINIŢII ŞI PROPRIETĂŢI GENERALE11.2 DESCOMPUNEREA UNUI GRAF ORIENTAT ÎN COMPONENTE TARE CONEXE11.3 DETERMINAREA DRUMURILOR HAMILTONIENE ALE UNUI GRAF CU ALGORITMUL LUI FULKES ÎN CADRUL UNEI LINII DE FABRICAŢIE11.4 DETERMINAREA SUCCESIUNII OPERAŢIILOR UNUI PROCES TEHNOLOGIC

11.1 GRAFURI. DEFINIŢII ŞI PROPRIETĂŢI GENERALE

11.1.1 Noţiunea de graf

Fie două mulţimi nevide.

Definiţia 1.1. Se numeşte graf orientat un triplet , unde: . Aplicaţia f, numită funcţie de incidenţă, asociază fiecărui element o pereche

ordonată .Dacă oricare este imaginea a cel mult p elemente din atunci G se

numeşte un p-graf orientat. Fiecare element se numeşte vîrf sau nod iar X - mulţimea vîrfurilor sau nodurilor grafului G.

Elementele lui se vor numi arce. Dacă , x se numeşte extremitatea iniţială şi y extremitatea finală a arcului u.

Un arc pentru care se numeşte buclă.

Definiţia 1.2. Un graf orientat se numeşte l -graf orientat dacă / este o funcţie injectivă.

Graful este finit dacă X este o mulţime finită.În continuare pentru o mulţime finită M vom nota cu | M | numărul elementelor

sale. Dacă un graf orientat are , , atunci G este numit un (n, m) - graf orientat.

Numărul n se numeşte ordinul grafului.

Definiţia 1.3. Un graf orientat se numeşte graf simplu dacă G este l-graf finit şi fără bucle.

Subliniem că în acest curs se consideră numai grafuri simple. Un astfel de graf va fi notat , unde va reprezenta mulţimea vârfurilor grafului iar mulţimea arcelor, cu precizarea că un arc cu extremităţile x şi y se notează cu .

Un graf se reprezintă geometric în modul următor (fig.11.1a):1) fiecare vîrf este reprezentat printr-un punct în plan;2) fiecare arc , se reprezintă printr-o linie (arc) care îi uneşte cele

două extremităţi distincte si pe care se află o săgeata cu sensul de la x la y.

2

a) b) Fig. 11.1 Reprezentarea grafurilor

Exemplul nr.1. Fie , unde , , , ,

, ,

Atunci graful este reprezentat geometric în figura 11.1b.

Definiţia 1.4. Două arce din G se numesc adiacente dacă au cel puţin o extremitate comună.

11.1.2 Matrice asociată unui graf

Fie un graf orientat cu X = şi . In vederea rezolvării problemelor cu ajutorul calculatorului, graful G trebuie reprezentat numeric.

În general, un graf poate fi reprezentat în mai multe moduri, dintre care alegem aici numai reprezentarea prin :

Matricea asociată. Matricea definită astfel:

se numeşte matricea asociată grafului G.

3

Matricea A ale cărei elemente sunt egale cu 1 şi 0 se numeşte şi matricea booleană asociată grafului G.

Exemplul nr.2. Fie un graf orientat reprezentat geometric în figura 11.2a.

a) b) Fig.11.2.

Matricea, asociată grafului G este dată de

11.1.3 Drumuri şi circuite într-un graf orientat

Fie un graf orientat cu , .

Definiţia 1.5. Un drum al grafului G este un şir de varfuri cu proprietatea că , , .

Se notează cu , iar x1, xp se numesc extremităţile drumului. Numărul arcelor care compun drumul se numeşte lungimea drumului. Un drum poate fi simplu sau compus după cum arcele sale sunt sau nu folosite fiecare cate o singură dată.

4

Fig.11.3 Fig. 11.4

Un drum elementar este şi simplu, dar reciproca nu este adevărată.În graful din figura 11.3, drumul este simplu, dar nu este

elementar.

Definiţia 1.6. Un drum elementar care trece prin toate varfurile grafului G se numeşte drum hamiltonian.În graful din figura 11.4, si sunt drumuri hamiltoniene.

Definiţia 1.7. Un drum se numeşte circuit dacă x1= xp şi toate arcele sunt distincte.

Un circuit este elementar sau nu după cum trece sau nu o singură dată prin fiecare din vârfurile sale.

Exemple de drumuri pentru graful din figura 11.3 sunt următoarele:, , ,

dintre care nu este elementar. Acest graf

conţine şi circuite elementare, cum ar fi: ,

, , , dar nu este elementar.

Definiţia 1.8. Un drum hamiltonian se numeşte circuit hamiltonian dacă extremităţile sale coincid.În graful din figura 11.4, .

11.1.4 Lanţuri şi cicluri într-un graf neorientat

Fie un graf neorientat cu ,

Definiţia 1.9. Un lanţ al grafului G este un şir de vârfuri cu proprietatea că , ,……, .

5

Definiţia 1.10. Un lanţ elementar care trece prin toate vârfurile grafului se numeşte lanţ hamiltonian.

In graful din figura 11.2b, lH= [x1, x2, x3, x4], lH= [x1, x4, x2, x3] sunt lanţuri hamiltoniene.

Definiţia 1.11. Un lanţ harniltonian se numeşte ciclu hamiltonian dacă extremităţile sale coincid.

Definiţia 1.12. Graful se numeşte conex dacă pentru oricare două vârfuri distincte există un lanţ de extremităţ x şi y.

Proprietatea ,,există un lanţ de la x la y sau x = y” defineşte pe X o relaţie de echivalenţă ale cărei clase se numesc componente conexe în G.

O componentă conexă a unui graf G mai poate fi definită ca un subgraf conex al lui G, care nu este conţinut strict în alt subgraf conex al lui G, adică este un subgraf maximal (în raport cu incluziunea) relativ la proprietatea de a fi conex.

11.1.5 Arborescenţă

Fie un graf orientat cu si . Proprietatea ,,există un drum de la x la y şi există un drum de la y la x” defineşte pe X o relaţie de

echivalenţă ale cărei clase se numesc componente tare conexe în G.

Definiţia 1.13. Un graf orientat G se numeşte tare conex dacă pentru orice există un drum de la x la y şi un drum de la y la x.

Din definiţia 1.13 rezultă că G este tare conex numai dacă admite o singură componentă tare conexă.

11.2 DESCOMPUNEREA UNUI GRAF ORIENTAT ÎN COMPONENTE TARE CONEXE

Din punct de vedere practice prezintă interes descompunerea unui graf orientat , în componentele sale tare conexe. Dintre metodele cunoscute vom folosi

algoritmul lui Fulkes. Pentru aceasta în mulţimea elementelor matricelor asociate unui

graf G se introduce operaţiile de sumă şi produs boolean după cum urmează:

1 1 = 1 1 1 = 1

6

1 0 = 1 şi 1 0 = 0

0 0 = 0 0 0 = 0

Algoritmul lui Fulkes are următoarele etape: 1 . Se scrie matricea booleană A a grafului G.

2 . Se ridică la puteri succesive matricea E A, unde E este matricea unitate de

acelaşi tip cu A. Operaţia de ridicare la putere continuă până când două puteri consecutive

ale lui E A sunt egale. Pentru a scurta calculele, atunci când n este destul de mare, se

caută K minim (2K < n), astfel încât:

3 . În matricea se suprimă liniile de rang care sunt formate

numai cu cifra 1 şi coloanele corespunzătoare care sunt formate numai cu cifra 0. Atunci formează clasa de echivalenţă I.

4 . Fie B matricea care formează cu elementele liniilor şi coloanelor nesuprimate ale lui . 5 . Pentru matricea B se aplică etapa 3 , iar dacă nu este cazul se aplică etapele 2 şi apoi 3 , determinând a doua clasă de echivalenţă II ş.a.m.d. 6 Pentru vârfurile fiecărei clase de echivalenţă: I, II, . . . se trasează arce care păstrează incidenţa din graful G.

Exemplul nr.3 Folosind algoritmul lui Fulkes să se descompună graful G din figura 11.5 în componentele sale tare conexe.

7

1 2 3 4 5 1 2 3 4 5

1 2 3 4 5

1 2 3 4

Fig. 11.5 Fig. 11.6

Etapa 1. Matricea booleană a grafului G este

iar

Avem

Suprimăm linia şi coloana 5 în matricea Prima clasă de echivalenţă a lui G

este I= Matricea care se formează cu elementele suprimate ale lui este:

8

1 2 3 4 5 6 1 2 3 4 5 6

Se suprimă liniile, respectiv coloanele 1, 2 şi 3. Deci, a doua clasă de echivalenţă a lui G este: II = Etapa 2. Matricea care se obţine din B prin suprimarea liniilor, respectiv coloanelor

1, 2, 3 este C = 4[ ]. A treia clasă de echivalenţă III =

În figura 11.6 este dat graful G cu vârfurile sale împărţite în clase de echivalenţă.

11.3 DETERMINAREA DRUMURILOR HAMILTONIENE ALE UNUI GRAF CU ALGORITMUL LUI FULKES ÎN CADRUL UNEI LINII DE FABRICAŢIE

Algoritmul lui Fulkes are următoarele etape: 1 . Se determină componentele tare conexe ale grafului G, notate cu I, II, . . . 2 . Între vârfurile acestor componente se trasează arce care păstrează incidenţa din graful G. 3 . Trecând de la o componentă la alta se stabilesc toate drumurile hamiltoniene ale grafului. Observaţie. Algoritmul lui Fulkes este eficient atunci când componentele tare conexe ale grafului conţin un număr mic de vârfuri.

Exemplul nr.4. Folosind algoritmul lui Fulkes, să se determine drumurile hamiltoniene ale grafului G din figura 11.7.

Fig. 11.7 Fig. 11.8

1 . Matricea booleană a grafului G este

9

1 2 3 4 5 6

1 2 3 5 6

şi

Avem:

Suprimăm linia şi coloana 4 în matricea Prima clasă de echivalenţă a lui

G este I= Matricea care se formează cu elemente nesuprimate ale lui este:

Se suprimă liniile, respectiv coloanele 1, 2 ,3. Deci a doua clasă de echivalenţă a lui G este

II =

Matricea care se obţine din G prin suprimarea liniilor, respectiv coloanelor 1, 2, 3 este:

10

5 6

1 2 3 4 5 1 2 3 4 5

A treia clasă de echivalenţă

III =

2 . Între vârfurile componentelor I, II, III, din figura 11.8, trasăm arce care păstrează incidenţa din graful G.3 . Trecând de la o componentă la alta obţinem drumul hamiltonian (

).

Exemplul nr.5. O linie de fabricaţie a unei întreprinderi industriale produce cinci produse . Dacă după produsul se fabrică produsul trebuie suportat un cost de lansare (trecere) , iar dacă produsul se fabrică după produsul atunci costul de lansare este (în general ).

Ştiind că matricea costurilor de trecere este:

1 2 3 4 5

Să se determine ordinea de execuţie a celor cinci produse astfel încât costul total de lansare, într-un interval de timp, să fie minim. O asemenea problemă se reduce la determinarea drumurilor hamiltoniene în graful în care vârfurile reprezintă cele cinci produse, arcele reprezintă posibilităţile de trecere de la un produs la altul în procesul de fabricaţie, iar lungimile arcelor reprezintă cheltuielile implicate de aceste treceri. Pentru aceasta definim matricea booleană

dacă unde dacă

dacă

11

1 2 3 4 5

1 2 4 5

iar

Avem

Suprimăm linia şi coloana 3 în matricea Prima clasă de echivalenţă a lui

G este { }. Matricea care se formează cu elementele nesuprimate ale lui este:

Se suprimă liniile, respectiv coloana 5. Deci, a doua clasă de echivalenţă a lui G este II =

Matricea care se obţine din B prin suprimarea liniei, respective coloanei 5 este:

12

1 2 4

A treia clasă de echivalenţă III =

Fig. 11.9 Fig. 11.10

Graful G care admite matricea A este reprezentat geometric în figura 11.9. Reprezentând geometric clasele de echivalenţă rezultate pe baza algoritmului lui Fulkes obţinem graful care indică ordinea de lansare în fabricaţie a produselor (figura 11.10). Pe acest graf sunt trecute costurile corespunzătoare operaţiilor de trecere. Costul total de trecere corespunzător drumului Hamiltonian de lungime minimă este

min

11.4 DETERMINAREA SUCCESIUNII OPERAŢIILOR UNUI PROCES TEHNOLOGIC

Stabilirea succesiunii optime a operaţiilor unui proces tehnologic este una din problemele deosebit de importante de rezolvat la proiectarea procesului tehnologic. Succesiunea optimă a operaţiilor este condiţionată, în principal, de asigurarea condiţiilor tehnice impuse cât şi de economicitatea procesului tehnologic. Pentru realizarea condiţiilor tehnice pot fi aplicate însă mai multe variante tehnologice. Reducerea acestei diversităţi de variante de procese tehnologice este posibilă prin optimizarea succesiunii operaţiilor. Tratarea matematică a problemei succesiunii optime a operaţiilor este posibilă prin asocierea unui graf procesului tehnologic. În acest scop este necesar să se parcurgă mai multe etape, şi anume: 1 . stabilirea naturii operaţiilor;

13

1 2 3 4 5 6 1 2 3 4 5 6

2 . folosirea restricţiilor tehnologice la stabilirea succesiunii operaţiilor; 3 stabilirea grafului asociat procesului tehnologic; 4 stabilirea matricei asociate grafului; 5 stabilirea drumului hamiltonian DH.

Fig. 11.11 Fig. 11.12

3 . Să presupunem că parcurgerea etapelor 1 şi 2 ne conduc pentru un proces tehnologic dat la graful din figura 11.11. 4 . Matricea asociată grafului G din figura 11.11 este:

;

5 . Pentru determinarea drumului hamiltonian ne folosim de algoritmul lui Fulkes. Avem

14

3 4 5 6

1 2 3 4 5 6

1 3 4 5 6

3 4 5

Suprimăm linia şi coloana 2 în matricea Prima clasă de echivalenţă a lui G

este I = Matricea care se formează cu elementele nesuprimate ale lui este:

Se suprimă linia, respectiv coloana 1. Atunci a doua clasă de echivalenţă a lui G este II = Matricea care se ob- ţine prin suprimarea liniei, respectiv coloanei 1 este:

Se suprimă linia, respectiv coloana 6. Deci a treia clasă de echivalenţă a lui G este III = Matricea care se ob- ţine prin suprimarea liniei, respectiv coloanei 6 este:

Suprimând linia, respectiv coloana 4 obţinem o a patra clasă de echivalenţă IV = şi în acelaşi mod clasele de echivalenţă V= , respectiv VI =

Reprezentând geometric clasele de echivalenţă rezultă, pe baza algoritmului lui Fulkes, graful din figura 11.12, care indică succesiunea optimă a operaţiilor procesului tehnologic.

15

16