11.3. 11.3. Példamegoldás

Egy beruházás során az eszközök közül választhatunk, amelyek beszerzési költsége rendre 6, 5, 4 pénzegység. Négy eszközcsoport hasznos a vállalatnak, ezek rendre . Az eszközcsoportok hasznossága rendre 3, 7, 4, 4 pénzegység.

Milyen eszközvásárlásnál lesz a vállalat nyeresége a legnagyobb, ha a nyereséget az elért összhasznosság és a beszerzett eszközök költségének különbségeként definiáljuk?

Megoldás:

Az ellátási feladatot az általános Kőnig feladatra vezetjük vissza, amelynek sémája az alábbi:

A megoldás lépései:

1. lépés: Induló folyam

2. lépés: Útkeresés címkézéssel

3. lépés: Folyamnövelés

Vége az algoritmusnak. A felső szegélyen csupa zérus áll, tehát a (2)-es esethez jutottunk. Eszerint mindegyik eszközt meg kell vásárolni, a tiszta nyereség pedig:

Módosítsuk a feladatot úgy, hogy az eszköz beszerzési költsége 4-ről 9-re, a eszközcsoport hasznossága pedig 4-ről 5-re változik. Természetes megoldás, hogy az elejéről elkezdjük az algoritmus végrehajtását. Mivel az adatok növekedtek, így az előző Kőnig feladat megoldását az új feladat induló megoldásaként felhasználhatjuk. Tehát az előző táblázattal folytatható az algoritmus. Módosítjuk a szegélyen az értékeket, majd címkézéssel folytatjuk a megoldást, ezt mutatja az alábbi táblázat.

Folyamnövelés és címkézést mutat az alábbi táblázat.

Vége az algoritmusnak. A (3) esethez jutottunk. A keresett R halmazt a megcímkézett eszközök adják. Tehát az eszközöket kell megvárárolni. A P halmazt a megcímkézett eszközcsoportok alkotják: . A tiszta nyereség: