[Excel 2010] Snelste combinatie binnen matrix zoeken

[DinX]

Korte samenvatting meteen:
Ik moet voor een zwemwedstrijd de snelste combinatie van zwemmers zoeken voor een aflossing wisselslag. Hier moet je voor elk van de 4 slagen 1 zwemmer hebben. Zouden ze allemaal dezelfde slag mogen zwemmen (zoals een 4 x 100 crawl) is het simpel, sorteren op de tijd en de 4 snelste nemen. Bij een wissel ligt dat echter anders.

Grafisch is het misschien makkelijker duidelijk te maken:



Uit deze matrix moet ik de snelste combinatie krijgen. Elke zwemmer mag maar 1 keer voorkomen, en elke slag mag maar 1 keer voorkomen. Je kan niet zomaar kolom per kolom gaan sorteren, de snelste eruit halen en die weglaten bij de volgende kolom. Door bijvoorbeeld iemand die iets trager is op crawl dan de rest crawl te laten zwemmen kan je op het einde weer sneller zijn doordat het verschil in schoolslag veel groter is.

Bestaat hier in Excel een ingebouwde functie voor of wordt dit scripten en alle mogelijike combinaties uitrekenen ? Intuïtief kan ik bijvoorbeeld wel enkele combinaties voor de geest halen (die ik dan allemaal moet gaan uitrekenen), maar ergens moet daar toch een logica in zitten die excel voor mij kan doen ?

[pedorus]

In principe is dit een taakje voor de solver/oplosser.

Maak een extra matrix aan met 1-en of 0-en (al dan niet zwemmen voor die afstand). Maak een sommatie aan voor iedere rij en kolom. Doe daarnaast een somproduct voor de tijd die iemand bij het zwemmen nodig heeft per rij, en tel al deze sommaties op als totale tijd. Solver instellen om totale tijd te minimaliseren door de 1/0-matrix aan te passen, met constraints binair, inzet per afstand >=1, inzet per zwemmer <=1.

Je zal er echter mogelijk achter komen dat de Excel solver een beroerd product is, op zich zou je die 9*8*7*6 mogelijkheden ook wel met een macro'tje/formules kunnen afgaan en dan ben je zekerder van je resultaat. Misschien nog wel makkelijker te maken ook met 4 for-loopjes..

[DinX]

Mja, je zit we met het feit dat je aanbod zwemmers groter is dan de selectie. Er mogen er maar 4 zwemmen
En die 9:99.99 kan ik nog veranderen in een schatting. Het is dus niet zo dat die dat niet mogen zwemmen.

[ Voor 33% gewijzigd door DinX op 25-09-2010 22:38 ]

[Wouter.S]

Zijn dit de enige zwemmers die deelnemen of is de echte lijst een stuk groter ? Als dit de volledige lijst is zou ik gewoon even puzzelen, zo extreem moeilijk is dit nu ook niet en een methode implementeren kost je waarschijnlijk meer tijd dan gewoon even puzzelen.

Als de lijst echter veel groter is zul je het met een een 'algoritme' moeten doen, of gewoon alle mogelijke combo's afgaan en de snelste eruit pikken.

[DinX]

Dit is nu de lijst. Maar het is iets wat wel vaker terugkomt. Het zijn namelijk niet altijd dezelfde die mee (kunnen) doen. Ik was voornamelijk benieuwd of er misschien iets standaard in Excel zat hiervoor. Dan moet ik de volgende keer alleen de tijden aanpassen en klaar

[pedorus]

DinX schreef op zaterdag 25 september 2010 @ 22:37:
Mja, je zit we met het feit dat je aanbod zwemmers groter is dan de selectie. Er mogen er maar 4 zwemmen
En die 9:99.99 kan ik nog veranderen in een schatting. Het is dus niet zo dat die dat niet mogen zwemmen.

Dit zijn geen problemen voor beide methodes die ik beschrijf. De minimalisatie van de totaaltijd zorgt er automatisch voor dat er geen 5 geselecteerd zullen worden. Maar anders kun je alsnog voor '=1' ipv '>=1' kiezen bij afstand.

Wouter.S schreef op zaterdag 25 september 2010 @ 22:43:
en een methode implementeren kost je waarschijnlijk meer tijd dan gewoon even puzzelen.

Hem misschien wel, mij niet:

Visual Basic:

Function BestCombination(times As Range) As String
    Dim arr()
    Dim i As Integer, j As Integer, k As Integer, l As Integer
    Dim tot As Double, mintot As Double
    mintot = 1E+99
    arr = times
    For i = 1 To UBound(arr, 1)
        For j = 1 To UBound(arr, 1)
            If j <> i Then
                For k = 1 To UBound(arr, 1)
                    If k <> i And k <> j Then
                        For l = 1 To UBound(arr, 1)
                            If l <> i And l <> j And l <> k Then
                                tot = arr(i, 1) + arr(j, 2) + arr(k, 3) + arr(l, 4)
                                If tot < mintot Then
                                    BestCombination = i & "," & j & "," & k & "," & l
                                    mintot = tot
                                End If
                            End If
                        Next
                    End If
                Next
            End If
        Next
    Next
End Function

[DinX]

Heel erg bedankt. Voordat je het script poste was ik al eens aan de slag gegaan met de Solver (nooit gebruikt).
Daarmee is het gelukt, en dit is zeker voor de toekomst erg makkelijk. Gewoon nu eens 1 keer een matrix met een hele hoop rijen maken en in het vervolg alleen namen en tijden aanpassen



Hartelijk bedankt. Weer wat bijgeleerd

[pedorus]

In je screenshot lijkt het mij een foutje dat Lindsay niet wordt ingezet, misschien is die voor het solven, of zijn je opties aan de solver niet goed, of werkt de solver gewoon niet goed.

[DinX]

Foutje is er inmiddels uit

[Lustucru]

pedorus schreef op zaterdag 25 september 2010 @ 21:41:
Je zal er echter mogelijk achter komen dat de Excel solver een beroerd product is, op zich zou je die 9*8*7*6 mogelijkheden ook wel met een macro'tje/formules kunnen afgaan en dan ben je zekerder van je resultaat. Misschien nog wel makkelijker te maken ook met 4 for-loopjes..

Tenzij de solver idd verbeterd is sinds XL 2003 is het idd een beroerd product. Bij een setje testdata miste de solver bij mij de meest optimale oplossing.
Nog afgezien van het slecht verversen van de oplossing bij kleine wijzigingen in de data; dan bleef de solver gewoon de eerste oplossing geven.