Szállítási feladat
MI Reitman
Szállítási feladat
Joe veszi a Bate tervet
# 150; Minden rendben van, szeretem a művelet tervét, Bate, # 150; - kérdezte Joe, megkerülve egy olcsó hotel számát, és leeresztette a szivar minden szagát egy jó korty whiskyvel. Az öreg Bate egy szenvedélyes kandallóban ül egy karosszékben, szokásosan érezte a pisztoly karját a hónaljával.
# 150; Természetesen! # 150; Bate feszítette a mesterséges fogait. # 150; Nem minden, hogy minden állam rendészete tizenöt éven át üldözött. Nem valószínű, hogy ilyen áron lennék, ha csak a sárgaréz csuklókat lehetett volna vezetni. Tudományos hírek # 150; Itt van a hobbijaim. Ne felejtsd el, Joe, ez az első alkalom, amikor egy bankrablásba vezettem helikoptereket. És ahogy én.
# 150; Várj egy percet! # 150; Joe félbeszakította büszke kollégáját. # 150; Köszönöm, ezért dolgozom veled. És ez az új ötleted # 150; hogy egy éjszakára három manufaktúra-raktárat tisztítsanak meg # 150; szintén gyönyörű. De a sofőrök.
# 150; Ezek vasemberek! # 150; - kiáltotta Bate. # 150; Bízhatsz benne! Egyik fáraó sem fogja ezeket kapni!
# 150; Bízom ezeket a srácokat, Bate. De az ár! 10 dollár egy tonnányi mérföldre a teherautóknál # 150; Igen, ilyen áron kéznél vagyok! Tönkremegyünk, még akkor is, ha minden ég.
És Joe egy olcsó szállodai széken mutatott rá, hogy készen áll a teherfelvételre. Az asszony sajgóan felkiáltott: ilyen szállodákban volt, hogy Joe szerette a nehéz műveletekről beszélni, kevésbé valószínű, hogy megbotlik egy rejtett rendőri mikrofonon.
# 150; De ne felejtsd el, Joe, mi kockáztatják a srácok. És ráadásul. Ügyeltem arra, hogy kevesebbet fizessek. Nem, ne, ne csaljon # 150; ilyenekkel nem fog működni. A lényeg teljesen más: alkalmazom a tudományos módszert.
Joe tisztelettel nézett Bate-re (végül is egyetemi végzettséggel), de ellenezte:
# 150; Figyelj, Bate. Értsd meg, sok pénzt, több ezer dollárt fektek be. Szeretnék kezdeményezőnek lenni az ügy szívében. Csak egyszerűbb vagy, tudod, inkább egy zsebtáska vagyok.
# 150; Jól van, Jo, # 150; Bate komolyan bólintott, és rájött, hogy mindenféle pedagógiai képességét meg kell fosztani, különben a dolgok nem mennek el, és ő is elfutna.
# 150; Hány lopott kereskedő vesz el a manufaktúrát?
# 150; Négy. Az első két hatvan tonna, a másik kettő # 150; negyven.
# 150; És mennyi a raktárban, emlékszel?
# 150; Nevetsz, Bate? Még egy álomban is emlékszem ezekre a számokra: 75, 75 és 50.
# 150; Jól van, Joe! Hadd írjam le mindent az asztalról.
Bate elhúzta a falon lógó naptárat, és a hátlapon lévő 1. táblázatot ábrázolta.
# 150; És az egyes cellák jobb felső sarkában van itt. # 150; Bate elkezdődött, de Joe megszakította.
# 150; Oh! Jobb, ha nem ismerem ezeket a számokat! Persze, felismerem őket! Annyi ilyen unokája az ördögtől egy tonna rakomány szállítására kér minden egyes útvonalat. Például 100 dollár / tonna a harmadik raktártól a negyedik vevőig, 10 mérföld van. Nem, jobb, ha magam kapom!
# 150; A srácok kockázatot vállalnak, Joe, # 150; Bate kifogásolta. # 150; Nevezzük ezeket a költségeket. Szóval, hogyan viseljük? Mely útvonalakon?
# 150; Világos, hogy ahol olcsóbb, # 150; - mormogta Joe, és egy piszkos trükköt érzékelt.
# 150; Ez így van! Vegyük az útvonalakat, ahol az útvonalak kisebbek. Olcsóbb az árut szállítani az első raktártól a negyedik vevőig # 150; csak ötven dollárt. Nevezzük ezt az utat az útvonalnak (1.4). Biztosan használjuk!
# 150; Természetesen! És meg kell venni, amennyire csak lehetséges!
# 150; Ez így van! De több mint 40 tonna nem fogsz szállítani # 150; a negyedik vevő nem fogadja el, ő is vállal kockázatokat. 40 tonna rakunk erre az útvonalra, és az útvonalon (3,2) # 150; 50 dollár is van # 150; 50 tonna: több a harmadik raktárban, amit nem! Megkapom a 2. táblázatot. Itt vagyok ugyanakkor korrigáltam a kapacitást és a szükségleteket. És a jövőben azokra az útvonalakra is szállítjuk a szállítást, ahol kisebb a díjszabás.
# 150; Nos, rendben van! # 150; Joe dörzsölte a kövér kezét. # 150; 35 × 150 + 40 × 50 + 60 × 60 + 10 × 70 + 5 × 90 + 50 × 50 = 14 500 dollárt fogunk csinálni. Nem, öreg Bate? Ezt nevezik tudományos módszernek? Fogadok a dollárral öt centrel, hogy minden rendőr meg fogja találni, hogyan találja meg ezt a szállítási tervet 14 500-ra # 150; ooh ooh- # 150; 14 500 dollár. Igaz, az útvonalat (1,3) # 150; 150 dollár tonnánként, # 150; Joe komoran nézett az asztalra.
# 150; Ja, Joe, # 150; itt az ideje Baita győzelemre. # 150; A tudománynak még szüksége van rá? Nagyon ésszerűen indokoltak, de mindazonáltal a legdrágább útvonalon futtak. Most próbáljuk megjavítani a szállítási tervet. Töltött rakományt rakunk az útvonalra (1,1).
# 150; Nem fog működni, # 150; kifogásolta Joe. # 150; Az első oszlop egyensúlya megszakad, ha tudok valamit ebben a kérdésben.
# 150; Meg fogja érteni, tudod, # 150; megnyugtatta Bate. # 150; De az egyensúly visszaállítható úgy, hogy egy tonna az útvonalról (2,1), nem igaz?
# 150; Várjon, majd a másodikban nem lesz egyensúly # 150; tonnánként kevesebb. Bár, bár. ha még egy tonnát adsz hozzá (2,3) és eltávolítod az (1,3) -ból, úgy tűnik, minden rendben lesz.
# 150; Képzeljük el ezt az új 5. táblázatban (már nincs szükség kapacitásokra és szükségletekre).
# 150; Ahol hozzáadtam egy tonna, van egy plusz jel, és hol tisztítottam # 150; mínusz. És azon sejtek készletét, amelyekben változtattak, nevezzük ciklusnak *. Tehát mi ad nekünk? Az útvonal egy tonna szállítása (1,1) # 150; 80 dollár. Hozzá kell adni őket. És 150 dollár # 150; tonna szállítása az útvonalon (1,3) # 150; éppen ellenkezőleg, valamint 60 másodperc az útvonalról (2,1). Nos, 90-et kell hozzá extra tonna az útvonalon (2,3). Összesen, a szállítási költségek 80 + 90-cel változnak # 150; 150 # 150; 60 = # 150; 40
# 150; Nagy! 40 dollár menthető! # 150; csodálta Joe. # 150; De ezt az útvonalon (1,4) csak egy tonnát tettük fel. Tegyünk fel 100 tonna, és mentse 4000, vagy sem, tedd 400 tonna, és akkor mi lesz fizetni extra!
Joe szemében a kapzsiság égett, de azonnal kiment:
# 150; Nem, itt valami nincs rendben.
# 150; Nyilvánvaló, hogy nem így van, # 150; Bate egyetértett. # 150; Végül is, hogy mennyi az útvonalhoz (1,1) adunk hozzá, ugyanazt el kell távolítani (1,3) és (2,1). És onnan legfeljebb 35 tonnát távolíthat el. Nem akarod a gyárat visszavenni a raktárba!
# 150; Ez azt jelenti, hogy legfeljebb 35 tonna szállítható az útvonal mentén (1,1); ez 40 × 35 = 1400 dollárt takarít meg, és az új szállítási terv ugyanaz lesz, mint a 6. táblázatban. A ciklusban nem szereplő sejtek mindegyike megegyezik.
# 150; 1400 dollár # 150; kerek összeg! Ellenőrizzük az üres cellákat. Talán eljutunk az útra, ami szintén érdemes használni. Kezdjük például a cellával (1,2). Ő számára a költségek 120 + 60-ra változhatnak # 150; 70 # 150; 80 = 30> 0.
Ezer ördög! Nem szükséges az útvonal (1,2) használata. És talán kihasználni.
# 150; Ne zavarj, Joe. Már ellenőriztem: maga a Danzig nem fog többet kihasználni ebből a tervből.
# 150; Danzig, Danzig. ez nem az, amely megtisztította a Bank of. „?
# 150; Nem, Joe, ő nem a miénk. Ez volt az, aki feltalálta ezt a módszert. Igaz, néhány piros előtt.
Inspector Cliff irodájában ült Avenue Street, újra és újra, bámulva a valódi bizonyíték: három mesterien törni a zárat, és a hamu az égett naptári óvatosan a szállodában, ahol tanácsot rablók. És semmi több. És mégis. emlékeztet Bate kézírására, amiért Cliff, sok éven át vadászik! Például egy naptárat. Miért? Talán ez történt rajta? Talán. De hol találja Baitát?
# 150; Őrmester, tedd le! Mellékelni az állami tudományi könyvtárat! Számomra # 150; gép és egy bilincs!
Mi menthetett a szállítási költségekre 1,400 dollárért? Legyünk kövessük az ügyes gengszterek cselekedeteit. Először Baith talált elfogadható szállítási tervet. A mód, ahogyan ő tehát úgy nevezett eljárás minimális elem, és az is világos, hogy miért: a közlekedés minden alkalommal fel útvonalakon minimális tarifák, és ha van két útvonal azonos tarifális preferencia, persze, meg kell adni, hogy az, amelyre ez lehetséges többet hordoz.
Miután megkapta a megvalósítható tervet, Bate és Joe megpróbálta javítani az elosztási módszerrel. Ez talán a legegyszerűbb, de nem a leggyorsabb módja a szállítási terv javításának. De mielőtt bemutatnánk ezt a módszert általános formában, a lineáris programozás szigorúan szállítási problémáját fogalmazzuk meg.
Legyen m szállítók (raktárak) és n fogyasztók, ai # 150; az i-es raktár kapacitása, és bj # 150; a jth felhasználó igénye. Tegyük fel, hogy xij # 150; szállítást az i. szállítótól a j-os fogyasztóhoz. Csak olyan szállítási tervek fogadhatók el, amelyekhez **
A megfogalmazott probléma # 150; ez a lineáris programozási probléma speciális esete, mivel az "objektív függvény" (2), a szállítási költségek és a korlátok (1) kifejezése lineáris.
Az elosztási módszer lényege, hogy minden szabad sejt esetében van egy ciklus, amely mellett csak a töltött sejtek tartoznak. Ennek a ciklusnak köszönhetően meg kell határozni, hogy a szállítási költségek milyen mértékben fognak változni, ha a rakományegységbe bejut a szabad cellába. Ezt a mennyiséget kij a szabad cellás indexnek (i. J) nevezzük. Ha kij <0, то в клетку вносится максимально возможная перевозка (она равна минимальной перевозке в «отрицательных» клетках цикла), а если kij ≥ 0, то маршрут (i. j ) использовать не стоит и проверяется следующая клетка. Процесс заканчивается, когда выясняется, что для всех свободных клеток kij ≥ 0.
Az optimális tervet olyan tervek között kell keresni, amelyekben a töltött sejtek nem ciklikusak. Általában a szállítási feladatban a töltött cellák száma pontosan m + n # 150; 1, és a ciklus egyedileg állítható össze (például a megfontolt probléma esetén a töltött sejtek száma 3 + 4 # 150; 1 = 6). Ha a ciklusban a "+" jelű szabad cellákat is felveszi, akkor a terv megváltoztatása után kiderülhet, hogy több mint m + n # 150; 1 töltött sejt, és a terv tartalmaz ciklusokat. Ezt ellenőrizheti az 5. táblázatban egy ciklus (1,1) → (1,4) → (2,4) → (2,1) létrehozásával.
Ha a töltött sejtek száma kisebb, mint m + n # 150; 1 (ez a probléma degeneráltnak nevezhető), akkor egy ciklus megépítése érdekében üres cellákat kell hozzáadni a sejtekhez úgy, hogy ne képezzenek ciklust a már kitöltöttekkel. Tegyük fel például, hogy a 7. táblázat egy degenerált szállítási tervet határoz meg (nincs teljes cellája).
Itt felveheti a töltött cellák számát (1,3) vagy (2,1), vagy (2,2) vagy (3,3). Ezt követően létrehozhat egy hurokot minden szabad cellához. És ha a cella közé (3,1), amely egy ciklus a sejtek (1,1), (1,2), (3,2), az építmények ciklus zártcellás még mindig nem. Lássuk, mi adott nekünk egy nulla cellát.
Az első szállítási terv költségei z1 = 25 × 3 + 30 × 2 + 40 × 4 + 50 × 6 = 595.
Keresse meg a szabad cellák indexeit:
Az útvonalon (2,1) a szállításhoz előnyös, de mennyit hordozhat vele? min (25,0) = 0. Így az útvonalon (2,1) csak 0-os szállítást lehet elhelyezni, akkor megkapjuk a 8. táblázatot.
Az új terv költségei ugyanazok maradnak: z2 = 595. Mindazonáltal, a nulla átvitel mûködése nem értelmetlen: most már az indexek is változni fognak. Valóban, most k13 = 3 + 3 # 150; 3 # 150; 4 = # 150; <0.
Ez most kiderül, hogy nyereséges útvonal (1,3). A 25 tonna szállítással történő közlekedés a z3 = 595 szállítási költségeket eredményezi # 150; 25 = 570.
A matematikai modell, amelyet Bate alkalmazott, # 150; A lineáris programozás közlekedési problémájának modellje, # 150; most nagyon széles körben használják a gazdaság és a termelés menedzsment. Az ilyen modellek segítségével sok helyen kezelik a termékek szállítását üzletekbe és téglákba az építési területekhez képest, így jelentősen csökkentik a szállítási költségeket.
A szállítási probléma megoldásának leírt módja hátránya a ciklusok létrehozásának szükségessége, amikor egy gépre számolva ez a probléma megoldásához szükséges idő nagy részét veszi igénybe. Ezért elterjedése más megoldási módjait, a közlekedési probléma, ami csökkentheti a ciklusok számát figyelembe (lehetséges eljárást, először javasolta a szovjet tudósok), vagy nem igényelnek az építési ciklus. Ha a raktárak száma vagy a fogyasztók száma nem túl nagy (legfeljebb 3 # 150; 4), akkor dinamikus programozásra van szükség.
A szállítási feladatnak számos fajtája van, és a leginkább váratlan alkalmazások. Az egyik ilyen alkalmazás, amelyet most megvizsgálunk.
Hozzárendelési feladat
Két idős úriember egy állam szép könyvtárában ült.
# 150; Biztos vagyok benne, hogy a vérhúrok nem ragadnak ide. Tehát a bankban 4 bejárat van. Mind a fiúk egyetértenek abban, hogy minden, de úgy tűnik, hogy a különböző veszélyes: az egyik bejárat ügyeletes rendőrségi autó, a többi megy a forgalmas utcán, a harmadik ajtó túl szűk. A dollárra vonatkozó követelményeket a 9. táblázat foglalja össze.