Gazdasági Ismeretek | Operációkutatás » Operációkutatás vizsgafeladatok megoldással, 2003

Operációkutatás vizsgadolgozat megoldásokkal 2003. december 19 Operációkutatás vizsgadolgozat 2003. december 19 Feladatok és megoldások 1. Adott az alábbi LP feladat: x1 + x2 − x3 ≤ 40 x1 – x2 + x3 = 60 x2 − x3 ≥ 30 x1, x2, x3 ≥ 0 z = x1 + 2x2 + x3 max a) Oldja meg a feladatot primál szimplex módszerrel! b) Az előző kérdésre adott válasz alapján mit állíthatunk a duál feladatról? (A duál feladatot nem kell megoldani!) (5) (3) Megoldások. a) A primál feladatnak nincs megengedett megoldása. Az első fázisban a másodlagos célfüggvény pozitív elemei felett választunk pivot elemet. Két transzformáció után a másodlagos célfüggvény sorában nincs pozitív elem, de még van pozitív értékű mesterséges eltérésváltozó a bázisváltozók között. b) Két eset lehetséges: vagy a duál feladatnak sincs megengedett megoldása vagy célfüggvénye alulról nem korlátos. 2. Egy kohászati üzem 100 tonna acél legyártására

kapott megrendelést, 2000 Ft tonnánkénti áron A leszállítandó mennyiségben legalább 3,5 tonna nikkelnek, legfeljebb 2,5 tonna szénnek és pontosan 4,5 tonna mangánnak kell lenni. A kívánt acélt négy ötvözetbõl állítják elõ, amelyeknek összetétele az alábbi: nikkel (%) szén (%) mangán (%) ár (Ft/t) 1 6 3 8 1 200 Őtvözetek 2 3 3 2 2 5 2 2 1 000 800 4 1 6 1 600 LINDO-val meghatározták, hogy hány tonnát kell felhasználni az egyes ötvözetekbõl ahhoz, hogy a nyereség maximális legyen. (A 2)-4) feltételeket úgy kapták, hogy a felírt feltételeket 100-zal megszorozták!) MAX 800 X1 + 1000 X2 + 1200 X3 + 1400 X4 SUBJECT TO 2) 6 X1 + 3 X2 + 2 X3 + X4 >= 350 3) 3 X1 + 2 X2 + 5 X3 + 6 X4 <= 250 4) 8 X1 + 2 X2 + 2 X3 + X4 = 450 5) X1 + X2 + X3 + X4 = 100 END OBJECTIVE FUNCTION VALUE 92400.00 VARIABLE VALUE REDUCED COST X1 42.000000 0.000000 X2 56.000000 0.000000 X3 0.000000 64.000000 X4 2.000000 0.000000 1 Operációkutatás vizsgadolgozat

megoldásokkal ROW 2) 3) 4) 5) 2003. december 19 SLACK OR SURPLUS DUAL PRICES 72.000000 0.000000 0.000000 88.000000 0.000000 -48.000000 0.000000 920.000000 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 800.000000 INFINITY 533.333435 X2 1000.000000 314285706 400000092 X3 1200.000000 64.000000 INFINITY X4 1400.000000 INFINITY 88.888901 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 350.000000 72.000000 INFINITY 3 250.000000 199.999985 8.333334 4 450.000000 50.000000 128.571426 5 100.000000 5.000000 27.692308 a) b) c) d) e) Hány tonna nikkel lesz a 100 tonna acélban? Hogyan változna a nyereség, ha a 3. ötvö zetből is felhasználnának 1 tonnát? Degenerált-e az optimális bázismegoldás? Mennyi lenne a maximális nyereség, ha 3 tonna szenet tartalmazhatna a 100 tonna acél? Kellene-e változtatni az acél összetételén, ha a 3. ötvözet tonnánként csak 700

Ft-ba kerülne? (2-2) Megoldások. a) 3,5 + 0,72 = 4,22. b) 64 forinttal csökkenne. c) Nem. d) 92 400 + 50×88 = 92 400 + 4400 = 96 800. e) Igen, mivel ebben az esetben x3 célegyütthatója 1200-ról 1300-ra nőne, azonban a megengedett növekedés csak 64. 3. Egy termék iránt a kereslet a következő 3 hónapban 40, 60 és 60 darab A szokásos munkaidőben havonta 45, 50 és 50 db-ot tudnak előállítani, továbbá havonta legfeljebb 10 db-ot túlórában. A termelési költségek az egyes hónapokban rendre 3000, 3200 és 4000 Ft/db, míg túlórában 4000, 4300 és 5000 Ft/db. A fajlagos készletezési költség havonta a normál termelési költség 10%-a A cél a kereslet kielégítése minimális költséggel. a) Írjon fel LP feladatot a probléma megoldására! (6) b) Írjon fel ILP feladatot a probléma megoldására, ha a termelés beindítását minden hónapban 100 ezer forint fix költség terheli! (3) Megoldások. Javasolom az Opkut Vizsgafeladatok file 5.1

feladata megoldásának áttanulmányozását 4. Adott az alábbi kvadratikus programozási feladat: 2x1 + 3x2 ≤ 18 x1 + x2 ≤ 7 x1, x2 ≥ 0 z = ( x1 − 2) 2 + ( x2 − 3) 2 max 2 Operációkutatás vizsgadolgozat megoldásokkal 2003. december 19 a) A K-T feltételek felhasználásával döntse el, hogy x = [3, 4] lehet-e lokális optimumhelye a feladatnak! (6) b) Grafikus módszerrel határozza meg a globális optimumhelyet! (3) Megoldások. a) A KT feltételek 2. csoportja alapján kapjuk, hogy λ1 = 0 és λ2 = 2 Mivel a KT feltételek szerint a Lagrange multiplikátoroknak nemnegatívaknak kell lenni, így az adott megoldás jelölt arra, hogy lokális optimumhely legyen. Megjegyzések: 1. A grafikus megoldásból látszik, hogy a [3, 4] pont nem lokális optimumhely, mivel a második feltételen a [7, 0] pont irányában elmozdulva a célfüggvényérték szigorúan nő. 2. Az adott feladat megengedett megoldásainak halmaza minden pontban reguláris Ekkor a KT

feltételek teljesülése a lokális optimumhelynek szükséges feltétele. Ez azt jelenti, hogy minden lokális optimumhelyhez vannak olyan Lagrange multiplikátorok, amelyek kielégítik a KT feltételeket. Ha egy megoldás nem elégíti ki a KT feltételeket, akkor nem lokális optimumhely. A KT feltételeket kielégítő pontok között lehetnek olyanok, amelyek nem lokális optimumhelyek, mivel a KT feltételek teljesülése a lokális optimumnak nem elegendő feltétele. Lokális optimumhelyre elegendő feltételt csak feltétel nélküli és egyenlőség feltételes feladatokra láttak a Hesse mátrix segítségével. b) A nívóvonalak [2, 3] középpontú koncentrikus körök. Nagyobb sugarú körön nagyobb a célfüggvény értéke. A második feltételt egy kör a [3, 4] pontban érinti A globális optimumhely a [7, 0] pont. E ponton halad át a legnagyobb olyan kör, amely belemetsz a megengedett megoldások halmazába. 5. Egy ILP feladat és LP lazításának optimális

táblája a következõ: 3x1− 2x2 5x1+ 4x2 2x1+ x2 x1, x2 ≥ 0, ≤ 3 ≥ 10 ≤ 5 egész z = 3x1− x2 max u1 u3 x1 u2 x2 1/7 − 3/7 − 2/7 2/7 22/7 3/7 13/7 31/7 9/7 −z − 5/7 − 3/7 − 30/7 a) Csatolja az x2 sorából készített Gomory metszést a táblához és válasszon pivot elemet! (4) b) Melyek Gomory metsző feltételének legfontosabb tulajdonságai? (3) Megoldások. a) u1 1/7 x1 u2 − 3/7 x2 − 2/7 s1 − 5/7 − z − 5/7 u3 2/7 22/7 3/7 − 3/7 − 3/7 13/7 31/7 9/7 − 2/7 − 30/7 s1 sorában mindkét elem válaszható pivot elemnek. b) Az LP lazítás optimális megoldása nem elégíti ki a metsző feltételt, a kitűzött ILP feladat egészértékű megoldásai azonban igen. 3 Operációkutatás vizsgadolgozat megoldásokkal 2003. december 19 6. Oldja meg az alábbi hátizsák feladatot dinamikus programozással! Számítsa ki a táblázat elemeit és határozza meg a változók optimális értékét! 3x1 + 5x2 + 2x3 + 6x4 ≤ 8 xj

≥ 0, egész z = 5x1 + 7x2 + 3x3 + 8x4 max (7) Megoldás. F4(y) F3(y) F2(y) F1(y) 0 0 0 0 1 0 0 0 2 0 3 3 3 0 3 3 4 0 6 6 5 0 6 7 6 8 9 9 7 8 9 10 8 8 12 12 13 Az utolsó lépés: max {12, 5+7, 2×5+3} = 13. Az optimális megoldás: x1 = 2, x2 = 0, x3 = 1, x4 = 0. 4 Operációkutatás vizsgadolgozat megoldásokkal 2003. december 19 Operációkutatás vizsgadolgozat 2003. december 30 B Feladatok és megoldások 1. Adott az alábbi LP feladat, megoldása LINDO-val és a megengedett megoldások halmaza MAX 12 ST 9 X1 + 3 X1 + END SUB X1 X1 + 11 X2 + 14 X3 4 X2 + 12 X3 <= 72 4 X2 + 6 X3 <= 48 2 OBJECTIVE FUNCTION VALUE VARIABLE X1 X2 VALUE 2.000000 10.500000 X3 ROW 2) 3) SLACK OR SURPLUS 12.000000 0.000000 1) 139.5000 REDUCED COST -3.750000 0.000000 0.000000 2.500000 DUAL PRICES 0.000000 2.750000 x3 [0, 0, 6 ] [0, 6, 4] [2, 0, 4,5] [2, 7,5 , 2] [0, 12, 0] x2 x1 a) b) c) d) [2, 0, 0] [2, 10,5 , 0] Értelmezze az x3 változó redukált

költségét! Értelmezze az x1 változó redukált költségét! Mit jelent a SUB X1 2 parancs és miért célszerű a használata? Rajzolja be a leghosszabb utat, amely mentén a szimplex módszer alkalmazásával az optimális pontba eljuthatunk! (2-2) Megoldások. a) Legalább 2,5-del kell javítani (növelni, mert maximum a cél) az x3 változó célegyütthatóját, hogy x3 bázisváltozó lehessen egy optimális megoldásban. A másik értelmezés szerint az optimális célfüggvényérték 2,5-del romlana (csökkenne), ha x3 értékét 1-gyel növelnénk, azaza a feltételrendszerhez csatolnánk az x3 ≥ 1 feltételt. b) A redukált költség (degenerációmentes esetben!) megmutatja, hogy mennyivel kell javítani a változó célegyütthatóját, hogy egy optimális megoldásban bázisváltozó lehessen. 5 Operációkutatás vizsgadolgozat megoldásokkal 2003. december 19 Az x1 változó az optimális megoldásban nem bázisváltozó. Ha egy változó szigorúan a

korlátai közötti értéket vesz fel, akkor bázisváltozó. Degeneráció esetén vannak korlátjuk értékén szereplő bázisváltozók is. Most az optimális megoldás nem degenerált (Ha a változókra csak nemnegativitás va kikötve, akkor a pozitív értékűek a bázisváltozók, továbbá degeneráció esetén bizonyos nulla értékűek.) Legalább −3,75-tel kellene javítani, azaz legalább 3,75-tel kellene rontani (csökkenteni, mivel a maximumot keressük) x1 célegyütthatóját, hogy egy optimális megoldásban bázisváltozó legyen, azaz szigorúan a korlátai közötti értéket vegye fel. c) A SUB X1 2 parancs azt jelenti, hogy x1 ≤ 2. Előnye, hogy a LINDO ekkor az x1 ≤ 2 egyedi felső korlátot nem tekinti feltételnek és így naygobb méretű feladatokat is megoldhatunk. Az egyedi korlátok kezelhetők a szimplex tábla méretének növelése nélkül is. (A tankönyben megtalálható hogyan, de ez nem tananyag.) E parancs használatakor az x1 ≤ 2

feltétel duál ára ellentett előjellel a változó redukált költségeként jelenik meg. Ha a parancs helyett az x1 ≤ 2 feltételt írjuk a modellbe, akkor duál ára 3,75 lesz. Ha a korlátot 1-gyel növelnénk, akkor az optimális célfüggvényérték 3,75-tel nőne. d) A leghosszabb út itt azt jelenti, hogy a legtöbb csúcsponton megy át. A szimplex módszer esetén az ábrán látható konvex poliéder egy csúcspontjából egy szomszédos és legalább olyan jó célfüggvényértékű pontra ugrunk. A megoldáshoz ki kell számolni a csúcspontokhoz tartozó célfüggvényértékeket. Az origóból indulunk és a [2; 10,5; 0] optimális pontba érkezünk Három olyan útvonal van, amely a fentieken kívül még három csúcspontot tartalmaz. 2. Döntse el az alábbi állításokról, hogy igazak-e vagy hamisak és indokolja meg állítását! (Hivatkozzon tételekre, készítsen egyszerű példát, stb.) a) Ha egy LP feladat duálja normál feladat, akkor megoldható

duál szimplex algoritmussal. (4) b) Egy klasszikus szállítási feladat duáljának mindig van megengedett megoldása. (3) Megoldások. a) Igaz. Tekintsük az alábbi primál-duál feladatpárt, ahol a baloldali normál feladat Ax ≤ b (b ≥ o) yA ≥ c x≥o y≥o z = cx max w = yb min A jobboldali feladat megoldható duál szimplex algoritmussal, mivel minimumfeladat alakban nincs negatív célegyütthatója. (Mivel a célfüggvényt maximum alakban írjuk a táblába, így a célsorban nem lesz pozitív szám.) b) Igaz. A klaszikus szállítási feladatnak mindig van optimális megoldása A LP dualitási tétele szerint, ha egy feladatnak van optimális megoldása, akkor a duál párjának is van. Ha a duálnak van optimális megoldása, akkor van megengedett megoldása is. 3. Egy vállalat 10 millió forintot szándékozik reklámra költeni Egy órányi reklám a televízióban 3 millió forintba, a rádióban 1 millió forintba kerül. Ha x órát reklámoznak a

televízióban és y órát a rádióban, akkor bevételük az alábbi lesz: f(x, y) = − 2 x2 − y2 + xy + 8x + 3y A vállalat a reklámra szánt teljes összeget el kívánja költeni. Hány órát reklámozzon a televízióban és hányat a rádióban, hogy bevétele maximális legyen? a) Fogalmazzon meg egyenlőség feltételes programozási feladatot a probléma megoldására és írja fel a Lagrange függvényt! (4) b) Keresse meg a Lagrange függvény stacionárius pontját! (3) c) Állíthatjuk-e, további vizsgálat nélkül, hogy megkaptuk a feladat optimális megoldását? És azt, hogy megkaptunk egy lokális optimumhelyet? (3) 6 Operációkutatás vizsgadolgozat megoldásokkal 2003. december 19 Megoldások. a) A megoldandó egyenlőségfeltételes szélsőértékfeladat: f(x, y) = − 2 x2 − y2 + xy + 8x + 3y max feltéve, hogy 3x + y = 10. A feladat Lagrange függvénye: L(x, λ) = − 2 x2 − y2 + xy + 8x + 3y − λ(3x + y − 10) b) A Lagrange függvény

stacionárius pontjait meghatározó egyenletrendszer: = − 4x + y + 8 − 3λ = 0, (1) Lx′ (x, λ) (2) L′y (x, λ) = − 2y + x + 3 − λ = 0, Lλ′ (x, λ) = 10 − 3x − y = 0. (3) A második egyenletből λ-t kifejezve és az első és harmadik egyenletbe helyettesítve a kapott egyenletrendszer megoldása x = 69/28 = 2,46 és y = 73/28 = 2,60 , így a = [2,46 ; 2,6] a feladat egyetlen L-stacionárius pontja. Ezt felhasználva λ = 0,25 c) A Lagrange függvény stacionárius pontjai csupán jelöltek lokális optimumhelyre. Regularitás esetén e stacionárius pontok között minden lokális optimumhely előfordul. A fenti (1)-(3) feltételrendszer teljesülése a lokális optimumhelynek csupán szükséges feltétele Minden lokális optimumhely kielégíti, de ha egy pont kielégíti, akkor még nem biztos, hogy lokális optimumhely. A kapott stacionárius pontról a szegélyezett Hesse mátrix inerciájának meghatározásával lehetne eldönteni, hogy lokális

maximumhely-e. (Ez elsős tananyag, most nem kell tudni a Hesse mátrixot felírni és inerciát számítani.) Ha kiderülne, hogy lokális maximumhely, akkor abból arra következtethetnénk, hogy globális maximumhely is, hiszen ha csak egy lokális maximumhely van, akkor az globális is egyúttal. Vegyük figyelembe, hogy egy globális optimumhely egyúttal lokális optimumhely is, de ez fordítva természetesen nem igaz. (Nem igaz azt jelenti, hogy nem mindig igaz és nem azt, hogy sosem.) 4. a) Ábrázolja a megengedett megoldások és az efficiens pontok halmazát! (4) x1 − x2 ≤ 3 z1 = x1 + x2 min x1 + 2x2 ≥ 6 z2 = 2x1 − x2 max x2 ≤ 5 x1, x2 ≥ 0 (Jelölje egyértelműen az efficiens pontok halmazát!) b) Az x = [4, 1] pont miért efficiens pontja a fenti többcélú LP feladatnak? (3) Megoldások. a) Az efficiens pontok a [0, 3] és [4, 1], továbbá a [4, 1] és [8, 5] pontok által meghatározott szakaszok pontjai. E pontokból a megengedett megoldások

halmazában nem tudunk olyan pontba elmozdulni, hogy egyik célfüggvény értéke se romoljon. (Csak olyan pontba tudunk elmozdulni, hogy legalább az egyik célfüggvény értéke romlik.) b) Az x = [4, 1] megengedett megoldás efficiens, mivel nincs olyan másik megengedett megoldás, amelyik az egyik célfüggvény szerint legalább olyan jót, a másik szerint pedig jobbat venne fel, mint ő. 5. Egy sütőipari vállalat négy új üzem építését fontolgatja A szóbajöhet õ helyszinek: Pécs, Szekszárd, Kaposvár és Siófok. Mindegyik üzem kapacitása legfeljebb 900 ezer kg kenyér évente A kenyeret öt szupermarketnek adják el, amelyek mindegyikének kereslete 500 ezer kg kenyér évente. A vállalat célja a telepítési és szállítási költség összegének minimalizálása 7 Operációkutatás vizsgadolgozat megoldásokkal 2003. december 19 a) Definiáljon változókat és írja fel a telepítési probléma ILP modelljének feltételrendszerét! (6) b)

Milyen további feltételekkel biztosítaná az alábbi követelmények teljesülését? - Háromnál több új üzem ne épüljön. - Vagy Kaposváron épüljön üzem vagy Siófokon, de mindkét helyen ne. (2-2) Megoldások. a) Tanulmányozza a 4.22 példát és a 423 feladatot! b) y1 + y2 + y3 + y4 ≤ 1 és y3 + y4 = 1. 6. Egy kétszemélyes zérusösszegű játék kifizetési mátrixa a következő: B C J F 3 7 2 K 8 2 5 L 9 4 1 a) A szigorúan dominált stratégiák eliminációjával redukálja a kifizetési mátrixot! (3) b) Írja fel azt a matematikai programozási feladatot, amelynek megoldásával meghatározható a a P1 játékos kevert egyensúlyi stratégiája! (5) Megoldások. a) A mátrix elemei a P1 játékos nyereményét mutatják az összes lehetséges stratégiakombináció esetére. A P2 játékos ugyanennyit veszít P2 soha nem fogja a B stratégiát választani, mivel ezzel P1 bármely választása eetén határozottan többet veszít, mint a J

stratégiával. J tehát szigorúan dominálja (jobb) a B stratégiát, így eliminálható (törölhető, figyelmen kívül hagyható). Mivel P1 számít arra, hogy P2 sosem fogja B-t választani, P1 figyelmen kívül hagyhatja L-t, hiszen F szigorúan dominálja. Ezután már nincs szigorúan dominált stratégia A redukált kifizetési mátrix: C J F 7 2 K 2 5 E játéknak nincs tiszta stratégiákból álló Nash egyensúlya, hiszen a sorminimumok maximuma 2, az oszlopmaximumok minimuma pedig 5, tehát nem egyenlők. Úgy is beláthatjuk, hogy nincs tiszta stratégiákból álló Nash egyensúly, hogy felírjuk a kifizetési mátrixot bimátrix alakban és aláhúzzuk a legjobb válaszokat. Sehol sem lesz mindkét komponens aláhúzva. C J F (7, −7) (2, −2) K (2, −2) (5, −5) A redukált játék kevert egyensúlyát az alábbi LP feladattal határozhatjuk meg: u ≤ 7x1 + 2x2 u ≤ 2x1 + 5x2 x1 + x2 = 1 x1, x2 ≥ 0 u max LINGO modell és megoldás: MAX=U; U <= 7*X1 +

2X2; U <= 2*X1 + 5X2; X1 + X2 = 1; @FREE(U); Global optimal solution found at step: 4 8 Operációkutatás vizsgadolgozat megoldásokkal Objective value: Variable U X1 X2 Value 3.875000 0.3750000 0.6250000 2003. december 19 3.875000 Reduced Cost 0.0000000 0.0000000 0.0000000 9