minimum-cost flow problem

minimum-cost flow problem (tsz. minimum-cost flow problems)

1. (informatika) A Minimum-Cost Flow Problem (MCFP), magyarul: minimális költségű áramlási probléma, egy alapvető hálózati optimalizálási feladat, amelyben az a cél, hogy bizonyos mennyiségű áramlást juttassunk el egy irányított hálózaton keresztül minimális költséggel, kapacitáskorlátok figyelembevételével.

Ez a probléma egyesíti a maximum flow (legnagyobb áramlás) és a legrövidebb út (költségminimalizálás) problémákat, és alkalmazható logisztikai elosztásban, ellátási lánc menedzsmentben, távközlési hálózatokban, stb.

Legyen adott:

• Egy irányított gráf: ${\textstyle G=(V,E)}$
• Minden élhez tartozik:
  • kapacitás: ${\textstyle u_{ij}\geq 0}$
  • költség: ${\textstyle c_{ij}}$ (egységnyi áramlás költsége)
  • (esetleg alsó korlát: ${\textstyle l_{ij}}$)
• Minden csúcshoz tartozik egy kínálat vagy kereslet ${\textstyle b_{i}}$:
  • ha ${\textstyle b_{i}>0}$, akkor forrás (supply node)
  • ha ${\textstyle b_{i}<0}$, akkor nyelő (demand node)
  • ha ${\textstyle b_{i}=0}$, akkor átmeneti csomópont
• A feltétel: ${\textstyle \sum b_{i}=0}$

Keressünk egy áramlást ${\textstyle f_{ij}}$ az éleken, hogy:

1. Kapacitáskorlátokat betartja:

   $${\displaystyle 0\leq f_{ij}\leq u_{ij}}$$

2. Anyagmegmaradás teljesül minden csúcspontban:

   $${\displaystyle \sum _{j}f_{ji}-\sum _{j}f_{ij}=b_{i}}$$

3. Összköltség minimalizált:

   $${\displaystyle \min \sum _{(i,j)\in E}c_{ij}\cdot f_{ij}}$$

Egy raktárban 20 egység áru van, amelyet 2 boltba kell szállítani (10 és 10 egység). A szállítás különböző útvonalakon lehetséges, eltérő költséggel és kapacitással. A cél: az áru eljuttatása a boltokhoz legkisebb összköltséggel.

• Amíg van el nem küldött kínálat:
  1. Legrövidebb utat keres (a költségek alapján) a forrástól valamelyik nyelőig
  2. A kiválasztott útvonalon a lehető legtöbb egységet küldi
  3. Frissíti a reziduális gráfot és folytatja

Előny: egyszerű, jól működik kis- és közepes méretű hálózatokon Hátrány: sok iteráció, ha az egyenlegek kis lépésekben rendezhetők

• Kezd egy tetszőleges megvalósítható áramlással
• Amíg van negatív költségű kör a reziduális gráfban:
  • Küld áramlást ezen a körön (javítva a költséget)
  • Frissíti a reziduális hálózatot

Előny: garantált konvergencia Hátrány: lassú lehet, ha sok kör van

• A klasszikus szimplex módszer hálózati változata
• Bázis = feszítőfa
• Pivotál: él belép a fába, másik kilép
• Állandóan egy megvalósítható fa-alapú áramlást tart fenn
• Gyors a gyakorlatban

• A push-relabel elvhez hasonló: áramlást küld szinteken, feszültség segítségével
• Gabow-Tarjan és Goldberg-Tarjan algoritmusai példák rá

1. Kezdetben f_{ij} = 0 minden élre
2. Amíg van b_i > 0 (nem teljesített kínálat)
   a. Keress legrövidebb utat s-t (supply → demand) a reziduális hálózatban
   b. Számítsd ki az út minimális kapacitását (Δ)
   c. Küldj Δ egység áramlást ezen az úton
   d. Frissítsd az egyenlegeket és a reziduális gráfot
3. Ha nincs több kínálat: kész, optimális megoldás

• Szállítási és disztribúciós hálózatok
• Telekommunikáció és routing
• Energiaelosztás
• Projektmenedzsment (idő és erőforrás elosztás)

• minimum-cost flow problem - Szótár.net (en-hu)
• minimum-cost flow problem - Sztaki (en-hu)
• minimum-cost flow problem - Merriam–Webster
• minimum-cost flow problem - Cambridge
• minimum-cost flow problem - WordNet
• minimum-cost flow problem - Яндекс (en-ru)
• minimum-cost flow problem - Google (en-hu)
• minimum-cost flow problem - Wikidata
• minimum-cost flow problem - Wikipédia (angol)