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 é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 jelenti, hogy az i-edik munkás elvégzi a j-edik munkát vagy sem. Az 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: | ||
ahol | ||
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: | ||
ahol | ||
A célfüggvény pedig: | ||
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 | ||
|
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): | |||||||||||||||||
| |||||||||||||||||
Melyik munkás melyik feladatot kapja meg, hogy a költségek minimálisak legyenek. | |||||||||||||||||
Megoldás: | |||||||||||||||||
| |||||||||||||||||
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): | |||||||||||||||||
| |||||||||||||||||
| |||||||||||||||||
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 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: | |||||||||||||||||
Megoldás: | |||||||||||||||||
A munkásokra vonatkozó feltételek: | |||||||||||||||||
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: | |||||||||||||||||
Költségfüggvény: | |||||||||||||||||
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 értékét! = ![]() | |||||||||||||||||
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. ![]() |