Rygsækproblem

Rygsækproblemet er et af de mest studerede optimeringsproblemer inden for operationsanalyse, kombinatorisk optimering og datalogi. Dette skyldes dels problemets enkelthed dels dets store anvendelighed. Problemet bliver ofte præsenteret på følgende måde: antag at vi har en mængde af artikler som hver har en værdi og en vægt. Givet er også en rygsæk som har en grænse for hvor meget den kan bære. Rygsækproblemet er således givet ved: hvilke artikler skal fyldes i rygsækken for at maksimere værdien af rygsækkens indhold mens kapaciteten samtidig er overholdt.

På trods af denne lidt naive definition har rygsækproblemet mange praktiske anvendelser; maksimering af den forventede profit ved udvælgelse af (diskrete) aktiver givet et budget og når for eksempel et stykke stof skal skæres i mønstre og spildet skal minimimeres.

Matematisk formulering

Lad mængden af artikler være givet ved $I$. Hver artikel $i\in I$ har en værdi og en vægt henholdsvis givet ved $p_i$ og $w_i$. Rygsækkens kapacitet kaldes her $c$. Lad nu $x_i$ være en binær variable, som antager værdien 1 hvis artikel $i$ vælges og 0 ellers. På denne måde kan problemet skrives som

$\begin{array}{cc}\max & \sum _{i\in I}{p}_i{x}_i\\ \text{under bibetingelsen}& \sum _{i\in I}{w}_i{x}_i\le c\\ & x_i\in \{0,1\},\mathrm{\forall }i\in I\end{array}$