Nettverksmodeller: én familie, fire klassikere

Transport-, tilordnings-, korteste-vei- og maks-flyt-problemer er alle nettverksmodeller: de kan tegnes som noder (lagre, butikker, veikryss) forbundet med kanter (ruter med kostnad og/eller kapasitet). Alle er spesialtilfeller av lineær nettverksflyt, og alle har en verdifull egenskap: bibetingelsesmatrisen er totalt unimodulær, så en vanlig LP-løsning gir automatisk heltallige svar – du trenger sjelden å legge på heltallskrav. I Analytic Solver settes de opp som ordinære LP-modeller med en kostnads-/kapasitetstabell.

Transportproblemet

Beslutningsvariabelen er $x_{ij}$ = mengden som sendes fra tilbudspunkt $i$ til etterspørselspunkt $j$. Modellen er

$$\min \sum_i\sum_j c_{ij}x_{ij}\quad\text{u.b.}\quad \sum_j x_{ij}=S_i,\ \ \sum_i x_{ij}=D_j,\ \ x_{ij}\ge 0.$$

Problemet er balansert når samlet tilbud er lik samlet etterspørsel, $\sum_i S_i=\sum_j D_j$. Er det ikke det, legger du til en dummy: en fiktiv kolonne (hvis tilbud > etterspørsel) eller rad (hvis etterspørsel > tilbud) med kostnad 0, dimensjonert til å ta opp differansen. Enheter som havner i en dummy sendes ikke fysisk – de representerer lager som blir stående, eller behov som ikke dekkes.

Eksempel 1 – balansert transport (Nordvest Logistikk)

Grossisten Nordvest Logistikk har tre lagre (tilbud 120, 100, 80 – sum 300) og fire butikker (behov 90, 70, 100, 40 – sum 300, altså balansert). Enhetskostnadene (kr) er:

	B1	B2	B3	B4
Lager A	8	6	10	9
Lager B	9	12	13	7
Lager C	14	9	16	5

Solver minimerer $\sum c_{ij}x_{ij}$ under de 3 tilbuds- og 4 etterspørselslikhetene. Optimal plan: A→B2 = 30, A→B3 = 90; B→B1 = 90, B→B3 = 10; C→B2 = 40, C→B4 = 40. Total kostnad blir

$$30\cdot6+90\cdot10+90\cdot9+10\cdot13+40\cdot9+40\cdot5 = 180+900+810+130+360+200 = 2580\text{ kr}.$$

Legg merke til at basisløsningen har $m+n-1=3+4-1=6$ brukte ruter. I sensitivitetsrapporten er skyggeprisen på en butikks etterspørselsrad marginalkostnaden ved én ekstra enhet dit; en ubrukt rute har positiv redusert kostnad $c_{ij}-(u_i+v_j)$, som er kostnadsøkningen per enhet du tvinger inn på ruten.

Tilordningsproblemet

Tilordning er transport der alle tilbud og etterspørsel er 1 – en én-til-én-kobling. Variablene er binære $x_{ij}\in\{0,1\}$, men pga. unimodularitet gir kontinuerlig LP likevel 0/1-svar. Maksimeringsvarianter (maksimer fortjeneste) løses ved å be Solver maksimere, eller ved å trekke hver verdi fra en stor konstant. Ubalanse (ulikt antall ressurser og oppgaver) fikses med dummy-rader/-kolonner.

Eksempel 2 – tilordning (Bjørke Verktøy)

Verkstedet Bjørke Verktøy skal fordele 4 montører på 4 jobber for å minimere timeforbruket:

	Jobb 1	Jobb 2	Jobb 3	Jobb 4
Montør 1	9	11	14	11
Montør 2	6	15	13	13
Montør 3	12	13	6	8
Montør 4	11	9	10	7

Optimal tilordning: montør 2→jobb 1 (6), montør 1→jobb 2 (11), montør 3→jobb 3 (6), montør 4→jobb 4 (7), til sammen $6+11+6+7=30$ timer. Fristelsen til å gi hver montør «sin billigste jobb» hver for seg feiler, fordi flere kan konkurrere om samme jobb – det er derfor man trenger en optimeringsmodell.

Korteste vei og maks flyt

Korteste vei minimerer summen av kantvektene (avstand, tid eller kostnad) fra en kilde til et mål. Den kan skrives som å sende 1 flytenhet fra kilde til mål med flytbalanse i hver node. For Kystlinjens rutenett A–F med kanter A→C=3, C→B=1, A→B=5, B→D=6, D→E=2, E→F=4 (m.fl.) blir korteste vei A→C→B→D→E→F med lengde $3+1+6+2+4=16$; direktekanten A→B (5) brukes ikke fordi via C koster bare $3+1=4$ til B.

Maks flyt maksimerer mengden fra kilde til sluk under kant-kapasiteter og flytbalanse. Kjerneresultatet er maks-flyt–min-snitt: maksimal flyt = kapasiteten til det minste snittet som skiller kilde fra sluk. Har sluket to innkommende kanter med kapasitet 7 og 5, kan flyten aldri overstige $7+5=12$; er begge mettet, er dette snittet flaskehalsen. Å utvide en kant utenfor min-snittet gir ingen økning.

Slik testes temaet på BED4-eksamen

Du får typisk en kostnads-/kapasitetstabell og skal (1) sette opp modellen med variabler, målfunksjon og bibetingelser, (2) avgjøre om problemet er balansert og evt. legge til dummy, (3) lese av og tolke en Analytic Solver-løsning eller sensitivitetsrapport (skyggepriser, reduserte kostnader, slakk), og (4) drøfte konsekvensen av en endring – f.eks. økt etterspørsel, en stengt rute eller utvidet kapasitet. Regn alltid ut totalkostnaden fra planen for å kontrollere, og knytt skyggepris/redusert kostnad til en konkret ledelsesbeslutning.

Studieguide: Transport-, tilordnings- og nettverksmodeller

Studieguide: Transport-, tilordnings- og nettverksmodeller