Gazdasági Ismeretek | Operációkutatás » Operációkutatás vizsga

Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu Operációkutatás vizsga A csoport Budapesti Corvinus Egyetem 2007. január 9 Egyéb gyakorló és vizsgaanyagok találhatók a http://matstat.fwhu honlapon a Letölthető vizsgasorok, segédanyagok OPERÁCIÓKUTATÁS 2007. január 9, 8 - 930 A menüpont alatt. NÉV: NEPTUN KÓD: 1. (18 pont) Egy vállalatnál 5 új munkatársat kell betanítani 5 feladat végzésére (mindegyik munkatársat pontosan egy feladatra tanítják be). A betanítási idők (órában) a következők: 2 23 11 15 5 8 8 16 27 26 7 9 21 11 12 13 10 6 18 15 17 7 24 22 29 a. (10 pont) Határozzuk meg a Magyar módszerrel a minimális összidőt eredményező hozzárendelést, és a minimális összidő értékét! -a1- Adjuk meg az előbb a sorok, majd az oszlopok redukciójával kapott ekvivalens feladatot! 0 6 5 11 15 0 5 5 11 15 16 1 2 3 0 16 0 2 3 0 5 10 15 0 18 5 9 15

0 18 4 16 0 7 11 4 15 0 7 11 0 21 7 10 24 0 20 7 10 24 -a2- Adjuk meg az algoritmus során kapott utolsó ekvivalens feladatot! 0 0 0 6 10 21 0 2 3 0 10 9 15 0 18 9 15 0 7 11 0 15 2 5 19 Az eredeti feladathoz tartozó minimális összidő:37 b. (8 pont) Maximálisan mekkora lehet az összidő növekedése az a) pontban meghatározotthoz képest, ha találomra készítjük el a hozzárendelést? 76 1 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu Adjuk meg a lehető legnagyobb összidőt eredményező hozzárendelést is! 2 23 11 15 5 8 8 16 27 26 7 9 21 11 12 13 10 6 18 15 17 7 24 22 29 A maximális összidő = 13+23+21+27+29 = 113. 113 –37 = 76 a max. veszteség 2. (20 pont) Tekintsük az alábbi irányított élekből és számozott csúcsokból álló gráf által megadott maximális folyam feladatot, amelyben az 1-es csúcs a forrás és a 7-es a nyelő! 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ékét. Tehát például az (1,2) él kapacitása 30 egység, s jelenleg 14 egység folyik át rajta 12/10 3 6 24/24 25/10 1 23/14 5/0 5/0 4 7 25/14 2/0 30/14 30/0 2 14/14 5 a. (8 p) Adja meg a lehetséges javítások maximális értékeit az alábbi láncok mentén! (1) 1 2 4 6 7 (nem lehetséges javítás, mert f67 = k67) (2) 1 3 6 ← 5 7 (nem lehetséges javítás, mert f56 = 0) (3) 1 4 ← 5 7 (javítás 5-tel) (4) 1 2 4 ← 5 7 ( javítás 2-vel) b. (12 p) 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. Maximális-e az így feljavított folyam? 2 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu 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!) (Nem) Ha nem, adja meg az összes olyan láncot, amely mentén a folyam értéke még javítható (a javítás maximális értékével együtt)! 1 2 4 ← 5 7 mentén 2-vel 1 3 6 ← 4 ← 5 7 mentén 2-vel 3. (20 pont) Az alábbi 10 á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) Az a.-e állítások mindegyike a CPM (kritikus út) feladattal kapcsolatos Az (i,j) él által reprezentált tevékenység időtartama tij , az i esemény legkorábbi bekövetkezésének időpontja ET(i), legkésőbbi bekövetkezésének időpontja LT(i). a. Egy kritikus út valamennyi élén a tűréshatár 0 I b. A tűréshatár nem haladhatja meg a mozgáshatár értékét H c. A mozgáshatár mindig nagyobb a tűréshatárnál H d. ET(j) = min

(ET(i)+tij ) H (i,j) e. LT(i) = min (LT(j)-tij ) I (i,j) . Egy tiszta egészértékű lineáris maximumfeladat optimumának értékét max-szal, a fellazított (relaxált) feladat optimumát maxf-fel jelöljük. f. Van olyan feladat-pár, amelyre max < maxf I g. Van olyan feladat-pár, amelyre maxf < max H h. Van olyan feladat-pár, amelyre maxf = max I i. Van olyan feladat-pár, hogy az egészértékű feladatnak nincs lehetséges megoldása, de a fellazított feladatnak van. I j. Van olyan feladat-pár, hogy a fellazított feladatnak nincs lehetséges megoldása, de az egészértékű feladatnak van. H 4. (22 pont) Egy vállalat 1000 db új telefon készüléket szeretne vásárolni Két szállító jön szóba. Az első szállító 11 ezer forintért adja darabját, és minden készüléket, amelyik egy éven belül meghibásodik, ingyen kicserél jóra. A másik szállító 10 ezer forintért adja darabját, de nem ad ingyen cserekészüléket, hanem azért is 10 ezer

forintot kell fizetni. Feltehetjük, hogy a cserekészülékek már garantáltan hibátlanok. A vállalat árubeszerzője 2 esetet vesz figyelembe: egy éven belül vagy 0 vagy 20 százalékos lehet a 3 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu meghibásodás. Ezekhez valószínűségeket rendeli: Meghibásodási % Valószínűség az 0 0.6 esetekhez a következő (szubjektív) 20 0.4 Ezek a valószínűségek mindkét szállító esetén azonosak. Az árubeszerzőnek el kell döntenie, hogy melyik szállítót válassza. a. (6 p) Írjuk fel az ehhez a döntési problémához tartozó kifizető mátrixot (ezer Ft-ban) kifizetés (ezer Ft) 1. szállító 2. szállító 0% meghibásodik 11000 10000 20% meghibásodik 11000 12000 Melyik beszállítót válasszák, hogy a telefon vásárlás egy évre vett várható költsége a lehető legkisebb legyen? a 2. beszállítót Hány

ezer Ft lesz ekkor a várható kifizetés? 10800 eFt Az árubeszerzőnek lehetősége van arra, hogy bármelyik 1000 telefont tartalmazó szállítmányból egy készüléket egy olyan vizsgálatnak vessenek alá, ami tévedés nélkül kimutatja, hogy a telefon hibás-e (pontosabban, hogy egy éven belül meghibásodik-e) vagy sem. b. (6 p) Mi annak a valószínűsége, hogy a megvizsgált készülék hibátlan? (0,92) Mi annak a valószínűsége, hogy nincs hibás készülék a szállítmányban, feltéve, hogy a megvizsgált készülék hibátlan volt? (0,652) Mi annak a valószínűsége, hogy a szállítmányban a készülékek 20%-a meghibásodik, feltéve, hogy a megvizsgált készülék hibás volt? (1) c. (4 p) Töltsük fel a vizsgálattal kapcsolatos döntési fát a szükséges valószínűségekkel és várható költségekkel! (Véletlen elágazás élein tüntesse fel a valószínűségeket, minden csúcsnál pedig a várható költség -1-szeresét!) 4 Matematika,

statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu 0% 1. szállító 0.55 4 -11 2. hibás 8.00% -11 2. szállító 0.55 1. szállító 0.55 92.00% 3.Nem hibás -10.696 -12 0% 0% hiba: -10 100% 20% hiba:-12 65.2% 0% hiba: -11 6 -11 2. szállító 0.55 20% hiba:-11 5 1 -10.72 100% 0% hiba: -11 34.8% 20% hiba:-11 65.2% 7 0% hiba: -10 -10.696 34.8% 20% hiba:-12 d. (4 p) Mi az optimális döntési stratégia? Ha a megvizsgált készülék hibátlan, akkor a 2. beszállítótól kell rendelni, ekkor az egy évre vett várható költség 10696 ezer Ft. Ha a megvizsgált készülék hibás, akkor a 1. beszállítótól kell rendelni, ekkor az egy évre vett várható költség 11000 ezer Ft. e. (2 p) Maximum mennyit érdemes fizetni a vizsgálatért? (80 ezer) 5. (20 pont) Két vállalat, A és B, ugyanolyan terméket gyárt Egy főútvonal mentén fekvő 4 város egyikében üzletet akarnak

nyitni. A városok távolságait az alábbi ábrában a 5 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu vonalak fölötti számok mutatják, a városokban a termék iránti keresletet pedig a körökben lévő számok jelölik (ezer főben). 20 10 km 1. 40 10 km 20 2. 10 km 3. 20 4. Ha valamelyik városhoz a nagyobb A vállalat üzlete van közelebb, akkor A az adott város forgalmának 80%-át szerzi meg magának. Ha egyenlő távolságra vannak az üzletek az illető várostól, akkor az A vállalaté lesz a forgalom 60%-a. Végül, ha a B vállalat üzlete van közelebb egy városhoz, akkor az A vállalat a forgalom 40%-át szerzi meg. a. (10 p) Írjuk fel a játék kifizetőmátrixát! A az 1. városban A a 2. városban A a 3. városban A a 4. városban B az 1. városban 60 72 64 56 B a 2. városban 48 60 56 52 B a 3. városban 56 64 60 48 b. (10 p) Határozzuk meg az

optimális stratégiákat, és a játék értékét! Mindkét vállalat a 2. városban nyit üzletet Az A vállalaté a forgalom 60%-a 6 B a 4. városban 64 68 72 60 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu Operációkutatás vizsga B csoport Budapesti Corvinus Egyetem 2007. január 16 Egyéb gyakorló és vizsgaanyagok találhatók a http://matstat.fwhu honlapon a Letölthető vizsgasorok, segédanyagok OPERÁCIÓKUTATÁS 2007. január 9, 8 - 930 B menüpont alatt. NÉV: NEPTUN KÓD: 1. (22 pont) Egy vállalat 1000 db új telefon készüléket szeretne vásárolni Két szállító jön szóba. Az első szállító 21 ezer forintért adja darabját, és minden készüléket, amelyik egy éven belül meghibásodik, ingyen kicserél jóra. A másik szállító 20 ezer forintért adja darabját, de nem ad ingyen cserekészüléket, hanem azért 15 ezer forintot kell fizetni.

Feltehetjük, hogy a cserekészülékek már garantáltan hibátlanok. A vállalat árubeszerzője 2 esetet vesz figyelembe: egy éven belül vagy 0 vagy 10 százalékos lehet a meghibásodás. Ezekhez az esetekhez a következő (szubjektív) valószínűségeket rendeli: Meghibásodási % Valószínűség 0 0.7 10 0.3 Ezek a valószínűségek mindkét szállító esetén azonosak. Az árubeszerzőnek el kell döntenie, hogy melyik szállítót válassza. a. (6 p) Írjuk fel az ehhez a döntési problémához tartozó kifizető mátrixot (ezer Ft-ban) kifizetés (ezer Ft) 1. szállító 2. szállító 0% meghibásodik 21000 20000 10% meghibásodik 21000 21500 Melyik beszállítót válasszák, hogy a telefon vásárlás egy évre vett várható költsége a lehető legkisebb legyen? a 2. beszállítót Hány ezer Ft lesz ekkor a várható kifizetés? 20450 eFt Az árubeszerzőnek lehetősége van arra, hogy bármelyik 1000 telefont tartalmazó szállítmányból egy

készüléket egy olyan vizsgálatnak vessenek alá, ami tévedés nélkül 1 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu kimutatja, hogy a telefon hibás-e (pontosabban, hogy egy éven belül meghibásodik-e) vagy sem. b. (6 p) Mi annak a valószínűsége, hogy a megvizsgált készülék hibátlan? (0,97) Mi annak a valószínűsége, hogy nincs hibás készülék a szállítmányban, feltéve, hogy a megvizsgált készülék hibátlan volt? (0,7216) Mi annak a valószínűsége, hogy a szállítmányban a készülékek 10%-a meghibásodik, feltéve, hogy a megvizsgált készülék hibás volt? (1) c. (4 p) Töltsük fel a vizsgálattal kapcsolatos döntési fát a szükséges valószínűségekkel és várható költségekkel! (Véletlen elágazás élein tüntesse fel a valószínűségeket, minden csúcsnál pedig a várható költség -1-szeresét!) 0% 1. szállító 0.55 4 -21 2.

hibás 3.00% -21 2. szállító 0.55 100% 0% 0% hiba: -20 -21.5 100% 10% hiba:-21.5 72.16% 1. szállító 0.55 97.00% 3.Nem hibás -20.418 0% hiba: -21 6 -21 2. szállító 0.55 10% hiba:-21 5 1 -20.435 0% hiba: -21 27.84% 10% hiba:-21 72.16% 7 0% hiba: -20 -20.418 27.84% 10% hiba:-21.5 2 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu d. (4 p) Mi az optimális döntési stratégia? Ha a megvizsgált készülék hibátlan, akkor a 2. beszállítótól kell rendelni, ekkor az egy évre vett várható költség 20418 ezer Ft. Ha a megvizsgált készülék hibás, akkor a 1. beszállítótól kell rendelni, ekkor az egy évre vett várható költség 21000 ezer Ft. e. (2 p) Maximum mennyit érdemes fizetni a vizsgálatért? (15 ezer) 2. (20 pont) Két vállalat, A és B, ugyanolyan terméket gyárt Egy főútvonal mentén fekvő 4 város egyikében üzletet akarnak nyitni. A

városok távolságait az alábbi ábrában a vonalak fölötti számok mutatják, a városokban a termék iránti keresletet pedig a körökben lévő számok jelölik (ezer főben). 20 10 km 1. 20 10 km 40 2. 10 km 3. 20 4. Ha valamelyik városhoz a nagyobb A vállalat üzlete van közelebb, akkor A az adott város forgalmának 80%-át szerzi meg magának. Ha egyenlő távolságra vannak az üzletek az illető várostól, akkor az A vállalaté lesz a forgalom 60%-a. Végül, ha a B vállalat üzlete van közelebb egy városhoz, akkor az A vállalat a forgalom 40%-át szerzi meg. a. (10 p) Írjuk fel a játék kifizetőmátrixát! A az 1. városban A a 2. városban A a 3. városban A a 4. városban B az 1. városban 60 72 68 64 B a 2. városban 48 60 64 56 B a 3. városban 52 56 60 48 B a 4. városban 56 64 72 60 b. (10 p) Határozzuk meg az optimális stratégiákat, és a játék értékét! Mindkét vállalat a 3. városban nyit üzletet Az A vállalaté a forgalom

60%-a 3. (18 pont) Egy vállalatnál 5 új munkatársat kell betanítani 5 feladat végzésére (mindegyik munkatársat pontosan egy feladatra tanítják be). A betanítási idők (órában) a következők: 28 7 19 15 25 22 22 14 3 4 23 21 9 19 8 17 20 24 12 15 23 23 6 8 1 3 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu a. (10 pont) Határozzuk meg a Magyar módszerrel a minimális összidőt eredményező hozzárendelést, és a minimális összidő értékét! -a1- Adjuk meg az előbb a sorok, majd az oszlopok redukciójával kapott ekvivalens feladatot! 11 5 6 0 6 11 5 3 0 6 0 15 14 13 16 0 15 11 13 16 13 8 3 18 0 13 8 0 18 0 12 0 16 9 5 12 0 13 9 5 24 3 7 14 0 24 3 4 14 0 -a2- Adjuk meg az algoritmus során kapott utolsó ekvivalens feladatot! 11 5 3 0 6 0 15 11 13 16 13 8 0 18 0 12 0 13 9 5 24 3 4 14 0 Az eredeti feladathoz tartozó minimális összidő: 37 b. (8 pont) Maximálisan

mekkora lehet az összidő növekedése az a) pontban meghatározotthoz képest, ha találomra készítjük el a hozzárendelést? 76 Adjuk meg a lehető legnagyobb összidőt eredményező hozzárendelést is! 28 22 23 17 23 7 22 21 20 23 19 14 9 24 6 15 3 19 12 8 25 4 8 15 1 Maximális összidő: 113 A másik maximális hozzárendelés: 1-5,2-2, a többi uaz. 4. (20 pont) Tekintsük az alábbi irányított élekből és számozott csúcsokból álló gráf által megadott maximális folyam feladatot, amelyben az 1-es csúcs a forrás és a 7-es a nyelő! 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ékét. Tehát például az (1,2) él kapacitása 30 egység, s jelenleg 14 egység folyik át rajta 4 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu 12/10 3 6 24/24 25/10 1 23/14 5/0 5/0 4 7 25/14 2/0 30/14 30/0 2

14/14 5 a. (8 p) Adja meg a lehetséges javítások maximális értékeit az alábbi láncok mentén! (1) 1 2 4 ← 5 7 (javítás 2-vel) (2) 1 3 6 5 7 (javítás 2-vel) (3) 1 4 6 7 (nem lehetséges, mert f67=k67) (4) 1 4 ← 5 7 ( javítás 5-tel) b. (12 p) 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. 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!) (Nem) Ha nem, adja meg az összes olyan láncot, amely mentén a folyam értéke még javítható (a javítás maximális értékével együtt)! 1 2 4 ← 5 7 mentén 2-vel 1 2 4 6 5 7 mentén 2-vel 1 3 6 ← 4 ← 5 7 mentén 2-vel 1 3 6 5 7 mentén 2-vel 5. (20 pont) Az alábbi 10 á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) 5 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu Az a.-e állítások mindegyike a CPM (kritikus út) feladattal kapcsolatos Az (i,j) él által reprezentált tevékenység időtartama tij , az i esemény legkorábbi bekövetkezésének időpontja ET(i), legkésőbbi bekövetkezésének időpontja LT(i). a. Egy kritikus út valamennyi élén a mozgáshatár 0 I b. A tűréshatár nem haladhatja meg a mozgáshatár értékét H c. A mozgáshatár mindig kisebb a tűréshatárnál H d. LT(i) = max (LT(j)-tij ) H (i,j) e. ET(j) = max (ET(i)+tij ) I (i,j) . Egy tiszta egészértékű lineáris minimumfeladat optimumának értékét min-nel, a fellazított (relaxált) feladat optimumát minf-fel jelöljük. f. Van olyan feladat-pár, hogy a

fellazított feladatnak nincs lehetséges megoldása, de az egészértékű feladatnak van. H g. Van olyan feladat-pár, hogy az egészértékű feladatnak nincs lehetséges megoldása, de a fellazított feladatnak van. I h. Van olyan feladat-pár, amelyre minf = min I i. Van olyan feladat-pár, amelyre minf < min I j. Van olyan feladat-pár, amelyre min < minf H 6 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu Operációkutatás vizsga A csoport Budapesti Corvinus Egyetem 2007. január 16 Egyéb gyakorló és vizsgaanyagok találhatók a http://matstat.fwhu honlapon a Letölthető vizsgasorok, segédanyagok OPERÁCIÓKUTATÁS, 2007. január 16 A 12 - 1330 menüpont alatt. NÉV: NEPTUN KÓD: 1. (26 pont) Fát kell szállítani Ajkáról illetve Várpalotáról Taszárra és Szigetvárra A szállításnál mind szárazföldön, mind vizen közbülső szállítási pontok iktathatók

be. Ajka kapacitása 1000 egység hetente, Várpalota kapacitása 900 egység/hét. Taszár igénye 800 egység/hét, Szigetvár igénye 900 egység/hét. Egy egységnyi fa szállítási költségeit az alábbi táblázatok tartalmazzák. Szárazföldön: Vízen Révfülöp Tihany Ajka 7 11 Révfülöp Várpalota 9 8 Tihany Boglár 2 5 Szántód 4 2 Szárazföldön Szárazföldön közvetlenül Taszár Szigetvár Taszár Szigetvár Boglár 7 10 Ajka 26 34 Szántód 10 9 Várpalota 32 31 Más viszonylatban (például Révfülöpről Tihanyba, vagy Ajkáról közvetlenül Boglárra, 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. 1 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu 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. 7 8 9 10 16 Duálvált. Révfülöp Tihany Boglár Szántód Taszár 0 Ajka 800 0 Várpalota 900 -7 Révfülöp 1100 800 -8 Tihany 1000 900 -9 Boglár 1100 800 -10 Szántód 1000 19 0 Szigetvár Fiktív 200 0 900 b.(8 pont) Tekintsük azt az optimális megoldást, amelyben Várpalotáról Tihanyba 700 egység fát stállítanak, és Várpalotáról 200 egység a Fiktív szállítás. Mennyit szállítanak ekkor a következő szakaszokon? Ajka-Révfülöp 1000 egységet Révfülöp-Boglár 1000 egységet Tihany Szántód 700 egységet Szántód-Szigetvár 700 egységet c.(4+4 pont) Az eredeti optimális megoldásban 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? Miért? 2 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu Tihany – Boglár hamis (A Várpalota-Fiktív redukált költség 0 marad, és ez a bázissal olyan hurkot alkot, amin lehet javítani) Szántód – Taszár hamis (A Várpalota-Fiktív redukált költség 0 marad, és ez a bázissal olyan hurkot alkot, amin lehet javítani.) 2.(20 pont) Az alábbi projekt hálózatban az élek tevékenységeket jelölnek, az élek mellé írt számok a tevékenységek időtartamát napokban. Egy csúcs azt az eseményt jelöli, hogy a hozzá befutó élekkel jelzett tevékenységek befejeződtek és egyben a belőle kiinduló élekkel jelzett tevékenységek elkezdődhetnek.A projekt kezdetét az A csúcs, befejezését a B csúcs

képviseli A projekt július 1-én reggel kezdődik. Munkaszüneti nap nincs (Július és Augusztus 31 naposak) 5 12 7 A 6 2 1 10 9 13 11 5 3 6 4 8 7 B a. (4 pont) Mi a projekt legkorábbi befejezési dátuma? Augusztus 5 b. (2 pont) Mi a kritikus út? (A,1) –(1,2) – (2,5) – (5,B) c. (4 pont) Mi az a legkorábbi dátum, amikor a 4-es csúccsal jelzett esemény bekövetkezhet? Július 11 5-ös csúccsal jelzett esemény bekövetkezhet? Július 23 d. (4 pont) Mi az a legkésőbbi dátum, amikor a projekt befejezésének késleltetése nélkül az 1-es csúccsal jelzett esemény bekövetkezhet? Július 6 Mi az a legkésőbbi dátum, amikor a projekt befejezésének késleltetése nélkül a 4-es csúccsal jelzett esemény bekövetkezhet? Július 22 3 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu e. (2 pont) Mi az a legkésőbbi dátum, amikor a projekt befejezésének késleltetése

nélkül elkezdődhet az (1,2) éllel jelzett tevékenység? Július 6 f. (4 pont) Hány nappal tolódhat el az (1,3) éllel jelzett tevékenység elkezdése - a többi tevékenység elkezdésének és a projekt befejezésének késleltetése nélkül - a legkorábbi kezdési dátumtól? 8 nap 3. (20 pont) Három gép (G1, G2 és G3) háromféle termék (T1, T2, T3) 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 35, 45 és 55 gépóra/hét, az egyes termékekből a hetente minimálisan előállítandó mennyiség rendre 30, 16, és 14 darab. Egy termék darabjának gyártási költsége az egyes gépeken az alábbi táblázatban látható: G1 G2 G3 T1 4 4 6 T2 5 5 4 T3 3 5 7 Jelölje xjk a j-edik gépen a k-adik termékből hetente gyártandó mennyiséget darabban, j= 1,2,3; k=1,2,3. a) (4 pont) Írjuk fel a célfüggvényt, ha a heti összköltséget szeretnénk minimalizálni. 4x11

+5x12 +3x13 +4x21 +5x22 +5 x23 +6x31 +4x32 +7x33 b) (4 pont) Írjuk fel azokat a feltételeket, amelyek a gépek heti kapacitásának korlátozottságát fejezik ki. x11 + x12 + x13 ≤ 35 x21 + x22 + x23 ≤ 45 x31 + x32 + x33 ≤ 55 c. (6 pont) Jelölje y1 , y2 , y3 ≥0 a gépek ki nem használt kapacitását! y1 = 35-(x11 + x12 + x13 ) y2 = 45-( x21 + x22 + x23 ) y3 = 55-(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 ≤ 35v1, y2 ≤ 45v2, y3 ≤ 55v3, v1+ v2+ v3 ≤ 1 4 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu d. (6 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 75% legyen. Az u nulla-egy változóval: y1-8,75<=M (1-u) 35-y1≤ Mu 4. (24 pont) X és Y a következő játékot játsszák Piros illetve kék golyók közül X kiválaszt egyet úgy, hogy azt Y ne lássa. Ez után Y megtippeli, hogy X milyen színű golyót választott ki Ha eltalálja, hogy pirosat, akkor kap X-től 1 Ft-t. Ha eltalálja, hogy kéket, akkor kap X-től 3 Ftt Ha viszont nem találja el a kiválasztott golyó színét, akkor ő fizet X-nek 2 Ft-t a. (4 pont) Adja meg a játékosok (tiszta) stratégiáit és a kifizető mátrixot az X szempontjából választ tippel piros kék piros -1 2 kék 2 -3 b. (2 pont) Redukálható-e a játék dominált stratégiák elhagyásával? (nem) c. (4 pont) Van-e a játéknak nyeregpontja (tiszta stratégiákban)? (nincs) Miért? Max sormin=-1 < 2 = min oszlopmax d. (6 pont)

Mi a sorjátékos optimális stratégiája? ((5/8 , 3/8)) e. (6 pont) Mi az oszlopjátékos optimális stratégiája? ((5/8 , 3/8)) f. (1 pont) Mennyi a játék értéke? (v= 1/8) g. (1 pont) Igazságos-e a játék? (nem) 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) Tekintsünk egy M/M/s típusú sorbanállási feladatot a szokásos jelölésekkel. Tehát: λ = Beérkezések átlagos száma (időegységenként) = Beérkezési gyakoriság µ = Kiszolgálások átlagos száma (időegységenként) = Kiszolgálási gyakoriság s = kiszolgáló helyek száma. ρ =a rendszer kihasználtsági foka L = A rendszerben tartózkodó ügyfelek átlagos száma Lq = A sorbanálló ügyfelek átlagos száma W = Az ügyfél által átlagosan a rendszerben töltött idő Wq = Az ügyfél által sorbanállással átlagosan

eltöltött idő P(j>=s)=annak a valószínűsége, hogy a rendszerben lévő ügyfelek száma eléri a kiszolgálóhelyek számát. (1) Lq =P(j>=s) ρ/(1-ρ) I (2) Ha s=1, akkor Lq = ρ2/(1-ρ) I 5 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu (3) Minden s-re W=Wq+ ρ H (4) Minden s-re W=Wq+ 1/µ I (5) W= λL H 6 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu Operációkutatás vizsga B csoport Budapesti Corvinus Egyetem 2007. január 16 Egyéb gyakorló és vizsgaanyagok találhatók a http://matstat.fwhu honlapon a Letölthető vizsgasorok, segédanyagok OPERÁCIÓKUTATÁS 2007. január 16, 12 - 1330 B menüpont alatt. NÉV: NEPTUN KÓD: 1. (20 pont) Az alábbi projekt hálózatban az élek tevékenységeket jelölnek, az élek mellé írt számok a tevékenységek időtartamát

napokban. Egy csúcs azt az eseményt jelöli, hogy a hozzá befutó élekkel jelzett tevékenységek befejeződtek és egyben a belőle kiinduló élekkel jelzett tevékenységek elkezdődhetnek. A projekt kezdetét az A csúcs, befejezését a B csúcs képviseli A projekt január 1-jén reggel kezdődik. Munkaszüneti nap nincs (Január és március 31 naposak, február 28 napos.) A 11 15 2 1 10 9 23 5 3 10 9 5 4 10 11 B 1 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu a. (4 p) Mi a projekt legkorábbi befejezési dátuma?március 7 b. (2 p) Mi a kritikus út? (A,1) –(1,2) – (2,3) – (3,4) – (4,5) – (5,B) c. (4 p) Mi az a legkorábbi dátum, amikor a 3-as csúccsal jelzett esemény bekövetkezhet? február 5 Mi az a legkorábbi dátum, amikor az 5-ös csúccsal jelzett esemény bekövetkezhet? február 24 d. (4 p) Mi az a legkésőbbi dátum, amikor a projekt befejezésének

késleltetése nélkül a(z) 2-es csúccsal jelzett esemény bekövetkezhet? Január 26 5-ös csúccsal jelzett eseménybekövetkezhet? február 24 e. (2 p) Mi az a legkésőbbi dátum, amikor a projekt befejezésének késleltetése nélkül elkezdődhet az (1,2) éllel jelzett tevékenység? Január 12 f. (4 p) Hány nappal tolódhat el az (1,4) éllel jelzett tevékenység elkezdése a legkorábbi kezdési dátumától anélkül, hogy ez késleltetné bármelyik másik tevékenység legkorábbi elkezdését? 26 nap 2. (20 pont) Három gép (G1, G2 és G3) mindegyike háromféle termék (T1, T2, T3) bármelyikét képes előállítani. Az egyes gépeken egy óra alatt bármelyik termékből egy darab készíthető el A gépek kapacitása rendre 45, 55 és 65 gépóra/hét, az egyes termékekből a hetente minimálisan előállítandó mennyiség rendre 40, 26, és 24 darab. Egy termék darabjának gyártási költsége (euróban) az egyes gépeken az alábbi táblázatban látható:

T1 T2 T3 G1 9 8 7 G2 6 5 4 G3 7 8 9 Jelölje xjk a j-edik gépen a k-adik termékből hetente gyártandó mennyiséget darabban, j= 1,2,3; k=1,2,3. a. (4 p) Írjuk fel a célfüggvényt, ha a heti összköltséget szeretnénk minimalizálni 9x11 +8x12 +7x13 +6x21 +5x22 +4x23 +7x31 +8x32 +9x33 b. (4 p) Írjuk fel azokat a feltételeket, amelyek az egyes termékekből hetente minimálisan előállítandó mennyiségekre vonatkoznak. x11 + x21 + x31 ≥ 40 x12 + x22 + x32 ≥ 26 x13 + x23 + x33 ≥ 24 c. (6 p) Jelölje y1 , y2 , y3 a gépek ki nem használt kapacitását! Azaz legyen y1 , y2 , y3 ≥ 0 és y1 = 45-(x11 + x12 + x13 ) y2 = 55-( x21 + x22 + x23 ) 2 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu y3 = 65-(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 az egyik 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 ≤ 45v1, y2 ≤ 55v2, y3 ≤ 65v3, v1+ v2+ v3 ≤ 2 d. (6 p) Írjon fel olyan lineáris egyenlőtlenségeket, amelyek azt a követelményt fejezik ki, hogy ha a harmadik gépet foglalkoztatjuk (legalább egy terméket gyártunk rajta), akkor a kapacitásának a kihasználtsága legalább 60% legyen. Az u nulla-egy változóval: y3 -26≤ M(1-u) (mert 26=0.4*65, s aki nem használtság legfeljebb 40%) 65-y3 ≤ Mu 3. (26 pont) Fát kell szállítani Taszárról illetve Szigetvárról Ajkára és Várpalotára A szállítás esetleg átrakodási pontok közbeiktatásával, és esetleg bizonyos szakaszokon vízen történhet. Taszár kapacitása 120 tonna hetente, Szigetvár kapacitása 80 tonna/hét. Ajka igénye 130 tonna/hét, Várpalota igénye 70 tonna/hét. Egy tonna fa szállítási költségét az egyes

viszonylatokban az alábbi táblázatok tartalmazzák. Szárazföldön: Vízen Boglár Szántód Révfülöp Tihany Taszár 14 19 Boglár 5 8 Szigetvár 21 15 Szántód 8 5 Szárazföldön Szárazföldön közvetlenül Ajka Várpalota Ajka Várpalota Révfülöp 15 20 Taszár 50 70 Tihany 18 16 Szigetvár 68 60 Más viszonylatokat (például Révfülöpről Tihanyba, vagy Taszárról közvetlenül Tihanyba, stb.) kizárunk, mert ott a szállítás vagy nem lehetséges, vagy borzasztóan költséges. Optimális (minimális költségű) szállítási tervet kell készíteni. a. (10 p) 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! (A ki nem töltött cellákat a javításnál M-nek értelmezzük, azokat nem szükséges beírni.) 3 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20)

932-2134 http://matstat.fwhu email: matstat@fw.hu 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 Duálvált. Boglár Szántód Révfülöp Tihany Ajka 0 Taszár 120 4 Szigetvár 80 -14 Boglár 80 120 -11 Szántód 120 80 -19 Révfülöp 80 120 -16 Tihany 120 10 32 Várpalota 70 b. (8 p) Tekintsük azt az optimális megoldást, amelyben Szántódról Révfülöpre10 tonna, míg Szántódról Tihanyba 70 tonna fát szállítanak. Mennyit szállítanak ekkor a következő szakaszokon? Boglárról Révfülöpre 120 tonnát, Révfülöpről Tihanyba 0 tonnát, Révfülöpről Ajkára 130 tonnát, Tihanyból Várpalotára 70 tonnát. c. (4+4 p) Az eredeti optimális megoldásban igaz-e vagy sem, hogy ha az adott alábbi 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?

Miért? Szántód – Révfülöp igaz , mert csak itt 0 redukált költség, és ez is pozitív lesz Boglár – Tihany hamis , mert a fenti redukált költség 0 marad és az optimális megoldás nemdegenerált. 4 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu 4. (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) Tekintsünk egy M/M/s típusú sorbanállási feladatot a szokásos jelölésekkel. Tehát: λ = Beérkezések átlagos száma (időegységenként) = Beérkezési gyakoriság µ = Kiszolgálások átlagos száma (időegységenként) = Kiszolgálási gyakoriság s = kiszolgáló helyek száma ρ = a rendszer kihasználtsági foka L = A rendszerben tartózkodó ügyfelek átlagos száma Lq = A sorbanálló ügyfelek átlagos

száma W = Az ügyfél által átlagosan a rendszerben töltött idő P(j≥s)=annak a valószínűsége, hogy a rendszerben lévő ügyfelek száma eléri a kiszolgálóhelyek számát. (1) Lq = P(j≥s)/(1-ρ) H (2) Ha s=1, akkor Lq = ρ/(1-ρ) H (3) Minden s-re L = Lq + ρλ (4) Minden s-re L = Lq + λ/µ I (5) L = λW I H 5. (24 p) Ali és Bea a következő játékot játsszák Ali betesz egy üveggolyót a bal vagy a jobb zsebébe úgy, hogy azt Bea ne lássa. Ez után Bea megtippeli, hogy Ali melyik zsebébe tette az üveggolyót. Ha eltalálja, hogy a balba, akkor kap Alitól 2 eurót. Ha eltalálja, hogy a jobba, akkor kap Alitól 4 eurót. Ha viszont nem találja el, hogy melyik zsebbe került a golyó, akkor ő fizet Alinak 3 eurót. a. (4 p) Adja meg a játékosok (tiszta) stratégiáit és a kifizető mátrixot Ali szempontjából A zseb B tipp bal jobb bal -2 3 jobb 3 -4 b. (2 p) Redukálható-e a játék dominált stratégiák elhagyásával? (nem) c. (4 p)

Van-e a játéknak nyeregpontja (tiszta stratégiákban)? (nincs) Miért? maxmin = -2 < 3 = minmax d. (6 p) Mi a sorjátékos (Ali) optimális stratégiája? (058 , 042) = (7/12 , 5/12) 5 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu e. (6 p) Mi az oszlopjátékos (Bea) optimális stratégiája? (058 , 042) = (7/12 , 5/12) f. (1 p) Mennyi a játék értéke? (v= 008 = 1/12) g. (1 p) Igazságos-e a játék? (nem) 6 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu Operációkutatás vizsga A csoport Budapesti Corvinus Egyetem 2007. január 23 Egyéb gyakorló és vizsgaanyagok találhatók a http://matstat.fwhu honlapon a Letölthető vizsgasorok, segédanyagok menüpont alatt. 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 0/1 4/7 F 4 4/4 2 0/4 4/4 7/9 Ny 7 0/1 0/5 4/6 3 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) 1 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu 3/3 1 4 3/5 4/4 0/1 7/7 F 2 0/4 4/4 8/9 Ny 7 1/1 3/5 6/6 3 5 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. 2 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu 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 L 3 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134

http://matstat.fwhu email: matstat@fw.hu Költség 680 281 342,7 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 TVstú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)=0395 4 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu 2: 0 5: 3 Nem Siker 0.7 3 Igen 1 1.5 1.59 Piackut Bukás: 0.3 Igen 13: 3 9 2.63 Bukás. 74% 14: -2 7 Poz.605% 4 Siker92.6% 6: -2 2.63 1.59 10: 0 Nem Igen 1 Neg.395% 8 Siker.354% . -0.23 Bukás646% 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? 159 d. (5 pont) Mennyit érdemes fizetni a piackutató cégnek az előrejelzésért? (<009) 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 5 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu 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 6 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu Operációkutatás vizsga B csoport Budapesti Corvinus Egyetem 2007. január 23 Egyéb gyakorló és vizsgaanyagok találhatók a http://matstat.fwhu honlapon a Letölthető vizsgasorok, segédanyagok OPERÁCIÓKUTATÁS 2007. január 23, 1200 - 1330 B menüpont alatt. 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 TVstú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)=041 1 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu 2: 0 Nem 5: 4 Siker 60% 3 Igen 1 1.2 1.798 Piackut Siker86.4% 6: -3 Bukás 40% 9 3.05 Poz.59% 4 Igen Bukás13.6% 14: -3 7 10: 0 Nem 3.05 1.798 Igen Neg.41% 13: 4 Siker22%. 8 0 15: 4 1 -1.46 Nem 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?

1798 d. (5 p) Mennyit érdemes fizetni a piackutató cégnek az előrejelzésért? (<0598) 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 . 2 Matematika, statisztika, közgazdaságtan, pénzügytan

korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu 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 = 2 0,643 0,75 1,93 3 0,237 0,5 0,237 4 0,075 0,375 0,045 L 3,43 1,737 1,545 W = 0,057 0,029 0,026 Költség = 285,8 224,2 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éjevé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 3 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu 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 7 0/2 2/5 9/13 3 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: Útvonal (lánc) F – 2 - 5 – Ny F – 2 – 4 – 5 – Ny F – 1 – 2 – 4 - Ny Például A javítás értéke 3 1 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 Ny 7 1/2 5/5 13/13 3 5 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)} 4 Matematika, statisztika, közgazdaságtan, pénzügytan korrepetálás. Tel.: (20) 932-2134 http://matstat.fwhu email: matstat@fw.hu 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 x b. (2 p) Az összköltség minimuma: 24 5