minimum-cost flow problem

Angol

Főnév

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.

---

📘 Formális definíció

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}$

Cél:

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

1. Kapacitáskorlátokat betartja:

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

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

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

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

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

---

🧠 Példa

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.

---

🔁 Algoritmusok

1. Successive Shortest Path Algorithm

• 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

---

2. Cycle-Canceling Algorithm

• 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

---

3. Network Simplex Algorithm

• 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

---

4. Cost Scaling / Capacity Scaling

• 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á

---

🧾 Pseudokód – Successive Shortest Path

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

---

📚 Alkalmazások

• 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)

---

✅ Összegzés

Jellemző	Érték
Feladat típusa	Hálózati lineáris program
Változók	Éleken lévő áramlások
Cél	Költség minimalizálás
Feltételek	Kapacitás + egyenleg
Alkalmazás	Logisztika, hálózat, energia

További információk

• 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)