Szállítási feladat

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. június 3-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A szállítási probléma ( Monge-Kantorovich probléma ) a lineáris programozás egy speciális fajtája matematikai problémája . [1] [2] Problémának tekinthető az áruk kiindulási pontoktól a fogyasztási pontokig történő szállításának optimális terve, minimális szállítási költséggel.

A számítási komplexitás elmélete szerint a szállítási probléma a P komplexitási osztályba tartozik . Ha az ajánlatok teljes mennyisége (az indulási pontokon elérhető áruk) nem egyenlő a fogyasztási helyek által igényelt áruk (áruk) teljes keresletével, a szállítási problémát kiegyensúlyozatlannak ( nyitottnak ) nevezzük.

A probléma leírása

A szállítási probléma (klasszikus) a homogén termék homogén elérhetőségi pontoktól homogén fogyasztási helyekre homogén járműveken történő szállításának optimális tervének problémája (előre meghatározott mennyiség), statikus adatokkal és lineáris megközelítéssel (ezek a fő feltételei a probléma).

A klasszikus szállítási feladatnál kétféle feladatot különböztetnek meg: a költségkritériumot (a szállítási költség minimális elérése) vagy a távolságok és az időkritériumot (a szállításra fordított minimális idő). A szállítási probléma elnevezés alatt egyetlen matematikai modellel a feladatok széles skáláját határozzák meg, ezek a feladatok lineáris programozási feladatokhoz kapcsolódnak, és az optimális módszerrel megoldhatók. A szállítási probléma megoldásának speciális módszere azonban jelentősen leegyszerűsítheti annak megoldását, hiszen a szállítási probléma a szállítási költségek minimalizálására lett kifejlesztve.

A feladat matematikai megfogalmazása

A homogén rakomány mennyiségben a szállítóknál koncentrálódik . Ezt a rakományt mennyiségben kell eljuttatni a fogyasztókhoz . - az áruk szállítótól a fogyasztóig történő szállításának költsége . Olyan szállítási tervet kell készíteni, amely lehetővé teszi az összes gyártó termékének teljes exportját, teljes mértékben kielégíti az összes fogyasztó igényeit, és minimális szállítási költséget biztosít. Jelölje a szállítótól a fogyasztóig történő szállítás mennyiségeként . [3] $m$ ${\displaystyle a_{1},a_{2},....a_{m))$ $n$ ${\displaystyle b_{1},b_{2},....b_{n))$ $c_{ij}$ $én$ $j$ $x_{ij}$ $én$ $j$

\sum _{j=1}^{n}x_{ij}=a_{i}

i=1,2,...,m

\sum _{i=1}^{m}x_{ij}=b_{j}

j=1,2,...,n

\sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}\rightarrow \min

A megoldási módszerek keresésének története

A problémát először Gaspard Monge francia matematikus formalizálta 1781 - ben [4] . A probléma megoldásában a Nagy Honvédő Háború alatt Leonyid Kantorovics szovjet matematikus és közgazdász ért el előrelépést [5] . Ezért ezt a problémát néha Monge-Kantorovich közlekedési problémának nevezik .

Megoldási módszerek

A klasszikus közlekedési probléma megoldható szimplex módszerrel , de számos jellemző miatt egyszerűbben is megoldható (kis dimenziójú problémák esetén).

A probléma feltételeit a táblázatban helyezzük el, a cellákba beírva a től a rakományig szállított rakomány mennyiségét , kis cellákba pedig a megfelelő tarifákat . $A_{i}$ $B_j$ $X_{ij}\geqslant 0$ $C_{ij}$

A szállítási terv iteratív javítása

Az alapvonal megtalálása

Meg kell határozni az alaptervet , és az egymást követő műveletekkel meg kell találni az optimális megoldást. A referenciatervet a következő módszerekkel találhatjuk meg: "északnyugati sarok" , "legkisebb elem" , kettős preferencia és Vogel-féle közelítés .

Északnyugati sarok módszer (átlós vagy javított)

Minden szakaszban a táblázat többi részének bal felső cellája a lehető legnagyobb számmal van kitöltve. Töltés oly módon, hogy a rakományt teljesen eltávolítsák, vagy a szükségletet teljesen kielégítsék . $A_{i}$ $B_j$

Legkisebb elem módszer

A probléma megoldásának egyik módja a minimális (legkisebb) elem módszere . Lényege, hogy minimalizálja az áruk fogyasztók közötti oldalirányú újraelosztását.

Algoritmus:

Az értéktáblázatból kiválasztjuk a legalacsonyabb költséget, és a számok közül a nagyobbat írjuk be a megfelelő cellába.
A beszállítói sorok egy sor használt készletet, a vevő oszlopokat pedig egy olyan oszlop esetében ellenőrzik, amelynek követelményei teljes mértékben kielégítettek. Az ilyen oszlopokat és sorokat a továbbiakban nem vesszük figyelembe.
Ha nem minden fogyasztó elégedett, és nem minden szállító használta fel az árut, térjen vissza az 1. lépéshez, különben a probléma megoldódik.

Iterációk

Az alapvető szállítási terv megtalálása után alkalmaznia kell az egyik algoritmust annak javítására, megközelítve az optimálisat.

Falling stone módszer
A potenciálok módszere .

Gráfelméleti megoldás

Egy olyan kétoldalú gráfot tekintünk , amelyben a termelési pontok a felső, a fogyasztási pontok pedig az alsóban vannak. A termelési és fogyasztási pontokat párokban kötik össze a végtelen áteresztőképesség és az áramlási egységenkénti ár élei . $C_{ij}$

A forrás mesterségesen kapcsolódik a felső lebenyhez . Az élek kapacitása a forrástól az egyes termelési pontokig megegyezik az adott ponton lévő termékkészlettel. Ezen élek áramlási egységenkénti költsége 0.

Hasonlóképpen, a lefolyó csatlakozik az alsó lebenyhez . A bordák áteresztőképessége az egyes fogyasztási pontoktól a mosogatóig megegyezik az adott ponton a termék iránti kereslettel. Ezen élek áramlási egységenkénti költsége szintén 0.

Ezután megoldódik a minimális költség maximális áramlásának ( mincost maxflow ) megtalálásának problémája. Megoldása hasonló a Ford-Fulkerson algoritmusban a maximális áramlás megtalálásához . Csak a legrövidebb kiegészítő áramlás helyett a legolcsóbbat keresik. Ennek megfelelően ez a részfeladat nem a szélességi keresést használja , hanem a Bellman-Ford algoritmust . Egy adatfolyam visszaküldésekor a költség negatívnak minősül.

A „mincost maxflow” algoritmus azonnal futtatható – alapvonal keresése nélkül. De ebben az esetben a döntési folyamat valamivel hosszabb lesz. A „mincost maxflow” algoritmus végrehajtása legfeljebb műveletekben történik. ( az élek száma, a csúcsok száma.) Véletlenszerűen kiválasztott adatokkal általában sokkal kevesebb szükséges - a műveletek sorrendje. $O(v^{2}e^{2})$ $e$ $v$ $O(ve)$

A kiegyensúlyozatlan szállítási probléma megoldása során egy technikát alkalmaznak a kiegyensúlyozottá tételre. Ehhez adjon meg fiktív úti célokat vagy indulásokat. A szállítási probléma egyensúlyának megvalósítása szükséges ahhoz, hogy a szállítási táblák felhasználásán alapuló megoldási algoritmust alkalmazni lehessen.

Általánosítások

A szállítási probléma a hálózati beállításban

Ebben a változatban a pontokat nem osztják kiindulási és fogyasztási pontokra, minden pont egyenlő, de a termelést pozitív számmal, a fogyasztást pedig negatív számmal adjuk meg. A szállítás egy adott hálózaton történik, amelyben ívek köthetnek össze tetszőleges pontot, beleértve a termelőt-termelőt, fogyasztót-fogyasztót.

A problémát a potenciálok enyhén módosított módszere oldja meg , gyakorlatilag megegyezik a klasszikus beállítással.

Szállítási probléma sávszélesség-korlátozással

A szállítási probléma egy változata hálózati beállításban, amelyben bizonyos ívek maximális áteresztőképessége van megadva.

A problémát a potenciálok egy kissé bonyolult módszere oldja meg .

Több termék szállítási probléma

Egy szállítási feladat olyan változata, amelyben több termék van (a pontok több terméket is előállíthatnak/fogyaszthatnak). Egyes íveknél átviteli korlát van beállítva (enélkül a feladat termékenként különálló feladatokra bomlik).

A problémát szimplex módszerrel oldjuk meg (a Danzig -Wulf kiterjesztést használjuk, részfeladatként egytermékes szállítási feladatokat használunk).

Jegyzetek

↑ A. V. Kuznyecov, N. I. Kholod, L. S. Kosztevics. Útmutató a problémamegoldáshoz a matematikai programozásban . - Minszk: Felsőiskola , 1978. - S. 110.
↑ Kibernetikai szótár / Szerk.: V. S. Mikhalevich akadémikus . - 2. - Kijev: M. P. Bazhanról elnevezett Ukrán Szovjet Enciklopédia főkiadása, 1989. - 751 p. - (C48). — 50.000 példány. - ISBN 5-88500-008-5 .
↑ Korbut, 1969 , p. 28.
↑ Monge G. Mémoire sur la théorie des deblais et de remblais. Histoire de l'Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, 666–704. oldal, 1781.
↑ Kantorovich L. A tömegek transzlokációjáról // CR (Doklady) Acad. sci. URSS (NS), 37:199-201, 1942.

Linkek

Szállítási feladat
Algoritmusok a maximális áramlás meghatározásához
http://kb.mista.ru/article.php?id=859 A szállítási probléma megoldása az 1C:Enterprise 8.2-ben

Irodalom

Korbut A.A. , Finkelstein Yu.Yu. Diszkrét programozás. - M. : Nauka, 1969. - 368 p.