Eksamenssett.no
Ressurser
Skolenytt
Hoderegning
ELE 3706
Cheat Sheet
Formler, begreper og oppsummering
Operasjonsanalyse
eksamenssett.no
Symboloversikt
Lineær programmering
•
Z
Z
Z
= målfunksjonsverdi |
x
j
x_j
x
j
= beslutningsvariabler |
c
j
c_j
c
j
= målfunksjonskoeffisienter
•
a
i
j
a_{ij}
a
ij
= teknologikoeffisienter |
b
i
b_i
b
i
= høyresider (ressurser) |
s
i
s_i
s
i
= slakkvariabel
•
y
i
y_i
y
i
= dualvariabel / skyggepris |
c
ˉ
j
\bar{c}_j
c
ˉ
j
= redusert kostnad
Transport og nettverk
•
c
i
j
c_{ij}
c
ij
= transportkostnad |
x
i
j
x_{ij}
x
ij
= transportmengde |
s
i
s_i
s
i
= tilbud kilde
i
i
i
•
d
j
d_j
d
j
= etterspørsel destinasjon
j
j
j
|
u
i
,
v
j
u_i, v_j
u
i
,
v
j
= MODI-variabler
Beslutningsanalyse
•
E
M
V
EMV
EM
V
= forventet pengeverdi |
E
V
P
I
EVPI
E
V
P
I
= verdi av perfekt informasjon
•
E
V
S
I
EVSI
E
V
S
I
= verdi av sample-informasjon |
p
i
p_i
p
i
= sannsynlighet for tilstand
i
i
i
Lagerstyring (EOQ)
•
D
D
D
= årlig etterspørsel |
S
S
S
= bestillingskostnad |
H
H
H
= lagerholdskostnad/enhet/år
•
Q
∗
Q^*
Q
∗
= optimal bestillingsmengde |
R
O
P
ROP
ROP
= bestillingspunkt |
L
L
L
= ledetid
Køteori
•
λ
\lambda
λ
= ankomstrate |
μ
\mu
μ
= betjeningsrate |
ρ
\rho
ρ
= utnyttelsesgrad (
λ
/
μ
\lambda/\mu
λ
/
μ
)
•
L
s
L_s
L
s
= antall i systemet |
L
q
L_q
L
q
= antall i kø |
W
s
W_s
W
s
= tid i systemet |
W
q
W_q
W
q
= ventetid
Formler
Lineær programmering
•
Standardform:
max
Z
=
c
x
\max Z = cx
max
Z
=
c
x
gitt
A
x
≤
b
Ax \leq b
A
x
≤
b
,
x
≥
0
x \geq 0
x
≥
0
•
Optimalitet: alle
c
j
−
z
j
≤
0
c_j - z_j \leq 0
c
j
−
z
j
≤
0
(maks)
•
Minimumskvotient:
θ
=
min
{
b
i
/
a
i
j
:
a
i
j
>
0
}
\theta = \min\{b_i/a_{ij} : a_{ij} > 0\}
θ
=
min
{
b
i
/
a
ij
:
a
ij
>
0
}
•
Dualitet:
max
c
x
=
min
y
b
\max cx = \min yb
max
c
x
=
min
y
b
Sensitivitetsanalyse
•
Skyggepris:
Δ
Z
=
y
i
∗
⋅
Δ
b
i
\Delta Z = y_i^* \cdot \Delta b_i
Δ
Z
=
y
i
∗
⋅
Δ
b
i
•
100 %-regelen:
∑
∣
Δ
c
j
∣
/
tillatt
≤
1
\displaystyle \sum |\Delta c_j|/\text{tillatt} \leq 1
∑
∣Δ
c
j
∣/
tillatt
≤
1
•
Ny variabel: profitt
−
∑
\displaystyle - \sum
−
∑
ressurskostnad
≷
0
\gtrless 0
≷
0
•
Komplementær slakkhet:
y
i
s
i
=
0
y_i s_i = 0
y
i
s
i
=
0
Transportproblemer
•
Balansering:
∑
s
i
=
∑
d
j
\displaystyle \sum s_i = \sum d_j
∑
s
i
=
∑
d
j
•
Basisvariabler:
m
+
n
−
1
m + n - 1
m
+
n
−
1
•
MODI:
u
i
+
v
j
=
c
i
j
u_i + v_j = c_{ij}
u
i
+
v
j
=
c
ij
(basis),
Δ
i
j
=
c
i
j
−
u
i
−
v
j
\Delta_{ij} = c_{ij} - u_i - v_j
Δ
ij
=
c
ij
−
u
i
−
v
j
Nettverksmodeller
•
Dijkstra:
d
(
v
)
=
min
(
d
(
v
)
,
d
(
u
)
+
w
(
u
,
v
)
)
d(v) = \min(d(v), d(u)+w(u,v))
d
(
v
)
=
min
(
d
(
v
)
,
d
(
u
)
+
w
(
u
,
v
))
•
MST:
n
−
1
n-1
n
−
1
kanter, min total vekt
•
Max-flow min-cut:
max
f
=
min
\max f = \min
max
f
=
min
snittkapasitet
•
CPM: slakk
=
L
S
−
E
S
= LS - ES
=
L
S
−
ES
•
PERT:
t
e
=
(
a
+
4
m
+
b
)
/
6
t_e = (a+4m+b)/6
t
e
=
(
a
+
4
m
+
b
)
/6
,
σ
2
=
(
(
b
−
a
)
/
6
)
2
\sigma^2 = ((b-a)/6)^2
σ
2
=
((
b
−
a
)
/6
)
2
Heltallsprogrammering
•
LP-relaksasjon: øvre grense for IP-maks
•
Branch:
x
j
≤
⌊
f
⌋
x_j \leq \lfloor f \rfloor
x
j
≤
⌊
f
⌋
og
x
j
≥
⌈
f
⌉
x_j \geq \lceil f \rceil
x
j
≥
⌈
f
⌉
•
Fast kostnad:
x
≤
M
y
x \leq My
x
≤
M
y
, kostnad
=
K
y
+
c
x
= Ky+cx
=
Ky
+
c
x
Beslutningsanalyse
•
E
M
V
(
a
)
=
∑
p
i
v
(
a
,
s
i
)
\displaystyle EMV(a) = \sum p_i v(a,s_i)
EM
V
(
a
)
=
∑
p
i
v
(
a
,
s
i
)
•
E
V
P
I
=
E
V
∣
P
I
−
E
M
V
∗
EVPI = EV|PI - EMV^*
E
V
P
I
=
E
V
∣
P
I
−
EM
V
∗
•
Bayes:
P
(
s
∣
I
)
=
P
(
I
∣
s
)
P
(
s
)
/
P
(
I
)
P(s|I) = P(I|s)P(s)/P(I)
P
(
s
∣
I
)
=
P
(
I
∣
s
)
P
(
s
)
/
P
(
I
)
•
Minimax regret:
r
(
a
,
s
)
=
v
∗
(
s
)
−
v
(
a
,
s
)
r(a,s) = v^*(s) - v(a,s)
r
(
a
,
s
)
=
v
∗
(
s
)
−
v
(
a
,
s
)
Lagerstyring (EOQ)
•
Q
∗
=
2
D
S
/
H
Q^* = \sqrt{2DS/H}
Q
∗
=
2
D
S
/
H
•
T
C
∗
=
2
D
S
H
TC^* = \sqrt{2DSH}
T
C
∗
=
2
D
S
H
•
R
O
P
=
d
×
L
ROP = d \times L
ROP
=
d
×
L
(uten sikkerhetslager)
•
EPQ:
Q
p
∗
=
2
D
S
/
(
H
(
1
−
d
/
p
)
)
Q_p^* = \sqrt{2DS/(H(1-d/p))}
Q
p
∗
=
2
D
S
/
(
H
(
1
−
d
/
p
))
Køteori
•
ρ
=
λ
/
μ
\rho = \lambda/\mu
ρ
=
λ
/
μ
(M/M/1)
•
L
s
=
λ
/
(
μ
−
λ
)
L_s = \lambda/(\mu-\lambda)
L
s
=
λ
/
(
μ
−
λ
)
,
W
s
=
1
/
(
μ
−
λ
)
W_s = 1/(\mu-\lambda)
W
s
=
1/
(
μ
−
λ
)
•
L
q
=
λ
2
/
(
μ
(
μ
−
λ
)
)
L_q = \lambda^2/(\mu(\mu-\lambda))
L
q
=
λ
2
/
(
μ
(
μ
−
λ
))
,
W
q
=
λ
/
(
μ
(
μ
−
λ
)
)
W_q = \lambda/(\mu(\mu-\lambda))
W
q
=
λ
/
(
μ
(
μ
−
λ
))
•
Littles lov:
L
=
λ
W
L = \lambda W
L
=
λW
•
P
n
=
(
1
−
ρ
)
ρ
n
P_n = (1-\rho)\rho^n
P
n
=
(
1
−
ρ
)
ρ
n
Nøkkelformler per tema
Lineær programmering
•
Standardform (maks):
max
Z
=
c
x
\max Z = cx
max
Z
=
c
x
gitt
A
x
≤
b
Ax \leq b
A
x
≤
b
,
x
≥
0
x \geq 0
x
≥
0
•
Slakkvariabel:
∑
a
i
j
x
j
+
s
i
=
b
i
\displaystyle \sum a_{ij}x_j + s_i = b_i
∑
a
ij
x
j
+
s
i
=
b
i
,
s
i
≥
0
s_i \geq 0
s
i
≥
0
•
Optimalitetskriterium: alle
c
j
−
z
j
≤
0
c_j - z_j \leq 0
c
j
−
z
j
≤
0
(maks)
•
Dualitet:
max
c
x
=
min
y
b
\max cx = \min yb
max
c
x
=
min
y
b
(sterk dualitet)
Sensitivitetsanalyse
•
Skyggepris:
Δ
Z
=
y
i
∗
⋅
Δ
b
i
\Delta Z = y_i^* \cdot \Delta b_i
Δ
Z
=
y
i
∗
⋅
Δ
b
i
(innenfor tillatt område)
•
Tillatt koeffisientintervall:
[
c
j
−
Δ
−
,
c
j
+
Δ
+
]
[c_j - \Delta^-, c_j + \Delta^+]
[
c
j
−
Δ
−
,
c
j
+
Δ
+
]
•
100 %-regelen:
∑
∣
Δ
c
j
∣
/
tillatt
≤
1
\displaystyle \sum |\Delta c_j| / \text{tillatt} \leq 1
∑
∣Δ
c
j
∣/
tillatt
≤
1
•
Ny variabel-test: profitt
−
-
−
∑
\displaystyle \sum
∑
ressurskostnad
≷
0
\gtrless 0
≷
0
•
Komplementær slakkhet:
y
i
∗
⋅
s
i
∗
=
0
y_i^* \cdot s_i^* = 0
y
i
∗
⋅
s
i
∗
=
0
Transportproblemer og tilordning
•
Transportproblem:
min
∑
∑
c
i
j
x
i
j
\displaystyle \min \sum\sum c_{ij}x_{ij}
min
∑∑
c
ij
x
ij
gitt
∑
j
x
i
j
=
s
i
\displaystyle \sum_j x_{ij} = s_i
j
∑
x
ij
=
s
i
,
∑
i
x
i
j
=
d
j
\displaystyle \sum_i x_{ij} = d_j
i
∑
x
ij
=
d
j
•
MODI:
u
i
+
v
j
=
c
i
j
u_i + v_j = c_{ij}
u
i
+
v
j
=
c
ij
(basis),
Δ
i
j
=
c
i
j
−
u
i
−
v
j
\Delta_{ij} = c_{ij} - u_i - v_j
Δ
ij
=
c
ij
−
u
i
−
v
j
(ikke-basis)
•
Optimalitet: alle
Δ
i
j
≥
0
\Delta_{ij} \geq 0
Δ
ij
≥
0
•
Balansering: legg til fiktiv kilde/destinasjon med
c
=
0
c = 0
c
=
0
Nettverksmodeller
•
Dijkstra:
d
(
v
)
=
min
(
d
(
v
)
,
d
(
u
)
+
w
(
u
,
v
)
)
d(v) = \min(d(v), d(u) + w(u,v))
d
(
v
)
=
min
(
d
(
v
)
,
d
(
u
)
+
w
(
u
,
v
))
•
MST:
n
−
1
n-1
n
−
1
kanter for
n
n
n
noder, minimum total vekt
•
CPM:
Slakk
=
L
S
−
E
S
\text{Slakk} = LS - ES
Slakk
=
L
S
−
ES
. Kritisk sti: slakk
=
0
= 0
=
0
Heltallsprogrammering
•
LP-relaksasjon gir øvre grense (maks) for IP-optimal
•
Branch-and-bound:
x
j
≤
⌊
f
⌋
x_j \leq \lfloor f \rfloor
x
j
≤
⌊
f
⌋
eller
x
j
≥
⌈
f
⌉
x_j \geq \lceil f \rceil
x
j
≥
⌈
f
⌉
•
Fast kostnad:
x
≤
M
y
x \leq My
x
≤
M
y
, totalkostnad
=
K
y
+
c
x
= Ky + cx
=
Ky
+
c
x
•
Knapsack:
max
∑
v
j
x
j
\displaystyle \max \sum v_j x_j
max
∑
v
j
x
j
gitt
∑
w
j
x
j
≤
W
\displaystyle \sum w_j x_j \leq W
∑
w
j
x
j
≤
W
,
x
j
∈
{
0
,
1
}
x_j \in \{0,1\}
x
j
∈
{
0
,
1
}
Beslutningsanalyse
•
E
M
V
(
a
)
=
∑
p
i
⋅
v
(
a
,
s
i
)
\displaystyle EMV(a) = \sum p_i \cdot v(a, s_i)
EM
V
(
a
)
=
∑
p
i
⋅
v
(
a
,
s
i
)
•
E
V
P
I
=
E
V
∣
P
I
−
E
M
V
∗
EVPI = EV|PI - EMV^*
E
V
P
I
=
E
V
∣
P
I
−
EM
V
∗
der
E
V
∣
P
I
=
∑
p
i
⋅
max
a
v
(
a
,
s
i
)
\displaystyle EV|PI = \sum p_i \cdot \max_a v(a,s_i)
E
V
∣
P
I
=
∑
p
i
⋅
a
max
v
(
a
,
s
i
)
•
Bayes:
P
(
s
i
∣
I
)
=
P
(
I
∣
s
i
)
P
(
s
i
)
/
P
(
I
)
P(s_i|I) = P(I|s_i)P(s_i) / P(I)
P
(
s
i
∣
I
)
=
P
(
I
∣
s
i
)
P
(
s
i
)
/
P
(
I
)
•
E
V
S
I
=
E
M
V
med info
−
E
M
V
uten info
EVSI = EMV_{\text{med info}} - EMV_{\text{uten info}}
E
V
S
I
=
EM
V
med info
−
EM
V
uten info
Lagerstyring (EOQ)
•
Q
∗
=
2
D
S
/
H
Q^* = \sqrt{2DS/H}
Q
∗
=
2
D
S
/
H
(EOQ-formelen)
•
T
C
=
D
S
/
Q
+
H
Q
/
2
TC = DS/Q + HQ/2
TC
=
D
S
/
Q
+
H
Q
/2
→
T
C
∗
=
2
D
S
H
TC^* = \sqrt{2DSH}
T
C
∗
=
2
D
S
H
•
R
O
P
=
d
L
+
z
σ
d
L
T
ROP = dL + z\sigma_{dLT}
ROP
=
d
L
+
z
σ
d
L
T
(med sikkerhetslager)
•
Med backorder:
Q
∗
=
2
D
S
/
H
⋅
(
H
+
B
)
/
B
Q^* = \sqrt{2DS/H} \cdot \sqrt{(H+B)/B}
Q
∗
=
2
D
S
/
H
⋅
(
H
+
B
)
/
B
Køteori
•
ρ
=
λ
/
μ
\rho = \lambda/\mu
ρ
=
λ
/
μ
(M/M/1 utnyttelsesgrad, krav
ρ
<
1
\rho < 1
ρ
<
1
)
•
P
n
=
(
1
−
ρ
)
ρ
n
P_n = (1-\rho)\rho^n
P
n
=
(
1
−
ρ
)
ρ
n
,
P
0
=
1
−
ρ
P_0 = 1-\rho
P
0
=
1
−
ρ
•
M/D/1:
L
q
=
ρ
2
/
(
2
(
1
−
ρ
)
)
L_q = \rho^2/(2(1-\rho))
L
q
=
ρ
2
/
(
2
(
1
−
ρ
))
Vanlige feil å unngå
Lineær programmering
•
Glemmer ikke-negativitetskrav
x
j
≥
0
x_j \geq 0
x
j
≥
0
•
Blander
≤
\leq
≤
og
≥
\geq
≥
i bibetingelser — sjekk alltid retningen
•
Velger feil pivotelement — husk at
a
i
j
a_{ij}
a
ij
må være
>
0
> 0
>
0
i kvotient-testen
•
Glemmer å sjekke alle hjørnepunkter i grafisk løsning
Sensitivitetsanalyse
•
Bruker skyggepris utenfor det tillatte området — da er den ikke gyldig
•
Glemmer at ikke-bindende bibetingelser har skyggepris
=
0
= 0
=
0
•
Forveksler skyggepris med markedspris — skyggepris er intern verdi
•
Glemmer å inkludere alle ressurser i ny variabel-testen
Transportproblemer og tilordning
•
Glemmer å balansere problemet (tilbud
≠
\neq
=
etterspørsel)
•
Feil antall basisvariabler — husk
m
+
n
−
1
m+n-1
m
+
n
−
1
, og sjekk for degenerering
•
Glemmer å stryke rader/kolonner etter tildeling i startmetoden
•
Feil fortegn i stepping-stone-evalueringen
Nettverksmodeller
•
Glemmer å oppdatere restgrafen (bakover-kanter) i Ford-Fulkerson
•
Feil i forover/bakover-pass — sjekk max/min for forgjengere vs. etterfølgere
•
Glemmer at PERT-varians summeres langs kritisk sti, ikke standardavvik
•
Bruker Dijkstra med negative vekter — det fungerer ikke
Heltallsprogrammering
•
Runder av LP-relaksasjonen i stedet for å bruke branch-and-bound
•
Glemmer at LP-relaksasjon er en bound, ikke løsningen
•
Velger
M
M
M
for lite i Big-M-formuleringer
•
Glemmer subtour-eliminering i TSP
Beslutningsanalyse
•
Bruker EMV-kriteriet uten sannsynligheter — da trenger du maximin/maximax
•
Beregner EVPI feil — husk at du velger optimalt for hver tilstand, så tar forventning
•
Glemmer å normalisere posterior-sannsynligheter i Bayes
•
Løser beslutningstre forlengs i stedet for baklengs
Lagerstyring (EOQ)
•
Blander
D
D
D
(årlig) med
d
d
d
(daglig) etterspørsel
•
Glemmer varekostnad
D
C
DC
D
C
ved kvantumsrabatt — dette ledd kan endre optimal
Q
Q
Q
•
Bruker feil formel — EOQ vs. EPQ vs. backorder-modellen
•
Beregner ROP med feil antall arbeidsdager per år
Køteori
•
Glemmer stabilitetskravet
ρ
<
1
\rho < 1
ρ
<
1
— sjekk dette først
•
Blander
L
s
L_s
L
s
(systemet) med
L
q
L_q
L
q
(kun køen) — husk
L
s
=
L
q
+
ρ
L_s = L_q + \rho
L
s
=
L
q
+
ρ
•
Blander
W
s
W_s
W
s
(total tid) med
W
q
W_q
W
q
(kun ventetid) — husk
W
s
=
W
q
+
1
/
μ
W_s = W_q + 1/\mu
W
s
=
W
q
+
1/
μ
•
Bruker M/M/1-formler for M/M/s-problemer
Eksamenstips
Lineær programmering
•
Vis tydelig formulering: variabler, målfunksjon, bibetingelser
•
I grafisk metode: marker hjørnepunkter og skriv
Z
Z
Z
-verdien for hvert punkt
•
Kontroller at løsningen tilfredsstiller alle bibetingelser
Sensitivitetsanalyse
•
Les sensitivitetsrapporten nøye — skriv opp hva du bruker
•
Sjekk alltid om endringen er innenfor tillatt område
•
Vis 100 %-regelen eksplisitt ved samtidige endringer
Transportproblemer og tilordning
•
Start med å sjekke om problemet er balansert
•
Vis startløsning, MODI-beregning og eventuell forbedring steg for steg
•
I tilordning: skriv ut den ungarske metoden trinn for trinn
Nettverksmodeller
•
Vis Dijkstra-tabellen steg for steg med merkelapper
•
I CPM: tegn nettverk, vis forover- og bakover-pass, marker kritisk sti
•
I PERT: vis beregning av
t
e
t_e
t
e
,
σ
2
\sigma^2
σ
2
,
Z
Z
Z
-verdi og sannsynlighet
Heltallsprogrammering
•
Tegn branch-and-bound-treet med alle noder, bounds og fathoming-grunner
•
Vis LP-relaksasjon og incumbent tydelig
•
Ved modellering: definer variabler, mål, bibetingelser inkl. binære koblinger
Beslutningsanalyse
•
Tegn beslutningstabell, beregn EMV for alle alternativer
•
Vis EVPI-beregning steg for steg
•
I beslutningstre: marker valg med dobbel strek, vis EMV i hver node
•
Ved Bayes: vis tabell med prior, likelihood, joint og posterior
Lagerstyring (EOQ)
•
Vis alltid hvilken modell du bruker og skriv opp alle parametere
•
Beregn også nøkkeltall: antall ordrer, tid mellom ordrer, gjennomsnittslager
•
Ved kvantumsrabatt: vis beregning for hvert prisintervall
Køteori
•
Beregn alltid
ρ
\rho
ρ
først — sjekk at
ρ
<
1
\rho < 1
ρ
<
1
•
Vis alle steg:
ρ
\rho
ρ
,
L
s
L_s
L
s
,
L
q
L_q
L
q
,
W
s
W_s
W
s
,
W
q
W_q
W
q
,
P
0
P_0
P
0
•
I økonomisk analyse: vis TC-tabell for ulike antall servere
•
Bruk Littles lov som krysscheck:
L
s
=
λ
×
W
s
L_s = \lambda \times W_s
L
s
=
λ
×
W
s