Gazdasági Ismeretek | Operációkutatás » Operációkutatás vizsgakérdések és válaszok

BMF Keleti Károly Gazdasági Főiskolai Kar OPERACIÓKUTATÁS OPERÁCIÓ KUTATÁS VIZSGAKÉRDÉSEK MŰSZAKI MENEDZSER SZAK II. ÉVFOLYAM I FÉLÉV Készítette: Papp Károly 1 BMF Keleti Károly Gazdasági Főiskolai Kar TARTALOMJEGYZÉK TARTALOMJEGYZÉK. 2 BEVEZETÉS . 4 1.0 Mivel foglalkozik az operációkutatás? Általában mi a célja? . 4 1.1 Adja meg a gazdasági folyamatok matematikai modelljének folyamatábráját. 4 1.2 Mit értünk analitikus illetve sztochasztikus modellezésen? . 4 1.3 Sorolja fel a döntési modellek három legfontosabb fogalmát, és adja meg a jelentésüket! . 4 MÁTRIXOK GAZDASÁGI ALKALMAZÁSAI. 5 1.4 Mit mutat meg egy n-elemű részesedésvektor, és milyen tulajdonságát ismeri?. 5 1.5 Mire használtuk az s = V*r képletet, ahol az s és r egy-egy részesedésvektor? Magyarázza meg a V mátrix elemeinek jelentését!. 5 1.6 Milyen mátrixművelettel választható ki egy m x n típusú A mátrix valamely sora, illetve

oszlopa? 5 1.7 Mi az összegző vektor? . 5 1.8 Definiálja egy üzem termelésének technológiai mátrixát! . 5 1.9 A T technológiai mátrixon túl milyen vektorokat definiáltunk a termelési összefüggések leírására? Hogyan ellenőrizhetjük ezek segítségével, hogy a program végrehajtható-e, illetve hogyan számítható ki a megvalósítható program nyeresége? . 6 LINEÁRIS PROGRAMOZÁS . 7 1) Mit értünk matematikai programozási feladat alatt?. 7 2) Mit értünk egy matematikai programozási feladat lehetséges illetve optimális megoldása alatt? . 7 3) Írja fel egy n-változós, m db korlátozó feltételt tartalmazó standard lineáris programozási feladat általános alakját. Nevezze meg a döntési változókat, a feltétel rendszert és a célfüggvényt! 7 4) Írja fel a standard lineáris programozási feladat általános alakját mátrixok felhasználásával! . 8 5) A feltételi rendszerben milyen típusú feltételeket különböztetünk

meg?. 8 6) Mi a megoldáshalma az x 1 x 2 síkon szemléltetve az 7) Mikor nevezünk egy standard lineáris programozási feladatot normál feladatnak? . 8 x1  x 2   alakú egyenlőtlenségnek? . 8 8) Hogyan hozhatunk standard formára egy LP feladatot, ha a feltételi rendszerben egyenlőségek is szerepelnek?. 8 9) 10) Írja le a kétváltozós LP-feladat grafikus megoldásának lépéseit!. 8 Milyen lehet egy kétváltozós LP feladat lehetséges megoldásainak halmaza az x 1 x 2 síkon?. 8 Készítette: Papp Károly 2 BMF Keleti Károly Gazdasági Főiskolai Kar 11) Milyen optimális megoldása fordulnak elő egy kétváltozós LP-feladatnak, ha a lehetséges megoldása korlátos, illetve nem korlátos? . 9 12) Egy kétváltozós LP-feladat megoldása során milyen esetben alkalmazható az a módszer, hogy a csúcspontokban kiszámítjuk a célfv értékét, és ezek közül választjuk ki a szélsőértéket? . 9 13) Egy gazdasági hátterű LP feladat

megoldásában, mely korlátozó feltételek adják a szűk keresztmetszetet? . 9 HÁLÓS TERVEZÉSEK . 10 1. Mit nevezünk gráfnak?. 10 2. Mi az irányított gráf?. 10 3. Mikor nevezünk egy gráfot összefüggőnek és egyszerűnek?. 10 4. Mit nevezünk útnak és körnek?. 10 5. Mit nevezünk forrásnak, nyelőnek? . 10 6. A gráf milyen mátrixprezentációját ismeri?. 10 7. A szomszédsági mátrix milyen tulajdonságait lehet megfeleltetni az adott gráf speciális tulajdonságainak? Soroljon fel néhányat! . 10 8. Mit nevezünk hálózatnak? . 10 9. Mit ért program alatt az operációkuta tásban? . 10 10. Mit értünk időütemezés alatt? . 10 11. Milyen módszereket tanult az időütemezés kivitelezésére?. 10 12. Mi az alapvető különbség a CPM és a PERT algoritmusok alkalmazása között? . 10 13. Mi a tevékenységháló?. 11 14. Mit ért esemény alatt? . 11 15. Hogyan számolhatjuk ki az eseményütemezés során az esemény

legkorábbi illetve legkésőbbi időpontját?. 11 16. Mi a kritikus út? . 11 17. Mit ért a tevékenység tartalékidején? . 11 18. Milyen célból alkalmazunk látszattevékenységet? . 11 19. Milyen tevékenységnek egyezhet meg a legkorábbi kezdési ideje és a legkorábbi befejezési ideje?11 20. Milyen eloszlásúnak feltételezzük a tevékenységidőt, mint valószínűségi változót a PERT algoritmusban?. 11 21. Milyen paraméterekkel és hogyan becsüljük a tevékenységidők várható értékét és szórását a PERT algoritmus alkalmazása során? . 11 Készítette: Papp Károly 3 BMF Keleti Károly Gazdasági Főiskolai Kar OPERACIÓKUTATÁS BEVEZETÉS 1.0 Mivel foglalkozik az operációkutatás? Általában mi a célja? Az operációkutatás általában matematikai módszerek alkalmazása legfőképp az iparban; a kereskedelemben; az államigazgatásban stb. Műveletek összehangolására használják. Célja az optimalizálás 1.1 Adja meg a

gazdasági folyamatok matematikai modelljének folyamatábráját. 1. A modellezendő gazdasági folyamat megadása. 2. Az adott gazdasági folyamat elemzése, főbb jellemzők kiválasztása. 3. A közgazdasági modell felállítása 4. Matematikai apparátus kiválasztása (analízis, lineáris algebra, valószínűség számítás stb.) 5. A matematikai modell fel állítás Matematikai eszköz összekapcsolása a közgazdasági modellel 6. A matematikai modell megoldása 7. Az eredmények közgazdasági értelmezése 1.2 Mit értünk analitikus illetve sztochasztikus modellezésen? Analitikus modellezés a közgazdasági modellt elméleti úton elemzi és oldja meg. Ennek fejlettebb változata a szimulációs modellezés, melynél -általában- számítógéppel sokszor lejátsszuk a közgazdasági modellt, ezzel szimulálva a várható végeredményt. A szimuláció során véletlen-szám generátorokkal utánozhatjuk a véletlent. Ezt nevezzük sztochasztikus modellezésnek. 1.3

Sorolja fel a döntési modellek három legfontosabb fogalmát, és adja meg a jelentésüket! A közgazdasági matematikai modellek döntési modellek. Ezek segítenek a döntések meghozatalában, mely modellek legfontosabb fogalmai a követezőek: Döntési változó: ennek értékét a modellel határozzuk meg. A modellben a feltételek összességét feltételrendszernek nevezzük. Ezzel írjuk meg a közgazdasági modellt Célfüggvény, melyet a döntési változókból képezhetünk. Minimalizálás vagy maximalizálás a cél. Készítette: Papp Károly 4 BMF Keleti Károly Gazdasági Főiskolai Kar OPERACIÓKUTATÁS MÁTRIXOK GAZDASÁGI ALKALMAZÁSAI 1.4 Mit mutat meg egy n-elemű részesedésvektor, és milyen tulajdonságát ismeri? A részesedés vektorral a piacon szereplő cégek piaci részesedése adható meg. 0,2 r  0,6 Elemei nem negatívak, és összegük 1. 0,2 1.5 Mire használtuk az s = V*r képletet, ahol az s és r

egy-egy részesedésvektor? Magyarázza meg a V mátrix elemeinek jelentését! 0,85 0,05 0,10  V  0,10 0,55 0,35 0,10 0,15 0,75 0,2 s  V r  0,6 0,2 * A V mátrix a piacon bekövetkezett változást mutatja meg. A v ij elem megmutatja, hogy i-edik cég fogyasztójának hány százaléka pártolt át a j-edik céghez. A következő év eleji részesedést egy másik részesedésvektor adja meg. Ezt úgy kapjuk hogy a változás mátrix (V) transzponáltját megszorozzuk a részesedés vektorral. s = V*r Milyen mátrixművelettel választható ki egy m x n típusú A mátrix valamely sora, illetve oszlopa? Egy m x n típusú Mátrix. Amennyiben ezt jobbról egy e k egységvektorral (oszlopvektorral) szorozzuk, akkor a matrix k-adik oszlopát kapjuk, ha balról el* egységvektorral (sorvektorral)szorozzuk, a l-edik sorát kapjuk eredményül. 1.6 1.7 Mi az összegző vektor? A csupa egyest tartalmazó

egységvektort, összegző vektornak nevezzük. Például: 1.8 1  1 1 1 * 1  és 1  1  1 Definiálja egy üzem termelésének technológiai mátrixát! A termelési mátrix esetében n-féle terméket gyárt a cég (  1 ; 2 ; 3  n ,) m-féle erőforrás (  1 ;  2 ;  3  m , ) igénybevételével. A Tm  n mátrix esetében a t ij eleme jelenti, hogy a  j egységnyi termék előállításához mennyi  i erőforrás felhasználása szükséges. Készítette: Papp Károly 5 BMF Keleti Károly Gazdasági Főiskolai Kar 1.9 OPERACIÓKUTATÁS A T technológiai mátrixon túl milyen vektorokat definiáltunk a termelési összefüggések leírására? Hogyan ellenőrizhetjük ezek segítségével, hogy a program végrehajtható-e, illetve hogyan számítható ki a megvalósítható program nyeresége? Megnevezés Kapacitás vektor Árvektor Vektor jelölése Jele: a Mit definiál? Fajtája az

erőforrásokból rendelkezésre Oszlopvektor / m elem / álló mennyiség Az erőforrások egységára Oszlopvektor / m elem / Programvektor Jele: p* Gyártandó mennyiség egysége Sorvektor / n elem / Egyéb ktsg. Jele: t* Gyártás egyéb ktsg-e Sorvektor / n elem / Piaci ár Jele: c* Eladási ár Sorvektor / n elem / Jele: k A termelési program akkor valósítható meg, ha nem használ föl több erőforrást, mint amennyi rendelkezésre áll. A Tp vektor mutatja meg, a program által felhasznált erőforrás mennyiségét, a k vektor pedig a rendelkezésre álló mennyiséget. Akkor valósítható meg a program, ha: Tp  k vagyis Tp nem lehet elemenként nagyobb k-nál. Megnevezés Kiszámítás Megjegyzés "p" vektor most oszlopvektor! És Program által felhasznált Tp erőforrás mennyiség Tp  k Összes erőforrás ktsg. Egyéb költségek a*Tp Skalár .t*p Skalár Összes költség a*Tp+.t*p Megvalósult program összes c*p

bevétele Nyereség / bevétel-költség / c * p - a Tp  t p  másképp c * -a T - t p Készítette: Papp Károly 6 A c*-aT+t elemei megmutatják az egyes termékek egységenként kapható nyereségét. BMF Keleti Károly Gazdasági Főiskolai Kar OPERACIÓKUTATÁS LINEÁRIS PROGRAMOZÁS 1) Mit értünk matematikai programozási feladat alatt? Amennyiben az optimalizálási probléma során n darab ( x1; x 2 ; ; x n -el jelölt ) döntési változónak olyan feltételi rendszert kell egyenlőtlenségekkel tudunk megadni, akkor beszélünk. kielégíteniük, mely összefüggéseket matematikai programozási feladatokról g 1  x1 ; x 2 ; x n   0 g 2  x1 ; x 2 ; x n   0 g 3  x1 ; x 2 ; x n   0  g m  x1 ; x 2 ; x n   0 feltételek mellett keressük x1 ; x 2 ; x n  R az f  x1 ; x 2 ; x n  célfüggvény szélső értékeit, ahol 2) Mit értünk egy matematikai programozási

feladat lehetséges illetve optimális megoldása alatt?   Programozási feladat egy lehetséges megoldása alatt minden olyan x1; x 2 ; ; x n szám n-es, amely a feltételeket kielégíti. A lehetséges megoldások közül optimális, amelynél a célfüggvénynek maximuma illetve minimuma van. 3) Írja fel egy n-változós, m db korlátozó feltételt tartalmazó standard lineáris programozási feladat általános alakját. Nevezze meg a döntési változókat, a feltétel rendszert és a célfüggvényt! a11 x1  a12 x 2  a13 x3  b1 a 21 x1  a 22 x 2  a 23 x3  b2  Általános alak a m1 x1  a m 2 x 2  a m 3 x3  bm x1 ; x 2 ; x3  0 z  c1 x1  c 2 x 2  c3 x3  max a11 x1  a12 x 2  a13 x3  b1 korlátozó feltételek a 21 x1  a 22 x 2  a 23 x3  b2  a m1 x1  a m 2 x 2  a m 3 x3  bm Nemnegativitási feltétel Célfüggvény z  c1 x1  c2 x2  c3 x3  max Korlátozó + nemnegativitási

feltétel = feltétel rendszer. Készítette: Papp Károly 7 x1 ; x 2 ; x3  0 BMF Keleti Károly Gazdasági Főiskolai Kar OPERACIÓKUTATÁS 4) Írja fel a standard lineáris programozási feladat általános alakját mátrixok felhasználásával!       1  i  m, 1  j  n A  aij , b  bi , x  x j és c  c j Ezen jelölésekkel tehát : Ax  b, x  0, c * x  max 5) A feltételi rendszerben milyen típusú feltételeket különböztetünk meg? Korlátozó és nemnegativitási feltétel 6) Mi a megoldáshalma az x 1 x 2 síkon szemléltetve az x1  x 2   egyenlőtlenségnek? Egy-egy zárt fél síkot alkotnak, mely a határoló egyenest is tartalmazza. alakú 7) Mikor nevezünk egy standard lineáris programozási feladatot normál feladatnak? Amennyiben felteszzük, hogy az általános alakban meghatározott feltételi rendszerben b i 1  i  m konstansok mindegyike nemnegatív. 8)

Hogyan hozhatunk standard formára egy LP feladatot, ha a feltételi rendszerben egyenlőségek is szerepelnek? Két egyenlőtlenséggel lehet az egyenlőséget helyettesíteni. 9) Írja le a kétváltozós LP-feladat grafikus megoldásának lépéseit! a.) Az x 1 x 2 első negyedében felrajzoljuk azokat az egyeneseket, melyek az egyenlőségjellel felírt korlátozó feltételek képei, majd megnézzük, hogy az egyenlőtlenséget az egyenes melyik oldali félsíkja teszi igazzá. b.) Az igazzá tevő oldalt besatírozzuk az egyenes félsíkján c.) Előbbi eljárást minden korlátozó feltételre elvégezzük d.) Mivel minden egyes feltételt ki kell elégítsen a megoldás halmaz, így a fél síkok közös részét besatírozzuk. / lehetséges megoldások halmazát kapjuk meg / e.) A kapott halmaz lehet üres, korlátos sokszög vagy nem korlátos tartomány f.) Mivel LP feladat megenged egyenlőséget is ezért minden esetben zárt lesz a kapott halmaz. g.) Ezek után grafikusan

keressük meg az optimális megoldást h.) A célfüggvény is lineáris z  c1 x1  c2 x 2 így az x 1 x 2 síkon c1 x1  c 2 x 2   egyenes, mely a célfüggvény  -hoz tartozó szintvonala. Ezen értéket változtatva elmozdul a szintvonal párhuzamosan. i.) El kell dönteni, hogy  növelésével merre mozdul el az egyenesünk, ezt be is kell jelölni Felveszünk a szintvonalon kívül eső pont koordinátáját melyet az szintvonal egyenletének bal oldalába helyettesítünk be. 10) Milyen lehet egy kétváltozós LP feladat lehetséges megoldásainak halmaza az x 1 x 2 síkon? Három féle lehetséges megoldás létezik: Egyetlen optimális megoldás: egy csucspontban veszi fel az optimumát Végtelen sok megoldás a célfüggvény egyik szélsőértékét egy szakasz nem korlátos tartomány esetén egy félegyenes mentén veszi fel Nincs optimális megoldás nem létezik optimális program. Készítette: Papp Károly 8 BMF Keleti Károly Gazdasági

Főiskolai Kar OPERACIÓKUTATÁS 11) Milyen optimális megoldása fordulnak elő egy kétváltozós LP-feladatnak, ha a lehetséges megoldása korlátos, illetve nem korlátos? Korlátos:  Egyetlen optimális megoldás van, ez a tartomány valamelyik csúcspontja  Végtelen sok optimális megoldás, s ez a tartomány valamelyik határoló szakaszának pontjai. Nem korlátos  Egyetlen optimális megoldás van, ez a tartomány valamelyik csúcspontja  Végtelen sok optimális megoldás, s ez a tartomány valamelyik határoló szakaszának vagy félegyenesének pontjai.  Nincs megoldás 12) Egy kétváltozós LP-feladat megoldása során milyen esetben alkalmazható az a módszer, hogy a csúcspontokban kiszámítjuk a célfv értékét, és ezek közül választjuk ki a szélsőértéket? Ha a lehetséges megoldások halmaza korlátos tartomány! 13) Egy gazdasági hátterű LP feladat megoldásában, mely korlátozó feltételek adják a szűk keresztmetszetet?

Készítette: Papp Károly 9 BMF Keleti Károly Gazdasági Főiskolai Kar OPERACIÓKUTATÁS HÁLÓS TERVEZÉSEK 1. Mit nevezünk gráfnak? A gráf pontok, csúcsok és szögek halmaza, ahol az élek végpontjai pontok. Egy G(V;E) rendezett pár, ahol V nem üres, véges halmaz, csúcsok halmaza. E pedig az élek halmaza E halmaz tetszőleges eleméhez egyértelműen hozzárendelhető V halmaz egy egy- vagy kételemű részhalmaza. Az e € E élhez rendelt {v 1 ,v 2 } € V esetén azt mondjuk, hogy e a gráf v 1 ,v 2 csúcsait összekötő éle. 2. Mi az irányított gráf? Az irányított gráf olyan gráf, melynek az élei irányítottak. 3. Mikor nevezünk egy gráfot összefüggőnek és egyszerűnek? Egyszerű gráf: amelyben nincs többszörös él és hurok. Összefüggö gráf: bármely két pont között van út. 4. Mit nevezünk útnak és körnek? Út: olyan egymáshoz csatlakozó élek sorozata, amely nem megy át kétszer ugyanazon a ponton Kör: olyan út melynek

kezdő és végpontja megegyezik. 5. Mit nevezünk forrásnak, nyelőnek? Irányított gráfokban értelmezett fogalmak. Forrás: pont, melyből indulhat ki de nem érkezhet be irányított él. Nyelő: olyan pont, melybe érkezik, de nem indul ki irányított él. 6. A gráf milyen mátrixprezentációját ismeri? A szomszédsági mátrixot. Egy n csúcsú gráf szomszédsági mátrixa az a C n x n mátrix, melynek c ij eleme megadja a gráf v i és v j csúcsai között halad élek számát. 7. A szomszédsági mátrix milyen tulajdonságait lehet megfeleltetni az adott gráf speciális tulajdonságainak? Soroljon fel néhányat! 8. Mit nevezünk hálózatnak? A hálózat olyan irányított gráf, melynek éleihez valós számokat rendelünk. 9. Mit ért program alatt az operációkuta tásban? Általában cél eléréséhez szükséges tevékenységek összességét. 10. Mit értünk időütemezés alatt? A tevékenységek kezdési és befejezési időpontjainak az

időkihasználás optimalizálása . érdekében tett megtervezését. 11. Milyen módszereket tanult az időütemezés kivitelezésére? CPM „kritikus űt” algoritmussal kifejezett PERT a tevékenységi időket valószínűségi változóknak tekintjük. 12. Mi az alapvető különbség a CPM és a PERT algoritmusok alkalmazása között? „kritikus űt” algoritmussal kifejezett CPM PERT a tevékenységi időket valószínűségi változóknak tekintjük. Készítette: Papp Károly 10 BMF Keleti Károly Gazdasági Főiskolai Kar OPERACIÓKUTATÁS 13. Mi a tevékenységháló? Egy program hálózattal való reprezentálása, ahol az élek a tevékenységeknek felelnek meg, az élekhez rendelt valós számok a tevékenységekhez szükséges idők, a csúcsok a tevékenységek kezdetei és végei azaz az események. 14. Mit ért esemény alatt? Azt értjük, hogy minden olyan tevékenység befejeződött, melynek nyila ebbe a csúcsba fut. 15. Hogyan számolhatjuk ki az

eseményütemezés során az esemény legkorábbi illetve legkésőbbi időpontját? 16. Mi a kritikus út? Egy olyan irányított út a hálóban , melynek pontjaihoz számított két érték ( a legkorábbi és legkésőbbi időpont ) megegyezik, és a két egymás követő esemény időpontjainak különbsége éppen a köztük húzódó tevékenység ideje. Ezen tevékenységek mentén bármi féle késés az egész program csúszását okozhatja. 17. Mit ért a tevékenység tartalékidején? Megmutatja, hogy legfeljebb mennyit lehet csúszni az adott tevékenységgel, hogy a program ne csússzon. A kritikus út élei mentén ez az idő 0! 18. Milyen célból alkalmazunk látszattevékenységet? 19. Milyen tevékenységnek egyezhet meg a legkorábbi kezdési ideje és a legkorábbi befejezési ideje? 20. Milyen eloszlásúnak feltételezzük a tevékenységidőt, mint valószínűségi változót a PERT algoritmusban? 21. Milyen paraméterekkel és hogyan becsüljük a

tevékenységidők várható értékét és szórását a PERT algoritmus alkalmazása során? Készítette: Papp Károly 11 BMF Keleti Károly Gazdasági Főiskolai Kar OPERACIÓKUTATÁS CPM rövidítések Jel ti ˆt i Jelentése, értelmezése Adott esemény legkorábbi időpontja Adott esemény legkésőbbi időpontja TÁBLÁZATOS FELÍRÁSA CPM MÓDSZER SZERINT Tevékenység X: i - j Tevékenység idő t ij Legkorábbi Kezdési idő ti Legkésőbbi kezdési idő ˆt i - t j A: 0-1 B: 0-3 Stb Készítette: Papp Károly 12 Legkorábbi bejefezési idő t i + t ij Legkésőbbi befejezési idő ˆt j Teljes tartalék Idő ˆt i - t ij - t i