KURZUS: Alkalmazott operációkutatás
MODUL: II. modul: Egészértékű programozási feladat fogalma és grafikus megoldása. Néhány nevezetes egészértékű modell
Modulzáró feladatok
1. feladat | |||||||||||||||||||||||||||||||||||||||||||||
Írja fel a "hátizsák probléma" matematikai modelljét! A hátizsák térfogatát jelöljük V-vel, a hátizsákban elviendő tárgy térfogatát -vel, a tárgy használati értékét -vel, a döntési változókat -vel, a tárgyak száma n db. | |||||||||||||||||||||||||||||||||||||||||||||
Írja ide a feltételeket: | |||||||||||||||||||||||||||||||||||||||||||||
a) A változókra vonatkozó feltételek: = vagy , ahol j = , ..., . | |||||||||||||||||||||||||||||||||||||||||||||
b) Feltétel(ek):
| |||||||||||||||||||||||||||||||||||||||||||||
c) Célfüggvény (Indexek helyett írjon csak számokat! Pl. x1, h1 stb.) | |||||||||||||||||||||||||||||||||||||||||||||
2. feladat | |||||||||||||||||||||||||||||||||||||||||||||
Többcélú lineáris programozási modellt akarjuk megoldani, de csak olyan számítógépes megoldási program áll rendelkezésre (Pl. Solver), amely csak egy célfüggvényt tud kezelni. Hogyan járjunk el? | |||||||||||||||||||||||||||||||||||||||||||||
Készítsen a két célfüggvényből egyet úgy, hogy | |||||||||||||||||||||||||||||||||||||||||||||
a) az első célfüggvény súlya 70%, a másodiké 30% legyen. Írja ide a célfüggvény együtthatóit: | |||||||||||||||||||||||||||||||||||||||||||||
b) a korlátok módszerét használja (11 legyen a 2. célfüggvény alsó korlátja). Akkor a modell (a kisebb-egyenlő és nagyobb egyenlő megadásához használja a <= és >= jeleket!):
| |||||||||||||||||||||||||||||||||||||||||||||
c) a legkisebb célfüggvény értékének maximalizálása elvet használja (Az eredeti adatokkal dolgozzon!). A modell ebben az esetben:
| |||||||||||||||||||||||||||||||||||||||||||||
3. feladat | |||||||||||||||||||||||||||||||||||||||||||||
Tegyük fel, hogy három feladóhelyen 30, 40 és 50 tonna áru van. Négy megrendelőhöz kell szállítani 20, 15, 60 és 55 tonnát. A 2. feladótól a 3. megrendelőnek technikai okok miatt nem lehet szállítani. A 1. megrendelő a sógorom, ezért az ő igényét mindenképpen ki kell elégíteni! A szállítási költségek mátrixa a következő (100 Ft/tonna): | |||||||||||||||||||||||||||||||||||||||||||||
a) Írja fel a feladatokra vonatkozó feltételek együtthat mátrixát, relációjeleket és a jobb oldalt (a kisebb-egyenlő és nagyobb egyenlő megadásához használja a <= és >= jeleket, ha szükséges!):
| |||||||||||||||||||||||||||||||||||||||||||||
b) Írja fel az igénylőkre vonatkozó feltételrendszer együttható mátrixát, a relációjeleket és a jobb oldalt (a kisebb-egyenlő és nagyobb egyenlő megadásához használja a <= és >= jeleket!):
| |||||||||||||||||||||||||||||||||||||||||||||
c) Mit fejez ki a modell változója? | |||||||||||||||||||||||||||||||||||||||||||||
A modell változója xij azt jelenti, hogy...
| |||||||||||||||||||||||||||||||||||||||||||||
4. feladat | |||||||||||||||||||||||||||||||||||||||||||||
Oldja meg a Solver programmal a következő hiperbolikus programozási feladatot! | |||||||||||||||||||||||||||||||||||||||||||||
a) Adja meg x1 értékét: = | |||||||||||||||||||||||||||||||||||||||||||||
b) Adja meg x2 értékét: = | |||||||||||||||||||||||||||||||||||||||||||||
c) Adja meg x3 értékét: = | |||||||||||||||||||||||||||||||||||||||||||||
d) Adja meg Zopt értékét: = | |||||||||||||||||||||||||||||||||||||||||||||
5. feladat | |||||||||||||||||||||||||||||||||||||||||||||
Oldja meg a következő hozzárendelési feladatot a szétválasztás és korlátozás módszerével: Egy üzemben 4 munkásnak kell kiosztani 3 feladatot úgy, hogy az összköltség a lehető legkisebb legyen! | |||||||||||||||||||||||||||||||||||||||||||||
A költségmátrix: | |||||||||||||||||||||||||||||||||||||||||||||
Feltételek: | |||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||
Vegyen elő egy négyzetrácsos lapot és oldja meg a feladatot a szétválasztás és korlátozás módszerével! | |||||||||||||||||||||||||||||||||||||||||||||
a) Írja ide a feladat kiegészített költségmátrixát: | |||||||||||||||||||||||||||||||||||||||||||||
b) Írja ide a redukált mátrixot (oszlop redukcióval kezdje) | |||||||||||||||||||||||||||||||||||||||||||||
c) Adja meg a redukció értékét, a költség alsó korlátját! A redukció értéke: | |||||||||||||||||||||||||||||||||||||||||||||
d) Adja meg az optimális megoldást: egészítse ki az elkezdett mondatokat! Első munkás kapja a(z) . munkát. | |||||||||||||||||||||||||||||||||||||||||||||
e) Adja meg a legkisebb költség értékét! A legkisebb költség értéke: |