Gyártórendszerek modellezése zh, 2010. december 7. A feladatsorban összesen 18 pontnyi feladat van, de a 100%-os ötöshöz elég 15 pontot szerezni. Ponthatárok: 14-15: 5 12-13: 4 10-11: 3 8 - 9: 2
LP feladatok 1. Egy városban 3 tejüzem működik, amelyek naponta 321, 432 és 213 liter tejet állítanak elő. A tejet 4 sajtgyárnak szállítják, amelyek nap igényei 100, 569, 150 és 147 liter tej. A tej szállítási költsége a szállított tej valamint az adott tejüzem és sajtgyár távolságának függvénye (mennyiség * távolság). A feladat az, hogy minden sajtgyárat ellássunk annyi tejjel, amennyire a gyáraknak szükségük van, és a tejüzemekben nem maradhat felesleges tej. Az egyes távolság adatokat az alábbi táblázat tartalmazza: 1. sajtgyár 2. sajtgyár 3. sajtgyár 4. sajtgyár 532 223 432 313 1. üzem 211 345 63 32 2. üzem 100 335 45 213 3. üzem a) *2 pont+ Írj glpk modellt, amellyel meghatározhatjuk, hogy mely üzemből mely gyárba mennyi tejet kell szállítani úgy, hogy a szállítás össz költsége minimális legyen. b) *2 pont+ Amennyiben a tejüzemekben felesleges tej marad, úgy tejüzemeknek a feleslegesen maradt tejért literenként adott mennyiségű büntetést kell fizetni. Ha egy sajtgyár nem kap elegendő tejet, akkor az egyes sajtgyárakban szintén adott forintnyi büntetést kell fizetni minden elmaradt literért. A büntetések összege hozzáadódik a teljes szállítási költséghez. A büntetések mértékeit az alábbi táblázatok tartalmazzák: Üzem 1. üzem 2. üzem 3. üzem 200 50 80 Büntetés Sajtgyár Büntetés
1. gyár 200
2. gyár 250
3. gyár 120
4. gyár 100
Azaz például, ha az 1. üzemben 10 liter tej marad, a 2. és 3. gyár 5-5 literrel kevesebbet kap, akkor 200*10 + 250*5 + 120*5 forint adódik a teljes szállítási költséghez. A fenti büntetéseket figyelembe véve megéri-e úgy szállítani, hogy felesleges tej marad az üzemekben és némely sajtgyár nem kap elegendő tejet, mennyi lesz így az összes költség, és melyik üzemből melyik gyárba mennyi tejet kell így szállítani? c) *2 pont+ Írj zimpl szkriptet, amely az a) feladatban ismertetett feladat megoldására modellt generál, a távolságokat, termelési és fogyasztási adatokat pedig fájlból olvassa be. 2. A Számítástechnikai Tanszék 1 000 000 Forintot nyert egy pályázaton, ezt a pénzt könyvekre és elektronikus berendezésekre költheti el. Minden könyvnek vagy berendezésnek más a hasznossága. A feladat az, hogy úgy válasszuk ki a megvásárlandó tételeket, hogy azok össz-hasznossága a lehető legnagyobb legyen. 1
Áru neve Ára [Forint] Hasznossága 120 000 5 Projektor 230 000 7 Intelligens tábla 65 000 4 LCD monitor 50 000 3 Iratmegsemmisítő 100 000 5 Filctábla 323 000 8 Beléptető rendszer 120 000 5 Fénymásoló gép 45 000 6 Lézernyomtató 5000 4 C programozási könyv 6000 2 Delphi programozási könyv 30000 6 Tannenbaum könyvcsomag a) *2 pont+ Glpk segítségével írj fel egy modellt, amellyel meghatározhatjuk, hogy mely tételeket éri meg megvásárolni úgy, hogy a kiválasztott áruk összhasznossága maximális legyen. b) *4 pont+ Írj zimpl szkriptet, amely fájlból beolvassa az egyes tételek árait és azok hasznosságait, majd generál egy modellt, amellyel megoldható a feladat.
PNS feladatok A város legjobb partijába csöppenünk, ahol a következő italok közül választhatunk: alkoholmentes koktélok vagy alkoholos koktélok. A következőkben pár receptet közlünk, amelyek tartalmazzák a szüksége hozzávalókat. Oldjunk meg pár feladatot ehhez kapcsolódóan. 3. [3 pont+ A választott koktélokat a leírás alapján megrendeljük (tehát az elkészítés menete nem, csak a hozzávalók a fontosak). Írjuk fel a rendelésekre vonatkozó maximális struktúrát az egyes összetevők arányinak megtartásával. A folyamat kimenete tehát az a koktél, amelyiket a kezünkben tartjuk. Az eredeti hozzávalókat azért kell ismernünk az ábrára nézve, hogy társainknak is könnyen ajánlhassuk ezt vagy azt, az egyéni ízlésüket figyelembe véve. A jégkockákat és egyebeket a recept hozzávalóinak listájában nem tüntettük fel, mivel azokat alapértelmezettnek tekintjük (tehát a maximális struktúrából is kihagyhatóak). Ahol a receptben lime leve szerepel, ott tartalékképpen szerepeljen az a verzió is, amikor azonos mennyiségű citromlevet használnak helyette. Az alkoholmentes koktélok egységesen 800 Ft-ba, az alkoholosak egységesen 1100 Ft-ba kerülnek. A vendégek további 100 Ft-ért dupla jéggel kérhetik az italokat. 1. Yellowjacket 2 rész narancslé 2 rész ananászlé 1,5 rész citromlé „Töltsük meg félig jéggel a shakert. Öntsük bele a narancslevet, ananészlevet és citromlevet. Rázzuk össze, szűrjük le jéggel töltött old fashioned pohárba.” 2. Hawaiian vodka 3 rész vodka 2
1 rész narancslé 1 rész citromlé 1 rész ananászlé 0,2 rész grenadine „Tegyük bele a jégkockákat a shakerbe. Töltsük bele az ananász-, narancs- és citromlevet és a vodkát. Rázzuk össze, majd szűrjük le az old fashioned pohárba, amibe előzőleg jégkockákat raktunk. Citromszelettel vagy citromkarikával díszítsünk.” 3. Tiger Juice 1,5 rész whisky 1 rész narancslé 0,5 rész citromlé „A jéggel töltött shakerbe öntsük a citromlevet, a narancslevet és a whiskyt. Rázzuk jól össze, majd szűrjük a koktélos pohárba.” 4. Batman Cocktail 6 rész narancslé 0,5 rész grenadine „Töltsük fel a Collins-poharat jégkockákkal. Öntsük bele a narancslevet és a grenadine-t. Keverjük jól össze, díszítsük narancskarikával. Kínáljuk szívószállal.” 5.Toothless Shark 1 lime leve 0,5 rész grenadine 4 rész narancslé „Töltsük meg a highball poharat félig jéggel. Öntsük bele a citromlevet és a narancslevet, keverjük össze. Töltsük hozzá a grenadine-t, hagyjuk leérni az aljára. Fogyasszuk szívószállal.”
4. *2 pont+ Egészítsük ki az előző modellt úgy, hogy vegyük figyelembe a szórakozóhely kínálta kedvezményeket: az első 3 rendelésünket még a standard árakon számlázzák ki, azonban tetszőleges fajtájú alkoholmentes (AM) koktélt tekintve az 4.-től kezdve 15% árkedvezményt kapunk. Amennyiben tetszőleges fajtájú alkoholos (A) koktélokat fogyasztunk, úgy az első 2 standard áron, majd a 3.-től kezdve 5%-os kedvezménnyel történik, illetve az 5.-től kezdve 10%-os kedvezmény van. Tehát ha előbb egy Yellowjacket (AM) koktélt iszunk, majd egy Tiger Juice-t (A) és két Batman Cocktailt (AM), akkor a következő Toothless Shark (AM) már csak 680 Ft-ba fog kerülni. Ezután egy Hawaiian Vodka (A) természetesen még az eredeti árán van (1100 Ft). (Részpontért egy összes rendelést (A és AM együtt) számláló, a 4.-től kezdve 15% kedvezményt adó megoldás is értékelhető.) 5. *1 pont+ Egészítsük ki a modellünket úgy, hogy a partira való bejutáshoz a karszalag vétele legyen szükséges. 3
Ez tehát egy egyszeri, fogyasztástól független ár (600 Ft). Amennyiben az illető VIP vendég, úgy ettől az összegtől eltekinthetünk. A karszalagok ellenőrzése például a kiszolgáláskor történhet.
4
Példakódok Glpk: var x1 >= 0, integer; var x2 >= 0, integer; s.t. ananasz: 2*x2 <= 100; s.t. sajt: 4*x1 + 3 * x2 <= 50; s.t. sonka: 3* x1 + 4*x2 <= 60; maximize bevetel: 800 * x1 + 600 * x2; end; # vagy: minimize
Zimpl: set V := {"a", "b", "s", "t"}; set A := {<"s","a">, <"s","b">, <"a","b">, <"a","t">, <"b","t">}; param c[A] := <"s","a"> 17, <"s","b"> 47, <"a","b"> 19, <"a","t">53, <"b","t"> 23; defset dminus(v) := {
in A}; defset dplus(v) := { in A}; var x[A] binary; minimize cost: sum in A: c[i, j] * x[i, j]; set V2 := V - {"s", "t"}; subto fd: forall in V2: sum in dminus(v): x[i, v] == sum in dplus(v): x[v,j]; subto uf: sum<s, i> in dplus("s"): x[s, i] == 1;
5
