11.2. 11.2. A feladat matematikai vizsgálata és megoldási algoritmusa

Legyen R a megvásárlandó eszközök halmaza. Az R halmaz meghatározza a hasznos csoportokat, amelyeket jelöljön P. A maximalizálandó célfüggvény ekkor:

Ezt egyszerű átírással az alábbi minimalizálandó célfüggvénnyé alakíthatjuk:

A fenti összefüggés első tagja konstans, így azonnal adódik a minimalizálandó célfüggvény:

Ez a célfüggvény pedig nem más, mint az általános Kőnig feladat folyamproblémára visszavezetett hálózatában a vágás értéke, amit a folyamproblémában minimalizálni kell. Tehát a feladatot az általános Kőnig feladat megoldási algoritmusával oldhatjuk meg. Az ismert algoritmus az alábbi három eset valamelyikével áll meg.

  1. A minimális vágás olyan, hogy . Ekkor a Kőnig feladat megoldható és . Tehát egyik eszközt sem szabad megvenni.

  2. A minimális vágás olyan, hogy . Ekkor a Kőnig feladat nem oldható meg és . Tehát mindegyik eszközt meg kell venni.

  3. A minimális vágás az (1) és a (2) eset egyikébe sem tartozik. Ekkor a Kőnig feladat nem oldható meg és az eszközhalmaba tartozó eszközöket kell megvenni.