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

7. lecke: Hozzárendelési feladat

Tanulási útmutató

A hozzárendelési feladat definíciója, matematikai modellje a tankönyv 5.4. fejezetében található. Az itt bemutatott példán keresztül jól érthető lesz a probléma lényege és a használt jelölések tartalma.

Könnyen észreveheti, hogy ez is egy speciális lineáris programozási modell (speciális elosztási feladat), amely szintén megoldható szimplex módszerrel, így a Solver programmal is. Mégis érdemes megismerkedni egy speciális matematikai megoldással - szétválasztás és korlátozás módszerével - mert nagyobb méretű feladatok is könnyen kezelhetők ezzel az eljárással.

Tevékenységek

Figyelmesen olvassa el a hozzárendelési feladat definícióját, modelljét. Jól jegyezze meg a modell paramétereit és gazdasági jelentéseit a tankönyvben található példán keresztül.

Jegyezze jól meg a költségmátrix elemeinek jelentését. Jegyezze meg a redukció szó értelmét és lássa be, hogy a redukált mátrix tartalma egyezik az eredetivel, de könnyebben kezelhető az optimális megoldás vizsgálata szempontjából.

Ha megértette a redukált mátrix értelmét, akkor érdemes a tankönyv 5.4.3. alfejezetéhez lapozni, hogy mindjárt az általánosabb feladatot is megértse: hogyan járjunk el, ha a munkások száma nem egyezik a munkák számával, illetve ha valamelyik munkás valamelyik munkát nem végezheti el.

Ha a redukált mátrixról nem olvasható le optimális megoldás, akkor alkalmazzuk a szétválasztás és korlátozás módszert. Ennek lényegét a tankönyvben találja. Gondolja át, és fogalmazza meg az  x ij , c ij , r ij , és k jelölések tartalmi jelentését. Kövesse végig a számítást úgy, hogy egy külön lapon Ön is írja a változásokat.

Gyakorolja az általános esetet is. Gondolja át, és fogalmazza meg az M szimbólum jelentését! Vegye észre, ha a mátrix egy elemét megváltoztatja, akkor egész más lehet az eljárás útja.

Helyezze el a költségmátrixot és az ismeretlenek mátrixát a szállítási feladatoknál megtanult módon Excel-táblán, hiszen ez egy speciális szállítási feladat.

Itt x ij jelenti, hogy az i-edik munkás elvégzi a j-edik munkát vagy sem. Az x ij ebben az esetben egy bináris változó, értéke 1, ha a munkás elvégzi a munkát, 0, ha nem végzi el.

"Az i-edik munkás valamelyik munkát elvégzi" magyar mondatnak matematikai megfelelője:

x i1 + x i2 +...+ x in =1, ahol i=1,2,...,n.

A munkás csak az egyik munkát végzi el, ennek a változónak az értéke 1, a többi 0, így lehet az összegük 1.

"A j-edik munkát valamelyik munkás elvégzi" magyar mondat megfelelője:

x 1j + x 2j +...+ x nj =1, ahol j=1,2,...,n.

A célfüggvény pedig:

k=8 x 11 +10 x 12 +7 x 13 +8 x 14 +.....+11 x 54 +18 x 55 min

lesz. Ezt érdemes a SZORZATÖSSZEG függvénnyel előállítani.

Hívja meg a Solver programot és jelölje be a célfüggvény cellájának helyét, a változók mátrixának tartományát, feltételi egyenlőségeket adja hozzá a feltételekhez. Itt jelölje be, hogy a változók mátrixának tartománya bináris lehet. Ne felejtse el a beállításokat: Lineáris modell, nemnegatív feltételezés.

(Ennek a feladatnak szinte mindig van optimális megoldása!)

Követelmények
  • Önállóan fel tudja írni egy adott (általános) hozzárendelési feladat matematikai modelljét.
  • Meg tudjon oldani egy költségmátrixszal adott, speciális feltételeket is tartalmazó feladatot szétválasztás és korlátozás módszerével.
  • Meg tudja keresni - egy Excel-táblán megadott költségmátrix ismeretében - a hozzárendelési feladat optimális megoldását.

Bemutató feladat

Négy munkás között kell 4 feladatot elvégeztetni úgy, hogy a termelés költsége a lehető legkisebb legyen. Az első munkás a második feladatot nem tudja ellátni, a harmadik munkás pedig a harmadik feladatot. A második munkásnak mindenképpen kell munkát kapnia. A költségek az alábbiak (eFt):

6834
5267
3428
2536

Melyik munkás melyik feladatot kapja meg, hogy a költségek minimálisak legyenek.

Megoldás:
Vigyük be az adatokat az Excel táblázatkezelőbe! Az "M" azt jelenti, hogy nem tudja elvégezni. Az Excelbe ilyenkor egy nagy számot írunk.

Ezután indítsuk el a Solvert, és írjuk be a korlátozó feltételeket az alábbi módon:

Korlátozó feltételek (egyenként kell felvenni őket):

  • $B$12:$E$12=1
  • $B$7:$E$10=bináris érték
  • $G$7:$G$10=1

Nyomjuk meg a megoldás gombot!

Önellenőrző feladat

1. A fent említett három követelménynek megfelelő feladat az alábbi:

Egy üzemben 4 munkásnak kell kiosztani 3 feladatot úgy, hogy az összes költség a lehető legkisebb legyen. A 2. munkás a 2. munkafeladatot nem tudja elvégezni, de a többi munkás minden feladatot el tud végezni.

A költségeket a [ 3 7 10 9 1 8 2 5 6 11 7 4 ] 1000 Ft költségmátrix szemlélteti.

További feltétel:

A harmadik munkás a sógorom, ezért ő mindenképpen kapjon munkát!

Kérdés:
Melyik munkás melyik munkát kapja, hogy az összes költség a lehető legkisebb legyen?

Megoldás:
Bevezetünk egy névleges munkafeladatot. Jelölje x ij azt, hogy az i-edik munkás a j-edik munkát elvégzi-e vagy nem. Azaz x ij 0 és x ij [ 0;1 ]

A munkásokra vonatkozó feltételek:

x 11 + x 12 + x 13 + x 14 = 1 x 21 + x 22 + x 23 + x 24 = 1 x 31 + x 32 + x 33 + x 34 = 1 x 41 + x 42 x 43 + x 44 = 1 x 34 = 0 x 22 = 0

Megjegyzés: az x34 azért =0, mert így a sógorom nem kaphatja meg a névleges munkát, azaz biztosan kap feladatot.

A munkákra vonatkozó feltételek:

x 11 + x 21 + x 31 + x 41 = 1 x 12 + x 22 + x 32 + x 42 = 1 x 13 + x 23 + x 33 + x 43 = 1 x 14 + x 24 + x 34 + x 44 = 1

Költségfüggvény:

k=3 x 11 +7 x 12 +10 x 13 +..... +11 x 41 +7 x 42 +4 x 43 min

Oldja meg a szétválasztás és korlátozás módszerével!

Vegyen elő egy négyzetrácsos lapot és oldja meg a feladatot. Az alábbi részeredményeket közölje:

a) Írja fel a feladat kiegészített költségmátrixát
b) Írja ide a redukált mátrixot. Oszlop szerint kezdje a redukciót!
c) Adja meg a redukció értékét!

A redukció értéke:

d) Állítsa elő az optimális megoldást!

Írja be a változók mátrixába az optimális megoldást: A változók értéke 0 vagy 1 lehet!
e) Adja meg az optimális megoldás k opt értékét!

k opt =

2. Oldja meg a feladatot Solver program segítségével!

Helyezze el az induló költségmátrixot egy Excel-táblán. A kiegészített költségmátrix első eleme a B3 cellában legyen! Az M helyébe egy nagy számot írjon!

A változók mátrixának első eleme a B10, a célfüggvény értéke C15 cellában legyen! A feltételek bal oldalának képletét a kiegészített mátrix melletti, illetve alatti cellákba képezze a Σ függvénnyel. Hívja meg a Solver programot, és rámutatással vigye be a kért adatokat.

a) Írja ide a mátrixba az optimális megoldást! Az értéke 0 vagy 1 lehet!
b) Adja meg az optimális megoldás költségét!

Az optimális megoldás költsége: eFt.