9. fejezet - Általános KŐNIG feladat

9.1. 9.1. A feladat megfogalmazása

Legyenek adottak a termelők, amelyek rendre kínálattal rendelkeznek és az fogyasztók, amelyek kereslete (igénye) rendre . A keresleti és a kínálati adatokról feltehetjük, hogy pozitív számok, mert ellenkező esetben nem érdemes szerepeltetni az illető termelőt ill. fogyasztót. Ismert továbbá, hogy mely termelőtől, mely fogyasztóhoz történhet szállítás, amelyet egy kvalifikációs táblázattal szoktunk megadni, amelynek (, ) cellájába *-ot teszünk, ha a termelő szállíthat árut az fogyasztóhoz. Ha a termelők és fogyasztók közötti szállítási viszonylatokat digráffal szemléltetnénk, akkor egy speciális digráfot kapnánk, a ponthalmaz két olyan részhalmazból áll, amelynél él csak az egyik részhalmazból vezet a másik részhalmazba. Az egyes részhalmazokon belül nincsenek élek. Az ilyen digráfot páros vagy kétrészes digráfnak nevezzük. Az általános Kőnig feladatot az alábbi sémával szoktuk jellemezni:

Az általános Kőnig feladatot kétféle formában is megfogalmazzuk, az egyiket egzisztencia formában, a másikat pedig optimalizálási feladat formájában.

Kőnig feladat egzisztencia formában:

Elszállítható-e az összes árú a termelőktől a fogyasztókhoz az alábbi feltételekkel:

  • csak olyan viszonylatban szállíthatunk, ami megengedett,

  • a fogyasztókhoz legfeljebb az igényüknek megfelelő mennyiségű árut szállíthatunk?

A legtöbb esetben azonban nem csak arra vagyunk kíváncsiak, hogy megoldható-e az elszállítás, amennyiben nem tudjuk az összes árut elszállítani, akkor jó lenne tudni, hogy maximálisan mennyi árú szállítható el. Ha a termelők összkínálata meghaladja a fogyasztók összkeresletét, akkor eleve nem lehet az összes árut elszállítani, tehát az egzisztencia formában megfogalmazott feladat megoldása triviális, azonban nem triviális a megoldása az olyan kérdésfelvetésnek, hogy maximálisan mennyi árú szállítható el a termelőktől.

Kőnig feladat optimalizálási formában:

Maximálisan mennyi árú szállítható el a termelőktől a fogyasztókhoz az alábbi feltételekkel:

  • csak olyan viszonylatban szállíthatunk, ami megengedett,

  • a termelőktől legfeljebb a kínálatuknak megfelelő mennyiségű árut szállíthatunk,

  • a fogyasztókhoz legfeljebb az igényüknek megfelelő mennyiségű árut szállíthatunk?

A részletes vizsgálat előtt néhány jelölést vezetünk be. Legyen a termelők, a fogyasztók halmaza. (A termelők halmazát azért nem T-vel jelöltük, mert a T-t már a vágás egyik ponthalmazára lefoglaltuk.) Jelölje a termelők egy tetszőleges részhalmazát és jelölje azon fogyasztók halmazát, amelyekhez a P-beli termelők együttesen szállíthatnak. Jelölje továbbá a P-beli termelők kínálatát, az -beli fogyasztók keresletét.

Példaként tekintsük az alábbi kvalifikációs táblázattal adott általános Kőnig feladatot:

Legyen . Könnyen meggyőződhetünk arról, hogy ekkor . A P-beli termelők kínálata , az -beli fogyasztók kereslete .