Ugrás a tartalomhoz

stepping-stone method

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

Angol


Főnév

stepping-stone method (tsz. stepping-stone methods)

  1. (informatika) A Stepping-Stone módszer a szállítási feladatok (transportation problem) optimalizálási módszereinek egyike. A célja, hogy egy már kezdetben megvalósítható (feasible) szállítási tervet javítsunk, és elérjük az optimális megoldást, azaz a lehető legalacsonyabb összköltséget a megadott kapacitások és igények mellett.

A módszer lépésenként halad (innen a „stepping-stone” név), és minden lépésben megpróbálunk egy még nem használt cellát bekapcsolni a szállításba, ha ezzel csökkenthetjük az összköltséget.


🌐 A módszer alkalmazási területe

A szállítási probléma egy speciális lineáris programozási feladat, amelynek célja, hogy több forrásból (pl. raktárakból) több célhelyre (pl. boltokba) szállítsunk árut úgy, hogy a költségek minimálisak legyenek, miközben minden igényt és kínálatot kielégítünk.


📦 A probléma felépítése

A szállítási probléma egy mátrixban jelenik meg:

  • Sorok: Források (pl. gyárak, raktárak)
  • Oszlopok: Célpontok (pl. boltok, vevők)
  • Cellák: A szállítási költség (pl. Ft/db) és a szállított mennyiség

A megoldás feltételei:

  • Minden sorhoz tartozik egy kínálati kapacitás (pl. raktárban elérhető mennyiség)
  • Minden oszlophoz tartozik egy igény (pl. bolt szükséglete)
  • A teljes kínálat megegyezik az összesített igénnyel (ha nem, „dummy” sor/oszlop hozzáadható)


🚦 Kiindulási pont: Kezdeti bázismegoldás

Mielőtt alkalmazhatnánk a Stepping-Stone módszert, szükségünk van egy kezdeti bázismegoldásra, például a:

  • North-West Corner Rule
  • Vogel Approximation Method (VAM)
  • Least Cost Method

A bázismegoldásban m+n−1 darab „alapváltozó” van megadva, ahol m a sorok, n az oszlopok száma.


🪜 Stepping-Stone módszer lépései

A módszer ciklikusan fut, amíg már nem található olyan „lépőköves” javítás, amely csökkenti az összköltséget.

1. Válassz ki egy üres cellát (nem része a bázisnak)

Ez a cella lehetőség a szállítás bevonására. Vizsgáljuk meg, milyen hatása lenne, ha itt szállítanánk árut.

2. Építsünk zárt ciklust (útvonalat)

Induljunk az üres cellából, majd váltakozva vízszintesen és függőlegesen haladjunk, mindig egy báziscellát választva, amíg vissza nem térünk a kiinduló cellába. Fontos, hogy a ciklus csak báziscellákon halad keresztül (kivéve az induló cellát), és a ciklusban részt vevő cellák száma páros legyen.

3. Jelöljük ki a jeleket a ciklus mentén (+ és −)

Az induló cellát + jellel jelöljük, majd váltakozva –, +, –, +… jeleket teszünk a ciklus mentén.

4. Számítsuk ki az új költséget (redukált költség)

Vegyük a cellákhoz tartozó költségeket és végezzük el a váltakozó előjeles összeadást:

Δc = +c1 − c2 + c3 − c4 + ...

Ha Δc < 0, akkor ezzel a lépéssel csökkenthető az összköltség → tehát érdemes végrehajtani.

5. Határozzuk meg az elmozdulás mértékét (θ)

Keressük meg a legkisebb mennyiséget a „–” jellel ellátott cellákban – ez fogja meghatározni, hogy mennyit lehet mozgatni anélkül, hogy valamelyik cella „negatívra” menne.

6. Végezzük el a szállítási mennyiség módosítását a ciklus mentén

  • A + jeles cellákban növeljük θ-val a szállított mennyiséget
  • A – jeles cellákban csökkentsük θ-val
  • Így a ciklus mentén egyensúlyban maradnak a mennyiségek

7. Frissítsük a bázist

Az új cella bekerül a bázisba, a „nullára csökkent” mennyiségű cella pedig kiesik.

8. Ismételjük a fenti lépéseket

Addig ismételjük a fenti lépéseket, amíg minden nem-báziscella Δc értéke ≥ 0. Ekkor elértük az optimális megoldást.


📌 Megjegyzések

  • A módszer iteratív és vizuálisan is követhető (táblázatban könnyen kezelhető)
  • Nem garantálja a legkevesebb iterációs lépést, de pontos eredményt ad
  • Fontos, hogy a bázismegoldás degenerált is lehet (kevesebb mint m+n−1 pozitív szállítás), ekkor „ε”-mennyiségekkel dolgozhatunk ideiglenesen


🧮 Példa (vázlatosan)

Tegyük fel, hogy van egy 3×3-as mátrix:

D1 D2 D3 Kapacitás
S1 4 6 8 20
S2 2 5 7 30
S3 3 4 6 25
15 35 25
  1. Induljunk egy VAM vagy North-West sarok alapján
  2. Válasszunk egy üres cellát, pl. (1,2)
  3. Építsünk zárt ciklust: (1,2) → (1,3) → (3,3) → (3,2) → (1,2)
  4. Számítsuk ki Δc: +6 − 8 + 6 − 4 = 0
    • Mivel Δc = 0 → nem javít az eredményen
  5. Próbáljunk másik üres cellát → ha találunk Δc < 0 értéket, hajtsuk végre


✅ Előnyök és hátrányok

Előnyök:

  • Egyszerű, jól érthető lépések
  • Könnyen implementálható manuálisan vagy géppel
  • Megbízhatóan talál optimális megoldást

Hátrányok:

  • Nagy problémák esetén sok iteráció szükséges lehet
  • Degeneráltság kezelése bonyolíthatja
  • A zárt ciklusok keresése manuálisan nehézkes lehet


💻 Számítógépes implementáció

A módszer programozása során:

  • A ciklusok keresése gráfalgoritmussal automatizálható
  • Az eredmény vizualizálható ASCII táblázatokkal
  • Kombinálható a Vogel-féle becsléssel a kiindulás optimalizálására


Összegzés

A Stepping-Stone módszer egy hatékony algoritmus a szállítási problémák optimalizálására. Első lépésként egy megvalósítható kezdő megoldásból indulunk, majd ciklikusan vizsgáljuk, hogy új cellák bekapcsolásával hogyan lehetne az összköltséget csökkenteni. Minden lépésben egy ciklus mentén végzünk elmozdításokat, és a költségcsökkentés mértékét a redukált költségek mutatják meg.

A módszer szisztematikus és garantálja az optimális megoldást, ha helyesen alkalmazzuk. Kiváló tanulási alap a lineáris programozás és az operációkutatás területén.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=stepping-stone_method&oldid=3502718”