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
6. lecke: Az egészértékű programozási feladatok fogalma és megoldási módszerei
Tanulási útmutató | |||
Az egészértékű programozási feladatok fogalma és megoldási módszerei a tankönyv 5. fejezetében találja meg. Néhány nevezetes egészértékű modell nevét, fogalmát és matematikai modelljét a tankönyv 5.6. fejezetében találja meg. | |||
Az egészértékű programozási modellek ugyancsak megoldhatók a Solver programmal. Ez teljesen megegyezik a 4. leckében megismert eljárással. Egészértékű feladatok jellegzetessége, hogy megköveteljük, bizonyos változók csak egész értéket vehetnek fel. Ezt a Solver programban beállíthatjuk. A "Korlátozó feltételek" mező mellett a "Hozzáadás" gombra kattintunk (lásd 1. ábra!). | |||
| |||
A megjelenő párbeszédablak lenyíló menüjéből választható ki az "int" lehetőség (2. ábra!). | |||
| |||
Az int (integer = egész) jelenti az egészértékűséget, bin (bináris) jelenti azt, hogy a változó csak a 0 vagy 1 értékét veheti fel. | |||
Tevékenységek | |||
Figyelmesen olvassa el az egészértékű lineáris programozási feladat definícióját, és jól jegyezze meg a matematikai modelljét. | |||
Rögzítse szemével a tankönyvben található ábra segítségével az egészértékűség megoldási problémáinak nehézségét! | |||
Tanulmányozza a probléma lényegéből adódó speciális matematikai eljárásokat. | |||
A Gomory-féle módszer lényegét jól végigkövetheti a tankönyvben található példán. Nem kell a számításokat végigvinni, mert a Solver program itt is nagy segítségünkre van. | |||
A tankönyvben található feladatot oldja meg a Solver segítségével! Vigyázzon arra, hogy a feltételek Hozzáadásánál a bal oldalon jelölje ki a változók tartományát, középen jelölje be int és jobb oldalon újból a változók tartományát. Ha nem tiszta egészértékű a feladat, akkor csak a szóban forgó változók celláira tegye meg ezt. Ha a változó csak 0 vagy 1 értéket vehet fel, akkor a bin lehetőséget jelölje ki. | |||
Tanulmányozza át a tankönyvben található egészértékű modelleket. Különösen jól jegyezze meg a Hátizsák- és a Hajórakodási problémát. Mindenképpen jegyezze meg a modellben szereplő jelölések matematikai és gazdasági jelentését. | |||
Követelmények | |||
|
Bemutató feladat | |||||||||||||||||||||
Egy gépeket gyártó vállalkozás háromféle terméket tud gyártani. A termeléshez három erőforrás áll rendelkezésre, amelyek a termelés kapacitását korlátozzák. Az erőforrások kapacitása és a termékek fajlagos erőforrás szükségletét a táblázat tartalmazza: | |||||||||||||||||||||
| |||||||||||||||||||||
A nyereség együtthatók: 3, 1, 1 | |||||||||||||||||||||
Vigyük be az adatokat Excelbe, és a már tanult módon töltsük ki a cellákat! | |||||||||||||||||||||
| |||||||||||||||||||||
Nyissuk meg a Solvert, és az alábbi módon írjuk be a korlátozó feltételeket: | |||||||||||||||||||||
Korlátozó feltételek: egyenként kell felvenni őket: | |||||||||||||||||||||
| |||||||||||||||||||||
| |||||||||||||||||||||
Ezután kattintsunk a megoldás gombra: | |||||||||||||||||||||
|
Önellenőrző feladatok | |||||||||
1. Válassza ki a helyes állítást! | |||||||||
"Egészértékű lineáris programozási feladatnak nevezzük azt a modellt, ahol..."
![]() | |||||||||
2. Oldja meg Solver program segítségével az alábbi lineáris programozási feladatot! | |||||||||
a) | |||||||||
Írja be a megfelelő helyre az optimális megoldás értékeit! = ![]() | |||||||||
b) Oldja meg a feladatot úgy, hogy az változó értéke csak egész lehet. | |||||||||
Írja be a megfelelő helyre a kapott értékeket! = ![]() | |||||||||
3. Oldja meg grafikusan az alábbi kétváltozós tiszta egészértékű feladatot. | |||||||||
Vegyen elő egy négyzetrácsos lapot, ábrázolja grafikusan a megadott feltételi egyenlőtlenségeket. Jelölje ki a lehetséges megoldások halmazát! | |||||||||
a) Adja meg a lehetséges megoldások halmazának csúcspontjait! Kezdje az x1 tengelyen lévő, azorigóhoz legközelebbivel és az óramutató járásával ellenkező irányban folytassa. Ha egy koordináta nem egész számra jön ki, akkor kerekítse 0,5-re. Például az 1 és 2 közötti érték esetén 1,5-et írjon. A(;), ![]() | |||||||||
b) Írja be az optimális megoldást a megfelelő helyre, ha létezik! = ![]() |