Kappsäcksproblemet

Exempel på ett endimensionellt (restriktion) kappsäcksproblem: vilka lådor bör väljas för att maximera mängden pengar men ändå hålla totalvikten under eller lika med 15 kg? Ett multirestriktionsproblem kan beakta både vikten och volymen av lådorna. Modellering av formerna och storlekarna skulle istället utgöra ett packningsproblem.
(Lösning: om valfritt antal av varje låda är tillgängligt, så blir det tre gula lådor och tre grå lådor; om endast dom visade lådorna är tillgängliga, så blir det alla utom den gröna lådan.)

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. $x_{1}$ antal guldtackor, $x_{2}$ antal rullar siden, $x_{3}$ antal säckar salt och $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:

$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å $x_{1}$ … $x_{4}$.

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

Vi har även bivillkor:

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

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

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

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

$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 $x_{1}=2$, $x_{2}=4$, $x_{3}=0$ och $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.