Kuljetustehtävä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 3.6.2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Kuljetusongelma ( Monge-Kantorovich-ongelma ) on eräänlaisen lineaarisen ohjelmoinnin matemaattinen ongelma . [1] [2] Sitä voidaan pitää ongelmana optimaalisessa suunnitelmassa tavaroiden kuljettamiseksi lähtöpisteistä kulutuspisteisiin minimaalisilla kuljetuskustannuksilla.

Laskennallisen monimutkaisuuden teorian mukaan kuljetusongelma sisältyy monimutkaisuusluokkaan P . Kun tarjousten kokonaismäärä (lähtöpisteissä saatavilla olevat tavarat) ei ole yhtä suuri kuin kulutuspisteiden pyytämien tavaroiden (tavaroiden) kokonaiskysynnän määrä, kuljetusongelmaa kutsutaan epätasapainoiseksi ( avoin ).

Ongelman selvitys

Kuljetusongelma (klassinen) on ongelma optimaalisesta suunnitelmasta homogeenisen tuotteen kuljettamiseksi homogeenisista saatavuudesta homogeenisiin kulutuspisteisiin homogeenisissa ajoneuvoissa (ennalta määrätty määrä) staattisilla tiedoilla ja lineaarisella lähestymistavalla (nämä ovat tuotteen pääehdot). ongelma).

Klassisessa kuljetustehtävässä erotetaan kahden tyyppisiä tehtäviä: kustannuskriteeri (minimikuljetuskustannusten saavuttaminen) tai etäisyydet ja aikakriteeri (kuljetuksiin käytetty minimiaika). Kuljetusongelman nimellä määritellään laaja joukko ongelmia yhdellä matemaattisella mallilla, nämä ongelmat liittyvät lineaariseen ohjelmointiongelmiin ja voidaan ratkaista optimaalisella menetelmällä. Erityinen menetelmä kuljetusongelman ratkaisemiseksi voi kuitenkin merkittävästi yksinkertaistaa sen ratkaisua, koska kuljetusongelma on kehitetty minimoimaan kuljetuskustannukset.

Tehtävän matemaattinen muotoilu

Homogeeninen rahti keskittyy volyymillisesti toimittajille . Tämä rahti on toimitettava kuluttajille määrinä . - tavaran kuljetuskustannukset toimittajalta kuluttajalle . On laadittava kuljetussuunnitelma, joka mahdollistaa kaikkien valmistajien tuotteiden täydellisen viennin, täyttää täysin kaikkien kuluttajien tarpeet ja antaa vähimmäiskuljetuskustannukset. Merkitään kuljetusmääränä toimittajalta kuluttajalle . [3] $m$ ${\displaystyle a_{1},a_{2},....a_{m))$ $n$ ${\displaystyle b_{1},b_{2},....b_{n))$ $c_{ij}$ $i$ $j$ $x_{ij}$ $i$ $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

Ratkaisumenetelmien etsintähistoria

Ensimmäisen kerran ranskalainen matemaatikko Gaspard Monge virallisti ongelman vuonna 1781 [4] . Edistystä ongelman ratkaisemisessa saavutti suuren isänmaallisen sodan aikana Neuvostoliiton matemaatikko ja taloustieteilijä Leonid Kantorovich [5] . Siksi joskus tätä ongelmaa kutsutaan Monge-Kantorovich-kuljetusongelmaksi .

Ratkaisumenetelmät

Klassinen kuljetusongelma voidaan ratkaista simplex-menetelmällä , mutta useiden ominaisuuksien ansiosta se voidaan ratkaista yksinkertaisemmin (pienikokoisille ongelmille).

Ongelman ehdot sijoitetaan taulukkoon syöttäen soluihin kuljetetun rahdin määrä lastille ja pieniin soluihin vastaavat tariffit . $A_{i}$ $B_j$ $X_{ij}\geqslant 0$ $C_{ij}$

Kuljetussuunnitelman iteratiivinen parantaminen

Perustason löytäminen

Tarvitaan perussuunnitelman määrittäminen ja peräkkäisten toimintojen avulla optimaalisen ratkaisun löytäminen. Viitesuunnitelma löytyy seuraavilla menetelmillä: "luoteinen kulma" , "pienin elementti" , kaksoispreferenssi ja Vogelin approksimaatio .

Luoteiskulmamenetelmä (diagonaalinen tai parannettu)

Jokaisessa vaiheessa taulukon muun osan vasen yläsolu täytetään suurimmalla mahdollisella määrällä. Täyttö siten, että lasti poistetaan kokonaan tai tarve on täysin tyydytetty . $A_{i}$ $B_j$

Vähiten elementti -menetelmä

Yksi tapa ratkaista ongelma on pienimmän (pienimmän) elementin menetelmä . Sen ydin on minimoida tavaroiden sivullinen uudelleenjako kuluttajien välillä.

Algoritmi:

Arvotaulukosta valitaan alin kustannus ja sitä vastaavaan soluun syötetään suurempi numeroista.
Toimittajariveiltä tarkistetaan rivi, jossa on käytetty varastoa, ja asiakassarakkeet sarakkeelta, jonka vaatimukset täyttyvät täysin. Tällaisia sarakkeita ja rivejä ei käsitellä enempää.
Jos kaikki kuluttajat eivät ole tyytyväisiä eivätkä kaikki toimittajat ole käyttäneet tavaroita, palaa vaiheeseen 1, muuten ongelma on ratkaistu.

Iteraatiot

Kun olet löytänyt peruskuljetussuunnitelman, sinun on sovellettava yhtä algoritmeista sen parantamiseksi, lähestyen optimaalista.

Falling stone -menetelmä
Potentiaalien menetelmä .

Graafiteorian ratkaisu

Tarkastellaan kaksiosaista graafia , jossa tuotantopisteet ovat ylempänä ja kulutuspisteet alemmassa osuudessa. Tuotanto - ja kulutuspisteitä yhdistävät pareittain äärettömän läpimenon ja virtausyksikköhinnan reunat . $C_{ij}$

Lähde on kiinnitetty keinotekoisesti ylälohkoon . Reunojen kapasiteetti lähteestä kuhunkin tuotantopisteeseen on sama kuin tuotevarasto kyseisessä kohdassa. Näiden reunojen hinta virtausyksikköä kohti on 0.

Samoin viemäri liittyy alalohkoon . Ripojen läpimeno kustakin kulutuspisteestä pesualtaaseen on sama kuin tuotteen kysyntä tässä vaiheessa. Näiden reunojen virtausyksikkökustannus on myös 0.

Seuraavaksi ratkaistaan pienimmän kustannusten maksimivirtauksen ( mincost maxflow ) löytämisen ongelma. Sen ratkaisu on samanlainen kuin Ford-Fulkerson-algoritmin maksimivirtauksen löytäminen . Vain lyhimmän täydentävän virtauksen sijasta etsitään halvinta. Näin ollen tämä alitehtävä ei käytä leveyshakua , vaan Bellman-Ford-algoritmia . Kun stream palautetaan, kustannus katsotaan negatiiviseksi.

"Mincost maxflow" -algoritmi voidaan ajaa välittömästi - perustasoa löytämättä. Mutta tässä tapauksessa päätösprosessi on jonkin verran pidempi. "Mincost maxflow" -algoritmin suoritus tapahtuu vain operaatioissa. ( on reunojen lukumäärä, on kärkien lukumäärä.) Satunnaisesti valituilla tiedoilla vaaditaan yleensä paljon vähemmän - operaatioiden järjestys. $O(v^{2}e^{2})$ $e$ $v$ $O(ve)$

Epätasapainoista kuljetusongelmaa ratkaistaessa käytetään tekniikkaa, jolla se tasapainotetaan. Voit tehdä tämän kirjoittamalla kuvitteellisia kohteita tai lähtöjä. Kuljetusongelman tasapainon toteutus on tarpeen, jotta voidaan soveltaa kuljetustaulukoiden käyttöön perustuvaa ratkaisualgoritmia.

Yleistykset

Kuljetusongelma verkkoasetuksissa

Tässä versiossa pisteitä ei jaeta lähtö- ja kulutuspisteisiin, kaikki pisteet ovat yhtä suuret, mutta tuotanto on annettu positiivisella luvulla ja kulutus negatiivisella luvulla. Kuljetus tapahtuu tietyssä verkossa, jossa kaaret voivat yhdistää mitä tahansa pisteitä, mukaan lukien tuottaja-tuottaja, kuluttaja-kuluttaja.

Ongelma ratkaistaan hieman modifioidulla potentiaalien menetelmällä , joka on käytännössä sama kuin klassinen asetus.

Kuljetusongelma kaistanleveyden rajoitusten kanssa

Muunnelma siirtoongelmasta verkkoasetuksissa, jossa on määritelty joidenkin kaarien maksimiläpäisykyky.

Ongelma ratkaistaan hieman monimutkaisella potentiaalien menetelmällä .

Usean tuotteen kuljetusongelma

Kuljetustehtävän muunnelma, jossa on useita tuotteita (pisteet voivat tuottaa/kuluttaa useita tuotteita). Joillekin kaarille asetetaan suoritusraja (ilman tätä rajaa tehtävä jakautuu erillisiin tehtäviin tuotteen mukaan).

Ongelma ratkaistaan simplex-menetelmällä (käytetään Danzig -Wulf-laajennusta, yhden tuotteen kuljetusongelmia käytetään alitehtävinä).

Muistiinpanot

↑ A. V. Kuznetsov, N. I. Kholod, L. S. Kostevitš. Opas ongelmanratkaisuun matemaattisessa ohjelmoinnissa . - Minsk: Higher School , 1978. - S. 110.
↑ Kybernetiikan sanakirja / Toimittanut akateemikko V. S. Mikhalevich . - 2. - Kiova: M. P. Bazhanin mukaan nimetyn Ukrainan neuvostotietosanakirjan pääpainos, 1989. - 751 s. - (C48). – 50 000 kappaletta. - 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, sivut 666-704, 1781.
↑ Kantorovich L. Massien translokaatiosta // CR (Doklady) Acad. sci. URSS (NS), 37:199-201, 1942.

Linkit

Kuljetustehtävä
Algoritmit maksimivirtauksen löytämiseksi
http://kb.mista.ru/article.php?id=859 Kuljetusongelman ratkaisu 1C:Enterprise 8.2:ssa

Kirjallisuus

Korbut A.A. , Finkelstein Yu.Yu. Diskreetti ohjelmointi. - M .: Nauka, 1969. - 368 s.