8.3 Lineær optimering utvidet | Matematikk S1

Mer enn ett optimalt hjørne

En møbelfabrikk produserer to bordmodeller og har funnet sin optimale produksjonsplan med lineær programmering (LP): tegn mulighetsområdet, regn ut målfunksjonen i hjørnepunktene, velg det beste. Men fabrikksjefen stiller spørsmålene som virkelig betyr noe i praksis: Hvor mye er én ekstra maskintime verdt? Hva skjer hvis prisene endrer seg litt? Og hva gjør vi med at man ikke kan produsere 3,7 bord?

Dette kapittelet utvider LP med tre slike verktøy: sensitivitetsanalyse (hvor stabilt er optimum?), skyggepris (verdien av økt kapasitet) og heltallsprogrammering (når variablene må være hele tall). De brukes daglig i logistikk, produksjonsplanlegging, ressursallokering og finans.

Det viktigste nye begrepet er skyggeprisen: skyggeprisen til en bibetingelse er den marginale forbedringen i målfunksjonsverdien dersom høyresiden av betingelsen økes med 1 enhet. Har maskinkapasiteten betingelsen $2x_1 + 3x_2 \leq 120$ og skyggepris $\lambda$ , vil en utvidelse til 121 timer forbedre optimal $z$ med $\lambda$ .

Tolkningen er umiddelbart økonomisk: skyggeprisen forteller hva det er verdt å betale for ekstra kapasitet. Kan kapasitet kjøpes billigere enn skyggeprisen, er investeringen lønnsom; koster den mer, er den det ikke. Og en viktig kontrast: ikke-bindende betingelser — de som ikke begrenser optimum — har skyggepris null. Det er ingenting å hente på å utvide en ressurs man ikke utnytter fullt ut. Slik blir skyggeprisene et kart over hvor flaskehalsene i bedriften faktisk sitter.

📝Oppgave Quiz 1

Fabrikkens regnestykke — og heltallsproblemet

La oss regne fabrikkens eksempel. To produkter gir $z = 400x_1 + 700x_2$ med betingelsene $2x_1 + 3x_2 \leq 120$ (maskintimer), $x_1 + 2x_2 \leq 60$ (arbeidstimer) og $x_1, x_2 \geq 0$ .

Hjørnepunktene: $(0, 0)$ gir $z = 0$ ; $(60, 0)$ gir $z = 24\,000$ ; $(0, 30)$ gir $z = 21\,000$ . Skjæringen mellom betingelsene: fra den andre er $x_1 = 60 - 2x_2$ , som innsatt i den første gir $120 - 4x_2 + 3x_2 = 120$ , altså $x_2 = 0$ og $x_1 = 60$ — samme punkt som før. Optimal løsning: $x_1 = 60$ , $x_2 = 0$ , $z = 24\,000$ kr.

Skyggeprisen for maskinkapasitet: øk høyresiden fra 120 til 121. Da gir $2x_1 = 121$ løsningen $x_1 = 60{,}5$ og $z = 400 \cdot 60{,}5 = 24\,200$ . Skyggeprisen er $24\,200 - 24\,000 = 200$ kr per maskintime. Kan timer leies for 150 kr, tjener fabrikken 50 kr per leid time — lønnsomt.

Så til virkelighetens harde krav: heltall. Man kan ikke produsere 3,7 bord, ansette 2,4 snekkere eller sende 1,6 lastebiler. Heltallsprogrammering (IP) legger til betingelsen $x_1, x_2 \in \mathbb{Z}_{\geq 0}$ . For to variabler finnes en enkel arbeidsgang: løs det kontinuerlige LP-problemet, rund av til nærmeste heltallspunkt, sjekk at det avrundede punktet faktisk er innenfor mulighetsområdet, og evaluer nabopunktene om nødvendig.

Men merk advarselen: det avrundede punktet er ikke alltid optimalt — og noen ganger ikke engang gyldig. Det ekte heltallsoptimumet kan ligge i et annet nabopunkt enn det nærmeste. For store problemer kreves egne IP-algoritmer; for eksamensoppgaver med to variabler holder det å sjekke kandidatpunktene systematisk.

📝Oppgave Quiz 2

Oppsummering: robusthet, flaskehalser og hele tall

Fabrikksjefens tre spørsmål har fått sine verktøy. Grunnmuren er som før: lineær optimering maksimerer en lineær målfunksjon under lineære beskrankninger, og optimum ligger alltid i et hjørnepunkt av mulighetsområdet — regn ut målfunksjonen i alle hjørner og velg det beste, slik fabrikken fant $x_1 = 60$ , $x_2 = 0$ og $z = 24\,000$ kr.

Skyggeprisen er utvidelsens juvel: verdien av én ekstra kapasitetsenhet, beregnet som $\Delta z$ når høyresiden økes med 1. Fabrikkens 200 kr per maskintime mot leiepris 150 kr gjorde investeringsbeslutningen til ren aritmetikk — og ikke-bindende betingelser med skyggepris null viste hvor det ikke er noe å hente. Skyggeprisene er bedriftens flaskehalskart.

Heltallsbetingelser minner om at virkeligheten teller i hele bord og hele ansatte: rund av den kontinuerlige løsningen, men sjekk gyldighet og nabopunkter, for avrunding gir ikke alltid optimum. Og sensitivitetsanalysen fra 8.1 går igjen: undersøk hvordan optimum flytter seg når priser og kapasiteter endres, før du satser penger på planen.

Fra kart til beslutning: det er spranget dette kapittelet handler om — og det samme spranget venter når modellene i neste kapittel møter ekte samfunnsøkonomiske data.