Szállítási feladat
Tisztelt kollégák,
A célkitűzések a lecke nem előadást az elmélet során matprogrammirovaniya, és egy egyszerű cél -, hogy bemutassák a gyakorlati alkalmazása a tudás, amit kap a folyamat tanulmányozása a „Mathematical Programming” során a magasabb matematika. Ezért a bemutatás a lehető legegyszerűbb, de nem teljesen "kanonikus".
Szállítási feladat
A négy pont a származási egyenletes terhelés koncentrálódik mennyiségben A = (90; 60; 70; 40), amely kell venni négy fogyasztók követelnek B = (30; 50; 90; 90) a rakományegység szállítási költség láthatók a mátrixban tarifa C :
2,4,5,1
3,7,6,2
1,3,4,2
4,5,2,6
Keresse meg a kellékek optimális elosztását és a minimális szállítási költségeket.
A megoldás.
A kezdeti állapotot csökkentjük a táblázathoz:
Szállítók és erőforrásaik
A fogyasztók és igényeik
A probléma megoldásához, ellentétben az univerzális szimplex módszerrel, egyszerűbb, de sokkal nyilvánvalóbb megoldási módszereket alkalmazunk. A kezdeti szállítási terv az észak-nyugati sarok módszerével érhető el. A fogyasztók elégedettsége, a megrendelés figyelembevétele a bal felső sarokban.
Szállítók és erőforrásaik
A fogyasztók és igényeik
Amint az eredeti tervből látható, az ellátás egyenlő a szükségletekkel, vagyis a feladat "zárt" vagy kiegyensúlyozott. Becsülje meg a szállítás kezdeti költségét:
2 * 30 + 4 * 50 + 5 * 10 + 6 * 60 + 4 * 20 + 2 * 50 + 6 * 40 = 1090
A választott terv optimumát a potenciál módszerével becsüljük. Ehhez két további oszlopot ismertetünk - az alfa és a béta. Az első sor nulla értékű. Ebből kiindulva kiszámítjuk az összes többi értéket (lásd a táblázatot).
A számítás elve azon a tényen alapul, hogy a béta [j] - alfa [i] = C [i, j], azaz a kiegészítő sor és oszlop értékei közötti különbség megegyezik a szállítás költségével (költségével). Mivel az 1. sorozatot nullának tekintettük, akkor β [j] - 2 = 0, és az első oszlop értéke 2.
Szállítók és erőforrásaik
A fogyasztók és igényeik
Most meghatározzuk az egyes cellák azon potenciálját, amelyek nem vettek részt az eredeti tervben, ugyanazt a béta formulát alkalmazva [j] - alpha [i] = C [i, j]. Az így kapott szám azonban megegyezik a szállítás "pszeudo-költségével". Számítsuk ki a béta [j] - alfa [i] - C [i, j] értékét. A különbséget a cella bal alsó sarkában tesszük. Tegye a következő táblázatot:
Szállítók és erőforrásaik
A fogyasztók és igényeik
Most válassza ki a tartócellát. A legkisebb érték a cella (4; 3) - a potenciális különbség -6. Új tervbe illesszük. Ennek megfelelően az oszlopot és a sorokat a tervben már szereplő más cellákhoz kell igazítani. Természetesen a kiigazításnak meg kell tartania a forgalom nagyságát - a források soronként nem lehet több, mint a raktárban, és az oszlop nem több, mint amennyi a rendeltetési helyen van.
Szállítók és erőforrásaik
A fogyasztók és igényeik
Költségei szállítás a terv szerint összeg 2 * 30 + 4 * 50 + 5 * 10 + 6 * 60 + 2 * 20 + 2 * 70 + 6 * 20 = 970. Amint látható, a terv az volt optimálisabb, mint az eredeti. Az új terv potenciáljának módját alkalmazzuk. Megkapjuk a táblázatot:
Szállítók és erőforrásaik
A fogyasztók és igényeik
Most újra meghatároztuk az egyes cellák potenciálját, amelyek nem vettek részt a tervben, a béta [j] - alfa [i] = C [i, j] képlet segítségével. Számítsuk ki a béta [j] - alfa [i] - C [i, j] értékét. A különbséget a cella bal alsó sarkában tesszük. Azonnal határozza meg a támogató sejtet. Tegye a következő táblázatot:
Szállítók és erőforrásaik
A fogyasztók és igényeik
Ennek a tervnek a szállítási költsége 2 * 30 + 4 * 50 + 6 * 60 + 2 * 30 + 1 * 10 + 2 * 70 + 6 * 10 = 890 lesz. Mint látható, a terv az optimálisabbá vált, mint az eredeti. Az új terv potenciáljának módját alkalmazzuk.
Szállítók és erőforrásaik
A fogyasztók és igényeik
Szállítási költségek a terv szerint mennyiségét a 2 * 30 + 4 * 50 + 6 * 50 + 2 * 40 + 1 * 10 + 2 * 10 + 2 * 70 = 810. Mint látható, a terv az optimálisabbá vált, mint az eredeti. Az új terv potenciáljának módját alkalmazzuk.
Szállítók és erőforrásaik
A fogyasztók és igényeik
Ennek a tervnek a szállítási költsége 1 * 30 + 4 * 50 + 6 * 50 + 2 * 40 + 1 * 40 + 2 * 10 + 2 * 40 = 750. A következő terv potenciáljának módját alkalmazzuk.
Szállítók és erőforrásaik
A fogyasztók és igényeik
Költségei szállítás a terv szerint összeget 1 * 30 + 4 * 10 + 3 * 40 + 6 * 50 + 2 * 40 + 1 * 80 + 2 * 10 = 670. A következő terv potenciáljának módját alkalmazzuk.
Szállítók és erőforrásaik
A fogyasztók és igényeik
Ennek a tervnek a szállítási költsége 2 * 10 + 1 * 20 + 3 * 50 + 6 * 50 + 2 * 40 + 1 * 80 + 2 * 10 = 670 lesz. A következő terv potenciáljának módját alkalmazzuk.
Szállítók és erőforrásaik
A fogyasztók és igényeik
Mivel minden kiszámított relatív potenciál nullánál nagyobb (potenciálkülönbség negatív), a terv optimális.
Válasz.
10,0 0,80
0,0,50,10
20,50,0,0
0,0,40,0.
Szállítási költségek.
Kattintson az oldal ajánlása másoknak: