Matematika | Felsőoktatás » Operációkutatás vizsgadolgozat B

Operációkutatás vizsgadolgozat megoldásokkal B 2003. december 30 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 X1 + 11 X2 + 14 X3 ST 9 X1 + 4 X2 + 12 X3 <= 72 3 X1 + 4 X2 + 6 X3 <= 48 END SUB X1 2 OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE X1 2.000000 X2 10.500000 X3 0.000000 ROW SLACK OR SURPLUS 2) 12.000000 3) 0.000000 139.5000 REDUCED COST -3.750000 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. 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.) 1

Operációkutatás vizsgadolgozat megoldásokkal B 2003. december 30 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) 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. 2 Operációkutatás vizsgadolgozat megoldásokkal B 2003. december 30 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 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) 3 Operációkutatás vizsgadolgozat megoldásokkal B 2003. december 30 Megoldások. a) Tanulmányozza a 4.22 példát és a 423 feladatot! és y3 + y4 =

1. b) y1 + y2 + 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 Objective value: 3.875000 Variable Value Reduced Cost U 3.875000 0.0000000 X1 0.3750000 0.0000000 X2 0.6250000 0.0000000 4