Kappsäcksproblemet
Från Rilpedia
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. x1 antal guldtackor, x2 antal rullar siden, x3 antal säckar salt och x4 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) = 500x1 + 200x2 + 150x3 + 100x4
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å x1 … x4.
max(z) = 50x1 + 20x2 + 15x3 + 10x4
Vi har även bivillkor:
(vad åsnan klarar av att bära i vikt)
(vad åsnan klarar av att bära i volym)
(antal tillgängliga guldtackor)
(antal tillgängliga sidenrullar)
(d.v.s. positiva 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 x1 = 2, x2 = 4, x3 = 0 och x4 = 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.
