Optimal skæring af emner

Du kan købe emner, som har en længde på 135 cm. Du vil skære emnet følgende stykker: 2 x 10 cm, 6 x 30 cm og 12 x 45 cm.

Hvor mange emner skal du købe, hvis du antager, at din klinge er ultra tynd?

Svar: 6 emner af 135 cm.

En lineær programmeringsmodel er anvendt til beregning af den optimale løsning. Problemer af denne type betegnes som Bin Packing Problems. Modellen og resultatet er vedhæftede. 

Når der er er "1" i Activity-kolonnen, betyder det, at x-variablen er aktiv. I nedenstående tilfælde ved vi, at den første definerede længde, skal skæres af emne 1

No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 x[1,1]       *              1             0             1 


Længde 2 skal skæres af emne 5:
       x[2,5]       *              1             0             1 

Du er velkommen til at kontakte mig, hvis du har en lignende udfordring eller har behov for et resultat i et andet format.

Den anvendte model følger med GLPK og er skrevet af Andrew Makhorin.

Nøgleord: udskæring