Kappsäcksproblemet

Kappsäcksproblemet är ett kombinatoriskt optimeringsproblem inom optimeringsläran. Namnet härstammar från den engelska beteckningen på problemet: knapsack problem.

Ursprungligen beskrevs ett problem där saker med olika volym ska packas ner i en kappsäck med begränsat utrymme så att samtliga saker inte kan packas ner. Sakerna anses också ha olika värden för personen som ska ta med sig kappsäcken. Frågan är vilka saker som ska packas ned i kappsäcken så att värdet av de nedpackade sakerna blir som störst.

Kappsäcksproblemet existerar inte bara som det klassiska problemet som beskrivits ovan, utan kan även hittas vid bland annat schemaläggning av flygplansrutter och produktionsplanering.

Exempel

Åsnedrivaren Åsneberg ska göra en resa mellan hamnstaden och en by i bergen. Det finns ett antal varor som de i byn betalar bra för. Byborna vill gärna ha guld, siden, salt och tvättsvamp. Åsneberg tjänar 500 kr/guldtacka, 200 kr/rulle siden, 150 kr/säcken salt och 100 kr/tvättsvamp. Åsneberg måste gå till en pålitlig guldsmed som inte förråder honom för rövarna som lurar längs vägen och smeden har bara två guldtackor. Åsneberg kan få köpa fyra rullar siden billigt från en sidenhandlare. Åsneberg kan köpa i princip hur mycket salt och tvättsvamp han vill. Hans åsna kan bära 80 kg packning, och packningens volym får inte överstiga 200 L. Guldet väger 1 kg/tacka, siden 2 kg/rulle, saltet 25 kg/säck och tvättsvampen 0,5 kg/st. Guldet tar 0,1 L/tacka, siden 5 L/rulle, saltet 20 L/säck och tvättsvampen 10 L/st.

Hjälp Åsneberg att tjäna så mycket som möjligt.

För att lösa problemet behöver vi en matematisk modell. Det första vi ska göra är att fundera på vad Åsneberg vill veta, det vill säga variabeldeklaration. ${\displaystyle x_{1}}$ antal guldtackor, ${\displaystyle x_{2}}$ antal rullar siden, ${\displaystyle x_{3}}$ antal säckar salt och ${\displaystyle x_{4}}$ antal tvättsvampar. Nästa steg är att bestämma vad vi ska optimera, d.v.s. målfunktion. I det här fallet är målfunktionen vad Åsneberg tjänar på de olika varorna. Tyvärr finns det också begränsningar som hindrar Åsneberg att tjäna hur mycket som helst på sin resa. Dessa begränsningar kallas bivillkor.

Målfunktionen ser ut som följande:

${\displaystyle max(z)=500x_{1}+200x_{2}+150x_{3}+100x_{4}}$

Det är brukligt att skala om målfunktioner för att underlätta räknandet. I det här fallet kan vi dividera med 10, värdet av optimum ändras (10 gånger) men det påverkar inte värdena på ${\displaystyle x_{1}}$ … ${\displaystyle x_{4}}$.

${\displaystyle max(z)=50x_{1}+20x_{2}+15x_{3}+10x_{4}}$

Vi har även bivillkor:

${\displaystyle x_{1}+2x_{2}+25x_{3}+0,5x_{4}\leq 80}$ (vad åsnan klarar av att bära i vikt)

${\displaystyle 0,\!1x_{1}+5x_{2}+20x_{3}+10x_{4}\leq 200}$ (vad åsnan klarar av att bära i volym)

${\displaystyle x_{1}\leq 2}$ (antal tillgängliga guldtackor)

${\displaystyle x_{2}\leq 4}$ (antal tillgängliga sidenrullar)

${\displaystyle x_{1},x_{2},x_{3},x_{4}\in N}$ (d.v.s. icke-negativa heltal)

Nu har vi optimeringsproblemet uttryckt i en matematisk modell och kan angripa det med lämplig metod, till exempel trädsökning.

En tillåten lösning på problemet är ${\displaystyle x_{1}=2}$, ${\displaystyle x_{2}=4}$, ${\displaystyle x_{3}=0}$ och ${\displaystyle x_{4}=17}$. Denna lösning är bevisligen optimallösningen.

Källor

• Kaj Holmberg, Kombinatorisk optimering med linjärprogrammering, 2006, Matematiska Institutionen Linköpings tekniska högskola.