• Privacywetgeving
    Het is bij Helpmij.nl niet toegestaan om persoonsgegevens in een voorbeeld te plaatsen. Alle voorbeelden die persoonsgegevens bevatten zullen zonder opgaaf van reden verwijderd worden. In de vraag zal specifiek vermeld moeten worden dat het om fictieve namen gaat.

Optimalisatie probleem

Status
Niet open voor verdere reacties.
R

Renee123

Gebruiker
Lid geworden
8 feb 2009
Berichten
65
Ik zit met een optimalisatie vraagstuk waarvan ik niet precies weet waar ik moet beginnen.

Om het makkelijk uit te leggen hierbij een voorbeeld:
Ik heb 10 cirkels waarvan sommigen met elkaar verbonden zijn en sommige niet. Ik kan dit bijv. overzichtelijk in een tabel weergeven met 0 (wel verbonden) en 1 (niet verbonden).
Elke cirkel moet van een bepaalde keur voorzien worden (6 opties van kleuren), maar cirkels die met elkaar verbonden zijn mogen niet dezelfde kleur hebben.

Kortom, volgens mij zijn dit de beperkingen:
- cirkels die met elkaar verbonden zijn hebben een 0 in de tabel
- cirkels die niet met elkaar verbonden zijn hebben een 1 in de tabel
- cirkels die met elkaar verbonden zijn mogen niet dezelfde kleur hebben.

Iemand een idee of ik dit in excel op kan lossen (via macro of via een solver) of dat ik dit toch op een andere manier moet oplossen.

Om het lastiger te maken: uiteindelijk moet dit ook werken voor ongeveer 300 cirkels met 14 kleuren. Maar als iemand me op weg kan helpen met de 10 cirkels en 6 kleuren, dan denk ik dat het wel kan uitbreiden naar 300 cirkels met 14 kleuren ;)

Tnx!
 
Ik weet niet of ik je kan helpen maar je zult toch eerst wat meer informatie moeten geven. Met name wat je bedoelt met optimaliseren. Je hebt nu 10 cirkels en een aantal beperkingen. En toen? Wanneer en hoe is dit optimaal?

Rebmog
 
solver is alleszins niet geschikt wegens te weinig binaire variabelen (max 30 dacht ik)

@Sylvester, eigenlijk moet je enkel alles boven de diagonaal invullen, want een relatie kan je zo spiegelen als C7 een relatie heeft met C9, dan geldt het omgekeerde ook.
 
Laatst bewerkt:
cow18 je hebt gelijk aanraken is aanraken en verder niet moeilijk doen
ik dacht een pijl van a naar b is anders dan een pijl van b naar a

ps ik krijg jouw file niet gedouwnload?? probeer jij het eens
 
ik had de file een 2e keer gedownload en misschien was je net op dat moment aan het proberen ???
Nu lukt het alleszins.
 
@ sylvester-ponte en cow18: dit komt al heel erg dicht in de buurt van wat ik wil!!

Ik begrijp (nog) niet precies hoe die macro in elkaar steekt, maar misschien dat één van jullie dit makkelijk uit kan leggen.

Maar ik loop nog wel tegen 2 dingen aan die volgens mij niet helemaal kloppen:
1) Stel ik zet alleen een 1 (=conflict) op de diagonaal en tussen C1-C2 en C1-C3, dan komt er altijd een oplossing uit waarbij C1, C2 én C3 een verschillende kleur hebben. Volgens mij is dit onjuist. Stel C1 heeft kleur1, dan mogen vanuit de conflictenmatrix C2 én C3 geen kleur1 hebben. Maar ze kunnen wél allebei kleur2 hebben (want er staat tussen C2-C3 geen conflict!). Alleen komt dit dus nooit als oplossing eruit. Zoals gezegd snap ik niet echt hoe die macro werkt, dus ik kan ook niet echt begrijpen waardoor het fout gaat.
Edit: hierdoor is het nu bijvoorbeeld ook niet mogelijk om C1 met alle anders cirkels te laten conflicteren, want dan denkt hij dat er tussen al die andere cirkels óók een conflict is, en dan zijn er dus te weinig kleuren beschikbaar om tot een oplossing te komen.

2) Iets anders wat niet helemaal klopt, is de aanname dat alle kleuren gebruikt moeten worden. Dit is niet nodig. Ik vind een oplossing acceptabel als er slechts 3 of 4 kleuren gebruikt worden.
Dus in het bovenstaande voorbeeld van alleen een conflict op de diagonaal en tussen C1-C2 en C1-C3, dan zou de makkelijkste oplossing volgens mij moeten zijn C1=kleur1 en C2 t/m C10=kleur2. Hiermee wordt aan alle conflicten voldaan en is een hebben alle cirkels een kleur toegewezen gekregen.
 
Laatst bewerkt:
met een klein beetje meer uitleg in de macro
eigenlijk doet die macro niets anders dan gewoon herberekenen (=F9) en de truuk zit in die "="kleur" & ASELECTTUSSEN(1;$L$1)" in de L-kolom, dus gewoonweg random kiezen van een getal tussen 1 en 10. De kans dat je dan 2 gelijke kleuren krijgt voor C2 en C3 is dan wel erg klein.
Ik heb het nu even geprobeerd met 3 kleuren en je 2 voorwaarden en een lus van max 1.000 pogingen om 2 gelijke kleuren te krijgen in C2 en C3 en inderdaad hij komt er niet, waar volgens mij toch 33% kans bestaat om daaraan te voldoen. Ik weet het ook even niet.
Ik heb dan even in kolom O: P hetzelfde overnieuw gedaan en daar kan je handmatig in de kolom O je kleuren zelf invullen en laten checken of het klopt. Dat klopt dus daar blijkbaar, maar via random kiezen van de kleuren komt hij er nooit ????
 

Bijlagen

Ja, raar is dat hè... Dat ie met 3 kleuren en 2 voorwaarden nooit uitkomt op 2 gelijke kleuren voor C2 en C3. Betekent het dan dat het op deze manier niet gaat werken? Want het is voor mij wel van belang dat alle mogelijke oplossingen als oplossing gezien worden (zeker als ik straks ga uitbreiden naar veel meer cirkels, waardoor het aantal mogelijkheden steeds kleiner wordt).

Uiteindelijk is mijn doel trouwens dat ik wil checken of er met 300 cirkels en 14 kleuren een oplossing uitkomt, hoe die er uit ziet dat maakt niet uit :)
 
nog een vraagje:
als c1 en c2 een conflict heben en
als c2 en c3 een conflict hebben
hebben c1 en c3 dan ook een conflict?

zo nee dan mogen c1 en c3 de zelfde kleur hebben
klopt dat?
 
als c1 en c2 een conflict heben en
als c2 en c3 een conflict hebben
Dan mogen c1 en c3 inderdaad dezelfde kleur hebben ( er is namelijk ook geen conflict gedefinieerd tussen c1 en c3)
 
nieuwe versie, probeer nu maar een aantal keren, je zal zien dat c2 en c3 soms de zelfde kleur krijgen.
Er zat een denkfout in de UDF.
Wat is de optimalisatie nu eigenlijk ? Met zo weinig mogelijk kleuren proberen te voldoen ?

PS ik kijk alleen naar de 1-tjes boven de diagonaal !!!!!!
 

Bijlagen

Laatst bewerkt:
Volgens mij werkt het nu wel inderdaad! Ik heb er even snel naar gekeken, maar ben niks geks tegen gekomen. Vanavond zal ik uitgebreider testen.

Het uiteindelijke doel is om voor 300 cirkels en 14 kleuren een oplossing te vinden dat alle cirkels een kleur krijgen én daarmee ook aan alle conflicten voldaan wordt (dus cirkels met een 1 in de matrix mogen niet dezelfde kleur hebben). Ik zou al heel blij zijn met een oplossing, want ik denk dat het lastig wordt.
Als ik uiteindelijk een oplossing krijg, dan moet ik nog verder gaan finetunen, want ik heb sommige cirkels al een kleur gegeven. Dus ik moet straks ook nog cirkels 'vast gaan zetten' op een bepaalde kleur. Daarmee ga je natuurlijk weer mogelijkheden beperken en is het maar de vraag of er uiteindelijk nog een valide oplossing overblijft.

Is het trouwens mogelijk om in kolom achter een cirkel handmatig een kleur in te vullen? Of help ik dan de macro om zeep? :)

En hoe kan ik 'm verder uitbreiden met meer cirkels? Gewoon alleen die matrix uitbreiden, of moet ik dan ook weer aanpassingen aan de macro doen?
 
Laatst bewerkt:
ik werk met "tabellen", dus misschien is dat eventjes wennen als je rijen of kolommen invoegt !

- in die 1e tabel kan je al je kleuren ingeven waaruit gekozen mag worden. Wil je een nieuw kleur toevoegen, ga dan gewoon onder de laatste staan (heeft zo'n klein blauw hoekje !!) en tik daar een kleur in. Voor de goede werking van mijn macro mag daar geen komma of het teken "|" in staan, maar voor een kleur lijkt dan geen probleem.

in die 2e tabel krijg je in :
- de 1e kolom al je cirkels
- daarna een kolom waarin je je "verplichte" kleuren kan ingeven zoals je gevraagd had.
- daarna de kolom die de macro vult met de mogelijke oplossing.
- daarna een kolom met het rijnr binnen de tabel (is nodig voor de checks)
- daarna volgt een kolom waarin berekent wordt of aan alles voldaan is. Bovenin in G1 wordt die kolom gesommeerd en die som moet 0 zijn, anders is de oplossing niet geldig.
- daarna volgen de kolommen met de relaties, met 1 = een relatie tss beide cirkels. Er wordt enkel boven de diagonaal gewerkt. Als je straks 300 cirkels zal hebben, hoe wil je die 1-tjes foutloos invullen ?????!!!! Hoe krijg je je relaties aangeleverd. Moet een 2e macro die 1-tjes invullen aan de hand van een door jou geleverde lijst met namen ?

als je nu op die groene knop "zoek kleuren" drukt, dan worden er tot 1.000 pogingen gedaan om een 0 in G1 te krijgen.
Klopt alles zoals je het in gedachten had of heb ik ergens een denkfout gemaakt ?

Hoe gaan we straks die tabel vergroten ?
selecteer even in de koprij van de tabel C2 tot C9 (I4 tot P4) klik met de rechtermuisknop en kies invoegen>tabelkolommen links en dat ga je misschien een paar keer moeten doen of dat moet dan maar met een macro gebeuren.
Identiek voor toevoegen van rijen kies je een aantal cellen in je tabel en daarna rechtermuisknop en Invoegen>tabelrijen

dat was het denk ik .
 

Bijlagen

Super bedankt! Dit ziet er goed uit en functioneert volgens mij precies zoals ik wil :)
Gelukkig hoef ik zelf niet de matrix te vullen. Als het goed is gaat daar morgen iemand mee aan de slag. Ik laat je weten of het allemaal werkt en gelukt is.
 
er zat nog een foutje in, als je een combinatie van verplichte kleuren opgaf waarbij een bepaalde kleur niet zou kunnen omdat bepaalde cirkels toch een relatie hebben.
Zie voorbeeld in bijlage : geef c2 en c4 samen een verplichte rode kleur. Dan zou niet mogen kunnen wegens hun relatie !

Daarnaast is het herrekenen wat sneller omdat nu niet meer het scherm geupdate wordt bij een nieuwe poging, je ziet nu gewoon een tellertje lopen in de statusbar.
 

Bijlagen

Laatst bewerkt:
Status
Niet open voor verdere reacties.
                    Steun ons                    

Nieuwste berichten

Terug
Bovenaan Onderaan