Dozenprobleem

Er zijn 8 voorwerpen met elk volgend gewicht:
12,15,14,18,11,13,8,9 (in kg). Deze 8 voorwerpen worden gepakt in dozen die elk ten hoogste 25 kg wegen. De vraag is nu het aantal dozen te minimaliseren. (Het zou als een integer probleem moeten worden geformuleerd).
Mijn oplossing is als volgt:
De slechtste opl. zou zijn : 8 dozen (1 vw. per doos). We willen dus het aantal dozen minimaliseren waar gewicht=0 is. Per doos creëeren we dan een y-variable (INT) die ofwel 0 of 1 (- doos gebruikt) is.
Hoe formuleer ik dit in een wiskundig IP-probleem?

Dank bij voorbaat,
Jan

Jan
Student universiteit België - woensdag 9 augustus 2006

Antwoord

Hallo Jan,

Zoek je een algemene oplossingsmethode voor dit soort problemen, of enkel een oplossing voor dit specifiek vraagstuk? Want dat laatste is vrij eenvoudig: het totale gewicht is 100 kg, dus je hebt minstens 4 dozen nodig. In 4 lukt het echter niet, want dan moet je in elke doos exact 25 kg steken. Maar dat voorwerp van 18 kg kan niet aangevuld worden (er zijn geen voorwerpen van 7 kg).

Dus je hebt minstens 5 dozen nodig. En een oplossing met 5 is vrij snel gevonden (er zijn er meerdere, bv 18 / 13+12 / 14+11 / 15+9 / 8)

Als je een algemene methode wou, dan reageer je maar he...
Groeten,
Christophe.

Christophe
woensdag 9 augustus 2006

©2001-2024 WisFaq