aplicatii_grafuri

7/24/2019 Aplicatii_grafuri

1/6

x0

x1

x3

x2 x4

x52

1

5

4

2

3 x6

2

1 4

3

x0

x1

x3

x2 x6

x5

6

65

4

3

3

x8

45

4

5

x7

x4

36

3

2

2

4

4

4

4

7

4

2 2

1

Teoria grafurilor Aplicaii LABORATOR

1. Din localitatea 0x este solicitat un produs de ctre o secie a unei ntreprinderi din localitatea

6x . Presupunnd c pentru transportul produsului se poate olosi siste!ul de linii erate din i". 1 unde aost indicat# pentru iecare poriune de cale erat# ti!pul de deplasare dintr$o localitate la alta# s sedeter!ine ruta care tre%uie s se alea" ntre cele dou localiti# astel nct ti!pul necesar transportului

produsului s ie !ini!.

Fig. 1

2. & a%ric de tractoare 'i transport produsele pentru export# spre un port !ariti!# cu trenul. (n

"raul din i"ura 2# nodul 0x repre)int localitatea n care se "se'te a%rica# nodul 8x localitatea n carese al portul !ariti!# iar restul "ri. *alorile arcelor repre)int nu!rul !axi! de +a"oane ce pot iata'ate supli!entar unor trenuri de !ar existente# pentru transportul produselor ntre dou "ri. , sedeter!ine nu!rul !axi! de +a"oane ce pot a-un"e de la a%ric n port.

Fig. 2

3. (ntr$o localitate de tran)it exist dou ci de intrare notate # / 'i trei ie'iri # # 'i P. Dincau)a deselor a"lo!erri de traic# pri!ria a cut un studiu din care a reie'it c n orele de traic !axi!n ora' sosesc 1000 de !a'ini pe or la intrarea 'i 1200 de !a'ini pe or la intrarea / 'i prsesc ora'ul600 de !a'ini prin ie'irea # 700 prin 'i 00 prin P.

apacitile 'oselelor !a'ini pe or care lea" intrrile de ie'iri sunt date n ta%elul ur!tor

P 300 300 600/ 400 500 100

, se deter!ine nu!rul !axi! de !a'ini care pot tran)ita prin localitate ntr$o or 'i ce soluiide asi"urare a necesarului pot i date.

4. Pentru a i ncl)it# apa de la un a"ent ter!ic este trecut# de la punctul de colectare0x

la punctulde ie'ire 7x # printr$un siste! de conducte care trec prin !ai !ulte ca)ane 621 #...## xxx i". 3# supuse surseicalorice.

1

4


2/6

x0

x1

x3

x4

x7

x6

5

8

3 2

4

15

3

x2 x55

1

6

1

4

x2

x1

x4

x5

x11

x12

7

5

7

15

15

5

5

4

x3

x10

30

7

15

4

5 x8

10

107

x6

x7 x

10

unoscndu$se de%itele !axi!e suportate de conducte trecute pe iecare arc s se or"ani)e)e transportul

astel nct s se o%in de%itul !axi! posi%il n punctul 7x # pentru distri%uia la %eneiciari.

Fig. 3

5. rei ora'e 121110 ## xxx sunt ali!entate cu ap de la patru staii de po!pare 4321 ### xxxx # alecror re)er+e )ilnice sunt de 15 !ii de !3 pentru x1# 10 !ii de !3 pentru x2# 15 !ii de !3pentru x3'i15 !ii de !3 pentru x4. eeaua de distri%uie este repre)entat n i"ura 4# de%itele !axi!e ale iecruitronson iind trecute pe iecare arc al reelei n !ii de ! 3pe )i. ererile )ilnice !axi!e pro%a%ile alecelor trei ora'e sunt de 15 !ii de ! 3pentru x10# 20 de !ii de !3pentru x11'i 15 !ii de !3pentru x12. , sedeter!ine luxul !axi! ce poate tra+ersa reeaua 'i tietura de capacitate !ini! corespun)toare.

Fig. 4

6. & co!panie %ancar dore'te s instale)e# la cel !ai !ic pre# o reea de trans!itere auto!at adatelor# de la a"enia sa central la 'apte din sucursalele sale. ostul de reali)are a unei linii de reea ntredou a"enii este dat n ta%elul ur!tor. , se !odele)e pro%le!a su% or! de "ra 'i s se deter!inesoluia opti!.

"enia

central / D 9 : ; < $/ 5 $ 18 17 $D 11 27 $9 13 7 23 20 $: 7 12 15 15 15 $; 38 38 20 40 40 35 $< 22 15 25 25 30 10 45 $

2


3/6

7. & societate dispune de trei centre de producie # / 'i care reali)ea) acela'i tip de produs.Produsele a%ricate sunt distri%uite spre +n)are la patru !a"a)ine 1# 2# 3 'i 4. apacitile de

producie pe spt!n ale celor trei centre# cererile !a"a)inelor n aceast period 'i costurile unitare detransport sunt date n ta%elul de !ai -os

/-Di

1 2 3 4 di

4 2 5$

480

/ 6$

7$

3 8100

3 5$

4$

5$ 120

%- 50 60 0 100

,e cere s se deter!ine planul opti! de transport al produselor de la cele trei centre de produciela cele patru !a"a)ine de desacere# astel nct costul total al transportului s ie !ini!.

8. & societate petrolier dispune de cinci rainrii # /# # D 'i 9 care utili)ea) !aterie pri!

din i!port ce pro+ine de la patru urni)ori =# ># ? 'i @. apacitatea de producie a iecreia dintrerainrii n !ii de tone# cantitile expediate de urni)ori n !ii de tone 'i costurile unitare de transportsunt date n ta%elul ur!tor.

/-Di

/ D 9 di

= 110 120 100 105 11560

> 165 155 150 180 17540

? 200 210 203 206 2075

@ 130 125 127 132 13225

%- 50 75 30 25 20

,e cere s se sta%ileasc un plan opti! de transport al produselor petroliere de la urni)ori larainrii# astel nct costul total al transportului s ie !ini!.

. Din trei depo)ite D1# D2# D3 tre%uie transportate cantiti de produs la patru centre de +n)are/1# /2# /3 'i /4# astel nct costul total al transportului s ie !ini!. Datele pro%le!ei sunt pre)entaten ta%elul de !ai -os

/-Di

/1 /2 /3 /4 di

D1 3 2 3 470

D2 1 2 3 410

D3 3 2 2 120

%- 50 25 15 10

a. , se deter!ine soluia opti! dac soluia iniial de %a) este deter!inat prin !etoda colului ord$*est.

%. , se deter!ine soluia opti! dac soluia iniial de %a) este deter!inat prin !etoda ele!entului!ini! din ta%el.

3


4/6

11. & societate are dou a%rici de ri"idere# una n ora'ul &1 'i alta n ora'ul &2. :a%rica din &1produce 160 ri"idere pe spt!n# iar cea din &2# 200 de !a'ini pe spt!n. ,ocietatea tri!iteprodusele la centrele de desacere din ora'ele &3 'i &4# care cer# iecare# cte 140 ri"idere pe spt!n.osturile unitare de transport sunt date n ta%elul de !ai -os

&3 &4&1 26 30

&2 26 249xist posi%ilitatea ca produsele s ie tri!ise !ai nti la centrele 1 Ai 2 'i apoi# de acolo# la

destinaiile inale# &3 'i &4. osturile de transport sunt respecti+

1 2 &3 &4 1 2&1 7 14 1 15 17 0 7&2 15 12 2 14 15 7 0

,e cere1. are este planul de transport 'i costul total !ini! dac produsele sunt tri!ise direct la destinatarB2. are este planul de transport 'i costul total !ini! dac se olosesc centrele inter!ediare 1 'i 2B

12. & ir! textil are dou a%rici# doi urni)ori de !aterii pri!e 'i trei centre de desacere.

osturile de transport pentru o ton de ncrctur ntre urni)or 'i a%rici 'i ntre a%rici 'i centrele dedesacere sunt date n ta%elul de !ai -os

:a%ric

:urni)or

/ entru dedesacere

:a%ric1 2 3

1 1 1#5 4 2 12 2 1#5 / 3 4 2

,unt disponi%ile 10 tone de la urni)orul 1 'i 15 tone de la urni)orul 2. ele trei centre dedesacere necesit 8# 14 respecti+ 3 tone de produse inite. ele dou a%rici au capacitate de producieneli!itat. ,e cere

a. , se reduc pro%le!a la o pro%le! de transport cu dou surse 'i trei destinaii 'i s se deter!ine un plande transport care s !ini!i)e)e cCeltuielile totale.

b. Dac a%rica are o capacitate de producie de 8 tone 'i a%rica / o capacitate de producie de 7 tone# s sedesco!pun pro%le!a n dou pro%le!e de transport 'i s se re)ol+e.

13., se reparti)e)e lucrrile 1# 2# 3# 4 la !uncitorii 1# 2# 3# 4 astel nct ti!pultotal de execuie s ie !ini!. Duratele de execuie ale iecrei lucrri de ctre iecare !uncitor sunttrecute n ta%elul ur!tor

1 2 3 41

13 37 52 10

2

37 61 67 34

3

52 7 85 37

4

43 82 88 31

14.Din cele 'ase produse # /# # D# 9# : ce pot i reali)ate la 'ase ntreprinderi E1# E2# E3# E4# E5#E6 s se reali)e)e acea repartiie care s asi"ure cCeltuieli de producie !ini!e. oeicienii din ta%elul de!ai -os repre)int costuri unitare de producie.

/ D 9 :

E1 2 2 23 2 26 3E2 14 10 63 78 7 0E3 3 76 56 0 3 57

4


5/6

E4 43 0 0 6 60 51E5 0 27 32 24 27 47E6 10 30 12 32 0 37

15. inci !uncitori pot executa oricare dintre cele patru lucrri ce tre%uie reali)ate# dar ti!pii deexecuie ai iecrei lucrri de ctre iecare !uncitor sunt dierii 'i dai n ta%el. , se reali)e)e repartiiaopti! astel nct ti!pul total de prelucrare s ie !ini!.

1 2 3 41

10 6 10 14

2

16 13 10 4

3

1 10 7 10

4

14 15 6 10

5

13 8 13 8

16. & ir! are patru +n)tori care tre%uie s !ear" la patru clieni. Proiturile reali)ate suntdate n ta%elul de !ai -os. , se deter!ine acea repartiie a +n)torilor la clieni care s asi"ure un proittotal !axi!.

1 2 3 4*1

22 17 20 24

*2

22 14 10 18

*3

14 22 14 8

*4

17 20 18 14

17. & ir! dore'te s an"a-e)e trei persoane pentru eectuarea unor lucrri de secretariat. aconcurs s$au pre)entat 'apte persoane# care au ost supuse unor teste. Punctele acordate acestora# pentrueectuarea celor trei tipuri de lucrri# sunt date n ta%el. e persoane +or i an"a-ate 'i ce lucrare +aexecuta iecare# dac se dore'te o%inerea puncta-ului !axi! totalB

1 2 3P1 17 15 1P2 18 14 16

P3 14 18 18P4 15 13 16P5 20 1 18P6 18 15 17P7 1 18 1

18. , se ale ciclul Ca!iltonian de +aloare !ini! punctul de plecare este pri!ul nod al"raului# n ordinea notrii pentru ur!toarele date iniiale distane ntre locaii

5


6/6

a. %.

6

aplicatii_grafuri

Documents