Allokeringsproblemer

Allokeringsproblemer er en kategori i operasjonsanalyse der man fordeler begrensede ressurser mellom konkurrerende oppgaver for å oppnå best mulig nytte eller lavest kostnad. Ressurser kan være tid, maskin- eller arbeidskapasitet, budsjett, eller materiell.

Vanlige varianter inkluderer transportproblemet, tildelingsproblemet (assignment problem), og mer generelle lineære programmeringsproblemer for ressursallokering. Mange allokeringsproblemer kan modelleres som lineær programmering eller heltallsprogrammering.

En standard formulering bruker beslutningsvariabler x_ij som angir mengden ressurs som tildeles oppgave i eller en rute. Mål: minimere kostnader eller maksimere gevinst. Med kapasitet- og etterspørselsbetingelser: sum_i x_ij <= s_j og sum_j x_ij >= d_i, med x_ij >= 0. Spesialiserte varianter inkluderer transport (minimer kostnad for å oppfylle etterspørsel med gitte leverandører) og tildeling (minimere kostnader for å tildele oppgaver til agenter med kapasitetsbegrensninger).

Algoritmer: For bestemte klasser som tildelings- og transportproblemer finnes polynomiske algoritmer (f.eks. Hungarian-algoritmen for tildeling, nettverksflytmetoder for transport og tildeling). Generelle allokeringsproblemer kan løses med lineær programmering ved bruk av simplex eller konturbaserte metoder.

Anvendelser og utfordringer: brukes i produksjon, logistikk, skytjenester, budsjettfordeling og kapasitetplanlegging. Utfordringer inkluderer usikkerhet, dynamiske miljøer og skalerbarhet, samt at generelle problemdomener ofte er NP-harde hvis integralløsninger kreves.