[excel 2007] Puzzel oplossen met solver

[HenkEisDS]

Op internet kwam ik de volgende puzzel tegen:
http://viewer.zmags.com/publication/b0fd98bd#/b0fd98bd/44

Oftewel:
In een land verdeeld in een matrix van 10 bij 10 staan 20 hutjes. Er worden 2 voedselpakketten gedropt in het gebied. Op welke locatie moeten deze pakketten worden gedropt om de totale loopafstand van de hutjes naar 1 van de twee pakketten te minimaliseren.

De afstand tussen cel A1 en A2 is 1
De afstand tussen cel A1 en B2 is 1,41 (Pythagoras)

Nu wil ik het natuurlijk niet met de hand doen, maar door middel van de solver van excel. Ik loop alleen tegen een paar problemen aan.

Dit is wat ik tot nu toe heb:
http://sjapeisjedies.nl/henkmeuk/Puzzel.xlsx

De afstand tot het dichtstbijzijnde bereken ik met (Excuses voor de Nederlandse excel):

=MIN(
WORTEL(ABS(RIJ($E$1) - RIJ($A$1)) ^ 2 + ABS(KOLOM($E$1) - KOLOM($A$1)) ^ 2),
WORTEL(ABS(RIJ($E$1) - RIJ($C$6)) ^ 2 + ABS(KOLOM($E$1) - KOLOM($C$6)) ^ 2)
)

Zoals je ziet is dit de berekening voor het huisje op E1, met voedselpakketten op A1 en C6. Deze formule heb ik nu voor vier huisje gemaakt en het is een klein genoege moeite om dit voor alle 20 huisjes te doen.

Maar................ik wil door de solver 2 pakketjes laten droppen net zolang tot M22 (de som van alle afstanden van alle huisjes) geminimaliseerd is. Logisch lijkt mij dan ook om 1en en 0en in te laten vullen door de solver. Dit kan echter niet gelezen worden door de bovenstaande formule. Er moet dus iets van een IF-statement in. Dan kom ik helaas in de problemen, want ik wil de afstand tot die 1en berekenen en heb dus de cel-locatie nodig, niet een waarde zoals meestal met ene IF-statement gebeurt.

MIN(
WORTEL(ABS(RIJ($J$2) - IF(A1>0,RIJ($A$1),Z99)) ^ 2 + ABS(KOLOM($J$2) - IF(A1>0,KOLOM($A$1),Z99)) ^ 2),
WORTEL(ABS(RIJ($J$2) - RIJ($C$6)) ^ 2 + ABS(KOLOM($J$2) - KOLOM($C$6)) ^ 2)
)

Hoe kan ik bovenstaande formule dynamisch maken zodat ik de afstand tot het voedselpakket kan laten berekenen, vanuit een cel die niet in de matrix zelf staat? Of zit ik helemaal op de verkeerde weg en is er een makkelijkere manier?


edit:
Zoals je ziet in de bovenste link is de puzzel een wedstrijd voor een magazine. De uiterste inleverdatum is helaas al verstreken.

Verder zijn er vast een hele hoop oplossingen te bedenken die geen gebruik maken van excel, maar ik wil het graag in excel kunnen.

[ Voor 6% gewijzigd door HenkEisDS op 06-12-2010 22:56 ]

[pedorus]

Ik zou toch even overnieuw beginnen. Er zijn zo'n 100*100 (eigenlijk 100*99, maar dat is lastiger) mogelijkheden, je zou dus ook zonder solver ze op 10.000 rijen kunnen doorrekenen en kunnen sorteren. De solver kent zo zijn eigenaardigheden, dus het is niet altijd zeker dat je daarmee een optimaal resultaat bereikt.

Wat hier fout gaat denk ik, is de manier waarop je de coordinaten neerzet. Je zet nu in een bepaalde cel 88 (pakkettje) of een letter (hulpbehoevende). Het lijkt me handiger om met coordinaten te werken. Je hebt dan 4 integers (1-10) die je wilt optimaliseren, de x en y coordinaten van de 2 pakketjes).

Als formule krijg je dan (voor burger A) iets als =sqrt(min((patk1x-5)^2+(pak1y-1)^2);(pak2x-5)^2+(pak2y-1)^2))
Dat is prima doortrekbaar voor 10.000 rijen, waarna sorteren op het totaal het juiste resultaat zal geven.

[Verwijderd]

Het is inderdaad mogelijk om dit probleem met solver op te lossen. Het probleem is dat je telkens op hut-niveau de gunstigste afstand moet kiezen tussen 2 variabele drop-locaties.
Dat kom je op 20 * 99 * ((99+1) /2) = 99.000 vergelijkingen.
Maar ik ben geen mathematicus dus wellicht is er een andere (betere) manier.

Met solver heb ik het uiteindelijk opgelost door 2 grids te creëren en de cellen met een hut te voorzien van een formule die de afstand uitrekende op basis van een variabel sector-nummer (drop-locatie), dus voor elk grid een eigen variabele. Deze kon de waarde 1 t/m 100 hebben.
Naast de 2 grids vergeleek ik telkens de afstanden voor elke hut t.o.v. de 2 drop-locaties en telde de laagste van de 2 afstanden bij elkaar op. De cel met deze som was de 'doelfunctie-cel' voor solver. En de 'variabele-cellen' de 2 cellen die het sector-nummer bevatte.

De uitkomst was identiek aan de uitkomst die ik al had verkregen met behulp van een programmaatje in VBA, dat overigens vele malen sneller en efficiënter was.

[HenkEisDS]

Dat ga ik eens proberen! Bedankt!