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 v j -vel, a tárgy használati értékét h j -vel, a döntési változókat x j -vel, a tárgyak száma n db.

Írja ide a feltételeket:

a) A változókra vonatkozó feltételek:

x j = vagy , ahol j = , ..., .

b) Feltétel(ek):
EgyütthatókRelációJobb oldal
x 1 + x 2 +...+ x n
c) Célfüggvény (Indexek helyett írjon csak számokat! Pl. x1, h1 stb.)

x 1 + x 2 +...+ x n

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?

x 1 , x 2 0 2 x 1 +3 x 2 80 x 1 +2 x 2 50 z 1 =3 x 1 +7 x 2 max z 2 =8 x 1 +5 x 2 max

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:

x 1 + x 2

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!):
x 1 x 2 relációjobb oldal
z
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:
x 1 x 2 yrelációjobb oldal
z

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):

[ 8 2 4 17 7 14 3 2 12 5 15 26 ]

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!):
EgyütthatókRelációkJobb oldal
1. feladóx11x12x13x14
2. feladóx21x22x23x24
3. feladóx31x32x33x34
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!):
Együttható mátrixRelációJobb oldal
1. megrendelő
2. megrendelő
3. megrendelő
4. megrendelő

c) Mit fejez ki a modell változója?

A modell változója xij azt jelenti, hogy...
az i-edik feladótól a j-edik megrendelőnek xij tonnát szállítunk.
az i-edik feladótól a j-edik megrendelőnek xij Ft költséggel szállítunk egy tonna árút.
az i-edik feladótól a j-edik megrendelőnek szállítunk árút, azaz értéke 0 vagy 1 lehet.

4. feladat

Oldja meg a Solver programmal a következő hiperbolikus programozási feladatot!

x 1 , x 2 , x 3 0 x 1 + x 3 = 50 x 1 + x 2 + x 3 100 x 3 10 g( x )= 8 x 1 + x 2 +2 x 3 +100 2 x 1 +2 x 2 +3 x 3 130 max

a) Adja meg x1 értékét:

x 1 =

b) Adja meg x2 értékét:

x 2 =

c) Adja meg x3 értékét:

x 3 =

d) Adja meg Zopt értékét:

z opt =

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:

[ 3 7 10 9 1 8 4 12 8 11 7 4 ]

Feltételek:

  • Minden munkás minden feladatot képes elvégezni
  • A 2. munkás a 2. feladatot most valamilyen ok miatt nem kaphatja meg
  • A 3. munkás a sógorom, ezért ő mindenképpen kapjon munkát.

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.
A második munkás a(z) . munkát.
A harmadik munkás a(z) . munkát.
A negyedik munkás a(z) . munkát.

e) Adja meg a legkisebb költség értékét!

A legkisebb költség értéke: