Vogeltilnærmingsmetoden

Vogeltilnærmingsmetoden (VAM) er en heuristisk metode for å finne en innledende, grunnleggende løsning til transportproblemet i lineær programmering. Den brukes for å skaffe en rimelig god startløsning som senere kan forbedres med andre metoder, som MODI. Metoden utnytter kostnadsstraffer for å velge hvilke celler som bør disponeres først.

Prosedyre

1) For hver rad og kolonne beregnes straffen som forskjellen mellom den minste og den nest minste kostnaden blant de gjenværende cellene i raden eller kolonnen.

2) Finn den største straffen blant alle rader og kolonner.

3) I den aktuelle raden eller kolonnen, finn cellen med laveste kostnad, og tildel så mye som mulig der (minimum av lagerkapasitet i raden og etterspørsel i kolonnen).

4) Oppdater lager og etterspørsel; fjern en hel rad eller kolonne når den blir oppfylt. Sett andre kostnader i den aktuelle raden/kolonnen til ubrukelige/kasserte verdier etter fjerning. Fortsett til alle behov er dekket.

Egenskaper og anvendelse

VAM gir en rask og enkel måte å skaffe en god innledende løsning for transportproblemer, ofte nær optimal løsning uten å måtte kjøre fullstendig transport-eller-soplanalyse fra starten. Metoden er spesielt nyttig for store problemstillinger der en effektiv initial løsning sparer tid.

Fordeler og begrensninger

Fordeler inkluderer enkel implementering og relativt god startløsning som ofte gir lavere total kostnad enn en ren gjennomsnittlig fordeling. Begrensninger er at det ikke garanterer optimal løsning og at kvaliteten avhenger av problemdesign og sekvensen av valg som tas under prosessen.

Historie og navn

Metoden er kjent som Vogeltilnærmingsmetoden, oppkalt etter utvikleren ved navnet Vogel, og brukes bredt i operasjonsforskning og logistikk som et standard verktøy for initiering av transportløsninger.