Potenciális módszer

A potenciális módszer egy lineáris programozási probléma megoldására szolgáló szimplex módszer módosítása egy szállítási feladathoz viszonyítva . Lehetővé teszi, hogy valamilyen megvalósítható megoldásból kiindulva véges számú iterációban megkapjuk az optimális megoldást .

A közlekedési probléma megfogalmazása

Kétféle szakaszolás létezik - mátrix és hálózati. A mátrix összetételben a szállítás csak a termelőtől a fogyasztóig megengedett. Hálózati környezetben a szállítás tetszőleges irányban végezhető (a pontok lehetnek tranzit). Legyenek  termelési/fogyasztási pontok,  szállítási ívek , fuvardíjak  ívek mentén ,  és alaposzlopok halmaza.

A feladat a következőképpen van megfogalmazva: [1]

megtalálja

feltételek mellett

ahol  - a szállítási költség ívenként,  - termelés (+) / fogyasztás (-)

 - megoldás

A szállítási probléma korlátozási mátrixa csak két nullától eltérő elemet tartalmazó oszlopokból áll - +1 a termelő és -1 a fogyasztó számára [2] .

Megjegyzés: Általánosságban elmondható, hogy a mátrix bármely négyzetes részmátrixa (azaz ) degenerált, ezért a szimplex módszer működéséhez mesterséges változókat kell bevezetni, vagy egy sort ki kell zárni a számításból. Kiíratás használatakor (lásd alább) a hozzá tartozó sort nem veszik figyelembe.

Algoritmus

A potenciális módszer a szimplex módszer módosítása, amelyben az alapmátrixot faként ábrázolják [3] .

A szimplex módszer transzportprobléma kettős változóit potenciáloknak nevezzük .

A potenciálokat a képlettel számítjuk ki , amely egyenértékű a

Egy ív esetén az ívek potenciáljait a képlet határozza meg .

Így a fogyasztó potenciálja megegyezik a termelő potenciáljával + a szállítási költség. Közgazdasági szempontból ez a termék fogyasztási hely szerinti költségeként értelmezhető.

A terv optimálisságának ellenőrzése közgazdasági szempontból könnyen értelmezhető - ha a termék fogyasztási költsége nagyobb, mint a gyártási hely költsége + a szállítási költség, akkor ezt az ívet kell szállítani. A mennyiséget maradék ívnek nevezzük .

Egy ív hozzáadása egy ciklust eredményez a fában. A bevezetett ív mentén a kocsi növekedése a ciklus áramlásainak újraszámítását eredményezi, és az egyik ív mentén a kocsi nullára csökken. A nulla áramlású ívet eltávolítjuk a bázisból, míg a bázisgráf fa marad (a ciklus megszakad).

Már csak a potenciálok újraszámítása - összeadás (vagy kivonás - az ív irányától függően) - a "lógó ág" összes csúcsához maradványértékkel

A folyamat akkor fejeződik be, amikor az optimalitási feltétel minden ívre teljesül.

Problémák megnyitása

A probléma akkor zárul le, ha a termelés összege egyenlő a fogyasztás összegével.

Általában a környezetben a termelés mennyisége nagyobb, mint a fogyasztás mennyisége. A nem lezárt feladatok megoldására, valamint a kezdeti alapterv könnyebb megszerzésére a mesterséges bázis módszert alkalmazzuk [4] . Ehhez az eredeti grafikont kibővítik, bevezetik a "dömpinget" - egy további pontot, amelyhez az összes felesleges termelést nulla áron hozzák.

Ha nagyon magas áron vezetünk be íveket a lerakótól a fogyasztási pontokig, akkor a kezdeti megoldás triviálisan épül meg - az összes termelést a lerakóba szállítjuk, az összes fogyasztást a lerakóról.

A termelési pontoktól a hulladéklerakáshoz vezető ívek a szimplex módszerben további változóknak , a hulladéklerakóktól a fogyasztási pontokig tartó ívek pedig mesterséges változóknak felelnek meg .

Északnyugati sarok módszer

A mátrix szállítási problémához egy másik algoritmus is lehetséges a kezdeti terv elkészítéséhez.

1. Válasszon ki egy i csúcsot.

2. Válasszon egy ívbeesést az i-hez. Állítsuk az ív mentén az áramlást egyenlőnek az ív végén lévő termelési és fogyasztási mennyiségek minimumával. Csökkentsük ezeket a térfogatokat az ív menti áramlás mértékével. A nulla térfogatú csúcsot a rá eső ívekkel együtt kivesszük a számításból. Térjünk át a 2. pontra.

Ha a termelési és fogyasztási csúcsokat újraszámozzuk, és minden alkalommal a legkisebb számú ívet választjuk, a módszert északnyugati sarok módszernek nevezzük [5] .

Néhány megjegyzés az algoritmus hatékonyságáról

A kimeneti ív meghatározása és a potenciálok újraszámítása meglehetősen hatékonyan valósul meg. Az idő fő "fogyasztója" az optimalitás-ellenőrzés [6] .

Az optimálisság ellenőrzéséhez szükséges idő csökkentése érdekében többféle módszert alkalmaznak.

1. Gát segítségével - amint az eltérés értéke nagyobb, mint egy bizonyos érték, bevezetjük az ívet az alapba anélkül, hogy átmennénk a többi íven. Ha az ív nem található, csökkentjük az akadályt a maximális talált eltérésre, és a megfelelő ívet bevisszük a bázisba.

2. Ciklikus nézet - a keresés onnan indul, ahol az előző nézetben megállt.

3. A "pályázók" kiválasztása - megtekintéskor nem egy ív kerül kiválasztásra, hanem több. A következő lépésben csak a kiválasztott íveket ellenőrizzük.

Az alapmátrix determinánsa mindig 1, így egész adatok mellett a feladat egész számú megoldást ad.

Sávszélesség korlátok

Egyes íveknél sávszélesség korlátok állíthatók be . Az algoritmus enyhe bonyodalma korlátozott sávszélesség mellett megoldhatja a problémát [7] .

megtalálja

feltételek mellett

Itt  – további változók (az egyenlőtlenség egyenlőséggé alakítására vezették be).

Az alap három halmazból áll majd - , és .

hol  vannak a szokásos megszorításoknak megfelelő ívek ( )

 — ívek, amelyek elérték a sávszélesség határát (telített ívek) ( )

 — olyan ívek, amelyek nem érték el a sávszélesség-határt (további változóknak felelnek meg)( )

Az alapmátrixnak van formája

Az alap inverze ekkor egyenlő

A kettős változókat a képlet számítja ki

Itt

 — potenciálok (mint a potenciálok standard módszerében).

 — telített ív mentén történő szállítás felára.

Az ív sávszélességének korlátozása a gráf enyhe módosításával is hozzáadható [8] .

Az A->B ívhez két csúcsot adunk c költséggel és p maximális áteresztőképességgel: C -p fogyasztással és D p termeléssel. A csúcsok az A->B helyett A->C<-D->B séma szerint kapcsolódnak. Az A->C ív költsége c, a C<-D és D->B ívek költsége nulla. Egy ilyen séma nem enged p-nél nagyobb áramlást áthaladni az A->B pontok között.

Algoritmus

Az algoritmus nagyon hasonló a standard potenciál módszerhez. A telített ívnek nem szabad megfelelnie az optimalitási kritériumnak, ellenkező esetben az áramlást csökkenteni kell. A fennmaradó íveket ugyanúgy ellenőrizzük a kritérium szempontjából, mint a standard változatban. Csakúgy, mint a standard algoritmusban, mindkét esetben megjelenik egy kontúr, amelyben az áramlást módosítani kell (a kiválasztott ívhez csökkenteni kell, ha az ívet telítettekből távolítjuk el, és növeljük a normál ív esetén). Amikor az áramlások megváltoznak, az egyik ív elérheti a 0-t (mint a szabványos algoritmusban), vagy a sávszélesség felső határáig - telítettekre fordítjuk.

A szabványos algoritmushoz hasonlóan a potenciálokat is újraszámolják.

Jegyzetek

  1. ↑ Romanovszkij, 1977 , p. 109-110.
  2. ↑ Romanovszkij, 1977 , p. 111.
  3. ↑ Romanovszkij, 1977 , p. 115.
  4. ↑ Romanovszkij, 1977 , p. 122.
  5. ↑ Romanovszkij, 1977 , p. 124.
  6. ↑ Valójában ezek ugyanazok a megközelítések, mint a szimplex módszernél, kissé megváltozott terminológiával. Lásd a szimplex módszerről szóló cikk Hatékonysági technikák című részét.
  7. ↑ Romanovszkij, 1977 , p. 137.
  8. ↑ Romanovszkij, 1977 , p. 139.

Linkek