Nyílt megoldás a közlekedési probléma
Nyitott modell megoldható azáltal, hogy a zárt modell.
Abban az esetben, (a) ha a teljes tartalék haladja meg a teljes kereslet, a fiktív felhasználó belépett Bn + 1. amelynek szüksége bn + 1 =
. Abban az esetben, (b), amikor a teljes igény meghaladja a teljes tartalék, bevezetett egy dummy Am + 1. tartalékok am + 1 =
A szállítás költségét, a rakomány egység fiktív ügyfél, és a költségeket a rakományt szállító egységek egy fiktív szállítót nullának, hiszen mindkét esetben az áru nem szállítható.
A transzformáció után a probléma formájában történik a zárt modell megoldott, és a szokásos módon. Azonos érték a rakományt szállító egységek a beszállítóktól a fiktív ügyfél szállítási költségek valós fogyasztók minimális, és az ügyfélnek meg kell küldeni egy dummy terhelés a legkevésbé jövedelmező beszállítók. Ugyanezt kapjuk tekintetében egy fiktív cég.
Megoldása előtt bármilyen közlekedési probléma, akkor először ellenőrizze, hogy melyik modell tartozik, és csak ezután, hogy a tábla megoldani.
1.3. Előállítására szolgáló módszerek a kezdeti támogatási program
Ami a másik probléma a lineáris programozás, iteratív folyamat találni az optimális terv a közlekedési problémát kezdődik a támogatási programot.
Tekintsük a rendszer korlátai (2) és (3) a közlekedési problémát. Ez tartalmazza m'n ismeretlenek és egyenletei m + n,
Kapcsolódó kapcsolatban (4). Ha összehajtogatott külön alrendszer termwise egyenlet (2) és a különálló alrendszert (3), kapjuk két azonos egyenletet. Ezen kívül egy ilyen táblázat egyenértékű túlmenően termwise rendre termwise hozzáadásával oszlopok és sorok.
Ez a rendszer határait két azonos egyenletek mutatja a lineáris összefüggés. Ha egy ilyen egyenletek dobni, akkor általában a rendszer korlátai kell tartalmaznia m + n-1 lineárisan független egyenletek
következetes volt, nem degenerált támogatási program szállítási feladat tartalmaz m + n-1 pozitív komponensek vagy szállítás.
Így, ha bármilyen módon, hogy egy nem degenerált támogatása a közlekedési problémát terv, a mátrix
(Xij) (i = 1, 2 m; j = 1, 2 n) értékekkel komponenseket (2. táblázat) csak a pozitív
M + n-1, a többi pedig nulla.
Ha a feltétele a közlekedési problémát és annak támogatási program kerül rögzítésre egy asztal, a sejt, amely eltér nullától szállítás, az úgynevezett elfoglalt, és a többi - nem foglalt.
Olyan sejteket felel ismeretlen, és a szám a támogatási program egy nem degenerált egyenlő
M + n-1. Ha a közlekedési problémát korlátozások írott formában (2) és (3), mint ismeretes, az alapvető ismeretlen, tartalmazza az alapvető tervet, a megfelelő rendszer lineárisan független vektor.
Minden terv a közlekedési probléma, több mint
M + n-1 alkalmazott nem támogatja a cellaazonosító, mert az felel lineárisan függő rendszer vektorok. Az ilyen feltételek a táblázatban mindig lehetséges egy zárt hurok révén, amelyek csökkentik a betöltött sejtek m + n-1.
Egy ciklus egy sor típusú sejtek (I1 J1) (i1 j2) * (J2 i2) (j1 im), amelyben két és csak két szomszédos cellák vannak elrendezve egy oszlopban vagy egy sorban az asztal, az utóbbi sejt ugyanabban a sorban vagy oszlopban, mint az első.
Ha egy foglalt cella meghatározása, a referencia terv egy nem degenerált, ezért nem gyűrűs, csatolja elfoglalatlan sejt, a terv válik hivatkozási van egy ciklusban minden alkotóeleme egy kivételével, amelyek használhatók a sejtekben.
Van néhány egyszerű rendszerek építése az eredeti támogatási program a közlekedési problémát.
Kidolgozásakor az eredeti referencia tervet az észak-nyugati sarkában az egység a szállítás költségét nem tartalmazza, így az épület tervei messze van az optimálistól, átvételét, amely kapcsolatban van a nagy mennyiségű számítási munkát. Ezért a fenti módszert használják a számítások és a számítógép segítségével.
módszerével minimális költségű szállítók készletek megkapnak a fogyasztók a legalacsonyabb áron. és eljárás kettős újraelosztó preferenciák előnyösen gyártott révén e sejtek, amelyeknek alacsony költség mind a szolgáltatók. és a fogyasztók számára.
Az ára a terv segítségével kapott a minimális érték és kevesebb, mint kétszerese a preferencia értéke a tervnek elő az észak-nyugati sarkában, így azok közelebb az optimális.
Egy minimális értéket és a vizsgálati módszerek kettős preferenciák ugyanazok, azok könnyen programozható. A kapott tervek beállítani az optimális lehetséges módszer.
1.4. A koncepció a kapacitás és a ciklus
Ha azt tervezi, X * = (x * ij) o szállítási feladat a legjobb, van egy sor m + n szám Ui * és Vj *. feltételeket teljesítő
(I = 1, 2, 3 m; j = 1, 2, 3 n).
Ui és Vj * szám * nevezzük potenciál, illetve a szállítók és a fogyasztók számára.
Bizonyítás. Közlekedési probléma minimalizálására egy lineáris függvény Z =
xij. 0 (i = 1, 2 m; j = 1, 2 n)
lehet tekinteni, mint egy kettős forrása lineáris programozási feladat, amelynek feltételei kapunk az általános rendszerben, ha minden egyes korlátozás xi1 + xi2 +. + Xin = ai az eredeti probléma megfelel változó Ui (i = 1, 2 m), valamint az egyes restrikciós x1j + x2j + xmj = BJ - változó Vj (j = 1, 2 n), nevezetesen, maximalizálja a lineáris függvény f =
(I = 1, 2 m; j = 1, 2 N).
X * egy terv optimális program a kettős probléma, így a terv Y * = (Ui *, Vj *) a terv az eredeti probléma, és ennek alapján a dualitás
Alapján a tétel a kettős probléma, azt találjuk, hogy a korlátozások az eredeti probléma, ami a pozitív összetevői optimális program a kettős probléma akkor teljesülnek, szigorú egyenlőség, és a megfelelő komponenseket nullára, ¾ az egyenlőtlenség t. E.
E tételből következik, hogy annak érdekében, hogy támogassa az eredeti terv az volt, hogy a legjobb, meg kell felelnie a következő feltételeknek:
a) minden egyes sejt által elfoglalt összege potenciálok egyenlőnek kell lennie a készülék szállítás költségét, áll a cellában:
b) Minden egyes üres sejtek összege potenciálok kisebbnek kell lennie, vagy egyenlő, mint az ára a szállítási egység, amely áll a cellában:
Ha legalább az egyik üres cellát nem teljesíti a feltételt (6), az alap terv nem optimális, és javítani lehetne beépítünk alapján vektorba megfelelő sejtbe, ami zavarta optimalitási feltétele (azaz. E. A sejt kell lépni egy bizonyos mennyiségű rakomány egységek ).
Így, hogy ellenőrizze a optimalitást először építeni egy potenciális rendszer.
Megépíteni a lehetséges felhasználása a rendszer állapotát
ahol Cij ¾ költsége a rakományt szállító egységek sejtek által elfoglalt az i-edik sorának és j-edik oszlop.
potenciális rendszer építhető csak nem degenerált támogatási program. Egy ilyen terv tartalmazza m + n-1 lineárisan független egyenletek formájában (5)
n + m ismeretlenek. Egyenletek eggyel kevesebb, mint ismeretlenek, így a rendszer nem definiált, és egy ismeretlen (általában Ui), így nulla. Ezután, a többi potenciálok egyedileg határozzuk meg.
Hagyja, hogy a potenciális ismert Ui; majd (5) egyenlettel
Ha tudja, hogy a lehetséges Vj. néhány azonos egyenletet, van
Így kivonni ismert képesség, hogy meghatározzuk az ismeretlen potenciál az elfoglalt sejtek Cij.
Állítsa egy tetszőleges halmaza forgalom közlekedés asztalra.
Lánc nevezett ilyen készletek, ahol mindegyik pár szomszédos sejtek a láncban vagy a rendezett egy oszlopban vagy egy sorban.
Egy ciklus egy lánc, a végén elemeit amely található vagy egy sorban vagy egy oszlop.
1.5.Kritery optimális lúgos oldatot a közlekedési probléma
Alap ellátási felosztás akkor optimális, ha és csak akkor, ha az összes rendelkezésre álló sejtek nagyobb, mint nulla. A sejtmentes építési konverziós ciklus, és a csúcsai a ciklus terjedt szekvenciáját összeszőtt szimbólumai kezdve egy plusz jel a szabad cella. Ahhoz, hogy a kínálat a táblázat a költségek együtthatók minden sorban és minden oszlopban kell hozzáadni, például számok (potenciálok) költség arány a töltött sejtek válnak nullával egyenlő.
Az eredmények tehát input együtthatók becsült szabad sejtek ezen sejtek.
1.6. A terjesztési módszert megoldására közlekedési probléma
Az egyik legegyszerűbb módszer megoldására közlekedési probléma - elosztási módszer.
Tegyük fel, hogy a közlekedési problémát talált kezdeti támogatást megoldás
és a számított érték a célfüggvény a döntés Z (
). By tétel minden probléma mentes sejtek a táblázat csak építeni egy hurok, amely a sejt és részben a sejtek által elfoglalt összehasonlító oldat. Jelentése a ciklus és végezzen eltolódás (újraelosztása terhelés) a ciklus egy összeget
, akkor kap egy új összehasonlító oldat X2.
Határozzuk meg, hogyan kell változtatni a célfüggvény az átmenet során egy új támogatási megoldást. Amikor változó rakatot a ciklus megfelelő sejt (l, k), a növekmény a célfüggvény
egyenlő a különbség a két összeg közötti:
- az összeg a szállítási költsége rakományegységekhez a páratlan ciklus jelölt cellák a „+”
- az összeg a szállítási költsége rakományegységekhez páros ciklusban a jelölt cellákra
A sejteket jelölt a „+” terhelési érték hozzáadott, amelyek növekedéséhez vezet a célfüggvény Z (
) És a jelölt cellák „-” a terhelési értékek csökkennek, ami csökkenti az értékét a célfüggvény.
Ha a különbség összegzi a szabad sejteket (l, k) kisebb, mint nulla, azaz a
<0, то перераспределение величины
az adott ciklus csökkenti az értéket Z (
, azaz a referencia-oldat lehet javítani. Ha az érték a
, úgynevezett becsléseket. minden szabad közlekedési problémát a táblázat sejtek nem-negatív, akkor az érték a célfüggvény nem csökkenthető, és az összehasonlító oldat optimális. ezért
optimalitási feltétele az elosztási módszer
Hogy oldja meg a közlekedési problémát a terjesztési módszert kell találni a kezdeti támogatási megoldás. Ezután, a következő referencia cella (l, k), és kiszámítja a épít ciklus értékelése
. Ha az értékelés nem negatív, az átmenetet a következő rendelkezésre álló sejt. Ha az eredmény negatív, akkor végre kell hajtani ellensúlyozza az összeg ciklus
. Az eredmény az lesz az új referencia oldat.
Minden egyes új referencia oldatok kiszámítása értékelések kezdődik az első szabad táblázat sejtek. Ellenőrizhető bizonyítékot szabad sejtek ajánlatos telepíteni szerint növekvő sorrendben a szállítás költségét
, igen, hogyan lehet megoldani a problémát, hogy találnak egy minimum.
2. Fejlesztési és leírása algoritmus a probléma megoldására
2.1. Értelmes állítás a probléma
Legyen gazdasági-matematikai modellt a probléma. Keresse meg a legjobb elosztás és a kínálat minimális szállítási költségeket. A kezdeti eloszlása kellékek eljárás végrehajtására az észak-nyugati sarkában.
A gyakorlatban ezek a problémák megoldódnak, természetesen, segítségével különböző szoftver, amely jelentősen egyszerűsíti a munkát és időt takaríthat meg.
Lássuk, hogyan lehet ezt tenni egy olyan környezetben, a Microsoft Excel táblázatkezelő.
A Microsoft Excel táblázatkezelő ilyen problémák megoldása biztosított Solver. Végezze el az alábbi előkészítő munka a megoldás a közlekedési problémát a Solver a Microsoft Excel táblázatkezelő alkalmazás.
1. Írja be az A6 cellatartományt: D8 érték kereslet
2. Írja be a cellatartományt A9: D9 mátrix költségeket.
3. Írja be a cellatartományt E6: E8 készletek.
4. A sejt, E9 optimális teljesítmény határozatot
= SUMPRODUCT (A1: D3; A6: D8). Ez megtehető a Függvénytündér kiválasztásával részben. Matematikai funkció SUMPRODUCT és megadja a kívánt tartományban.
Ezután válassza ki a parancsot szolgáltatás, keresd a megoldást, és töltse nyissa meg a keresési párbeszédablak megoldásokat.
A Keresés párbeszédpanelen jelölje be opciók megoldások lineáris modellt. A gomb megnyomása után. Run-making keresője megtalálja a legjobb tervet a szállításokról és a megfelelő szállítási költségeket.
Az optimális megoldás a közlekedési probléma