16.4. 16.4. Nem standard hozzárendelési feladat kezelése

A gyakorlati problémák nagyon sokszor nem standard alakú hozzárendelési feladatként fogalmazhatók meg, hanem annak különböző variánsaként. Ezek kezelése hasonló módon történik a szállítási feladatnál látottakhoz. A lényeg tehát itt is a standard feladatra való átalakítás.

  1. Egyedi tiltások kezelése.

    Ha valamely viszonylatban valamilyen oknál fogva nem lehetséges hozzárendelés, akkor ott a időt nagyon nagyra (M) választjuk.

  2. Nem egyenlő az egymáshoz rendelendők száma.

    Két esetet különböztetünk meg, attól függően, hogy a személyek vagy a munkák száma a nagyobb.

    • A munkák száma meghaladja a személyek számát.

      Ekkor annyi ún. fiktív vagy virtuális személyt iktatunk be, hogy a személyek száma megegyezzen a munkák számával. A beiktatott személyek soraiba zérus időértékeket írunk. Az eredeti feladat optimális megoldásában lesznek olyan munkák, amelyek elvégezetlenül maradnak. Ha a hozzárendelési feladat olyan, hogy például a munka feltétlenül el legyen végezve, akkor a fiktív személyek sorainak k-adik oszlopába zérus helyett nagyon nagy számot (M) írunk.

    • A személyek száma meghaladja a munkák számát.

      Ekkor annyi ún. fiktív vagy virtuális munkát iktatunk be, hogy a munkák száma megegyezzen a személyek számával. A beiktatott munkák oszlopaiba zérus időértékeket írunk. Az eredeti feladat optimális megoldásában lesznek olyan személyek, amelyek nem lesznek hozzárendelve munkához. Ha a hozzárendelési feladat olyan, hogy például az személy mindenképpen foglalkoztatva legyen, akkor a fiktív munkák oszlopainak k-adik sorába zérus helyett nagyon nagy számot (M) írunk.

  3. Maximum feladat kezelése.

    A hozzárendelési feladatoknál sűrün előfordul, hogy a célfüggvényt maximalizálni kell. Például az összidő legkisebb felső korlátját akarjuk meghatározni, vagy a értékek a személyek által előállított értéket jelentik, stb. Ekkor egy új táblázatot állítunk elő úgy, hogy a legnagyobb táblázatbeli elemből kivonjuk a táblázat elemeit és ezen táblázattal oldjuk meg a hozzárendelési feladatot.

Javasoljuk, hogy először a minimumra való visszavezetést végezzük el, ha több standard előírás nem teljesedik.