transportproblemer

Transportproblemer, ofte kalt transportproblemer i operasjonsforskning, er klassiske optimeringsmodeller som handler om å fordele varer fra flere leverandører til flere mottakere med lavest mulig kostnad, samtidig som etterspørsel og tilbud tilfredsstilles. Modellen er sentral i logistikk, produksjonsplanlegging og forsyningskjeder, og brukes også i nødhjelpsdistribusjon og energidistribusjon.

Matematisk kan problemet beskrives med variabler xij, som er mengden av varer som sendes fra leverandør i til mottaker j. Målfunksjonen er å minimere total transportkostnad: minimer sum over i og j av cij * xij, der cij er kostnaden per enhet for ruta fra i til j. Begrensningene består av tilbuds- og etterspørselsbetingelser: for hver leverandør i må summen av utgående xi• ikke overstige s_i (og i balanse hvis totalt tilbud brukes), mens for hver mottaker j må summen av innkommende x•j oppfylle d_j. Alle xij er ikke-negative. Dersom total leverandørkapasitet ikke tilsvarer total etterspørsel, legges en dummy-tilgang eller -avgang for å balansere modellen. Fordelen med transportproblemet er at det er et spesialtilfelle av lineær programmering med en helt spesifikk strukturb og en totalt unimodulær konsetmatrise, noe som ofte gir heltallige optimale løsninger når s_i og d_j er heltallige.

Løsningsmetoder inkluderer å få en gyldig startløsning (for eksempel nordvest- hjørne-metoden eller minste kost-metoden, eller Vogel-tilnærmingsmetoden) og deretter optimalisere med MODI-metoden eller andre lineære metoder. Det finnes også varianter som ubalanserte transportproblem, fler-varer-transport (multi-commodity), og transport med kapasitetstrestriksjoner eller tidsutvidelser (transshipments).

Historisk ble problemet introdusert som Hitchcock-transportproblemet i 1941 og har siden utviklet seg gjennom spesialiserte algoritmer innen optimering.