network simplex algorithm

network simplex algorithm (tsz. network simplex algorithms)

1. (informatika) A network simplex algorithm a szimplex módszer egy speciális változata, amelyet hálózati optimalizálási feladatokra — különösen minimum költségű áramlási problémákra (Minimum-Cost Flow) — terveztek. Ez az algoritmus kihasználja a hálózati struktúra sajátosságait, így hatékonyabb, mint az általános szimplex módszer, ha a probléma gráfként modellezhető.

• Irányított gráf ${\textstyle G=(V,E)}$
• Minden élen:
  • kapacitás ${\textstyle u_{ij}}$
  • költség ${\textstyle c_{ij}}$
• Minden csúcshoz:
  • kínálat vagy kereslet ${\textstyle b_{i}}$, ahol ${\textstyle \sum b_{i}=0}$

Keressünk olyan áramlást ${\textstyle x_{ij}}$ az éleken, amely:

• Kielégíti a kereslet/kínálatot:

  $${\displaystyle \sum _{j}x_{ji}-\sum _{j}x_{ij}=b_{i}\quad \forall i\in V}$$

• Kapacitáskorlát alatt marad:

  $${\displaystyle 0\leq x_{ij}\leq u_{ij}\quad \forall (i,j)\in E}$$

• Minimizálja a teljes költséget:

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

A network simplex algoritmus egy szimplex típusú módszer, de nem táblázatot használ, hanem:

• Spanning tree (feszítőfa) szerkezetet tart fenn az áramlás bázisához
• Az iterációk során a feszítőfát pivotálja: egy élt kivesz, egy másikat betesz
• Folyamatosan javítja az áramlást és a költséget

• A bázismegoldás egy feszítőfa, amely ${\textstyle |V|-1}$ aktív élből áll
• Minden nem-bázisélen (azaz nem a fában): áramlás 0 vagy kapacitás
• A báziséleken: az áramlás számítható a kereslet/kínálat egyenletekből

Minden csúcshoz rendeljünk egy potenciált ${\textstyle \pi _{i}}$, amely teljesíti:

$${\displaystyle \pi _{j}-\pi _{i}=c_{ij}\quad {\text{az összes bázisélen}}}$$

Ebből kiszámítható az élek csökkentett költsége:

$${\displaystyle {\bar {c}}_{ij}=c_{ij}+\pi _{i}-\pi _{j}}$$

Ha minden nem-bázisélen ${\textstyle {\bar {c}}_{ij}\geq 0}$ (a megfelelő feltételekkel), akkor optimális megoldás.

Válasszunk olyan nem-bázisélt, amelyiknél ${\textstyle {\bar {c}}_{ij}<0}$, azaz csökkentené a költséget. Ez lesz a belépő él a feszítőfába.

• A feszítőfához hozzáadott új él egy egyetlen ciklust hoz létre
• Válasszunk egy olyan élt a ciklusból, amelyet elhagyhatunk, hogy a feszítőfa újra feszítő maradjon (kilépő él)
• A ciklus mentén történik az áramlás módosítása: kiszámítjuk, mennyi a maximális növelhető/mérsékelhető mennyiség

• Átállítjuk az áramlás értékeit a ciklus mentén
• Frissítjük a feszítőfát (új él be, régi ki)
• Visszatérünk az első lépéshez

1. Inicializálj feszítőfát és megvalósítható áramlást (pl. nulláramlás)
2. Számítsd ki a csúcsok potenciáljait (π) a fa mentén
3. Ismételd:
    a. Keresd meg a nem-bázisélt legnegatívabb csökkentett költséggel
    b. Ha nincs ilyen él → optimális megoldás
    c. Építs ciklust a feszítőfával és új éllel
    d. Határozd meg a minimális megengedett áramlásmódosítást a ciklus mentén
    e. Pivotálj: módosítsd az áramlást, frissítsd a fát

• Szállítási problémák
• Telekommunikációs hálózat optimalizálás
• Logisztikai elosztás
• Ellátási lánc optimalizálás
• Készlet és termelés menedzsment

• Gyorsabb, mint az általános szimplex hálózati problémákra
• Használja a gráfok strukturális tulajdonságait
• Nagy méretű problémákra jól méretezhető

• Csak speciális LP-feladatokra alkalmazható (gráfszerű probléma kell)
• A feszítőfa-kezelés és potenciálok számítása nem triviális

A network simplex algorithm a klasszikus szimplex módszer hatékony hálózati változata, amely kihasználja a gráfstruktúrák sajátosságait. A bázismegoldás itt egy feszítőfa, és a pivotálás egy él cseréjét és a fa módosítását jelenti. A módszer gyors, robusztus, és ipari alkalmazásokban is széles körben használt.

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