Ugrás a tartalomhoz

modified distribution method

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

modified distribution method (tsz. modified distribution methods)

  1. (informatika) A MODI-módszer (teljes nevén: Modified Distribution Method, magyarul: módosított elosztási módszer) egy hatékony algoritmus a szállítási probléma optimalizálására. A célja ugyanaz, mint a Stepping-Stone módszeré: csökkenteni az összköltséget egy kezdeti, megvalósítható (feasible) szállítási terv folyamatos javításával. A MODI módszer azonban gyorsabb és strukturáltabb, mint a Stepping-Stone.


📦 A szállítási probléma röviden

Adott:

  • m darab forráshely (pl. raktár), mindegyikhez tartozik egy kínálat (supply)
  • n darab célállomás (pl. bolt), mindegyikhez tartozik egy igény (demand)
  • Minden (i,j) cellához tartozik egy költség: C[i][j], az egységnyi szállítás költsége

Cél:

Úgy meghatározni a szállított mennyiségeket X[i][j], hogy teljesüljenek a kínálati és igényfeltételek, és a teljes költség ΣΣ C[i][j] * X[i][j] minimális legyen.

🧩 MODI módszer alapgondolata

A MODI módszer az árnyékárakon (potenciálokon) keresztül számolja ki, hogy mely nem-alapváltozók (üres cellák) tudnának költséget csökkenteni.

A módszer a következő elven működik:

  • Minden sorhoz tartozik egy Ui potenciál
  • Minden oszlophoz tartozik egy Vj potenciál
  • Minden báziscellára (i,j) teljesül: Ui + Vj = C[i][j]
  • Ezekből a Ui és Vj értékekből kiszámíthatjuk minden üres cellára a redukált költséget: Δ[i][j] = C[i][j] - (Ui + Vj)

Ha minden Δ[i][j] ≥ 0, akkor az aktuális megoldás optimális. Ha van olyan Δ[i][j] < 0, akkor azon a cellán keresztül lehetne javítani az összköltségen – hasonlóan, mint a Stepping-Stone módszernél.


⚙️ MODI módszer lépései

1. Kezdeti bázismegoldás elkészítése

Ehhez használhatunk például:

  • North-West Corner Method
  • Vogel-féle közelítés (VAM)

A megoldásnak m+n−1 darab bázisváltozót kell tartalmaznia (nem lehet kevesebb – ha mégis, degenerált, kezelni kell “ε” értékekkel).


2. Potenciálok (Ui és Vj) kiszámítása

Indítsunk valamelyik sor vagy oszlop potenciálját nulláról (Ui = 0 vagy Vj = 0).

Ezután minden báziscellára alkalmazzuk: Ui + Vj = C[i][j] és ebből kiszámítjuk a többi Ui és Vj értéket lépésenként.


3. Redukált költségek kiszámítása minden üres cellára

Minden nem-báziscellára (i,j): Δ[i][j] = C[i][j] - (Ui + Vj)

Ha minden Δ[i][j] ≥ 0 → optimális megoldás.

Ha van olyan Δ[i][j] < 0 → lehetőség az optimalizálásra.


4. Válassz egy üres cellát, ahol Δ[i][j] < 0

Ez lesz a bejövő változó. Ezen keresztül próbálunk csökkenteni a költségeken.


5. Építs ciklust a bejövő változó köré

Ugyanúgy, mint a Stepping-Stone módszernél:

  • Kizárólag báziscellákon keresztül haladva
  • Váltakozva vízszintesen és függőlegesen
  • Kiinduló pont: az új (i,j) cella


6. + / – jelek, θ érték meghatározása

  • A ciklusban váltakozó jelekkel jelöljük a cellákat:
    • – + – + – …
  • Azokon a helyeken, ahol mínusz van, nézzük meg a szállított mennyiségeket.
  • A legkisebb ilyen érték adja θ-t (ennyi mozgatható anélkül, hogy negatívba mennénk)


7. Módosítsuk a szállított mennyiségeket a ciklus mentén

  • A + jeles cellákba hozzáadunk θ-t
  • A – jeles cellákból kivonunk θ-t


8. Frissítsük a bázist

  • Az új cella bekerül
  • Az a báziscella, ahol 0 lett a szállított mennyiség, kiesik


9. Ismétlés

Térjünk vissza a 2. lépéshez (új potenciálok, új redukált költségek), és ismételjük, amíg nincs több Δ[i][j] < 0.


👨‍🏫 Egyszerű példa

Legyen az alábbi költségmátrix:

D1 D2 D3 Igény
S1 2 3 1 30
S2 5 4 8 50
S3 5 6 8 20
20 40 40
  1. Készíts egy kezdeti megoldást (pl. VAM)
  2. Számítsd ki az Ui, Vj értékeket a bázis alapján
  3. Számítsd ki minden üres cellára Δ[i][j]
  4. Válassz olyan cellát, ahol Δ[i][j] < 0
  5. Hozz létre ciklust, módosítsd a megoldást


✅ Előnyök

  • Gyorsabb, mint a Stepping-Stone, mivel nem kell minden egyes üres cellára ciklust építeni
  • Könnyebben algoritmizálható
  • Skálázható nagyobb mátrixokra


⚠️ Hátrányok

  • A ciklusépítés továbbra is szükséges (mint Stepping-Stone-nál)
  • Degenerált eseteknél bonyolult lehet


🧮 Összefoglalás

Lépés Művelet
1. Kezdeti bázismegoldás
2. Ui, Vj potenciálok kiszámítása
3. Redukált költségek (Δ) kiszámítása
4. Ha van Δ<0 → lépj tovább, különben kész vagy
5. Ciklus létrehozása a legkedvezőbb Δ[i][j] köré
6. θ meghatározása, mennyiségek módosítása
7. Bázis frissítése
8. Vissza a 2. lépéshez


A MODI módszer tehát egy strukturált, mátrixalapú eljárás a szállítási probléma optimalizálására. Hatékony, könnyen implementálható, és gyakran része a műveletkutatás kurzusoknak, valamint gyakorlati logisztikai szoftverek belső motorjának.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=modified_distribution_method&oldid=3495429”