OPERÁCIÓKUTATÁS, 2005. december 28. A 12 - 1330
NÉV: NEPTUN KÓD:
1. Követ kell szállítani Tapolcáról, illetve Veszprémből Kaposvárra és Pécsre. A szállításnál mind szárazföldön, mind vizen közbülső szállítási pontok iktathatók be. Tapolca kapacitása 120 egység hetente, Veszprém kapacitása 80 egység/hét. Kaposvár igénye 130 egység/hét, Pécs igénye 70 egység/hét. Egy egységnyi kő szállítási költségeit az alábbi táblázatok tartalmazzák. Szárazföldön: Tapolca Veszprém
Vízen: Badacsony Bfüred 14 19 21 15
Szárazföldön Fonyód Siófok
Kaposvár 15 18
Pécs 20 16
Fonyód Siófok Badacsony 5 8 Bfüred 8 5 Szárazföldön közvetlenül Kaposvár Pécs Tapolca 50 70 Veszprém 68 60
Más viszonylatban (például Badacsonyból Füredre, vagy Tapolcáról közvetlenül Fonyódra, stb.) a szállítás értelmetlen, ezért nem lehetséges. Optimális (minimális költségű) szállítási tervet kell készíteni. a. (10 pont) Töltse ki az alábbi táblázatban az üres cellákat a megfelelő számokkal úgy, hogy az eredményül kapott klasszikus szállítási feladat alkalmas legyen a fenti összetett szállítási feladat megoldására! Az üresen hagyott cellákat M-nek értelmezzük, azokat kitölteni nem kell.
Megoldás:
Az alábbi táblázat egy optimális szállítási tervet tartalmaz a hozzátartozó (optimális) duálváltozókkal együtt: Duálvált. 14 11 19 16 34 32 Duálvált. Badacsony Bfüred Fonyód Siófok Kaposvár Pécs 0 Tapolca 120 4 Veszprém 80 -14 Badacsony 80 120 -11 Bfüred 120 80 -19 Fonyód 80 120 -16 Siófok 120 10 70 b. (5 pont) Van-e olyan optimális megoldás, ahol Balatonfüredről két kikötőbe is szállítanak? igen c. (5+5 pont) Az alábbi viszonylatok közül melyikre igaz az, hogy ha az adott viszonylat költségét egy kis pozitív számmal növeljük (minden mást változatlanul hagyva), akkor az optimális megoldás egyértelmű lesz? Bfüred – Fonyód igaz Siófok – Pécs hamis 2. 5 új szakmunkásnak kell 5 precíziós kivitelt igénylő feladat megoldását betanítani. Korábbi tapasztalataik és munkaköreik ismeretében a következő táblázat állítható össze, ami jó közelítést ad a betanítási időkre (cij = az i-edik munkás j-edik feladatra történő betanításához szükséges idő). 15
3
12
25
19
8
6
10
19
23
12
4
9
4
17
4
17
9
3
11
13
27
24
13
14
a. (13 pont) Határozza meg (karikázza be), hogy a munkások feladatokhoz történő milyen hozzárendelése esetén lesz minimális a betanításhoz szükséges összidő, feltéve, hogy a 4. munkás nem kaphatja a 3. feladatot!(Mindegyik munkáshoz egy feladatot, mindegyik feladathoz egy munkást rendelünk.) MEGOLDÁS 15 3
12
25
19
8
6
10
19
23
12
4
9
4
17
4
17
9
3
11
13
27
24
13
14
b.(2 pont) Mekkora a minimális összköltség ebben az esetben?
Cmin= 3 + 10 + 4 + 4 + 14 = 35 nap 3. Tekintsük az alábbi irányított élekből és számozott csúcsokból álló gráfot! Az élekre írt első szám az él kapacitását jelöli, míg a második a rajta aktuálisan átmenő folyam értéket. Tehát például az (1,2) él kapacitása 30 egység, s jelenleg 17 egység folyik át rajta.
17/17
2
5 29/7
30/17
1
28/10 13/0
3
7 30/10
7/0 40/17
27/27 4
19/17
6
a. (8 pont) Adja meg a lehetséges javítások maximális értékeit az alábbi láncok mentén! (1) 1 → 4 → 3 → 6 → 7 (nem lehetséges javítás, mert f67 = k67) (2) 1 → 3 ← 5 → 7 (10 javítás lehetséges, k1=min(13,22)=13, k2=10, k=min(k1,k2)=10) (3) 1 → 3 → 6 → 7 (nem lehetséges javítás, mert f67 = k67) (4) 1 → 4 → 3← 5 → 7 (7 javítás lehetséges, k1=min(23,7,22)=7, k2=10, k=min(k1,k2)=7) b. (12 pont) Tegyük fel, hogy az adott folyamot feljavítottuk az a. pontban felsorolt láncok közül annak mentén, amelyik a legnagyobb javulást eredményezi. (Az 1 → 3 ← 5 → 7 mentén kell javítani, a javítás értéke: 10) Maximális-e az így feljavított folyam? Ha igen, adja meg a maximális folyam értékét és egy minimális vágást (a vágásban szereplő élek megadásával, illetve a forrást tartalmazó csúcspontok halmazának megadásával egyaránt!) igen(A kialakult folyam maximális, értéke 44; a keresett minimális vágás: {(2,5), (6,7)}, csúcspontokkal: 1, 2, 3, 4, 6)
Ha nem, adja meg az összes lehetséges láncot, mely mentén a folyam értéke még javítható (természetesen a javítás értékével együtt)!
4.Tekintsük az alábbi kifizetési mátrixszal reprezentálható, kétszemélyes, zéróösszegű játékot! (A táblázatban szereplő számok sorjátékos kifizetéseit mutatják, amit oszlopjátékostól kap.) 4 2 1
-1 -1 5
6 7 3
a. (4 pont) Keresse meg, és hagyja el a dominált sorokat és oszlopokat! Adja meg a lehető legjobban leredukált mátrixot! A 3. oszlopot lehet elhagyni, utána pedig a második sort. 4 1
-1 5
b. (4 pont) Van-e a játéknak nyeregpontja? Ha igen, melyik pozícióban? Ha nincs, miért nincs? Nincs, mert maximin = 1 < 4 = minimax c. (10 pont) Határozza meg az egyes játékosok optimális kevert stratégiáit! A sorjátékosé: x1=4/9 , x2=0 , x3=5/9 Az oszlopjátékosé: y1=2/3 , y2=1/3 , y3=0 d. (2 pont) Adja meg a játék értékét! A játék értéke v=7/3 5. Tekintsük a következő LP-t: max z=3x1 x1 + x2 + x1 + x3 + x1 ,
+ 6x2 -4x3 + x4 – x5 + 6x6 x3 + x4 <= 15 x3 + x5 <= 17 x2 + x4 + x5 <= 19 x4 + x6 <= 14 x2 , x3 , x4 , x5 , x6 >= 0
Milyen változókkal és feltételekkel kell a modellt bővíteni ahhoz, hogy a kiegészített modell lineáris maradjon és minden lehetséges megoldása teljesítse az alábbi kikötéseket? Ügyeljen arra, hogy az új feltételek szükségtelen megszorításokat ne jelentsenek! (a) (7pont) ha x4 > 0, akkor x4 >= 2 legyen Megoldás: 2y <= x4 <= 14y , y = 0 vagy 1
(b) (7 pont) az x2 , x3 , x4 változók közül legalább egy 0 legyen Megoldás: x2<=17z1 , x3<=14z2 , x4<=14z3 , z1+z2+z3<=2 , z1 , z2 , z3 = 0 vagy 1 (c) (6 pont) az x2 + x3 >=7 , x4 + x6 <=5 feltételek közül legalább az egyik biztosan teljesüljön Megoldás: x2 + x3 >= 7v , x4 + x6 <= 5+9v , v = 0 vagy 1
OPERÁCIÓKUTATÁS, 2006. január 19. A 14 - 1530
NÉV: NEPTUN KÓD:
1. A B1, B2, B3 bányákból az E1, E2, E3 erőművekbe lehet szenet szállítani. A bányák havi kapacitásait, az erőművek havi igényeit és az egységnyi szállítási költségeket az alábbi táblázat tartalmazza.
a. (3 pont) Készítsen lehetséges induló bázismegoldást az északnyugati sarok módszerrel! (Az eredményt írja az alábbi táblázatba!)
B1 B2 B3
E1 100 100
E2 50 50 100
E3 100 100 200
150 150 100
b. (6 pont) Adjon meg egy optimális bázismegoldást a duál-optimális változókkal együtt! (Az eredményt írja az alábbi táblázatba!)
0 -8 -7
10 100 100
11
100 100
14 50 150 0 200
150 150 100
c. (2 pont) Mekkora a célfüggvény optimális értéke? 3000 d. (4 pont) Hogyan változik az optimális célfüggvényérték, ha az E1 erőmű igényét és a B2 bánya kapacitását egyaránt x-szel növeljük, ahol x egy kis pozitív szám?...2x-szel nő.....
2. A Malév két jegykezelő pultnál szolgálja ki londoni járatának utasait. Az utasok egy sorban várakoznak és az először megüresedő pulthoz mennek, ha sorra kerülnek. Az utasok beérkezése között eltelt idő exponenciális eloszlású, 10 percenként átlag 15 utas érkezik meg. A jegykezelés időtartama szintén exponenciális eloszlású 1 perces várható értékkel. A jegykezelő pult működtetésének óránkénti költsége 2000 Ft függetlenül attól, hogy éppen folyik-e utaskiszolgálás. Egy utas várakoztatásának költsége 3000 Ft óránként, ami elsősorban abból adódik, hogy a sorbanállás és kiszolgálás ideje alatt az utasok nem tudják igénybe venni a reptéri éttermek és boltok szolgáltatásait. Ennek a sorbanállási modellnek a megoldása során a QSB a következőket írta ki: System Performance Summary for Malév Performance Measure 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
Result
System: M/M/2 From Formula Customer arrival rate (lambda) per hour = ... Service rate per server (mu) per hour = ... Overall system effective arrival rate per hour = ... Overall system effective service rate per hour = ... Overall system utilization = ... Average number of customers in the system (L) = 3,4286 Average number of customers in the queue (Lq) = 1,9286 Average number of customers in the queue for a busy system(Lb)=3,0000 Average time customer spends in the system (W) = 0,0381 Average time customer spends in the queue (Wq) = 0,0214 Average time customer spends in the queue for a busy system(Wb)0,0333 The probability that all servers are idle (Po) = 14,2857% The probability that system is busy (Pb) = 64,2857% Average number of customers being balked per hour = 0 Total cost of busy server per hour = ... Total cost of idle server per hour = ... Total cost of customer waiting per hour = ... Total cost of customer being served per hour = ... Total cost of customer being balked per hour = 0 Total queue space cost per hour = 0 Total system cost per hour = ...
Amint látjuk a kiírás nem lett tökéletes, mert bizonyos mezők üresen maradtak. A meglévő adatok segítségével is meg lehet azonban válaszolni a következő kérdéseket: a) (8 pont) Mekkora az egész rendszer költsége óránként? 14286 b) (2 pont) Mekkora a rendszer kihasználtsági együtthatója? 0,75 A menedzsment elhatározza, hogy ezentúl két külön sort képez, egyet az elsőosztályú, egyet pedig a másodosztályú utasoknak. A jegykezelés szempontjából a két csoport között nincs különbség. Az utasok 50-50%-ban oszlanak meg első és másodosztályúakra. c) (2 pont) Az új rendszerben a régihez képest az egész rendszer költsége növekszik csökken nem változik d) (6 pont) Mennyi lesz az új rendszer költsége? 22000 e) (2 pont) Mi annak a valószínűsége, hogy az új rendszerben egyik sorban sem várakozik senki? (1-(45/60)2)2 =0,19 (senki sem várakozik, ha a rendszerben 0 vagy 1 üzletfél van)
3. Az alábbi gráfon az élek mellé írt számok az él hosszát jelentik. Az éleken mindkét irányban
haladhatunk. 6 12 7
5 6
2 10
1
9
13
11 14
3 8
4 a) (10 pont) Adja meg az 1-es csúcsból a többi csúcsba vezető legrövidebb utakat az alábbi táblázat kitöltésével: megoldás: felső ábra 1-ből 2-be 3-ba 4-be 5-be 6-ba
vezető út csúcsokkal megadva
b. (5 pont) Rajzolja be a minimális feszítő fát! (a megfelelő éleket duplán húzza ki, vagy egyértelmű x jelzéssel lássa el!) megoldás: Alsó ábra c. (5 pont) Változtassa meg egyetlenegy él hosszát úgy, hogy az 1-es pontból bármely másik pontba a minimális feszítő fa mentén vezessen a legrövidebb út! Melyik él hosszát változtatja? Pl. (1, 2)
Mennyi legyen az új élhossz? 1
6 12 7
5 6
2 10
1
9
13
11 14
3 8
4
4. Három gép (F, G és H) háromféle (P, R, S) termék bármelyikét képes előállítani. Az egyes gépeken egy óra alatt bármelyik termékből egy készíthető el. A gépek kapacitása rendre 30, 40 és 50 gépóra, az egyes termékekből minimálisan előállítandó mennyiség rendre 20, 14 és 16 darab. Egy termék darabjának gyártási költsége az egyes gépeken az alábbi táblázatban látható: F G H
P 4 4 3
R 5 6 4
S 6 5 7
Jelölje xij az i-edik gépen a j-edik termékből gyártandó mennyiséget darabban, i= 1,2,3; j=1,2,3. a.(4 pont) Írjuk fel a célfüggvényt, ha az összköltséget szeretnénk minimalizálni. 4x11 +5x12 +6x13 +4x21 +6x22 +5 x23 +3x31 +4x32 +7x33 b.(6 pont) Irjuk fel azokat a feltételeket, amelyek a gépek kapacitásának korlátozottságát fejezik ki. x11 + x12 + x13 ≤ 30 x21 + x22 + x23 ≤ 40 x31 + x32 + x33 ≤ 50
c. (8 pont) Jelölje y1 , y2 , y3 ≥0 a gépek ki nem használt kapacitását! y1 = 30-(x11 + x12 + x13 ) y2 = 40-(x21 + x22 + x23 ) y3 = 50-(x31 + x32 + x33 ), Vezessen be nulla-egy változókat, és írjon fel olyan lineáris egyenlőtlenségeket, amelyek azt a követelményt fejezik ki, hogy legalább két gép kapacitását teljesen ki kell használni. Vezessük be a v1, v2, v3 nulla-egy változókat. Ekkor a következő feltételeket kell csatolni a feladat feltételrendszeréhez: y1 ≤ 30v1, y2 ≤ 40v2, y3 ≤ 50v3, v1+ v2+ v3 ≤ 1 d. (7 pont) Írjunk fel olyan lineáris egyenlőtlenségeket, amelyek azt a követelményt fejezik ki, hogy ha az első gépet foglalkoztatjuk (legalább egy terméket gyártunk rajta), akkor a kapacitáskihasználtsága legalább 50% legyen. Az u nulla-egy változót használva: y1-15<=M (1-u) 30-y1≤ Mu 5. Az alábbi 10 állítás közül az igazakat jelölje meg I betűvel, a hamisakat pedig H-val! (Minden helyes válasz 2 pont, minden helytelen válasz –1 pont, ha nem jelölt be semmit 0 pont) Egy klasszikus szállítási feladat költségmátrixa n sort és m oszlopot tartalmaz. A következő 5 állítás a feladat báziscelláival illetve bázisonkívüli celláival foglalkozik. a) Ha a báziscellákhoz egy bázison kívüli cellát hozzáveszünk, akkor az így kapott cellák pontosan egy hurkot tartalmaznak. b) A báziscellák száma n+m. c) A báziscellák száma n+m-1. d) A báziscellák halmaza nem tartalmaz hurkot. e) Tetszőleges n+m cellából álló halmaz tartalmaz hurkot. Helyes válasz: (a) , (c) (d) és (e) igaz. A következő 5 állítás egy egészértékű maximum feladatra vonatkozik, melyet a szétválasztás és korlátozás módszerével oldunk meg. a) A feladat LP-lazításának optimális értéke az eredeti feladat optimumának felső korlátja. b) Az ágaztatást mindig a legnagyobb célfüggvény-értékű részfeladat mentén folytatjuk. c) A keresztléptetés (jumptracking) során nem ugorhatunk át a fa egyik ágáról a másikra. d) A feladatnak mindig van optimális megoldása. e) Az optimális megoldást a legnagyobb célfüggvény-értékű megoldás-jelölt adja. Igaz: a), e)
OPERÁCIÓKUTATÁS, 2007. január 23. A 1200 - 1330
NÉV: NEPTUN KÓD:
1. (25 pont) Az alábbi hálózaton az élek mellé írt számok közül az első az él terhelése (a folyam értéke az élen), a második pedig az él kapacitása, F a forrás, Ny pedig a nyelő. Például a 2-es pontból az 5-ösbe vezető él terhelése jelenleg 0, az él kapacitása pedig 5. 3/3
1 3/5 4/7
2 0/4
4/4
7/9
4/4
0/1
F
4
Ny
0/1
0/5
3
4/6
5
4/4 A megadott folyamból kiindulva készítsen maximális folyamot! a. Adja meg a javító lépéseket az alábbi táblázat kitöltésével: (8 pont) Útvonal (lánc) A javítás értéke F – 2 - 5 – Ny 2 F – 2 – 5 – 4 - Ny 1 b. Adja meg a maximális folyamot! (4 pont) 3/3
1 3/5 0/1 7/7
F
4 4/4
2 0/4
4/4
8/9
3
Ny
1/1
3/5
5
6/6
4/4 c. Mennyi a maximális folyam értéke? 14 (2 pont) d. Adjon meg egy minimális vágást (sorolja fel a vágás éleit)!{1, 4), (2, 4), (5, 4), (5, Ny} (5 pont) e. Sorolja fel az összes olyan élt (vagy jelezze ha nincs ilyen), amelyre igaz, hogy az adott él kapacitását növelve, ugyanakkor a többi él kapacitását változatlanul hagyva, a maximális folyam értéke növekszik! (1,4), (2,4), (5,4), (5,Ny) (6 pont)
2. (20 pont) Tekintsük a következő hozzárendelési (minimum)feladatot! F1 F2 F3 F4 F5
M1 4 2 4 3 15
M2 11 10 1 8 7
M3 8 8 3 5 9
M4 8 10 3 9 12
M5 9 7 4 12 11
A feladat magyar módszerrel történő megoldása során a WinQSB programmal lépésről lépésre haladva az alábbi táblához jutottunk.
Folytassa az algoritmust, és adjon meg két optimális hozzárendelést (a megfelelő cellákat jelölje x-szel)! (14+4 pont) X
x x
x
x
x
x x
x x
Az összköltség minimuma: 26. (2 pont) 3. (20 pont) Egy kis bank ügyfélforgalma jól leírható az M/M/s sorbanállási rendszerrel. Egy ügyintéző fizetése naponta 80 USD Egy ügyintéző naponta átlagosan 30 ügyfelet tud kiszolgálni. Naponta átlagosan 25 ügyfél érkezik a bankba. Az ügyfelek várakoztatási költsége 120 USD/nap. Összköltségnek nevezzük az ügyintéző(k) fizetésének és a várakoztatási költségnek az összegét. (A sorbanállás ideje és a kiszolgálás ideje egyaránt várakoztatásnak számít.) A bank célja az összköltség minimalizálása.Az ügyintézők száma s, a rendszerben lévő ügyfelek száma j, ρ a rendszer kihasználtsági együtthatója, L a rendszerben tartózkodó ügyfelek átlagos száma, Lq = a sorbanálló ügyfelek átlagos száma.
Töltse ki az alábbi táblázatot (számítsa ki a hiányzó értékeket)! (18 pont) s
1
2
3
P(j>=s) ρ=
0,833
0,2451
0,0577
0,833
0,4166
0,2778
Lq =
4,166 5,000
0,1751 1,0084
0,0222 0,8555
680
281
342,7
L Költség
Hány ügyintézőt célszerű alkalmazni, ha az összköltség minimalizálása a cél? Kettőt (2 pont) 4. (25 pont) Egy folytatásos TV-játék elkészítéséről és műsorba állításáról kell döntenie egy TV-stúdiónak A hasonló műsorokról a múltban készített felmérések alapján tudják, hogy az ilyen műsorok kb. 70%-a sikeres (S), és 30% a megbukott (B) műsorok aránya. Egy sikeres műsor az első félévben (múltbeli tapasztalatok alapján) 3m€ nettó jövedelmet, míg egy bukás pedig 2m€ veszteséget hoz magával. Lehetőség van egy piackutató cég megbízására, amely véleményt mond a sorozat várható sikerességéről, tehát hogy siker (pozitív jóslat) vagy bukás (negatív jóslat) lesz-e az. eredmény. Rendelkezésre állnak a piackutató cég korábbi ilyen jellegű munkái eredményességét jellemző adatok: A sikeres sorozatok esetén az esetek 80%-ában az előrejelzés is sikert jósolt, 20%-ában pedig bukás volt az előrejelzés. Ugyanakkor a bukást megélő produkciók esetén az esetek 85%-nál az előrejelzés is bukás, 15% esetében pedig az előrejelzés siker volt. Dönteni kell arról, hogy alkalmazzák-e a piackutatót, s milyen esetben készítsék el, s tegyék műsorra sorozatot. a. (10 pont) Töltse ki az alábbi döntési fát a hiányzó valószínűségekkel és várható nyereségekkel! A számítások rövidítésére két kiszámolandó valószínűséget előre megadunk: P(S/negatív jóslat)= 0.354, P(negatív jóslat)=0.395
2: 0
5: 3
Nem Siker 0.7 1
3
Igen
1.5
1.59 Piackut
Bukás: 0.3 Igen 7
Poz.60.5% 4
Siker92.6%.
6: -2
2.63
1.59
13: 3
9 2.63
Bukás. 7.4%
14: -2
10: 0
Nem
Siker.35.4%
Igen
11
Neg.39.5% 8
-0.23 Bukás64.6%
15: 3 16: -2
0 Nem 12: 0 b. (6 pont) Mi az optimális döntéssorozat? B1:igénybe vesszük-e a Piackutató céget? Igen B2 Mit teszünk pozitív előrejelzés esetén? Megcsináljuk B3 Mit teszünk negatív előrejelzés esetén? Nem csináljuk meg a műsort c. (4 pont) Mennyi a maximális várható nyereség optimális döntéshozatal esetén? 1.59 d. (5 pont) Mennyit érdemes fizetni a piackutató cégnek az előrejelzésért? (<0.09)
5. (10 pont) Az alábbi 5 állítás közül az igazakat jelölje meg I betűvel, a hamisakat pedig Hval! (Minden jó megjelölés 2 pont, minden rossz megjelölés –1 pont, ha nem jelölte meg az állítást, 0 pont) Egy n csúcsból és m élből álló gráfban legrövidebb utakat keresünk az 1-es csúcsból a többi csúcsba. a. Az 1-esből bármely másik P csúcsba vezető legrövidebb út legfeljebb (n-1) élből áll. I b. Az 1-esből bármely másik P csúcsba vezető legrövidebb út legfeljebb (m-1) élből áll. H c. Ha a B csúcs rajta van az 1-esből az A csúcsba vezető legrövidebb úton, akkor (1 és A távolsága) = (1 és B távolsága) + (B és A távolsága) I d. Ha a Dijkstra féle címkézési algoritmus végén minden csúcs végleges címkéje véges, akkor a gráf összefüggő. I e. Ha az 1-esből bármely másik P csúcsba vezető legrövidebb út egyértelmű, akkor a legrövidebb utak fát alkotnak. I
OPERÁCIÓKUTATÁS 2007. január 23., 1200 - 1330
B
NÉV: NEPTUN KÓD:
1. (25 pont) Egy folytatásos TV-játék elkészítéséről és műsorba állításáról kell döntenie egy TV-stúdiónak. A hasonló műsorokról a múltban készített felmérések alapján tudják, hogy az ilyen műsorok kb. 60%-a sikeres (S), és 40% a megbukott (B) műsorok aránya. Egy sikeres műsor az első félévben (múltbeli tapasztalatok alapján) 4m€ nettó jövedelmet, míg egy bukás pedig 3m€ veszteséget hoz magával. Lehetőség van egy piackutató cég megbízására, amely véleményt mond a sorozat várható eredményességéről, vagyis, hogy az siker (pozitív jóslat) vagy bukás (negatív jóslat) lesz-e. Rendelkezésre állnak a piackutató cég korábbi ilyen jellegű előrejelzéseinek pontosságára vonatkozó adatok: a sikeresnek bizonyult sorozatok 85%-át az előrejelzés is sikernek jósolta, 15%-át viszont bukásnak. Ugyanakkor a végül megbukott produkciók 80%-át az előrejelzés is bukásnak, 20%-át viszont sikernek jósolta. Dönteni kell arról, hogy alkalmazzák-e a piackutatót, s milyen esetben készítsék el, és tűzzék műsorra sorozatot. a. (10 p.) Töltse ki az alábbi döntési fát a hiányzó valószínűségekkel és nyereségekkel! A számítások rövidítésére két kiszámolandó valószínűséget előre megadunk: P(Siker / pozitív jóslat)= 0.864, P(negatív jóslat)=0.41 2: 0 Nem
1
5: 4 Siker 60%
3
Igen
1.2
1.798 Piackut
Siker86.4%.
6: -3 Bukás 40%
Poz.59% 4
Igen
Neg.41%
Igen
8 0
Bukás13.6%
14: -3
10: 0
Nem
3.05
1.798
9 3.05
7
13: 4
Siker22%.
15: 4
11 Nem
-1.46
Bukás78%
16: -3
12: 0 b. (6 p.) Mi az optimális döntéssorozat? B1: Igénybe vesszük-e a piackutató céget? Igen B2: Mit teszünk pozitív előrejelzés esetén? Megcsináljuk a műsort B3: Mit teszünk negatív előrejelzés esetén? Nem csináljuk meg a műsort c. (4 p.) Mennyi a maximális várható nyereség optimális döntéshozatal esetén? 1.798 d. (5 p) Mennyit érdemes fizetni a piackutató cégnek az előrejelzésért? (<0.598)
2. (20 pont) Egy önkormányzati ügyfélszolgálati iroda ügyfélforgalma megfelelően leírható az M/M/s sorbanállási rendszerrel. Egy ügyintéző fizetése naponta 40 Euro. Egy ügyintéző naponta átlagosan 40 ügyfelet tud kiszolgálni. Naponta átlagosan 60 ügyfél érkezik az irodába. Az ügyfelek várakoztatási költsége 60 Euro/nap. Összköltségnek nevezzük az ügyintéző(k) fizetésének és a várakoztatási költségnek az összegét. (A sorbanállás ideje és a kiszolgálás ideje egyaránt várakoztatásnak számít.) Az önkormányzat célja az összköltség minimalizálása. Az ügyintézők száma s, a rendszerben lévő ügyfelek száma j, a rendszer kihasználtsági együtthatója ρ, a rendszerben tartózkodó ügyfelek átlagos száma L, a sorbanálló ügyfelek átlagos száma Lq . a. (18 p.) Töltse ki az alábbi táblázatot (a hiányzó értékek kiszámítása után)! s = P(j ≥ s)= ρ = Lq = L = W = Költség =
2 0,643 0,75 1,93 3,43 0,057 285,8
3 0,237 0,5 0,237 1,737 0,029 224,2
4 0,075 0,375 0,045 1,545 0,026 252,7
b. (2 p.) Hány ügyintézőt célszerű alkalmazni, ha az összköltség minimalizálása a cél? Hármat
3. (10 pont) Az alábbi 5 állítás közül az igazakat jelölje meg I betűvel, a hamisakat pedig Hval! (Minden jó megjelölés 2 pont, minden rossz megjelölés –1 pont, ha nem jelölte meg az állítást, 0 pont) Egy n csúcsból és m élből álló gráfban legrövidebb utakat keresünk az 1-es csúcsból a többi csúcsba. a. Ha a legrövidebb utak fát alkotnak, akkor az 1-esből bármely másik P csúcsba vezető legrövidebb út egyértelmű. I b. Az 1-esből bármely másik P csúcsba vezető legrövidebb út legfeljebb (m-1) élből áll. H c. Ha az A csúcs rajta van az 1-esből a B csúcsba vezető legrövidebb úton, akkor (1 és A távolsága) = (1 és B távolsága) - (A és B távolsága) I d. Ha a Dijkstra féle címkézési algoritmus végén valamelyik csúcs végleges címkéje végtelen, akkor a gráf nem összefüggő. I e. Az 1-esből bármely másik P csúcsba vezető legrövidebb út legfeljebb (n-1) élből áll. I
4. (25 pont) Az alábbi hálózatban az élek mellé írt számok közül az első az él terhelése (a folyam értéke az élen), a második pedig az él kapacitása, F a forrás, Ny pedig a nyelő. Például a Forrásból az 1-esbe vezető él terhelése jelenleg 5, az él kapacitása pedig 9. 5/5
1 5/9 4/8
2 0/7
7/7
7/17
2/4
0/1
F
4
Ny
0/2
2/5
3
9/13
5
7/7 A megadott folyamból indulva készítsen maximális folyamot! a. (8 p.) Adja meg a javító lépéseket az alábbi táblázat kitöltésével: Például Útvonal (lánc) A javítás értéke F – 2 - 5 – Ny 3 F – 2 – 4 – 5 – Ny 1 F – 1 – 2 – 4 - Ny 1 b. (4 p.) Adja meg a maximális folyamot! A (4,5), (4,Ny), (5,Ny) élek kivételével egyértelmű. 5/5
1 6/9 1/1 8/8
F
4 4/4
2 0/7
7/7
8/17
1/2
5/5
3
Ny
5
13/13
7/7 c. (2 p.) Mennyi a maximális folyam értéke? 21 d. (5 p.) Adjon meg egy minimális vágást (sorolja fel a vágás éleit)! Három van: {(1,4), (2,4), (2,5), (3,5)} vagy {(1,4), (1,2), (F,2), (F,3)} vagy {(1,4), (1,2), (F,2), (3,5)} e. (6 p.) Sorolja fel az összes olyan élt (vagy jelezze, ha nincs ilyen), amelyre igaz, hogy az adott él kapacitását növelve, ugyanakkor a többi él kapacitását változatlanul hagyva, a maximális folyam értéke növekszik! (1,4) a három minimális vágásban az egyetlen közös él
5. (20 pont) Tekintsük a következő hozzárendelési (minimum)feladatot! F1 F2 F3 F4 F5
M1 5 3 5 4 13
M2 9 8 3 6 8
M3 9 9 2 6 7
M4 6 8 3 10 20
M5 5 8 2 10 9
A feladat magyar módszerrel történő megoldása során a WinQSB programmal lépésről lépésre haladva az alábbi táblához jutottunk.
a. (14+4 p.) Folytassa az algoritmust, és adjon meg két optimális hozzárendelést (a megfelelő cellákat jelölje x-szel)! x
x
x
x x X
x x
x
b. (2 p.) Az összköltség minimuma: 24.
x
