Når trenger vi heltall?

Lineær programmering forutsetter at variablene er kontinuerlige. Men mange bedriftsøkonomiske beslutninger er udelelige eller ja/nei: skal vi inngå kontrakt med en leverandør, åpne et lager, gjennomføre et investeringsprosjekt, sette et produkt i produksjon? Slike valg modelleres med binærvariabler $y \in \{0,1\}$, mens antall busser, ansatte eller produksjonsrunder krever generelle heltallsvariabler $x \in \{0,1,2,\dots\}$. En modell som blander heltalls-/binærvariabler med kontinuerlige variabler kalles et blandet heltallsproblem (MILP). I Analytic Solver angir man kravet ved å legge til en bibetingelse med type «bin» (for $\{0,1\}$) eller «int» (for hele tall) på beslutningscellene, og løser med den lineære motoren (simplex + branch-and-bound).

Faste kostnader og koblingsbetingelsen

Det viktigste mønsteret er faste kostnader (fixed charge): en kostnad $s$ som påløper så snart en aktivitet i det hele tatt brukes, uavhengig av nivå – en kontraktsavgift, en riggekostnad, en åpningskostnad. Vi kobler den kontinuerlige mengden $x$ til en binær $y$: legg $s\cdot y$ i (minimerings)målfunksjonen og bind mengden med koblingsbetingelsen $x \le M\,y$. Når $y=0$ tvinges $x \le 0$ (aktiviteten er «av» og ingen fast kostnad); når $y=1$ tillates $x \le M$. Her er $M$ en Big-M: velg den minste gyldige verdien (leverandørens kapasitet eller totalbehovet), aldri et vilkårlig stort tall – en for stor $M$ svekker LP-relaksasjonen og gjør branch-and-bound tregere. Vil man kreve «enten 0, eller minst en batch på $L$», legger man til $x \ge L\,y$ i tillegg.

Logiske betingelser

Binærvariabler lar oss oversette forretningslogikk til lineære betingelser: enten-eller (høyst én: $y_1+y_2 \le 1$; nøyaktig én: $y_1+y_2 = 1$), hvis-så ($y_2 \le y_1$ betyr «B krever A»), minst/høyst k av n ($\sum y_i \ge k$ eller $\le k$), gjensidig utelukkende ($y_1+y_2 \le 1$) og avhengige prosjekter ($y_1 = y_2$: begge eller ingen). Hver ekstra logisk betingelse innskrenker løsningsområdet, så den optimale verdien kan bare bli dårligere eller uendret – aldri bedre.

Eksempel 1 – Leverandørvalg med faste kostnader (Fjellbjørk Møbler)

Fjellbjørk Møbler trenger 500 kubikkmeter eik og kan kjøpe fra to leverandører. Leverandør A: fast kontrakt 3 000 kr, variabel pris 80 kr/enhet, kapasitet 400. Leverandør B: fast 1 500 kr, variabel 95 kr/enhet, kapasitet 500. Med $a,b \ge 0$ og binære $y_A,y_B$:

$\min\; 80a + 95b + 3000y_A + 1500y_B$ gitt $a+b \ge 500$, $a \le 400y_A$, $b \le 500y_B$.

B alene kan dekke behovet (kapasitet 500), men til høy variabel pris: $1\,500 + 95\cdot500 = 49\,000$ kr. Optimum (verifisert i Solver) er derimot å bruke begge: $a=400$ fra billige A og $b=100$ fra B. Kostnad: A gir $3\,000 + 80\cdot400 = 35\,000$, B gir $1\,500 + 95\cdot100 = 11\,000$, til sammen 46 000 kr. Poenget: A har lavest variabel pris og fylles opp til kapasitet; B dekker bare restbehovet på 100 enheter. Å ta med den faste kostnaden for begge (4 500 kr) lønner seg fordi besparelsen på variabel pris er større.

Eksempel 2 – Avrundingsfellen (Bjørke Verktøy)

Bjørke Verktøy kan kjøre to produktbatcher. Hver batch av produkt 1 gir dekningsbidrag 13 (i tusen kr) og krever 5 maskintimer; hver batch av produkt 2 gir 8 og krever 3 timer. Det er 11 maskintimer tilgjengelig, og antall batcher må være hele tall: $\max\; 13x_1 + 8x_2$ gitt $5x_1 + 3x_2 \le 11$, $x_1,x_2 \ge 0$ heltall.

LP-relaksasjonen (uten heltallskrav) gir $x_2 = 11/3 \approx 3{,}67$, $x_1 = 0$, med verdi $\approx 29{,}3$. Fristelsen er å avrunde: $x_2 = 3$ gir en gyldig løsning ($3\cdot3 = 9 \le 11$) med verdi $8\cdot3 = 24$. Men det er suboptimalt! Det ekte heltallsoptimet er $x_1 = 1$, $x_2 = 2$: da brukes $5 + 6 = 11$ timer (akkurat innenfor) og verdien blir $13 + 16 = \mathbf{29}$. Avrunding av LP-løsningen fant altså aldri den beste kombinasjonen, fordi heltallsoptimet ligger i et helt annet hjørne. Runder man i stedet opp til $x_2 = 4$, blir løsningen ugyldig ($3\cdot4 = 12 > 11$). Dette er avrundingsfellen: LP-verdien 29,3 er en øvre skranke, men veien til heltallsoptimet går gjennom branch-and-bound, ikke gjennom avrunding.

Slik testes temaet på BED4-eksamen

På BED4 kommer heltalls-/binæroppgaver typisk i to former. Formulering: du får en verbal beskrivelse (leverandørvalg med kontraktsavgifter, prosjektportefølje under kapitalbudsjett, lokalisering av lagre) og skal definere beslutningsvariabler, sette opp målfunksjon og bibetingelser – inkludert korrekte koblings- og logiske betingelser. Her gis det uttelling for å skille $x$ (mengde) fra $y$ (ja/nei) og for å skrive koblingen $x \le My$ med en fornuftig $M$. Tolkning: du får en Analytic Solver-rapport og skal lese av optimal løsning, identifisere bindende/ikke-bindende betingelser og forklare hvorfor et tilsynelatende billig alternativ ikke velges (fixed-charge-avveiningen). Nesten alltid dukker avrundingsfellen opp: du skal vise at LP-relaksasjonens løsning ikke uten videre kan avrundes, og at heltallsmodellen må løses direkte.

Studieguide: Heltalls- og binærprogrammering