MI Reitman
Activitate de transport
Joe ia planul Bate
# 150; Totul e bine, îmi place planul operației, Bate, # 150; spuse Joe, trecând în jurul numelui unui hotel ieftin și spălând fiecare puf de țigară cu o gustare bună de whisky. Old Bate stătea într-un fotoliu lângă un șemineu mizerabil, simțind în mod obișnuit brațul pistolului cu axile sale.
# 150; Bineînțeles! # 150; Bate sa strecurat prin dinții artificiali. # 150; Nu este nimic de care poliția tuturor statelor a urmărit după mine timp de cincisprezece ani. Este puțin probabil să fi intrat într-un astfel de preț, dacă aș fi putut purta mănunchii de alamă. Stiri stiintifice # 150; Aici este hobby-ul meu. Ține minte, Joe, e prima dată când am introdus elicoptere într-un jaf de bănci. Și cum fac eu.
# 150; Stai puțin! # 150; Joe îl întrerupse pe colegul său lăudător. # 150; Te apreciez, de aceea lucrez cu tine. Și aceasta este noua ta idee # 150; să curețe pentru o noapte trei depozite cu o fabrica # 150; este, de asemenea, superba. Dar șoferii.
# 150; Sunt tipi de fier! # 150; exclamă Bate. # 150; Te poți baza pe ele! Faraon nu le va primi!
# 150; Am încredere în tipii ăștia, Bate. Dar prețul! 10 dolari pentru un ton-mile pe camioane # 150; Da, pentru un astfel de preț, sunt pregătit să-l duc manual! Suntem distruși, chiar dacă totul arde.
Și Joe a arătat pe un scaun de hotel ieftin cum era gata să transporte încărcături. Scaunul trosnit plângăreț: este în aceste hoteluri este iubit Joe negocieze operațiuni dificile, acestea sunt mai puțin probabil să se poticnească pe un polițist microfon ascuns.
# 150; Dar nu uitați, Joe, ce băieți riscă. Și pe lângă asta. Am avut grijă să le plătesc mai puțin. Nu, nu trișa # 150; cu astfel de nu va funcționa. Ideea este destul de diferită: voi aplica metoda științifică.
Joe se uită la Bate cu respect (la urma urmei, el a absolvit o dată la colegiu), dar încă a obiectat:
# 150; Ascultă, Bate. Înțelegeți-mă, investesc foarte mulți bani, mii de dolari. Vreau să fiu inițiat în centrul chestiunii. Numai tu esti mai simplu, stii, sunt mai mult un buzunar.
# 150; Bine, Jo, # 150; Bate încuviință din cap în serios, realizându-și că trebuie să-și strice toate abilitățile pedagogice, altfel lucrurile nu vor dispărea și el s-ar rupe.
# 150; Câți negustori furați iau fabrica?
# 150; Patru. Primele două sunt șaizeci de tone, iar celelalte două # 150; pe patruzeci.
# 150; Și cât de mult în depozite, îți amintești?
# 150; Râzi, Bate? Îmi amintesc aceste numere chiar și într-un vis: 75, 75 și 50.
# 150; Așa e, Joe! Lasă-mă să scriu totul în masă.
Bate a rupt calendarul atârnat pe perete și a reprezentat tabelul 1 pe spate.
# 150; Și în colțul din dreapta sus al fiecărei celule este aici. # 150; Bate începu, dar Joe îl întrerupse.
# 150; Oh! Mai bine nu știam aceste numere! Desigur, le recunosc! Atât de mulți dintre acești nepoți ai diavolului cer transportul unei tone de încărcătură pentru fiecare rută. De exemplu, 100 de dolari pe tonă de la cel de-al treilea depozit până la cel de-al patrulea cumpărător, există 10 mile. Nu, mai bine să-l găsesc eu!
# 150; Baietii iau riscuri, Joe, # 150; Bate a obiectat. # 150; Să numim aceste tarife pentru costuri. Deci, cum putem purta? Pe ce trasee?
# 150; În mod evident, în cazul în care este mai ieftin, # 150; murmură Joe, simțind un truc murdar.
# 150; Așa este! Să luăm traseele unde traseele sunt mai mici. Este mai ieftin să transportați bunuri de la primul depozit la al patrulea cumpărător # 150; doar cincizeci de dolari. Să numim această cale calea (1.4). Cu siguranță o vom folosi!
# 150; Bineînțeles! Și trebuie să o luați cât mai mult posibil!
# 150; Așa este! Dar mai mult de 40 de tone nu veți purta # 150; al patrulea cumpărător nu acceptă, el, de asemenea, ia riscuri. Vom pune 40 de tone pe această rută și pe ruta (3,2) # 150; există, de asemenea, 50 de dolari # 150; 50 de tone: mai mult în al treilea depozit nu! Primesc masa 2. Sunt în același timp corectat capacitatea și nevoile. Și în viitor vom pune transportul pe acele rute în care există un tarif mai mic.
# 150; Ei bine, e în regulă! # 150; Joe își frecă mâinile grase. # 150; Vom face acest lucru în 35 × 150 + 40 × 50 + 60 × 60 + 10 × 70 + 5 × 90 + 50 × 50 = 14.500 de dolari. Nu-i așa, Bate? Și aceasta se numește metoda științifică? Pun pariu dolarul contra cinci cenți, că orice polițist va afla cum să găsească acest plan de transport pentru 14.500 # 150; ooh-ooh # 150; 14 500 de dolari. Este adevărat că trebuie să folosim ruta (1,3) # 150; 150 de dolari pe tonă, # 150; Joe se uită cu gloanțe la masă.
# 150; Da, Joe, # 150; a fost timpul să triumfăm pe Baita. # 150; Știința mai are nevoie de ea? Am raspuns destul de sensibil, insa am inceput sa folosim cel mai scump traseu. Să încercăm acum să îmbunătățim planul de transport. Vom pune o tona de marfă pe ruta (1,1).
# 150; Acesta nu va funcționa, # 150; îl opri pe Joe. # 150; Soldul din prima coloană va fi anulat dacă știu ceva despre această problemă.
# 150; Veți înțelege, știți, # 150; liniștiți Bate. # 150; Dar echilibrul poate fi restabilit prin a lua o tonă de pe traseu (2,1), nu-i așa?
# 150; Așteptați, apoi în cel de-al doilea nu va fi nici un echilibru # 150; pe tonă mai puțin. Deși, totuși. dacă adăugați o altă tonă la (2,3) și eliminați-o din (1,3), se pare că totul va fi bine.
# 150; Să ne imaginăm acest lucru în noul tabel 5 (nu mai avem nevoie de capacități și nevoi).
# 150; În cazul în care am adăugat o tonă, există un semn plus și unde am curățat # 150; minus. Și mulțimea de celule în care am făcut modificări, să o numim un ciclu *. Deci, ce ne dă asta? Transportul unei tone pe ruta (1,1) # 150; 80 de dolari. Trebuie să fie adăugate. Și 150 de dolari # 150; transportul unei tone pe traseu (1,3) # 150; dimpotrivă, și 60 de secunde de pe traseu (2,1). Ei bine, 90 va trebui să adauge o tonă suplimentară pe traseu (2,3). Total, costurile de transport se vor schimba cu 80 + 90 # 150; 150 # 150; 60 = # 150; 40
# 150; Excelent! 40 de dolari pot fi salvate! # 150; îl admira pe Joe. # 150; Dar acest lucru am pus pe ruta (1,4) doar o tona. Să punem 100 de tone și să salvăm 4000, sau nu, să punem 400 de tone și apoi vom fi plătiți suplimentar!
În ochii lui Joe, o flacără de lăcomie a ars, dar imediat a ieșit:
# 150; Nu, e ceva în neregulă aici.
# 150; În mod evident, nu așa, # 150; Bate a fost de acord. # 150; La urma urmei, cât de mult adăugăm pe ruta (1,1), același lucru va trebui să fie eliminat din (1,3) și (2,1). Și de acolo puteți elimina cel mult 35 de tone. Nu vrei să duci fabrica înapoi în depozit!
# 150; Aceasta înseamnă că cel mult va fi posibilă transportul a 35 de tone de-a lungul rutei (1,1); acest lucru va economisi 40 × 35 = 1.400 de dolari, iar noul plan de transport va fi același ca în tabelul 6. În celulele care nu sunt incluse în ciclu, totul rămâne același.
# 150; 1.400 de dolari # 150; sumă rotundă! Să verificăm alte celule goale. Poate vom ajunge pe traseu, ceea ce merită de folosit. De exemplu, să începem cu celula (1,2). Pentru ea, costurile vor fi modificate cu 120 + 60 # 150; 70 # 150; 80 = 30> 0.
O mie de diavoli! Nu este necesar să utilizați ruta (1,2). Și, poate, profitați.
# 150; Nu te deranja, Joe. Am verificat deja: Danzigul însuși nu va mai stoarce din acest plan.
# 150; Danzig, Danzig. aceasta nu este cea care a curățat banca. „?
# 150; Nu, Joe, nu e unul al nostru. Acesta este cel care a inventat această metodă. Adevărat, înainte de ea unele roșu.
Inspectorul Cliff stătea în biroul său de la Avenue Street, din nou și din nou, uitându-se la probele reale: trei rupe magistral încuietorile, și cenușa calendarului ars cu atenție la hotel, în cazul în care spărgători sfat. Și nimic mai mult. Și totuși. se aseamănă scrierii de mână Batam, pentru care, Cliff, de vânătoare pentru atât de mulți ani! De exemplu, un calendar. Pentru ce? Poate că sa făcut pe asta? Poate. Dar unde să găsiți Baita?
# 150; Sergent, opriți-l! Pentru a închide biblioteca științifică de stat! Pentru mine # 150; mașină și un set de cătușe!
Ceea ce a permis economisirea costurilor de transport a fost de 1400 de dolari? Să urmăm acțiunile gangsterilor dexter. La început, Baith a găsit un plan de transport acceptabil. Modul în care el a luat, astfel, numita metoda elementului minim, și este clar de ce: l transporta tot timpul pus pe rutele cu tarife minime, iar în cazul în care există două rute cu aceeași preferință tarifară, desigur, aveți nevoie pentru a da celui pentru care este posibil creșterea transportului.
După ce a primit un plan fezabil, Bate și Joe au început să încerce să-l îmbunătățească prin metoda distribuției. Aceasta este probabil cea mai simplă, deși nu cea mai rapidă modalitate de îmbunătățire a planului de transport. Dar, înainte de a prezenta această metodă în formă generală, vom formula o problemă strict de transport a programării liniare.
Să existe furnizori (depozite) și n consumatori, ai # 150; capacitatea depozitului i, și bj # 150; nevoia utilizatorului j. Să presupunem că xij # 150; transportul de la furnizorul i la consumatorul j. Numai astfel de planuri de transport sunt acceptabile, pentru care **
Problema formulată # 150; acesta este un caz special al problemei de programare liniară, deoarece "funcția obiectivă" (2), exprimând costurile de transport, și constrângerile (1) sunt lineare.
Esența metodei de distribuție este că pentru fiecare celulă liberă există un ciclu, care include, pe lângă acesta, numai celulele umplut. Cu ajutorul acestui ciclu, se determină costurile de transport care se vor modifica dacă introduceți o unitate de marfă în celula liberă. Această cantitate kij este numită indicele celular liber (i. J). Dacă kij <0, то в клетку вносится максимально возможная перевозка (она равна минимальной перевозке в «отрицательных» клетках цикла), а если kij ≥ 0, то маршрут (i. j ) использовать не стоит и проверяется следующая клетка. Процесс заканчивается, когда выясняется, что для всех свободных клеток kij ≥ 0.
Planul optim trebuie căutat în planurile în care celulele umplute nu formează cicluri. De obicei, în sarcina de transport numărul de celule umplut este exact m + n # 150; 1, iar ciclul poate fi construit într-un mod unic (de exemplu, în problema considerată numărul de celule umplut este de 3 + 4 # 150; 1 = 6). Dacă includeți celule libere cu semnul "+" în ciclu, atunci după modificarea planului, se poate dovedi a fi mai mare decât m + n # 150; 1 celule umplut și planul va conține cicluri. Puteți verifica acest lucru încercând să construiți în tabelul 5 un ciclu (1,1) → (1,4) → (2,4) → (2,1).
Dacă numărul de celule umplut este mai mic decât m + n # 150; 1 (această problemă se numește degenerat), în scopul de a construi un ciclu, umplut la celulele pe care doriți să le adăugați semifabricatului, astfel încât deja nu este completat formează un ciclu. De exemplu, permiteți tabelului 7 să setați planul de transport degenerat (nu are o celulă completă).
Aici este posibil să se includă în numărul de celule umplut (1,3) sau (2,1), sau (2,2) sau (3,3). După aceasta, veți putea construi o buclă pentru orice celulă liberă. Și dacă includeți o celulă (3,1), care formează un ciclu cu celule (1,1), (1,2), (3,2), atunci nu veți putea construi oricum un ciclu cu celule umplut. Să vedem ce ne-a dat o celulă cu zero.
Costurile pentru primul plan de transport vor fi z1 = 25 × 3 + 30 × 2 + 40 × 4 + 50 × 6 = 595.
Găsiți indicii de celule libere:
Pe traseul (2,1) de transportat este benefic, dar cât de mult îl poți purta? min (25,0) = 0. Deci, pe ruta (2,1) poti pune doar transportul de 0, primim tabelul 8.
Costurile pentru acest plan nou vor rămâne aceleași: z2 = 595. Dar, totuși, funcționarea transferului de zero nu este lipsită de sens: acum indicii se vor schimba. Într-adevăr, acum k13 = 3 + 3 # 150; 3 # 150; 4 = # 150; 1 <0.
Acum se dovedește a fi o rută profitabilă (1,3). Utilizarea sa cu transport de 25 de tone va conduce la costuri de transport în valoare de z3 = 595 # 150; 25 = 570.
Modelul matematic pe care Bate la aplicat, # 150; Modelul problemei transportului de programare liniară, # 150; acum foarte utilizat în economie și managementul producției. Cu ajutorul unor astfel de modele, în multe locuri, acestea gestionează transportul de produse către magazine și cărămizi către șantierele de construcții, obținând o reducere semnificativă a costurilor de transport.
Dezavantajul metodei descrise de rezolvare a problemei de transport este necesitatea de a construi cicluri, atunci când numărăm pe o mașină acest lucru durează cea mai mare parte a timpului necesar pentru a rezolva problema. Prin urmare, au fost extinse și alte metode de rezolvare a problemelor de transport care reduc numărul de cicluri examinate (metoda potențialului propus de oamenii de știință sovietici pentru prima dată) sau nu necesită construirea de cicluri. Dacă numărul depozitelor sau numărul de consumatori nu este prea mare (până la 3 # 150; 4), atunci se aplică programarea dinamică.
Sarcina de transport are o serie de soiuri și cele mai neașteptate aplicații. Una dintre aceste aplicații vom lua în considerare acum.
Activitatea de atribuire
Doi domni în vârstă stăteau într-o bibliotecă de stat bine în stat.
# 150;. Sunt sigur că hrănitorii nu rămân aici. Deci, în bancă există 4 intrări. Fiecare dintre băieți este de acord să ia orice, dar li se pare diferit periculoși: la o intrare se află o mașină de poliție, alta intra pe o stradă aglomerată, în a treia ușa este prea îngustă. Cerințele lor în dolari sunt rezumate în Tabelul 9.