ELE 3706

Studieguide

Komplett gjennomgang av pensum med forklaringer, formler, vanlige feil og eksamenstips.

Introduksjon

ELE 3706 Operasjonsanalyse gir deg verktøy for å modellere og løse optimeringsproblemer i næringslivet. Kurset dekker kvantitative metoder som lineær programmering, nettverksoptimering, beslutningsanalyse, lagerstyring og køteori — alle sentrale verktøy for effektiv drift og strategisk planlegging.

Denne studieguiden gir deg en kompakt gjennomgang av alle pensum-temaer med formler, eksempler og eksamenstips. Bruk den som supplement til lærebok og forelesninger.

Symboloversikt

Lineær programmering:

$Z$ = målfunksjonsverdi | $x_j$ = beslutningsvariabler | $c_j$ = målfunksjonskoeffisienter

$a_{ij}$ = teknologikoeffisienter | $b_i$ = høyresider (ressurser) | $s_i$ = slakkvariabel

$y_i$ = dualvariabel / skyggepris | $\bar{c}_j$ = redusert kostnad

Transport og nettverk:

$c_{ij}$ = transportkostnad | $x_{ij}$ = transportmengde | $s_i$ = tilbud kilde $i$

$d_j$ = etterspørsel destinasjon $j$ | $u_i, v_j$ = MODI-variabler

Beslutningsanalyse:

$EMV$ = forventet pengeverdi | $EVPI$ = verdi av perfekt informasjon

$EVSI$ = verdi av sample-informasjon | $p_i$ = sannsynlighet for tilstand $i$

Lagerstyring (EOQ):

$D$ = årlig etterspørsel | $S$ = bestillingskostnad | $H$ = lagerholdskostnad/enhet/år

$Q^*$ = optimal bestillingsmengde | $ROP$ = bestillingspunkt | $L$ = ledetid

Køteori:

$\lambda$ = ankomstrate | $\mu$ = betjeningsrate | $\rho$ = utnyttelsesgrad ( $\lambda/\mu$ )

$L_s$ = antall i systemet | $L_q$ = antall i kø | $W_s$ = tid i systemet | $W_q$ = ventetid

Lineær programmering

Formulering, grafisk løsning og simpleksmetoden for å optimere lineære målfunksjoner med lineære bibetingelser.

Hva er lineær programmering?

Lineær programmering (LP) er den mest fundamentale teknikken i operasjonsanalyse. Den handler om å maksimere eller minimere en lineær funksjon (målfunksjonen) underlagt lineære begrensninger (bibetingelser). Typiske anvendelser er produksjonsplanlegging, ressursallokering, transport og blanding.

Formulering av LP-problemer

Et LP-problem formuleres i tre steg:

Beslutningsvariabler: Hva skal bestemmes? Definer $x_1, x_2, \ldots$
Målfunksjon: Hva skal optimeres? $ $\max Z = c_1x_1 + c_2x_2 + \ldots + c_nx_n$ $
Bibetingelser: Hvilke begrensninger gjelder? $ $a_{i1}x_1 + a_{i2}x_2 + \ldots \leq b_i \quad \text{og} \quad x_j \geq 0$ $

Eksempel — produksjonsplanlegging:

En fabrikk lager produkter A ( $x_1$ ) og B ( $x_2$ ). Profitt: 5 kr per A, 4 kr per B.

Maskin 1: 6 timer per A, 4 timer per B, totalt 24 timer. Maskin 2: 1 time per A, 2 timer per B, totalt 6 timer.

\max Z = 5x_1 + 4x_2

$ $

6x_1 + 4x_2 \leq 24

$ $

x_1 + 2x_2 \leq 6

$ $

x_1, x_2 \geq 0

Grafisk løsning (to variabler)

For problemer med to variabler kan vi løse grafisk:

Tegn bibetingelsene som rette linjer
Skraver det tillatte området (feasible region)
Evaluer målfunksjonen $Z$ i alle hjørnepunkter
Hjørnepunktet med best $Z$ -verdi er optimalt

Fundamentalt teorem:

Hvis et LP-problem har en optimal løsning, finnes den alltid i et hjørnepunkt av det tillatte området. Dermed trenger vi bare sjekke et endelig antall punkter.

Simpleksmetoden

For problemer med flere variabler bruker vi simpleksmetoden — en algebraisk prosedyre som systematisk beveger seg fra hjørnepunkt til hjørnepunkt og forbedrer målfunksjonen i hvert steg.

Simpleksmetodens steg:

1. Gjør om til standardform med slakkvariabler: $Ax + s = b$ , $x, s \geq 0$ .

2. Finn inngående variabel: mest negativ $c_j - z_j$ (redusert kostnad).

3. Finn utgående variabel: minimumskvotient $\min\{b_i/a_{ij} : a_{ij} > 0\}$ .

4. Pivot: Gauss-eliminasjon i tabellen.

5. Gjenta til alle $c_j - z_j \leq 0$ (optimal for maks).

Spesialtilfeller

Ubegrenset: Målfunksjonen kan økes uten grense — alle $a_{ij} \leq 0$ i pivotkolonnen.

Utillatt: Ingen løsning tilfredsstiller alle bibetingelser.

Alternative optima: Isoprofittlinjen parallell med aktiv bibetingelse.

Degenerering: Basisvariabel med verdi 0 — kan gi cycling (sjelden i praksis).

Dualitet

Hvert LP-problem (primal) har et tilhørende dualt problem. Sterk dualitet: optimal primalverdi $=$ optimal dualverdi. Dualvariablene er skyggeprisene — de kobler LP til sensitivitetsanalyse.

Nøkkelformler

•Standardform (maks): $\max Z = cx$ gitt $Ax \leq b$ , $x \geq 0$
•Slakkvariabel: $\sum a_{ij}x_j + s_i = b_i$ , $s_i \geq 0$
•Optimalitetskriterium: alle $c_j - z_j \leq 0$ (maks)
•Minimumskvotient: $\theta = \min\{b_i/a_{ij} : a_{ij} > 0\}$
•Dualitet: $\max cx = \min yb$ (sterk dualitet)

Vanlige feil

⚠️Glemmer ikke-negativitetskrav $x_j \geq 0$
⚠️Blander $\leq$ og $\geq$ i bibetingelser — sjekk alltid retningen
⚠️Velger feil pivotelement — husk at $a_{ij}$ må være $> 0$ i kvotient-testen
⚠️Glemmer å sjekke alle hjørnepunkter i grafisk løsning

Eksamenstips

💡Vis tydelig formulering: variabler, målfunksjon, bibetingelser
💡I grafisk metode: marker hjørnepunkter og skriv $Z$ -verdien for hvert punkt
💡Kontroller at løsningen tilfredsstiller alle bibetingelser

Laster...