16. fejezet - Hozzárendelési feladat

16.1. 16.1. A hozzárendelési feladat megfogalmazása

Jelölje a személyeket, a munkahelyeket (munkákat). Legyen adva az alábbi táblázat, amelynek , (egész) eleme azt jelenti, hogy az munkás a munkát mennyi idő alatt tudja elvégezni. A személyek és a munkák számának azonosnak kell lenni!

A hozzárendelési feladat (primál feladat):

Rendeljük a személyeket a munkahelyekre (munkákhoz) úgy, hogy egy személy egy munkahelyen dolgozzon, egy munkahelyre egy személy kerüljön és a munkavégzés összideje a lehető legkisebb legyen.

Az olyan hozzárendelést, amelynél előírjuk, hogy egy személy egy munkahelyen dolgozzon és egy munkahelyen egy személy dolgozzon, kölcsönösen egyértelmű hozzárendelésnek nevezzük.

A hozzárendelést egy döntési változóval jelöljük. Legyen , ha az személy hozzá van rendelve a munkához és , ha az személy nincs hozzárendelve a munkához. Az a feltétel, hogy az személy egy munkahelyen dolgozzon úgy fogalmazható meg, hogy az döntési változók i-edik sorbeli összege 1. Az a feltétel pedig, hogy a munkát egy személy végezze úgy fogalmazható meg, hogy az döntési változók j-edik oszlopbeli összege 1. A munkavégzés összidejét azon időértékek összege adja, amelyekre , ez pedig ekvivalens a összeggel.

A hozzárendelési feladat matematikai megfogalmazása:

Meghatározandó úgy, hogy

feltételek teljesülése mellett a

mennyiség minimális legyen.

Könnyen felismerhető, hogy a hozzárendelési feladat a szállítási feladat azon speciális esete, amikor minden és minden .

A hozzárendelési feladat duál feladata:

A hozzárendelési feladat duál feladata a szállítási feladat duál feladatából könnyen származtatható és az alábbi alakban írható:

Meghatározandók az és egész számok úgy, hogy

feltételek teljesülése mellett a

mennyiség maximális legyen.

A hozzárendelési feladatra is ugyanazon elméleti összefüggések levezethetők, mint amiket a szállítási feladatra láttunk. A megoldást is a „magyar módszerrel” végezzük.