Nyílt típusú szállítási feladat
Ha az egyik feltétel teljesül a szállítási feladathoz
akkor a probléma modellje nyílt. Annak érdekében, hogy ez a feladat megoldást nyerhessen, zárt típusúnak kell lenni, azaz. hogy az egyenlőség teljesüljön.
Ez a következőképpen történik: if. majd adj hozzá egy fiktív fogyasztót a kereslethez (az elosztási táblázatban további oszlop lesz), ha. akkor egy fiktív beszállítót ad hozzá egy javaslattal (egy további sor jelenik meg a terjesztési táblázatban). Mindkét esetben a díjak nullának számítanak. Ezenkívül a probléma a korábban megfogalmazott sorrendben oldódik meg.
Írjuk le az algoritmust a közlekedési probléma megoldására:
1) Ellenőrizze a TK modell típusát.
2) A kezdeti támogatási terv elkészítése (bármilyen módszerrel).
3) A degenerációra vonatkozó terv ellenőrzése.
4) Az optimalitás tervének ellenőrzése a potenciál módszerével:
a) megkeressük a potenciálokat a rendszerből
(minden töltött cellához);
b) a második optimalitási feltétel ellenőrzése
(minden üres cellához).
5) Átmenet a legszegényebb támogatási tervhez (ha szükséges).
Egy példa. A raktárakban ugyanazon típusú áruk állnak a (35, 40, 40, 50) mennyiségben, amelyeket a fogyasztóknak kell átadniuk. A fogyasztók igényeit a b (31; 52; 17; 20) vektor adja. Az i. Szállítótól a j-os fogyasztóhoz tartozó áruegység szállítási költségmátrixa:
Készítsen egy szállítási tervet minimális szállítási költségekkel.
A megoldás. Határozza meg a közlekedési probléma típusát. A szállítók teljes kapacitása: 35 + 40 + 40 + 50 = 165 (áruegység); A fogyasztók teljes kereslete: 31 + 52 + 17 + 20 = 120 (áruegység).
mert . akkor van egy nyílt típus modell.
Bemutatunk egy olyan fiktív fogyasztót, akinek a kereslete van
165-120 = 45 (termékegységek).
Díjak 0.T. zárt típusú modellt kapunk, m = 4 a beszállítók száma, n = 5 a fogyasztók száma. A problémamátrix rangja. A kezdeti támogatási tervet a minimális elem módszerrel állítjuk össze (legalacsonyabb költség).
A 8 elosztási táblázatban töltött cellák száma megegyezik az r = 8 problémamátrix rangával, ezért a támogatási terv nem degenerált.
A támogatási tervnek megfelelő szállítási költségek:
Vizsgáljuk meg az optimális támogatási programot a potenciál módszerével.
Az 1. táblázatot oszlopokkal és potenciálsorokkal egészítjük ki. Az első optimalitási feltételt használva a potenciális rendszert találjuk: a szállítással töltött sejtek esetében.
A rögzített rendszerből :. . . . . . . . .
Ellenőrizzük a második optimalitási feltétel teljesülését. Minden üres cellához a következő egyenlőtlenséget kell teljesíteni :.
(1; 1) 0 + 1 - 5 = -4 0;
(1; 2) 0 + 2 - 4 = -2 0;
(1; 5) 0 - 4-0 = -4 0;
(2; 3) 1 + 3 - 5 = -1 0;
(2; 4) 1 + 1 - 8 = -6 0;
(2; 5) 1 - 4 - 0 = -4 0;
(3; 1) 4 + 1 - 6 = -1 0;
(3; 2) 4 + 2 - 8 = -2 0;
(3, 3) 4 + 3 - 7 = 0 0;
(3; 4) 4 + 1 - 10 = -5 0;
(4; 1) 4 + 1 - 5 = 0 0;
(4; 4) 4 + 1 - 2 = 3 0.
mert a szabad sejtek között vannak azok, amelyekben a második optimalitási feltétel nem teljesül, akkor a terv nem optimális.
A nem rosszabb támogatási tervre való áttérés. A legígéretesebb a cellának kitöltésére (4; 4), mert ez a legnagyobb pozitív becslésnek felel meg
Találjuk meg a rakomány újraelosztásának ciklusát ehhez a cellához.
A kijelölt cella "+" jelzéssel van ellátva, majd váltsa fel a jeleket. A csúcspontok között a "-" megjelölés választja ki a legalacsonyabb szállítást.
A szállítmányokat egy ciklusra osztjuk szét, így átkeressük az új alaptervet.
A támogatási tervnek megfelelő szállítási költségek:
Vizsgáljuk meg az optimalitás támogatási programját. Találjuk meg a potenciál értékeit az első optimalitási feltétel használatával. A készletekkel töltött sejtek esetében.
Ellenőrizzük a második optimalitási feltétel teljesülését. Minden üres cellához a következő egyenlőtlenséget kell teljesíteni :.
Kiírjuk azokat a sejteket, amelyekben a feltétel sérül:
(1; 2) 0 + 5 - 4 = 1 0.
A nem rosszabb támogatási tervre való áttérés. A legígéretesebb a cellák töltéséhez (1; 2), mert Ez egy pozitív pontszámnak felel meg. Lássuk a rakomány újraelosztásának ciklusát ehhez a cellához.
A 8 elosztási táblázat töltött celláinak száma megegyezik a r = 8 probléma mátrixának rangával, ezért a támogatási terv (3. táblázat) nem degenerált.
A támogatási tervnek megfelelő szállítási költségek:
Vizsgáljuk meg az optimalitás támogatási programját.
Találjuk meg a potenciál értékeit az első optimalitási feltétel használatával. A készletekkel töltött sejtek esetében.
Ellenőrizzük a második optimalitási feltétel teljesülését. Minden üres cellához a következő egyenlőtlenséget kell teljesíteni :.
A második optimalitási feltétel minden szabad sejtre érvényes, ezért a terv optimális.
A legkisebb szállítási költség.
A :; Az optimális terjesztési terv a 3. táblázatban található.
Hozzárendelések független munkához.
Készítsen egy szállítási tervet minimális szállítási költségekkel.