TIØ4120 · NTNU

Studieguide for TIØ4120 Operasjonsanalyse

Komplett pensumoversikt for operasjonsanalyse ved NTNU — med forklaringer, sentrale begreper, eksamenstips og vanlige fallgruver. Eksamensoptimalisert basert på tidligere eksamener.

Introduksjon

Denne studieguiden dekker hele pensum i TIØ4120 Operasjonsanalyse, grunnkurs ved NTNU. Emnet gir en innføring i matematisk modellering av beslutningsproblemer og i de viktigste metodene i operasjonsanalysen (operations research): lineær programmering, dualitet og sensitivitetsanalyse, heltallsprogrammering, køteori, nettverksmodeller og dynamisk programmering, simulering og beslutningsmodeller.

Den røde tråden gjennom faget er modelleringssyklusen: du oversetter en verbal problembeskrivelse til en presis matematisk modell (definer variabler, målfunksjon og bivilkår), løser modellen med en passende algoritme, og tolker løsningen tilbake i den virkelige konteksten. På eksamen er evnen til å formulere en korrekt modell fra en ordbeskrivelse like viktig som å regne riktig.

Eksamen er en 4-timers skriftlig skoleeksamen med hjelpemiddelkode C (godkjent kalkulator og K. Rottmann «Matematisk formelsamling»). Settet består typisk av tre til fem oppgaver med oppgitt vekting. To bolker dominerer: en stor LP-oppgave (ofte ~40 %) som går gjennom hele kjeden formulering → dual → simpleks → sensitivitet, og en stor køteorioppgave (ofte ~40 %) der du skal sette opp en fødsels- og dødsprosess og utlede tilstandssannsynligheter og ytelsesmål. En heltallsprogrammeringsoppgave (ofte ~20 %) ber deg modellere et tilordnings- eller dimensjoneringsproblem med binær- og heltallsvariabler. I tillegg kommer korte teorispørsmål om Branch & Bound, diskret hendelsessimulering, inverstransformasjonsmetoden og baklengs rekursjon i dynamisk programmering — billige poeng som mange lar ligge.

Vektangivelsene over bygger på de eksamenssettene vi har hatt tilgang til, og disse er fra 2012/2013. NTNUs gjeldende emnebeskrivelse lister i tillegg nettverksmodeller (transport-, tilordnings- og strømproblemer), beslutningstrær og forventede verdier og praktisk simulering i regneark som sentrale tema. Disse er derfor dekket i guiden selv om de ikke er de tyngste bolkene i arkivmaterialet — sjekk alltid emnesiden og forelesers egne vektangivelser for ditt semester.

Sentrale verktøy du må beherske flytende: simpleksmetoden på tablåform (inkludert big-M), forholdet mellom primal og dual løsning, tolkning av skyggepriser og reduserte kostnader, oppsett av M/M/s/K-køer fra et tilstandsdiagram, Little’s formel med effektiv ankomstrate, og bruk av binærvariabler til å uttrykke logiske betingelser i en heltallsmodell.

Lineær programmering

Eksamensrelevant

Modellering av beslutningsproblemer som LP, utvidet form, grafisk løsning, simpleks på tablåform, big-M, spesialtilfeller og rekonstruksjon av det optimale tablået.

Hva er et LP-problem?

Et lineærprogrammeringsproblem (LP) består av en lineær målfunksjon som skal maksimeres eller minimeres, et sett lineære bivilkår og ikke-negativitetskrav på variablene. Ved maksimering:

$\max Z = \sum_{j} c_j x_j \quad\text{slik at}\quad \sum_j a_{ij}x_j \le b_i \ \ \forall i,\qquad x_j\ge 0.$

LP er selve ryggraden i TIØ4120: på begge eksamenssettene i arkivet er den største enkeltoppgaven en LP-oppgave som går gjennom hele kjeden formulering → tablå → dual → sensitivitet.

Modellering fra ordbeskrivelse

Fremgangsmåten er alltid den samme, og du bør skrive den ned i samme rekkefølge hver gang:

Definer beslutningsvariablene presist og med enhet: «la $x_j$ være antall enheter produsert av produkt $j$ per uke».
Sett opp målfunksjonen — maksimer dekningsbidrag/inntekt eller minimer kostnad.
Ett bivilkår per knapp ressurs eller avtale, med en kort tekstforklaring i parentes.
Ikke-negativitet, samt eventuelle minimums- og maksimumskrav.

Vær særlig oppmerksom på signalordene: «høyst / kapasitet» gir $\le$ , «minst / kontraktsforpliktelse» gir $\ge$ , og «brukes opp / kjøpes inn nøyaktig» gir likhet. Feil fortegn her forplanter seg gjennom hele oppgaven.

Eksempel — Produksjonsmiks

En verkstedbedrift lager tre produkter A, B og C. Per enhet krever de (stål, maskintimer, arbeidstimer) henholdsvis A=(4, 3, 6), B=(1, 1, 2), C=(2, 0, 4). Dekningsbidrag per enhet er 30, 9 og 16 kr. Bedriften har 60 enheter stål, 30 maskintimer og 100 arbeidstimer per uke.

La $x_1,x_2,x_3\ge 0$ være antall produserte enheter av A, B og C per uke:

$\max Z = 30x_1+9x_2+16x_3$
$4x_1+x_2+2x_3 \le 60$ (stål)
$3x_1+x_2 \le 30$ (maskintimer)
$6x_1+2x_2+4x_3 \le 100$ (arbeidstimer)

To modelleringsgrep som går igjen

Konveks kombinasjon av kapasitet. «Maskinen rekker enten 50 stoler eller 50 bord, eller en konveks kombinasjon» betyr $x_1/50+x_2/50\le 1$ , altså $x_1+x_2\le 50$ . Generelt: $x_1/K_1+x_2/K_2\le 1$ når kapasitetene er ulike.

Etterspørsel som avhenger av en annen variabel. «Det selges 10 stoler fast, pluss 3 stoler per bord» gir $x_{\text{stol}}\le 10+3x_{\text{bord}}$ , som må ryddes til standardform: $x_{\text{stol}}-3x_{\text{bord}}\le 10$ . Her er den vanligste feilen å glemme å flytte den andre variabelen over på venstresiden.

Utvidet form

For å regne med simpleks gjør vi alle bivilkår om til likheter:

$\le$ : legg til en slakkvariabel, $4x_1+x_2+2x_3+s_1=60$ . Slakken måler ubrukt kapasitet.
$\ge$ : trekk fra en overskuddsvariabel, $\sum_j a_{ij}x_j-e_i=b_i$ , og legg i tillegg til en kunstvariabel $a_i$ for å få en tillatt startbasis.
$=$ : ingen slakk, men det trengs en kunstvariabel.

Grafisk løsning

Med to variabler tegner du halvplanene, finner hjørnepunktene og regner ut $Z$ i hvert av dem. Optimum ligger alltid i et hjørnepunkt. Metoden er også et fullgodt svar når en oppgave spør om optimum i et lite, parametrisert problem: tegn området, finn de få tillatte hjørnene, sammenlign verdiene.

Simpleksmetoden på tablåform

Simpleks starter i et hjørne (typisk origo, med slakkvariablene i basis) og flytter seg til stadig bedre nabohjørner:

Innkommende variabel: ved maksimering den med mest negativ koeffisient i $Z$ -raden.
Forholdstallstesten (FHT): del RHS på de positive koeffisientene i pivotkolonnen; minste forhold peker ut den forlatende basisvariabelen.
Pivotering: gjør pivotelementet til 1 og null ut resten av kolonnen.

Optimum er nådd når alle koeffisientene i $Z$ -raden er ikke-negative.

Eksempel — Én fullstendig simpleksiterasjon

Initielt tablå for produksjonsmiksen over ( $Z$ -raden føres inn med negative koeffisienter):

Z: 1 | -30 -9 -16 | 0 0 0 | 0
s1: 0 | 4 1 2 | 1 0 0 | 60
s2: 0 | 3 1 0 | 0 1 0 | 30
s3: 0 | 6 2 4 | 0 0 1 | 100

Mest negativ er $-30$ , så $x_1$ går inn. FHT: $60/4=15$ , $30/3=10$ , $100/6\approx 16{,}7$ . Minste forhold er 10, så $s_2$ -raden er pivotraden og $s_2$ forlater basis. Etter pivotering på tallet 3:

Z: 1 | 0 1 -16 | 0 10 0 | 300
s1: 0 | 0 -1/3 2 | 1 -4/3 0 | 20
x1: 0 | 1 1/3 0 | 0 1/3 0 | 10
s3: 0 | 0 0 4 | 0 -2 1 | 40

Nå er $x_1=10$ og $Z=300$ . Fordi $x_3$ fortsatt har negativ redusert kostnad ( $-16$ ) er vi ikke ferdige — men hvis oppgaven sier «utfør nøyaktig én iterasjon», stopper du her og skriver eksplisitt at én iterasjon er gjennomført.

Big-M-metoden

Ved $\ge$ - eller likhetsrestriksjoner straffes kunstvariablene i målfunksjonen: $\max Z=\sum_j c_jx_j-M\sum_k a_k$ med $M$ svært stor. Trikset i tablået er at $Z$ -raden må skrives uten startbasisvariablene. Har du $a_1=b_1-\sum_j a_{1j}x_j+e_1$ , setter du dette inn i målfunksjonen, og koeffisientene foran $x$ -ene får hvert sitt $-M$ -ledd mens høyresiden blir $-Mb_1$ . Simpleks driver da kunstvariablene ut av basis av seg selv. Blir en kunstvariabel stående igjen i basis med positiv verdi i et ellers optimalt tablå, har det opprinnelige problemet ingen tillatt løsning.

Spesialtilfeller du må kunne kjenne igjen

Alternative optima: en ikke-basisvariabel har redusert kostnad 0 i optimalt tablå. Ta den inn i basis og du får et annet optimalt hjørne med samme $Z$ ; hele kanten mellom hjørnene er optimal.
Degenerert basis: en basisvariabel har verdi 0. Da kan FLERE ulike basiser beskrive samme hjørnepunkt, og to studenter som regner riktig kan ende med forskjellige optimale tablå. Det gir samme $x$ -løsning, men ulike dualverdier.
Ubegrenset: en variabel med negativ redusert kostnad har ingen positive elementer i kolonnen — FHT kan ikke gjennomføres.
Utillatt: kunstvariabel igjen i basis med positiv verdi.

Å rekonstruere hele det optimale tablået

En oppgavetype som er lett å bli tatt på senga av: du får bare slakkvariabelkolonnene i det optimale tablået og skal finne resten. Nøkkelen er at hver rad i det optimale tablået er en fast lineærkombinasjon av radene i det initielle tablået, og at nettopp slakkvariabelkolonnene avslører koeffisientene i den kombinasjonen (fordi slakkolonnene i starttablået utgjør en enhetsmatrise). Er den optimale $Z$ -raden under slakkvariablene $(\tfrac{15}{2},\tfrac34,0)$ , betyr det at optimal $Z$ -rad = 1·(initiell $Z$ -rad) + $\tfrac{15}{2}$ ·(rad 1) + $\tfrac34$ ·(rad 2) + 0·(rad 3). Regn ut den kombinasjonen kolonne for kolonne, gjenta for hver rad, og hele tablået faller på plass — RHS inkludert.

Nøkkelformler

•Generelt LP (maks): $\max Z=\sum_j c_j x_j$ slik at $\sum_j a_{ij}x_j \le b_i,\ x_j\ge 0$
•Slakkvariabel ( $\le$ ): $\sum_j a_{ij}x_j + s_i = b_i,\ s_i\ge0$ (måler ubrukt kapasitet)
•Overskudds- + kunstvariabel ( $\ge$ ): $\sum_j a_{ij}x_j - e_i + a_i = b_i$
•Forholdstallstesten: forlatende variabel $=\arg\min_i\{b_i/a_{ik} : a_{ik}>0\}$ for pivotkolonne $k$
•Optimalitetskriterium (maks): alle reduserte kostnader i $Z$ -raden $\ge 0$
•Big-M målfunksjon: $\max Z=\sum_j c_j x_j - M\sum_k a_k$
•Konveks kombinasjon av to kapasiteter: $x_1/K_1 + x_2/K_2 \le 1$
•Rekonstruksjon: optimal rad $=$ lineærkombinasjon av startradene med slakkolonnene som vekter

Vanlige feil

⚠️Definerer ikke variablene med enhet — «la x1 = lenestol» gir trekk; det skal stå «antall lenestoler produsert per uke».
⚠️Setter inn slakkvariabel ved en $\ge$ -restriksjon i stedet for overskuddsvariabel pluss kunstvariabel.
⚠️Glemmer å flytte en variabel over på venstresiden når etterspørselen avhenger av en annen variabel ( $x_1\le 10+3x_2$ må bli $x_1-3x_2\le 10$ ).
⚠️Velger forlatende variabel ut fra hele RHS-kolonnen i stedet for forholdstallstesten — bare positive pivotelementer teller.
⚠️Avslutter simpleks for tidlig: optimum krever at ALLE reduserte kostnader er ikke-negative.
⚠️Tolker et degenerert tablå som en regnefeil. Ulike optimale basiser for samme hjørnepunkt er helt normalt og skal kommenteres, ikke «rettes».

Eksamenstips

💡Følg fast mal ved modellering: variabler (med enhet) → målfunksjon → ett bivilkår per ressurs → ikke-negativitet. Skriv en kort parentes bak hvert bivilkår som sier hva det er.
💡Når oppgaven sier «utfør nøyaktig én iterasjon», stopper du etter én pivotering og skriver eksplisitt at du har gjort det — ikke regn videre.
💡Vis FHT-kolonnen i tablået. Sensor gir delpoeng for korrekt forholdstallstest selv om aritmetikken senere glipper.
💡Ved $\ge$ - eller =-restriksjoner tester eksamen nesten alltid big-M: innfør overskudds- OG kunstvariabler, og skriv Z-raden uten startbasisvariablene.
💡Får du oppgitt bare slakkvariabelkolonnene i det optimale tablået: bruk dem som vekter på radene i STARTtablået for å bygge opp resten.
💡Kontroller svaret mot sunn fornuft — negative produksjonstall eller en overforbrukt bindende ressurs betyr regnefeil.

Laster...

Laster…