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!).

1. ábra

A megjelenő párbeszédablak lenyíló menüjéből választható ki az "int" lehetőség (2. ábra!).

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
  • Felsorolásból ki tudja választani az egészértékű programozási feladatok definícióját és a megoldási eljárások lényegét.
  • Adott egészértékű feladatot Solver segítségével meg tudjon oldani.
  • Kétváltozós egészértékű feladatot grafikusan meg tudjon oldani.

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:

I.II.III.Kapacitás
E112110
E21-118
E30112

A nyereség együtthatók: 3, 1, 1
A cég a harmadik erőforrást teljes mértékben ki akarja használni, és a nyereséget maximalizálni szeretné. Határozza meg a termékösszetételt Solver segítségével. A termékek jellegéből adódóan az egyes termékek mennyiségére csak egész értékű megoldás lehet.

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:

  • $B$7:$D$7=egész érték
  • $E$3<=$G$3
  • $E$4<=$G$4
  • $E$5=$G$35

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..."
a változók csak valós számok lehetnek.
a modellben szereplő számok egész számok.
kikötjük, hogy a változói csak nemnegatív egész értéket vehetnek fel.
a jobb oldalon csak egész szám szerepel.

2. Oldja meg Solver program segítségével az alábbi lineáris programozási feladatot!

a) x 1 , x 2 , x 3 , 0 5 x 1 +3 x 2 x 3 27 3 x 1 +2 x 2 +4 x 3 25 2 x 1 + x 2 + x 3 = 10 z=90 x 1 +50 x 2 +30 x 3 max

Írja be a megfelelő helyre az optimális megoldás értékeit!

x 1 =
x 2 =
x 3 =
z =

b) Oldja meg a feladatot úgy, hogy az x 2 , x 3 változó értéke csak egész lehet.

Írja be a megfelelő helyre a kapott értékeket!

x 1 =
x 2 =
x 3 =
z =

3. Oldja meg grafikusan az alábbi kétváltozós tiszta egészértékű feladatot.

x 1 , x 2 0 x 1 +2 x 2 8 x 1 + x 2 5 x 1 1 2 x 1 7 z=20 x 1 +10 x 2 max

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(;),
C(; ),
D(;),
E(;)

b) Írja be az optimális megoldást a megfelelő helyre, ha létezik!

x 1 =
x 2 =
z együtt =