WisFaq!

Verdelen van een aantal getallen over 3 groepen, met randvoorwaarde

Hoe verdeel ik N (niet noodzakelijk een veelvoud van 3) volstrekt willekeurige natuurlijke getallen, die in waarde al dan niet ver uit elkaar liggen,over 3 groepen zodanig dat de som van de getallen in elk van de 3 groepen, ongeveer gelijk is. Met ongeveer wordt wel impliciet verwacht die kombinatie te vinden die de onderlinge afwijkingen in de sommen minimaal maakt.

Jean-Pierre Vandamme
24-4-2003

Antwoord

Mooi probleem!
Ik heb het volgende bedacht:
Definieer 3 vectoren, N-dimensionaal, noem ze x, y en z, waarvan de kentallen allemaal 0 of 1 zijn.
Noem de vector van de gegeven natuurlijke getallen: a.
Het gaat nu om het minimaliseren van de volgende doelfunctie:
abs((x·a)-(y·a))+abs((x·a)-(z·a))+abs((y·a)-(z·a))
waarbij steeds het inproduct van de vectoren bedoeld wordt.
De randvoorwaarden zijn:
x+y+z=e, waarbij e een vector van N enen is.
Met Excel kun je dit probleem oplossen, bijvoorbeeld met de Oplosser uit het menu Extra.
Als je nadere uitleg nodig hebt, dan hoor ik het graag.

groet, Anneke

Anneke
25-4-2003