Transportopgave

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 3. juni 2021; verifikation kræver 1 redigering .

Transportproblemet ( Monge-Kantorovich-problemet ) er et matematisk problem med lineær programmering af en særlig art. [1] [2] Det kan ses som et problem med den optimale plan for transport af varer fra afgangssteder til forbrugssteder med minimale transportomkostninger.

Ifølge teorien om beregningsmæssig kompleksitet indgår transportproblemet i kompleksitetsklassen P . Når den samlede mængde af tilbud (varer, der er tilgængelige på afgangsstederne) ikke er lig med den samlede mængde efterspørgsel efter varer (varer), der efterspørges af forbrugsstederne, kaldes transportproblemet ubalanceret ( åbent ).

Udtalelse af problemet

Transportproblemet (klassisk) er problemet med den optimale plan for transport af et homogent produkt fra homogene tilgængelighedspunkter til homogene forbrugssteder på homogene køretøjer (forudbestemt mængde) med statiske data og en lineær tilgang (disse er hovedbetingelserne for problem).

For den klassiske transportopgave skelnes der mellem to typer opgaver: omkostningskriteriet (opnåelse af et minimum af transportomkostninger) eller afstande og tidskriteriet (minimumstiden bruges på transport). Under navnet transportproblemet defineres en bred vifte af problemer med en enkelt matematisk model, disse problemer er relateret til lineære programmeringsproblemer og kan løses ved den optimale metode. En særlig metode til at løse et transportproblem kan dog forenkle løsningen betydeligt, da transportproblemet er udviklet for at minimere transportomkostningerne.

Matematisk formulering af problemet

Homogen last er koncentreret hos leverandører i mængder . Denne last skal leveres til forbrugerne i mængder . - omkostningerne ved at transportere varer fra leverandøren til forbrugeren . Det er påkrævet at udarbejde en transportplan, der giver dig mulighed for fuldstændigt at eksportere produkter fra alle producenter, fuldt ud opfylder alle forbrugeres behov og giver et minimum af samlede transportomkostninger. Angiv som mængden af transport fra leverandøren til forbrugeren . [3] $m$ ${\displaystyle a_{1},a_{2},....a_{m))$ $n$ ${\displaystyle b_{1},b_{2},....b_{n))$ $c_{ij}$ $jeg$ $j$ $x_{ij}$ $jeg$ $j$

{\displaystyle \sum _{j=1}^{n}x_{ij}=a_{i))

i=1,2,...,m

{\displaystyle \sum _{i=1}^{m}x_{ij}=b_{j))

j=1,2,...,n

\sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}\rightarrow \min

Historien om søgningen efter løsningsmetoder

Problemet blev først formaliseret af den franske matematiker Gaspard Monge i 1781 [4] . Fremskridt med at løse problemet blev opnået under den store patriotiske krig af den sovjetiske matematiker og økonom Leonid Kantorovich [5] . Derfor kaldes dette problem nogle gange Monge-Kantorovich-transportproblemet .

Løsningsmetoder

Det klassiske transportproblem kan løses ved simpleksmetoden , men på grund af en række funktioner kan det løses mere enkelt (for problemer med lav dimension).

Betingelserne for problemet er placeret i tabellen, indtastning i cellerne mængden af gods, der transporteres fra til last , og i små celler - de tilsvarende tariffer . $A_{i}$ $B_j$ $X_{ij}\geqslant 0$ $C_{ij}$

Iterativ forbedring af transportplanen

At finde basislinjen

Det er nødvendigt at fastlægge grundplanen og gennem successive operationer finde den optimale løsning. Referenceplanen kan findes ved følgende metoder: "nordvestlige hjørne" , "mindste element" , dobbelt præference og Vogels tilnærmelse .

Nordvestlige hjørnemetode (diagonal eller forbedret)

På hvert trin er den øverste venstre celle i resten af bordet fyldt med det maksimalt mulige antal. Påfyldning på en sådan måde, at lasten er helt fjernet fra eller behovet er helt opfyldt . $A_{i}$ $B_j$

Mindste element metode

En måde at løse problemet på er metoden med det mindste (mindste) element . Dens essens ligger i at minimere sideomfordelingen af varer mellem forbrugerne.

Algoritme:

Fra værditabellen vælges den laveste pris, og den største af tallene indtastes i den celle, der svarer til den.
Leverandørrækkerne kontrolleres for en række med brugt beholdning, og kundekolonnerne for en kolonne, hvis krav er fuldt opfyldt. Sådanne kolonner og rækker behandles ikke yderligere.
Hvis ikke alle forbrugere er tilfredse, og ikke alle leverandører har opbrugt varerne, så gå tilbage til trin 1, ellers er problemet løst.

Gentagelser

Efter at have fundet den grundlæggende transportplan, skal du anvende en af algoritmerne for at forbedre den og nærme dig den optimale.

Faldende sten metode
Fremgangsmåde for potentialer .

Graph Theory Solution

Vi betragter en todelt graf , hvor produktionspunkterne er i den øvre andel, og forbrugspunkterne er i den nederste. Produktions- og forbrugspunkter er forbundet parvis af kanter med uendelig gennemstrømning og pris pr. flowenhed . $C_{ij}$

Kilden er kunstigt fastgjort til den øvre lap . Kapaciteten af kanterne fra kilden til hvert produktionssted er lig med lageret af produktet på det tidspunkt. Prisen pr. flowenhed for disse kanter er 0.

På samme måde slutter afløb sig til den nedre lap . Gennemstrømningen af ribbenene fra hvert forbrugssted til vasken er lig efterspørgslen efter produktet på dette tidspunkt. Prisen pr. flowenhed for disse kanter er også 0.

Dernæst er problemet med at finde det maksimale flow af minimumsomkostningerne ( mincost maxflow ) løst. Dens løsning svarer til at finde det maksimale flow i Ford-Fulkerson-algoritmen . Kun i stedet for det korteste komplementære flow søges det billigste. Derfor bruger denne underopgave ikke bredde-først-søgning , men Bellman-Ford-algoritmen . Når en strøm returneres, betragtes omkostningerne som negative.

"Mincost maxflow"-algoritmen kan køres med det samme - uden at finde en baseline. Men i dette tilfælde bliver beslutningsprocessen noget længere. Udførelsen af "mincost maxflow"-algoritmen finder ikke sted i mere end operationer. ( er antallet af kanter, er antallet af hjørner.) Med tilfældigt udvalgte data kræves der normalt meget mindre - rækkefølgen af operationer. $O(v^{2}e^{2})$ $e$ $v$ $O(ve)$

Når man løser et ubalanceret transportproblem, bruges en teknik til at gøre det afbalanceret. For at gøre dette skal du indtaste fiktive destinationer eller afgange. Implementeringen af balancen i transportproblemet er nødvendig for at kunne anvende løsningsalgoritmen baseret på brug af transporttabeller.

Generaliseringer

Transportproblemet i netværksindstillingen

I denne variant er point ikke opdelt i udgangspunkter og forbrugspunkter, alle point er lige store, men produktionen er givet ved et positivt tal, og forbruget med et negativt. Transport udføres på et givet netværk, hvor lysbuer kan forbinde alle punkter, herunder producent-producent, forbruger-forbruger.

Problemet er løst ved en let modificeret metode for potentialer , praktisk talt den samme som den klassiske indstilling.

Transportproblem med båndbreddebegrænsninger

En variant af transportproblemet i en netværksindstilling, hvor den maksimale gennemstrømning af nogle buer er angivet.

Problemet løses ved en lidt kompliceret metode for potentialer .

Transportproblem med flere produkter

En variant af en transportopgave, hvor der er flere produkter (punkter kan producere/forbruge flere produkter). For nogle buer er der sat en gennemløbsgrænse (uden denne grænse opdeles opgaven i separate opgaver efter produkt).

Problemet løses ved simplex-metoden ( Danzig- Wulf-udvidelsen bruges, enkelt-produkt transportproblemer bruges som delopgaver).

Noter

↑ A. V. Kuznetsov, N. I. Kholod, L. S. Kostevich. En guide til problemløsning i matematisk programmering . - Minsk: Higher School , 1978. - S. 110.
↑ Dictionary of Cybernetics / Redigeret af akademiker V. S. Mikhalevich . - 2. - Kiev: Hovedudgave af den ukrainske sovjetiske encyklopædi opkaldt efter M. P. Bazhan, 1989. - 751 s. - (C48). — 50.000 eksemplarer. - ISBN 5-88500-008-5 .
↑ Korbut, 1969 , s. 28.
↑ Monge G. Mémoire sur la théorie des deblais et de remblais. Histoire de l'Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, side 666-704, 1781.
↑ Kantorovich L. Om translokation af masser // CR (Doklady) Acad. sci. URSS (NS), 37:199-201, 1942.

Litteratur

Korbut A.A. , Finkelstein Yu.Yu. Diskret programmering. - M. : Nauka, 1969. - 368 s.