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

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