Szállítási feladat
A közlekedési probléma az LPA speciális esete vagy a hálózat optimalizálási problémájának speciális esete, a közlekedési útvonalak kiválasztására tervezett feladatok megoldására szolgál. Általában az alábbiak szerint van kialakítva. Vegyük fontolóra m különböző beszállítókat (kiindulási pontokat) Pi, amelyek homogén termékeket tartalmaznak az ai mennyiségekben. és ezeknek a termékeknek a n fogyasztási pontokra történő átküldését fontolóra veszik. j =. akiknek a szükséglete megegyezik a bj-vel. Ismert tarifák vannak e termékeknek Pi pontről a Qj pontra történő szállítására (rakományegység szállítási költségei). Szükséges egy ilyen szállítási terv összeállítása, hogy a költségek összköltsége minimális legyen.
Ehhez a sávszélességre vonatkozó korlátozások, a közbülső visszaállítási pontok, a rakomány forrása és ürítései kiegészíthetők. A probléma matematikai modellje a következő:
Xij - a rakományegységek száma i-től j-ig.
Figyelembe véve, hogy ez a probléma különleges eset az LPA-ban, akkor ezeknek a problémáknak a megoldását különösképpen figyelembe veszik.
A probléma szállítási táblája így néz ki:
A szállítási probléma megoldás, ha Σai = Σbj (zárt modell).
Ha Σai <∑bj. то вводят фиктивный пункт производства, и не все пункты в оптимальном решении будут удовлетворены в потребности.
Ha Σai> Σbj, akkor nem minden állomány kerül kiviteli termelési pontokba, a megoldás fiktív fogyasztási pontot vezet be. Megjegyezzük, hogy a fiktív pont kimeneti mennyisége megegyezik a különbséggel # 9474; Σai -Σbj # 9474;.
A szállítási táblázatban egy ciklus egy zárt, megszakított vonal, amely megfelel a következő feltételeknek:
1. A vonallánc minden csúcsa a szállítótábla celláiban van.
2. Az élek sorokban vagy oszlopokban vannak elhelyezve, de nem átlósan.
3. Minden csúcsra két szél van: egy - egy vonalon, egy másik - egy szállítóasztal oszlopában.
4. A szállítási táblázatban lévő sejtek halmaza aciklikusnak mondható, ha nincs ciklus, amelynek összes csúcsa ebben a cellában található.
Tétel. A szállítási probléma elfogadható megoldása a támogatás, azaz. a töltött sejtek halmaza aciklikus, azaz. tartalmaz m + n-1 sejteket.
Definíció. A támogatási megoldás lehetősége # 945; A közlekedési probléma az Ui szám. Vj j =. oly módon, hogy Ui + Vj = Cij a töltött sejt sebessége.
Tétel (A támogatási megoldás optimális feltételeinek megfelelő feltétel). Ha minden kitöltetlen sejt esetében (i, j) Ui + Vj = Cij. ahol Ui és Vj a támogatási megoldás lehetőségei # 945, akkor ez a támogatási megoldás optimális.
A támogatási megoldások létrehozásának módszerei:
1. Az északnyugati sarok módszere. Elkezdtük tölteni a cellából (1,1) - az asztal északnyugati sarkát vagy kielégítve a szükségletet, vagy a tartalékok kimerítése ezen a ponton. Ezután folytassa a következő sor vagy oszlop, igényeitől függően és a rendelkezésre álló készletek, mint megy átlósan a táblázatot, hogy befejezze kitöltése a ketrec (m, n), átvevő a referencia oldat.
2. A minimális elem módszer. Között a sejtek, válassza ki a cellát a legalacsonyabb KW és elkezd kitöltésével ebben a cellában, vagy igény kielégítésére vagy lebontó tartalékok (ha ilyen sejtek kevés, akkor töltse ki az összes sejt). Ezután folytatjuk a cellák kitöltését nagy tarifákkal, amíg teljes mértékben lemerítjük a kínálatunkat, vagy kielégítjük a keresletet.
A Fogel approximáció módszere. Bármelyik iterációnál minden sor és minden oszlop esetében megtaláljuk a különbséget a két minimális díjszabás között, és írjuk meg őket a táblázat egy külön sorában és oszlopában. A különbségek közül a legkisebbet választjuk. A különbségnek megfelelő sorban vagy oszlopban a minimális díjszabást találja meg, és töltse ki a cellát ezzel a tarifával ezen az iteráción, akár kifogyja a készleteket, vagy kielégíti az igényeket. Ha a minimális üteme megegyezik több a kiválasztott sorban vagy oszlopban a sejtek, akkor úgy dönt, hogy töltse ki a ketrec, amely található egy oszlopban vagy sorban, illetve a legnagyobb különbség a két minimális mértékének ebben az oszlopban vagy sorban.
Megjegyzés: Ha a töltött sejtek kevesebb volt, mint m + n-1, akkor az eredményül kapott készlete bizonyos hozzáfűzi „0” sejtek, úgy, hogy az összes töltött sejtek válnak m + n-1.
Algoritmus a közlekedési probléma potenciál módszerével történő megoldására.
1. Hozzon létre egy szállítási probléma megoldását a fenti három módszerrel. Minden egyes referencia-megoldáshoz keresse meg az objektumfüggvény értékét, és állítsa le azt az értéket, amelyre ez az érték minimális.
2. Keresse meg a töltött cellák potenciálját.
3. Üres cellák esetén ellenőrizze az optimális állapotot. Ha az optimális feltétel teljesül, akkor a kapott oldat optimális.
4. Egyébként a kijelölt cella (k, k), amelyekhez Uk + Vs> KW és épít asztal szállítási hurok tulajdonított sejt „+” jellel és váltakozó jelek az összes többi cella a ciklus.
5. A következő szabály szerint újraszámítjuk a táblázatot. Szükséges kiválasztani a r = min xij számot a ciklus "-" jelzéssel ellátott celláitól. A "+" jelzéssel ellátott ciklus sejtjeiben adja hozzá ezt a számot. A "-" jelzéssel ellátott ciklus sejtjeiben ezt a számot levonják. A ciklus fennmaradó sejtjei nem változnak, és a sejt, amelyben r találtak, nem töltötte be.
6. Visszatérünk a 2. pontba.
Egy példa. Oldja meg a szállítási problémát