NYHET För att effektivisera julstöket gäller det att tänka smart. Vi har tagit hjälp av matematikern Per Håkan Lundow för att ta reda på hur man får plats med flest pepparkakor på en plåt, packar julklapparna bäst och delar ut paket utan att slita ut sig. Det visade sig vara svårare än väntat.
Per Håkan Lundow, Institutionen för matematik och matematisk statistik.
BildSara-Lena BrännströmHar du någon gång kliat dig i huvudet och tänkt något i stil med att ”det borde finnas ett bättre sätt”? Då är Per Håkan Lundow din vän. Här visar han hur det med matematikens hjälp är möjligt att räkna ut lösningar på några av julens vanliga problem.
Låt oss börja i pepparkaksbaket. Säg att du har en kvadratisk bakplåt och vill göra 12 likadana cirkelrunda pepparkakor, så stora som möjligt. Hur ska de placeras på plåten?
Om du provar dig fram kommer du rätt snabbt att märka att det bästa är att lägga pepparkakorna lite omlott. Vill du imponera på vännerna kan du säga att du precis löst ett matematiskt optimeringsproblem, där varje kakas diameter är 27,9918 procent av plåtens bredd och att plåten nu är fylld till nästan 74 procent med pepparkakor.
– Det här är ett av få fall där man vet att detta är en optimal lösning, säger Per Håkan Lundow, forskare och lärare i matematik.
Illustrationen visar en optimal placering av 12 pepparkakor på en kvadratisk plåt.
BildAnna-Lena LindskogOkej, vi höjer ribban. Nu vill du istället baka 49 pepparkakor. Omlottmönstret visar sig snabbt lämna en del tomma ytor, men eftersom 49 är lika med 7 gånger 7 borde väl ett rutmönster fungera? Jämnt och fint blir det i alla fall.
– Nej, överraskande nog är inte det fina rutmönstret optimalt, säger Per Håkan.
Lösningen blir att använda en algoritm, tillföra data och diverse bivillkor och låta en dator bearbeta problemet med hjälp av avancerad programvara.
– Bivillkoren är till exempel att du måste hålla dig inom bakplåten, pepparkakorna får inte överlappa och så vidare. I slutändan är det tusentals ekvationer som beskriver det, säger han.
Du har nu 49 lika stora pepparkakor. Till vänster: en enkel, men icke-optimal lösning. Till höger: Den bästa kända lösningen (baserad på data från www.packomania.com). Denna lösning innebär att pepparkakorna går att göra något större.
BildAnna-Lena LindskogLösningen till höger ovan är den bästa någon dator har hittat – men problemet innehåller så många faktorer att det faktiskt skulle kunna finnas en ännu bättre. Lägger vi till fler pepparkakor blir problemet snabbt mycket svårare. Antalet ekvationer som beskriver lösningarna växer nämligen lavinartat med antalet pepparkakor.
– Det här är ett exempel på ett vardagsproblem som är relativt enkelt att förstå men ändå visar sig vara väldigt svårt att lösa, säger Per Håkan.
Julklapparna är inhandlade och nu bär det av till julfirandet med tjocka släkten. Men det finns ett problem: Vi kan bara packa 165 kilo i bagaget innan bilen blir överlastad och de 10 paketen är rejält tunga. Du tvingas välja
BildAnna-Lena Lindskog
ut de klappar som tillsammans har störst pengavärde utan att totalvikten överskrids. Paketen har alla olika vikter och värden. Hur i hela friden räknar vi ut detta?
– Vilken tur att det finns en enkel matematisk modell för detta, säger Per Håkan Lundow.
Enkelt för en matematiker kanske.... Även här behövs en algoritm. Utan den blir det svårt eftersom det krävs 165 gånger 10, det vill säga 1 650, steg för att lösa just det där problemet! Algoritmen och datorn kommer fram till en lösning där packningen väger exakt 165 kilo – med maximal valuta för pengarna. Den goda nyheten är att om antalet paket nästa år är dubbelt så många blir problemet ”bara” dubbelt så svårt (så länge totalvikten är konstant), det växer alltså inte exponentiellt. Det är det matematikern menar med enkelt.
Vårt sista problem är en klassiker. I ett svagt ögonblick har du lovat att vara tomte och leverera julklappar till familjer runt om i kommunen. Vilken väg ska du ta för att besöka alla hus utan att passera samma två gånger? Problemet är känt som ”the travelling salesman problem”.
Hur blir tomtens rutt så effektiv som möjligt? Till vänster: Avstånd i kilometer mellan de 10 husen (A-J). Till höger: Optimal rutt med total sträcka 61 kilometer.
BildAnna-Lena LindskogDen vänstra bilden ovan visar husen och avstånden mellan dem. Du bor vid A. De röda vägarna i den högra bilden visar den optimala rutten. Faktum är att det bara finns två möjliga rutter i just det här fallet. Den andra har en total sträcka på 63 kilometer. (Kan du hitta den också?)
– Så fort man börjar försöka känner man nog själv att det är svårt. Dels är det i sig svårt att hitta en väg runt. Att dessutom hitta den bästa vägen skulle då i princip innebära att du måste känna till och undersöka alla tillåtna sätt att ta sig runt, men i praktiken är algoritmerna betydligt smartare än så. Med dagens algoritmer och datorer kan man hantera förbluffande stora problem, med tiotusentals hörn, det vill säga hus i det här fallet, säger Per Håkan.
Han brukar använda sig av det här problemet, och flera av de andra vi gått igenom, i undervisningen på tredje året i industriell ekonomi.
– Ungefär då, efter att ha läst en hel del matematik, är studenterna nätt och jämnt redo för det. Det är lätt att hitta bra lösningar som är nästan optimala men att hitta det riktigt optimala, och veta att det är optimalt, är inte så lätt. Ett sätt att garantera det är att pröva alla möjliga kombinationer men de är oftast för många – även för en dator, säger Per Håkan Lundow.