8.3 Lineær optimering utvidet

Sensitivitetsanalyse, heltallsbetingelser, skyggepris og LP-problemer.

55 min

8 oppgaver

SensitivitetsanalyseHeltallsbetingelserSkyggeprisLP

Du leser den tradisjonelle versjonen

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Bygger på

8.2Lineær programmering

Lineær optimering -- videre analyse

I grunnleggende lineær programmering (LP) finner vi det optimale hjørnepunktet i det feasible området. Men i praksis er det like viktig å forstå hvor robust løsningen er: Hvor mye kan koeffisientene endre seg før en annen løsning blir optimal? Hva er kostnaden ved å ha begrenset kapasitet?

Utvidede temaer:
- Sensitivitetsanalyse -- stabilitetsområde for koeffisienter
- Skyggepris -- verdien av økt kapasitet
- Heltallsprogrammering -- når variablene må være hele tall

Disse verktøyene brukes i logistikk, produksjonsplanlegging, ressursallokering og finans.

Skyggepris (Shadow price)

a_1 x_1 + a_2 x_2 \leq b

✏️Eksempel: Produksjonsplanlegging med sensitivitetsanalyse

En møbelfabrikk produserer stoler ( $x_1$ ) og bord ( $x_2$ ).
- Fortjeneste: 400 kr per stol, 700 kr per bord
- Maskinkapasitet: $2x_1 + 3x_2 \leq 120$ timer
- Trekapasitet: $x_1 + 2x_2 \leq 60$ tonn
- $x_1, x_2 \geq 0$

a) Finn den optimale produksjonsplanen.
b) Beregn skyggeprisen for maskinkapasiteten.
c) Er det lønnsomt å kjøpe 10 ekstra maskintimer til 150 kr/time?

a) Hjørnepunkter:

$(0, 0)$ : $z = 0$
$(60, 0)$ : $z = 24000$
$(0, 30)$ : Sjekk trekapasitet: $2(30)=60$ ✓. $z = 21000$
Skjæringspunkt: $2x_1+3x_2=120$ og $x_1+2x_2=60$ . Fra andrе: $x_1=60-2x_2$ . Setter inn: $120-4x_2+3x_2=120 \Rightarrow x_2=0, x_1=60$ .

Optimal løsning: $x_1 = 60$ , $x_2 = 0$ , $z = 24000$ kr.

b) Skyggepris for maskinkapasitet:

Øker til 121: $2x_1 = 121 \Rightarrow x_1 = 60{,}5$ , $z = 400 \cdot 60{,}5 = 24200$ .

Skyggepris $= 24200 - 24000 = 200$ kr per maskinttime.

c) Lønnsomt?

200 kr/time (skyggepris) > 150 kr/time (kostnad). Ja, det er lønnsomt.

📊Utforsk: Mulighetsområdet i lineær optimering

Det skraverte området viser alle punkter som oppfyller bindingene $x + y \le 8$ , $2x + y \le 10$ , $x \ge 0$ og $y \ge 0$ . Optimal løsning ligger alltid i et hjørne. Tegn nivålinjer for målfunksjonen og finn hjørnet.

Mange praktiske problemer krever hele tall: du kan ikke produsere 3,7 biler, ansette 2,4 arbeidere, eller sende 1,6 lastebiler.

Heltallsprogrammering (IP) legger til betingelsen $x_1, x_2 \in \mathbb{Z}_{\geq 0}$ .

Enkel metode for to variabler:
1. Løs det kontinuerlige LP-problemet
2. Rund av til nærmeste heltallspunkt i det feasible området
3. Sjekk om avrundede verdier er feasible
4. Evaluer nabopunkter om nødvendig

Obs: Det avrundede punktet er ikke alltid optimalt! For store problemer kreves spesielle IP-algoritmer.

📝Oppgave 1

En baker produserer rundstykker ( $x$ ) og brød ( $y$ ) med fortjeneste 3 kr og 8 kr. Betingelser: $x + 2y \leq 40$ (ovntid), $x + y \leq 30$ (arbeidstid), $x, y \geq 0$ .

Finn alle hjørnepunkter i det feasible området.

Finn det optimale punktet og maksimal fortjeneste.

Beregn skyggeprisen for ovnsbetingelsen.

Løs oppgaven Tren

📝Oppgave 2

Et transportselskap fordeler transporter mellom to ruter. Rute 1: fortjeneste 500 kr, krever 2 sjåførtimer og 3 tonn brensel. Rute 2: fortjeneste 800 kr, krever 4 sjåførtimer og 2 tonn brensel. Tilgjengelig: 40 sjåførtimer og 30 tonn brensel.

Formuler LP-problemet matematisk.

Finn den optimale løsningen ved hjørnepunktanalyse.

Heltallsbetingelse: Finn beste feasible heltallspunkt.

📝Oppgave 3

Sensitivitetsanalyse: LP-problemet Maks $z = cx_1 + 4x_2$ s.t. $x_1 + x_2 \leq 6$ , $2x_1 + x_2 \leq 10$ , $x_1, x_2 \geq 0$ .

Finn den optimale løsningen når $c = 2$ .

For hvilke verdier av $c$ er $(4, 2)$ optimalt?

Forklar hva sensitivitetsanalyse betyr for beslutningstakere.

Oppsummering

I dette kapittelet har du lært:

- Lineær optimering: Maksimer/minimer en lineær målfunksjon under lineære beskrankninger. Optimum ligger alltid i et hjørnepunkt av mulighetsområdet.
- Skyggepris: Hvor mye målfunksjonens optimale verdi øker hvis en beskrankning utvides med én enhet.
- Heltallsbetingelser: Når løsningen må være heltall, kan avrunding av den kontinuerlige løsningen gi feil svar — sjekk gyldige heltallspunkter.
- Sensitivitet: Undersøk hvordan optimum endres når priser eller kapasiteter endres.

Nøkkelbegreper

Begrep	Forklaring
Mulighetsområde	Området som oppfyller alle beskrankninger
Hjørnepunkt	Kandidat for optimum
Skyggepris	Verdi av én ekstra kapasitetsenhet
Heltallsløsning	Krav om hele enheter

Viktige formler

- Optimum i hjørnepunkt: regn ut målfunksjonen i alle hjørner
- Skyggepris

= \Delta Z

per enhet økt kapasitet

Repetisjonsoppgaver

Din fremgang

0deloppgaver0 / 5 oppgaver

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.