14.4. 14.4. Nem standard szállítási feladat kezelése

Az előzőekben ismertetett szállítási feladatra az ún. standard alakúra dolgozták ki a „magyar módszert”. A gyakorlatban sok esetben a szállítási feladat különböző variánsaival találkozunk. Ezeket is a „magyar módszerrel” fogjuk megoldani, de a módszer alkalmazásához a feladatot standard alakra kell hozni. Három különbőző esetet vizsgálunk, természetesen ezek egyidejűleg is előfordulhatnak egy feladat kapcsán.

  1. Egyedi tiltások kezelése.

    Ha valamely viszonylatban valamilyen oknál fogva a szállítás nem lehetséges (útjavítás, szerződés hiánya, stb.), akkor úgy járunk el, hogy a szállítási egységköltséget nagyon nagyra választjuk. Kézi számolásnál szokásos az M jelölés.

  2. Nem teljesül a kereslet-kínálat egyensúlya.

    Két esetet különböztetünk meg, attól függően, hogy a kínálat vagy a kereslet a nagyobb. Mindkét esetben standard feladatra kell alakítanunk a feladatot, amelyben már a kereslet-kínálat egyensúlya fennáll.

    • Az összkereslet meghaladja az összkínálatot.

      Ekkor egy ún. fiktív vagy virtuális termelőt iktatunk be szállítási egységköltségekkel és kínálattal. Könnyen ellenőrizhető, hogy így standard feladatot kaptunk és ennek optimális megoldása megegyezik az eredeti feladat optimális megoldásával.

      Az eredeti feladat optimális megoldásában biztosan lesznek olyan fogyasztók, amelyeknek az igénye nem lesz kielégítve. Ha olyan nem standard szállítási feladatunk van, amelyben például az fogyasztó igényét valamilyen ok (gazdasági érdek, egészségügyi okok, stb.) miatt feltétlenül ki kell elégíteni, akkor le kell tiltani a fiktív viszonylatot, ezzel biztosítjuk, hogy az fogyasztó igénye valóságos termelők által legyen kielégítve. Az előzőek alapján ezt úgy valósítjuk meg, hogy a zérus szállítási egységköltség helyett a -et használjuk.

    • Az összkínálat meghaladja az összkeresletet.

      Ekkor egy ún. fiktív vagy virtuális fogyasztót iktatunk be szállítási egységköltségekkel és kereslettel. Nyilvánvalóan az optimális esetben lesznek olyan termelők, amelyektől nem szállítjuk el a kínálatuknak megfelelő mennyiségű árut. Ha olyan a nem standard szállítási feladat, hogy például a termelőnél ne maradjon árú raktáron, akkor hasonlóan az előzőhöz a zérus szállítási egységköltség helyett a -et kell választani.

  3. Maximum feladat kezelése.

    Ha a szállítási feladat célfüggvényét maximalizálni kell (pl. a szállítási költség legkisebb felső korlátját akarjuk meghatározni), akkor a célfüggvényt standard alakra, azaz minimalizálandó formára kell hozni. Legyen k egy tetszőleges szám. A „költségtáblázat”-hoz tartozó célfüggvény ekkor az alábbiak szerint írható:

    A kereslet-kínálat egyensúlya miatt , azaz a fenti célfüggvény első tagja konstans, így az új „költségtáblázat”-hoz tartozó célfüggvény minimalizálása ekvivalens az eredeti költségekkel megfogalmazott szállítási feladat célfüggvényének maximalizálásával. Hogy a megszokott nemnegatív számokkal dolgozhassunk, azaz nemnegatív legyen, úgy k értékét a legnagyobb szállítási egységköltségnek (vagy annál nagyobbnak) kell választani. Összefoglalva tehát, olyan „költségtáblázat”-ot készítünk, amelyet úgy kapunk, hogy a legnagyobb szállítási egységköltségből kivonjuk a szállítási egységköltségeket.

Megjegyzés:

Ha egy nem standard feladatban maximalizálni kell és a kereslet-kínálat sem teljesül, akkor célszerű először a minimalizálásra visszavezetni a feladatot, majd ezután bevezetni a fiktív termelőt vagy a fiktív fogyasztót. Megjegyezzük azt is, hogy a fenti levezetésben szereplő mennyiség akkor is konstans lesz, mégpedig a és az mennyiségek kisebbikével lesz egyenlő.

Mint említettük, ha van letiltás, akkor azt egy nagy értékű szállítási költséggel valósítjuk meg, a minimalizálás miatt ide biztosan nem adódik szállítás. A nagy szám helyett egy M szimbólumot használunk a költségtáblázatban. Az algoritmus során a költségtáblázaton végrehajtandó módosításoknál ezt a kölségadatot sohasem változtatjuk, mindig M marad. Ha egy táblázatban sok letiltás szerepel, akkor elképzelhető az is, hogy a kereslet-kínálati szállítás egyáltalán nem valósítható meg. Erről egy általános Kőnig feladat megoldásával lehet meggyőződni.