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 -- vidare analyse

I grunnleggjande lineær programmering (LP) finn vi det optimale hjørnepunktet i det feasible området. Men i praksis er det like viktig å forstå kor robust løysinga er: Kor mykje kan koeffisientane endre seg før ei anna løysing blir optimal? Kva er kostnaden ved å ha avgrensa kapasitet?

Utvida tema:
- Sensitivitetsanalyse -- stabilitetsområde for koeffisientar
- Skyggepris -- verdien av auka kapasitet
- Heiltalsprogrammering -- når variablane må vere heile tal

Desse verktøya blir brukte i logistikk, produksjonsplanlegging, ressursallokering og finans.

Skyggepris (Shadow price)

a_1 x_1 + a_2 x_2 \leq b

✏️Eksempel: Produksjonsplanlegging med sensitivitetsanalyse

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

a) Finn den optimale produksjonsplanen.
b) Rekn ut skyggeprisen for maskinkapasiteten.
c) Er det lønsamt å kjøpe 10 ekstra maskintimar til 150 kr/time?

a) Hjørnepunkt:

$(0, 0)$ : $z = 0$
$(60, 0)$ : $z = 24000$
$(0, 30)$ : Sjekk trekapasitet: $2(30)=60$ ✓. $z = 21000$
Skjeringspunkt: $2x_1+3x_2=120$ og $x_1+2x_2=60$ . Frå det andre: $x_1=60-2x_2$ . Set inn: $120-4x_2+3x_2=120 \Rightarrow x_2=0, x_1=60$ .

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

b) Skyggepris for maskinkapasitet:

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

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

c) Lønsamt?

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

📊Utforsk: Mulegheitsområdet i lineær optimering

Det skraverte området viser alle punkt som oppfyller bindingane $x + y \le 8$ , $2x + y \le 10$ , $x \ge 0$ og $y \ge 0$ . Optimal løysing ligg alltid i eit hjørne. Teikn nivålinjer for målfunksjonen og finn hjørnet.

Mange praktiske problem krev heile tal: du kan ikkje produsere 3,7 bilar, tilsetje 2,4 arbeidarar, eller sende 1,6 lastebilar.

Heiltalsprogrammering (IP) legg til vilkåret $x_1, x_2 \in \mathbb{Z}_{\geq 0}$ .

Enkel metode for to variablar:
1. Løys det kontinuerlege LP-problemet
2. Rund av til næraste heiltalspunkt i det feasible området
3. Sjekk om avrunda verdiar er feasible
4. Evaluer nabopunkt om nødvendig

Obs: Det avrunda punktet er ikkje alltid optimalt! For store problem trengst spesielle IP-algoritmar.

📝Oppgave 1

Ein bakar produserer rundstykke ( $x$ ) og brød ( $y$ ) med forteneste 3 kr og 8 kr. Vilkår: $x + 2y \leq 40$ (omnstid), $x + y \leq 30$ (arbeidstid), $x, y \geq 0$ .

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

Finn det optimale punktet og maksimal forteneste.

Rekn ut skyggeprisen for omnsvilkåret.

Løs oppgaven Tren

📝Oppgave 2

Eit transportselskap fordeler transportar mellom to ruter. Rute 1: forteneste 500 kr, krev 2 sjåførtimar og 3 tonn brensel. Rute 2: forteneste 800 kr, krev 4 sjåførtimar og 2 tonn brensel. Tilgjengeleg: 40 sjåførtimar og 30 tonn brensel.

Formuler LP-problemet matematisk.

Finn den optimale løysinga ved hjørnepunktanalyse.

Heiltalsvilkår: Finn beste feasible heiltalspunkt.

📝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øysinga når $c = 2$ .

For kva verdiar av $c$ er $(4, 2)$ optimalt?

Forklar kva sensitivitetsanalyse tyder for avgjerdstakarar.

Oppsummering

I dette kapittelet har du lært:

- Lineær optimering: Maksimer/minimer ein lineær målfunksjon under lineære skrankar. Optimum ligg alltid i eit hjørnepunkt av mulegheitsområdet.
- Skyggepris: Kor mykje den optimale verdien til målfunksjonen aukar dersom ein skranke blir utvida med éi eining.
- Heiltalsvilkår: Når løysinga må vere heiltal, kan avrunding av den kontinuerlege løysinga gje feil svar — sjekk gyldige heiltalspunkt.
- Sensitivitet: Undersøk korleis optimum endrar seg når prisar eller kapasitetar endrar seg.

Nøkkelomgrep

Omgrep	Forklaring
Mulegheitsområde	Området som oppfyller alle skrankar
Hjørnepunkt	Kandidat for optimum
Skyggepris	Verdi av éi ekstra kapasitetseining
Heiltalsløysing	Krav om heile einingar

Viktige formlar

- Optimum i hjørnepunkt: rekn ut målfunksjonen i alle hjørne
- Skyggepris

= \Delta Z

per eining auka kapasitet

Repetisjonsoppgåver

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.