Springen naar inhoud

Optimalisatie kavelverdeling in woonwijk


  • Log in om te kunnen reageren

#1

Woeka

    Woeka


  • 0 - 25 berichten
  • 6 berichten
  • Gebruiker

Geplaatst op 09 januari 2011 - 19:53

Ik zit in een Collectief (particulier) opdrachtgeverschap waarmee we met een groep een woonwijk gaan neerzetten. Nu willen we de kavels gaan toewijzen aan huishoudens. Dat leek me nu echt een wiskundig probleem wat gewoon op te lossen moet zijn. Alleen hoe .. iemand die me daar verder mee kan helpen? Een simplex algoritme dacht ik eerst aan .. maar dat lijkt het toch niet helemaal te kunnen vatten.

Probleem 1
Het zo optimaal mogelijk toewijzen van 20 kavels in een woonwijk. Twintig huishoudens moeten geplaatst worden op 20 kavels. Ieder huishouden geeft een ranking aan ieder kavel van 1 tot 20 waarbij 1 de hoogste is. Daarmee zou de wijk zo optimaal mogelijk in gedeeld moeten kunnen worden. Volgens mij zijn de mogelijkheden 20! dus iets van
2,4 * 10^18 beetje te veel om brute force alles af te gaan.

Hieronder wat ik denk dat het zou moeten zijn:

Optimalisatie:
x1 + x2 + x3 + ... + x20 -> min

Waarbij x1, x2, ... , x20 de waarde heeft van de ranking van het huishouden dat geplaatst is op een bepaald kavel.

a1, a2, a3, .. , a20 = willekeurige volgorde van (1+2+3+4+..+20) waarbij ieder getal eenmaal voorkomt = 210
b1, b2, b3, .. , b20 = idem
.
.
t1, t2, t3, .. , t20 = idem

Waarbij a1-20 de ranking is van een huishouden voor de kavels dat voor 20 huishoudens kom je op a-t uit.

Waarbij:
x1 element uit (a1, b1, c1, .. , t1)
x2 element uit (a2, b2, c2, .. , t2)
.
.
x20 element uit (a20, b20, c20, .. , t20)

en
0 < x1 + x2 + x3 + ... + x20 < 21

Vraag 1
Hoe is het bovenstaande probleem op te lossen?

Probleem 2
Zo simpel als het probleem hierboven is geschetst is het natuurlijk niet, maar wel een goed begin als dat iig duidelijk is. Naast de ranking die huishoudens kunnen geven aan een kavel heeft een huishouden zelf ook een ranking op basis van binnenkomst in de groep.

Vraag 2
Hoe is de ranking van binnenkomst mee te nemen en hoe is het bovenstaande probleem dan op te lossen?

Iemand die met hierbij kan helpen?

Veranderd door Woeka, 09 januari 2011 - 19:54


Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 10 januari 2011 - 13:26

[quote name='Woeka' post='649286' date='9 January 2011, 19:53']Vraag 1
Hoe is het bovenstaande probleem op te lossen?[/quote]
Dit is een niet-triviaal probleem, en het is op te lossen met Bericht bekijken
Probleem 2
Zo simpel als het probleem hierboven is geschetst is het natuurlijk niet, maar wel een goed begin als dat iig duidelijk is. Naast de ranking die huishoudens kunnen geven aan een kavel heeft een huishouden zelf ook een ranking op basis van binnenkomst in de groep.
Hoe is de ranking van binnenkomst mee te nemen en hoe is het bovenstaande probleem dan op te lossen?[/quote]
Gebruik:
c1*x1 + c2*x2 + c3*x3 + ... + c20*x20 -> min

Met c als het gewicht voor hoe belangrijk die familie is. 1-> heel belangrijk. 0->irrelevant.

Na wat opzoekwerk heb ik het algoritme gevonden. Je probleem is een "weighted matching problem in a bipartite graph".
[quote]In a weighted bipartite graph, each edge has an associated value. A maximum weighted bipartite matching[2] is defined as a perfect matching where the sum of the values of the edges in the matching have a maximal value. If the graph is not complete bipartite, missing edges are inserted with value zero. Finding such a matching is known as the assignment problem. It can be solved by using a modified shortest path search in the augmenting path algorithm. If the Bellman-Ford algorithm is used, the running time becomes O(V2E), or the edge cost can be shifted with a potential to achieve O(V2log(V) + VE) running time with the Dijkstra algorithm and Fibonacci heap. The remarkable Hungarian algorithm solves the assignment problem and it was one of the beginnings of combinatorial optimization algorithms. The original approach of this algorithm need O(V2E) running time, but it could be improved to O(V2log(V) + VE) time with extensive use of priority queues.[/quote]
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-

#3

Kaspace

    Kaspace


  • >100 berichten
  • 202 berichten
  • Ervaren gebruiker

Geplaatst op 10 januari 2011 - 14:26

Ik begrijp dat dit een praktijksituatie is. Niet elk huishouden is hetzelfde. Je hebt er van 1, 2 en nog meer personen. Wellicht kan het probleem vereenvoudigd worden door die variatie mee te nemen. Het aantal willekeurige mogelijkheden vermindert Ún je houdt toch meer rekening met individuele behoeftes.

#4

Woeka

    Woeka


  • 0 - 25 berichten
  • 6 berichten
  • Gebruiker

Geplaatst op 10 januari 2011 - 14:45

Bedankt voor de tips,

Het geheel kon iets worden versimpeld tot een 16x16 probleem door huishoudens voor een hoekhuis en een tussenwoningen te scheiden. De tussenwoningen is een 4x4 probleem dus die is makkelijk op te lossen met Matlab of zelfs met de hand, 4! = 24 oplossingen. Die 16! zijn er echter nog steeds te veel ;)

Als ik eruit ben zal ik het resultaat posten, maar laat je dat niet weerhouden te reageren als je nog tips hebt :P





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures