courses/tiø4120 ✨

TIØ4120 - Operations Research, Introduction

Overview of the Operations Research Modeling Approach (11 pages)

Define the problem of interest and gather relevant data. (data mining)
Formulate a mathematical model to represent the problem. (decision variables, objective function, constraints, parameters, sensitivity analysis, linear programming model, overall measure of performance)
Develop a computer-based procedure for deriving solutions to the problem from the model. (algorithms, optimal, solution, satisficing, heuristic procedures, suboptimal solution, metaheuristics, postoptimality analysis, what-if analysis, sensitivity analysis)
Test the model and refine it as needed. (model validation)
Prepare for the ongoing application of the model as prescribed by management. (decision support system)
Implement.

Introduction to Linear Programming (52 pages)

LP-modell

Indekser, Mengder
Parametre
Variable
Modell
- Objektivfunksjon / målfunksjon
- Restriksjoner / begrensninger

Antagelser i LP

Proporsjonalitet
Additive ledd
Delbarhet (kontinuerlige variabler)
Parametre kjent og konstant

LP-modell på utvidet form

Først, standardform
- Max z
- Alle restriksjoner på <=-form
- Alle variabler >= 0
Så, utvidet form
- Alle restriksjoner på =-form
- Slackvariable, én per restriksjon
  - s = 0 medfører bindende restriksjon
  - s > 0 medfører ressurser til overs
  - s < 0 medfører ulovlig løsning

Solving Linear Programming Problems: The Simplex Method (60 pages)

Simplex

Krever utvidet form
Fokuserer kun på mulige hjørnepunkter
Iterativ metode
Velger origio som startløsning
Vei til optimum følger kantene av mulighetsrommet
Beregner naboløsningen som gir størst forbedringsrate i målfunksjonen
Hvis ingen naboløsning er bedre har vi funnet den optimale

Simplex-tablå

Basis	z	x1	x2	...	s1	s2	...	RHS	Forholdstest

Optimalitet dersom alle koeffisienter i øverste rekke (målfunksjon) er større eller lik 0.

Iterasjon:

Pivotkolonne: den med mest negativ koeffisient i målfunksjonen
- Dersom uavgjort kolonnetest: like gode søkeretninger, velg én.
Pivotrad, ved forholdstalltest: $\argmin_i{\left( \frac{\text{RHS}_i}{A_{ij}} \mid A_{ij} > 0 \right)}$ $a r g m i n_{i} (\frac{RHS _{i}}{A _{i j}} ∣ A_{i j} > 0)$
- Dersom uavgjort forholdstalltest: degenerert løsning (to restriksjoner blir bindende samtidig), velg én.
- Dersom alle $A_{ij} < 0$ : ubegrenset mulighetsrom

To-fase-Simplex (TODO)

Dersom vi har et min-problem, eller vi har =-begrensning

Kan introdusere Big-M og kunstvariabler
Løses i to separate steg:
1. Finn startløsning (få kunstvariable ut av basis)
2. Finn optimal løsning (kunstvariable lik 0)

Duality Theory and Sensitivity Analysis (65 pages)

Parametere i en LP-modell:

Målfunksjonskoeffisienter $C_j$
Restriksjonenes høyresider $B_i$
Restriksjonskoeffisienter $A_{ij}$

Sensitivitetsanalyse

Hva skjer med den optimale løsningen når en endrer parameterverdiene?

Sensitivitetsområde for $C_j$ $C_{j}$ : Verdiområdet for $C_j$ $C_{j}$ hvor den optimale løsningen forblir optimal.
- Legge til delta ( $C_j^* = C_j + \Delta$ ) i starten av Simplex, bli kvitt den i siste steg ved å gange den inn i innkommende rad.
Sensitivitetsområde for $B_i$ $B_{i}$ : Verdiområdet for $B_i$ $B_{i}$ hvor variabelverdiene kan skifte verdi, men variablene i basis forblir de samme. Samme hjørnepunkt forblir optimalt, men verdiene av variablene i basis kan endre seg.
- Legge til delta i RHS i starten av Simplex, se hvordan den propegerer, finn intervall tilslutt ved basisvariables >= 0.
Endre $A_{ij}$ : Løs på nytt
Legge til restriksjon: Løs på nytt dersom optimal løsning bryter den
Legge til en variabel: Her kan vi gjøre noe smart
Skyggepris: marginalverdien for ressursen, også kalt dualverdi.
- Endring i z per endring i $B_i$ .
- Sensitivitetsområdet for $B_i$ gir også info om området hvor skyggeprisen forblir gyldig.
- Leses fra koeffisienten til tilhørende slackvariabel i målfunksjonen i optimalt tablå

Dualitet

Primal	Dual
max	min
min	max
restriksjoner	variabler
variabler	restriksjoner
målfunksjonerskoeffisienter	RHS
RHS	målfunksjonskoeffisienter

Optimal løsning på dualen gir skyggeprisen til restriksjonene i primalen.
Optimal løsning er eneste som er feasible for både primalen og dualen.
Ny variabel i primal = Ny restriksjon i dual.

SOB-reglene (TODO)

Network Optimization Models (53 pages)

Minimalt spenntre problem (MST) (Prim's algoritme)

Korteste vei-problem (Dijkstra)

Dijkstras algoritme forutsetter at alle buekostnader er ikkenegative.

Maks flyt-problem

Max-flow min-cut teoremet: For et nettverk med én kilde og ett sluk, er maks flyt mellom disse lik verdien av det minste kuttet over nettverket

Min-kost-flyt-problemet

Integer Programming (57 pages)

Hvorfor heltallsprogrammering?

Beslutningsvariable må representere et helt antall
Modellering av logiske restriksjoner

Bruk av binærvariable

Enten-eller restriksjoner: + My og + M(1-y)
K av N restriksjoner: én y per restriksjon
Fast og variabel kostnad: min z = Cx + Fy; x - My <= 0

Branch and bound

Tre kriterier for å ikke forgrene fra node i B&B-treet:

Finner heltallig løsning (hmm? TODO)
Finner ingen lovlig løsning
LP-løsning dårligere enn kjent IP-løsning

Non-Linear Programming (56 pages)

Vi deler problemer inn i problemklassene konvekse problem og ikke-konvekse problem. Vi kaller et problem uten restriksjoner på variablene for konvekst dersom:

Vi maksimerer en konkav funksjon, eller
Vi minimerer en konveks funksjon

Lagrange multiplikator metoden

Har en funksjon å minimere, $z = f(x_1, \dots)$ , samt ekstra begrensninger, feks. en kapasitet.
Omformuler begrensninger til $b_1(x_1, \dots) = 0$ .
$L(x_1, x_2, \dots, \lambda_1, \lambda_2, \dots) = f(x_1, \dots) + \lambda_1(b_1) + \lambda_2(b_2) + \dots$
Løs likningssettet $\frac{\partial L}{\partial z} = 0$ for $z = x_1, x_2, \dots, \lambda_1, \lambda_2, \dots$

I likhet med skyggepris, er $\lambda_i$ kostnadsbesparelsen (virkning på $z$ ) dersom RHS i begrensning $i$ økes med $1$ .

KKT-betingelser (Karush-Kuhn-Tucker) (TODO)

Decision Analysis (37 pages)

Beslutningskriterier

Maximin-kriteriet (pessimistisk)
Maximum likelihood-kriteriet
Bayes' regel

Sensitivitetsanalyse (TODO ?)

Beslutningstrær

Beslutningsnoder (kvadrater)
Hendelsesnoder (sirkler)
Kanter som binder disse sammen
(og løvnoder som representerer pay-off)

Verdi av informasjon (TODO)

Differanse på forventet verdi og forventet verdi ved informasjon.

Expected Value of Perfect Information (EVPI)
Expected Value of Experiment (EVE)

Risiko og nyttefunksjoner (TODO)

Ved å substituere nytte for resultat i beslutningstre er det lett å regne seg frem til optimale beslutninger gitt at vi maksimerer forventet nytte.

Nyttefunksjoner, under y = x: risikoavers
Nyttefunksjon, y = x: risikonøytral
Nyttefunksjoner, over y = x: risikosøkende

Queueing Theory (53 pages)

Kendall's notation

Fordeling av ankomsttider
Fordeling av betjeningstider
Antall betjeningsstasjoner (s)
Kapasitet i systemet (ventende og betjente)
Størrelse på kundegrunnlag

Fordelinger kan være

M: eksponentialfordeling
D: degenerert (konstant, deterministisk)
E_k: Erlang-k fordeling
G: generell fordeling

Køsystem

Notasjon for køsystem i stabil tilstand

$P_n$ , sannsynlighet for nøyaktig n kunder i systemet
$L$ , forventet antall kunder i systemet
$L_q$ , forventet kølengde (ekskl. kunder som betjenes)
$\mathcal{W}$ , tid i systemet (inkl. betjeningstid) for hver enkelt kunde
$W = E(\mathcal{W})$ , forventet tid i systemet
$\mathcal{W}_q$ , ventetid i køen (ekskl. betjeningstid) for hver enkelt kunde
$W_q = E(\mathcal{W}_q)$ , forventet ventetid

Fødsels- og dødsprosesser (Markov-kjeder), overgangsdiagram

Balking (TODO)

Inventory Theory (62 pages) (TODO)

Hva er riktig lagernivå?
Hvor mye skal bestilles ( $Q^*$ ) og når/hvor ofte?

Lagermodeller kan klassifiseres som:

deterministiske eller stokastiske,
kontinuerlige eller periodiske

Modellkomponenter

$K$ , kostnad per bestilling
$c$ , kostnad per enhet
$h$ , lagerkostnad per enhet per tidsenhet (holding cost):
$d$ , etterspørselrate per tidsenhet (demand):
$p$ , shortage kostnad per enhet per tidsenhet
rentesats (TODO ?)
ledetid (TODO ?)

Beregne

$Q^*$ , optimalt ordrekvantum
$R$ , bestillingspunkt, lagerkvantum ved ny bestilling

Simulation (47 pages)

Simuleringsmodeller kan klassifiseres som:

analoge eller digitale,
statiske eller dynamiske,
diskrete eller kontinuerlige og
deterministiske eller stokastiske.

Elementene i en simuleringsmodell

En definisjon av systemets tilstand
Identifikasjon av mulige tilstander
Identifikasjon av mulige hendelser
Simuleringsklokke som holder rede på tiden
Metode for å generere tilfeldige hendelser
Beskrivelse av hvilken effekt hendelsene har på tilstanden til systemet (overgangsfunksjoner)

Tilfeldige tall

Krav til en generator av tilfeldige tall:

Tallene må være uavhengige
Tallene som genereres må være uniformt fordelt
Sekvensen av tall bør være reproduserbar
Tallene må kunne genereres raskt

Kongruensmetoder: Heltall og uniform fordeling (TODO)

Mixed congruential method
Multiplicative congruential method
Additive congruential method

Andre sannsynlighetsfordelinger

Direkte oppslag
Inverstransformasjonsmetoden (TODO)
Akseptanse/avslag-metoden

Simuleringsklokka (tidsinkrement)

Hendelsesbaserte tidsinkrement: Oppdaterer klokka med tidspunktet hvor neste hendelse inntreffer.
Faste tidsinkrement: Inkrementerer klokka men en liten fast tidsenhet ved hver iterasjon.