Solver i kombinacja liczb dających określoną sumę

by Marcin

solver_VBA_ExcelBlog_pl

Kilka dni temu stanąłem (mam dziwne wrażenie, że nie ja pierwszy) przed następującym problemem: w jaki sposób z listy liczb wybrać wszystkie kombinacje dające określoną sumę ?

Problem tylko pozornie wydaje się prosty (w każdym razie wydawał mi się taki kilka dni temu, kiedy pełen zapału postanowiłem pomóc współpracownikowi, który musi ręcznie wyłuskiwać z bardzo długiej listy mniejsze kwoty transakcji bankwych, które “składają się” na większe kwoty, które zostały zaksięgowane.) Niestety, okazało się, że zadanie jest tak naprawdę bardzo trudne. Ostatecznie udało mi się napisać krótkie makro, które przy pomocy Solvera radzi sobie z problemem, ALE :

  • w praktyce, można je wykorzystać tylko z relatywnie krótkimi listami. W moim przypadku, mam silne wrażenie, że znalezienie wszystkich rozwiązań (lista transakcji bankowych jest bardzo długa) zajełoby Solverowi lata,
  • nie czuję się zbyt pewnie pracując z Solverem. Nie do końca rozumiem bowiem całą teorię stojącą za tym narzędziem, co sprawia, że nie bardzo wiem, które opcje odpowiadają za co (to znaczy niby wiem, ale bez dokładnego zrozumienia jak to wszystko działa „w tle” mam problem z przewidzeniem jak zmiana jednej z opcji wpłynie na mój model). Okazuje, się że Solver jest narzędziem bardzo wrażliwym, I niewielka nawet zmiana w w ustawieniach dramatycznie zmienia sposób działania,
  • proces poszukiwania rozwiązania przez dodatek Solver jest raczej WOLNY. Nie jest tak,  ze klikamy sobie gdzies i … BUM ! … zrobione. Trzeba raczej chwilkę odczekać  (cały czas mówię tu o niewielkich listach),
  • skrypt działą u mnie całkiem sprawnie (co widać na animacji) w Excelu 2007, ale np. w Excelu 2010 już nie chce. I NIE WIEM DLACZEGO (jeżeli ktoś mógłby mi pomóc zrozumieć byłbym bardzo wdzięczny). Istnieje więc spora szansa, że z jakiegoś powodu nie zadziała też u Ciebie. Mam nadzieję jednak, że mój kod może Ci nieco pomóc i zainspirować do stworzenia lepszego rozwiązania.

W przypadku problemów proszę nie zadręczać mnie więc pytaniami “dlaczego nie działa”, “co zrobić, żeby działało” etc. NIE WIEM. NIE ORIENTUJĘ SIĘ. ZAROBIONY JESTEM. U mnie działa w sposób zadowalający i w zasadzie to się liczy (patrząc na wszystko z mojej egoistycznej perspektywy)  Jeżeli jednak  miałbyś pomysł jak usprawnić skrypt – bardzo liczę na wskazówki.

Jak wspomniałem wykorzystamy narzędzie SOLVER. Pierwszy krok to przygotowanie listy z liczbami posród których będziemy (w zasadzie Solver będzie) poszukiwali tych, których suma będzie równa liczbie, której poszukujemy. Specjalnie się tu nie wysilimy i w kolumnę B wpiszemy co tam nam do głowy przyjdzie. Mi przyszło to co widac na obrazku poniżej.

Excel_Solver_SumaWartosci_1

Następnie, w kolumnie B umieścimy formułę “=B3*C3” i skopiujemy ją w dół aż do wiersza 16. Niżej (D19) zsumujemy wszystkie wartości z kolumny D. Teraz jesteśmy już gotowi na użycie Solvera.

Rozpocząłem od nagrania odpowiedniego makra, a następnie jego edycji. Parametry dodatku Solver, których użyłem widać na rysunku poniżej.

Excel_Solver_SumaWartosci_2

Okienko to wygląda nieco inaczej w Excelu 2007 (zrzut ekranu robiłem z Excela 2010). Zasadniczo idea jest jednak ta sama i pewien jestem, że nie będziesz miał trudności. W przypadku problemów poszperaj i poczytaj sobie o Solverze.

No dobrze, Solver znajdzie nam rozwiązanie, jak jednak zmusić go do tego, aby znalazł wszystkie rozwiązania (lub przynajmniej więcej niż tylko jedno) ? Postanowiłem rozwiązać to w sposób następujący.

Po znalezieniu każdego rozwiązania, w kolumnie C pojawia się seria zer i jedynek, które jednoznacznie identyfikują dane rozwiązanie. Jeżeli więc obok cyfr 7 i 8 pojawi się jedynka, oznacza to, że dają one nam w sumie 15, i że nie chcemy aby Solver raz jeszcze znalazł to rozwiązanie. Skoro widzę zera i jedynki to, chcąc nie chcąc, do głowy przychodzi mi zapis binarny (dwójkowy system liczbowy). Postanowiłem więc zamienić sobie ten ciąg zer i jedynek (liczba w systemie dwójkowym) na liczbę w systemie dziesiętnym. Nie sprawdzając nawet za bardzo czy w Excelu nie ma gdzieś zaszytej odpowiedniej formuły (jestem jednak pewien, że Ty to sprawdzisz)  wykorzystałem pierwszą formułę jaka mi przyszła do głowy. W komórce C19 znalazła się więc formuła tablicowa:

{=SUMA(C3:C16*2^(WIERSZ(ADR.POŚR("1:"&ILE.WIERSZY(C3:C16)))-1))}

Za każdym razem kiedy Excel znajdzie rozwiązanie, odpowiednią liczbę z komórki C19, kopiował będę (w zasadzie mój kod VBA) do kolumny A . Trzeba jeszcze tylko Solverowi wytłumaczyć jakoś, że nie interesują nas rozwiązania, które znajdują się w kolumnie A. Jeżeli wrócisz teraz na chwilę do obrazka z parametrami Solvera to zobaczysz, że w polu “podlegających ograniczeniom” dodałem następujące ograniczenie:

$C$21 = 0

W komórce C21 znajduje się zaś formuła:

=LICZ.JEŻELI(A2:A36,C19)

Sprawdza ona, czy właśnie obliczona liczba dziesiętna nie pojawia się przypadkiem w kolumnie A. My chcemy, aby jako wynik ZAWSZE znalazło się tam zero oznaczające, że obliczonego właśnie przez Solver rozwiązania jeszcze nie było na naszej liście.

Reszta to już po prostu zapisanie przy pomocy pętli każdego rozwiązania w osobnym wierszu. Ostatecznie, mój kod VBA wygląda następująco:

Sub Solve()
Dim SolverResult
Dim AlreadyFound As Range
Dim counterZnalezione As Integer
Dim counterRozwiazanie As Integer
Dim tmpKomorka As Range
Dim czyKontynuowac As Boolean

Columns(1).Clear

Set AlreadyFound = Range("A2")

counterZnalezione = 0
counterRozwiazanie = 0
czyKontynuowac = True

Range("C3:C16").Value = ""

SolverReset

SolverOk SetCell:=Range("$D$19"), MaxMinVal:=3, ValueOf:=Range("G3").Value, ByChange:="$C$3:$C$16"
SolverAdd CellRef:="$C$3:$C$16", Relation:=5, FormulaText:="binary"
SolverAdd CellRef:="$C$21", Relation:=2, FormulaText:="0"

Do While czyKontynuowac = True

counterRozwiazanie = 0

SolverResult = (SolverSolve(True, ""))

Select Case SolverResult
Case 0, 1, 2, 14

SolverFinish KeepFinal:=1

AlreadyFound.Offset(counterZnalezione, 0).Value = Range("c19").Value
counterZnalezione = counterZnalezione + 1

For Each tmpKomorka In Range("C3:C16")

If tmpKomorka.Value = 1 Then
Range("I3").Offset(counterZnalezione, counterRozwiazanie).Value = tmpKomorka.Offset(0, -1).Value
counterRozwiazanie = counterRozwiazanie + 1
End If

Next

Case Else
czyKontynuowac = False
Range("C3:C16").Value = ""
MsgBox "Solver nie mogl znalezc rozwiazania"
End Select

Loop

End Sub

Na koniec, jak zwykle, przykładowy plik

Excel timestamp - plik przykładowy

{ 6 comments… read them below or add one }


Fatal error: Cannot assign by reference to overloaded object in /home/klient.dhosting.pl/antiquus/excelblog.pl/public_html/wp-content/themes/thesis_182/lib/classes/comments.php on line 176