Download - 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
-
7/24/2019 Aplicatii_grafuri
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
-
7/24/2019 Aplicatii_grafuri
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
-
7/24/2019 Aplicatii_grafuri
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
-
7/24/2019 Aplicatii_grafuri
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
-
7/24/2019 Aplicatii_grafuri
6/6
a. %.
6