Hva er lineær programmering?

Lineær programmering (LP) er en metode for å finne den beste beslutningen når du har et klart mål og begrensede ressurser. En LP-modell består alltid av tre byggeklosser: beslutningsvariabler (hva vi kan styre, f.eks. antall enheter $x_1, x_2$), en målfunksjon (det vi vil maksimere eller minimere, f.eks. samlet dekningsbidrag), og bibetingelser (det som begrenser oss, typisk ressurskapasiteter). I BED4 løses modellene i Analytic Solver med Standard LP/Quadratic-motoren, som forutsetter at både mål og bibetingelser er lineære.

Den generelle formen er $\max\ c^{\top}x$ gitt $Ax \le b$ og $x \ge 0$. LP hviler på fire antakelser: proporsjonalitet (dobbelt volum gir dobbelt bidrag og ressursbruk), additivitet (totalen er summen av delene), delelighet (variablene kan ta brøkverdier) og determinisme (koeffisientene er kjente tall). Brytes proporsjonaliteten – f.eks. ved kvantumsrabatt – blir modellen ikke-lineær og må løses med en annen motor.

Å formulere en modell

Oversettelsen fra tekst til modell er selve kjernen på eksamen. En kapasitet blir en $\le$-bibetingelse, et minimumskrav blir $\ge$, og en fast blandingsmengde blir en likhet $=$. Et salgstak skrives $x_1 \le 60$. Andelskrav som «minst 40 % IPA» skrives $x_2 \ge 0{,}4(x_1+x_2)$ og ryddes til lineær form $-0{,}4x_1 + 0{,}6x_2 \ge 0$. Husk at alle ledd i en bibetingelse må ha samme enhet – du kan ikke summere timer og kroner.

Grafisk løsning for to variabler

Med to variabler kan modellen løses grafisk. Man tegner hver bibetingelse som en linje, skraverer det feasible området (snittet av alle halvplan – alltid konvekst), og skyver en iso-bidragslinje utover til det siste hjørnet den berører. Hjørnepunktsteoremet garanterer at et optimum ligger i et hjørne, så det holder å evaluere målfunksjonen i hjørnene.

Gjennomregnet eksempel 1 – Fjellbjørk Møbler (produktmiks). Fjellbjørk lager spisebord ($x_1$, dekningsbidrag 900 kr) og stoler ($x_2$, 500 kr). Saging: $3x_1 + x_2 \le 240$ timer. Montering: $2x_1 + 2x_2 \le 200$ timer. Lakkering (kun bord): $x_1 \le 60$. Modellen blir

$\max\ 900x_1 + 500x_2$ gitt $3x_1+x_2\le240,\ 2x_1+2x_2\le200,\ x_1\le60,\ x_1,x_2\ge0.$

I optimum er montering og lakkering bindende. Løser vi likningssettet $x_1=60$ og $2x_1+2x_2=200$, får vi $2x_2 = 200-120 = 80$, altså $x_2 = 40$. Optimal miks er dermed $(x_1,x_2) = (60,40)$ med dekningsbidrag $900\cdot60 + 500\cdot40 = 54000 + 20000 = 74000$ kr. Sagingen bruker $3\cdot60 + 40 = 220$ timer, altså 20 timer ledig – den er ikke-bindende.

Produktmiks med flere produkter og blanding

Med tre eller flere produkter faller den grafiske metoden bort, men modellstrukturen er den samme og Solver løser den. Et beslektet problem er blandingsproblemet, der ingredienser blandes til lavest kost under kvalitetskrav.

Gjennomregnet eksempel 2 – Kornmo bakeri (blanding). Kornmo skal lage 100 kg deig av hvetemel ($x_1$, 8 kr/kg) og rugmel ($x_2$, 6 kr/kg). Proteinkravet er minst 10 % ($0{,}12x_1 + 0{,}08x_2 \ge 10$), fiberkravet minst 5 % ($0{,}03x_1 + 0{,}09x_2 \ge 5$), og blandingen skal veie nøyaktig 100 kg ($x_1 + x_2 = 100$). Vi minimerer $8x_1 + 6x_2$. Analytic Solver (eller scipy) gir optimal blanding $x_1 = 50$ kg hvete og $x_2 = 50$ kg rug til en kostnad på $8\cdot50 + 6\cdot50 = 400 + 300 = 700$ kr. Proteinkravet er akkurat bindende ($0{,}12\cdot50 + 0{,}08\cdot50 = 10$), mens fiberkravet gir $0{,}03\cdot50 + 0{,}09\cdot50 = 6$ – ett prosentpoeng over kravet, altså overskudd.

Standardform og slakkvariabler

Simpleksmetoden, som Solver bygger på, krever standardform: hver $\le$-bibetingelse gjøres om til en likhet ved å legge til en ikke-negativ slakkvariabel, f.eks. $3x_1 + x_2 + s_1 = 240,\ s_1 \ge 0$. Slakken måler ubrukt kapasitet. For $\ge$-krav trekkes en overskuddsvariabel fra. Simpleks starter i et hjørne og flytter til stadig bedre nabohjørner til ingen forbedring er mulig.

Hvordan LP testes på BED4-eksamen

På eksamen får du en case (en fiktiv bedrift) og skal formulere en fullstendig LP-modell: definere variablene i ord, sette opp målfunksjonen og alle bibetingelser med riktig ulikhetstegn og enheter. Ofte skal du løse et to-variabelproblem grafisk eller sette opp modellen slik den ville legges inn i Analytic Solver (målcelle, justerbare celler, bibetingelser). Du bør kunne identifisere hvilke bibetingelser som er bindende, regne ut den optimale verdien, og forklare antakelsene bak LP. Regn alltid kontroll: sett den optimale løsningen inn i hver bibetingelse og sjekk at den er oppfylt.

Studieguide: Lineær programmering