Solver: wybór optymalnej drużyny

Dzisiaj napiszę trochę o Solverze. Będziemy wybierać optymalną kadrę zawodników – umownie nazwiemy ją “drużyną marzeń”. Naszym celem jest to, aby zmaksymalizować wartość drużyny, uwzględniając szereg warunków ograniczających.

Warunki Zadania

• Na liście mamy 60 nazwisk, potrzebujemy wybrać 15-graczy.
• Każdy gracz ma przypisane takie atrybuty jak:
  – drużyna w której gra (Team)
  – pozycja na boisku (Pos)
  – punkty jakie uzbierał za swoją grę (Pts)
  – cena rynkowa (Cost)
• Naszym zadaniem jest wybrać 15-takich zawodników, których łączna wartość rynkowa nie przekroczy 100 jednostek, a których wartość sportowa (punkty) jest najwyższa.
• Istnieje cały szereg warunków ograniczających:
  – łączny koszt drużyny nie może przekraczać 100 jednostek (napisałem o tym powyżej)
  – maksymalnie z jednej drużyny możemy wybrać trzech graczy (mamy sporo drużyn)
  – musimy wybrać dwóch bramkarzy (GKP), pięciu obrońców (DEF), pięciu pomocników (MID) i trzech napastników (FWD).

Rozwiązanie

Warunki Ograniczające

1. W pierwszej kolejności zdecydowałem się do oryginalnej tabeli dorzucić kolumnę BestTeam. Będzie nam ona przechowywać informację 0/1 czy dany zawodnik znajdzie się w naszej “drużynie marzeń”. Ta kolumna to nasze zmienne, którymi będzie mógł manipulować Solver. Nie znajduje się w nich rzecz jasna żadna formuła.
2. W środku wypisałem wszystkie możliwe drużyny i formułę zliczającą ilość zawodników wybranych do “drużyny marzeń” właśnie z każdej z tych drużyn. Formuła w komórce I2 to: =SUMA.JEŻELI(Team;$H2;BestTeam).
3. Podobnie, w kolumnie K na górze wypisałem wszystkie możliwe pozycje i formułę zliczającą ilość zawodników wybranych do “drużyny marzeń” właśnie dla każdej z tych pozycji. Formuła w komórce L2 to: =SUMA.JEŻELI(Pos;$K2;BestTeam)
4. W komórce L7 mam formułę: =MAX($I$2:$I$18) – pamiętajmy, że nie możemy mieć więcej niż trzech graczy z jednej drużyny.
5. W komórce L8 mam formułę: =SUMA.ILOCZYNÓW(Cost;BestTeam) pamiętajmy, że nasza drużyna nie może kosztować więcej niż 100 jednostek.

Kolumna Celu

Kolumna celu (na prawo od pomarańczowego pola) zawiera formułę: =SUMA.ILOCZYNÓW(Pts;BestTeam) – czyli przemnażamy dwie tablice (pierwsza dotyczy punktów, druga informacji 0/1 czy gracz znajdzie się w “drużynie marzeń”).

Solver

Aby uzyskać wyniki takie jak na screenie musiałem zdefiniować warunki w Solverze.
Poza opisanymi warunkami musiałem zaznaczyć, że kolumna BestTeam powinna zawierać wartości binarne (zawodnik nie może być w połowie w “drużynie marzeń” – albo jest albo go nie ma).

Screen

A tak wygląda moja “drużyna marzeń”. Jak widać Solver nie wybrał tych najdroższych piłkarzy, ale tych względnie tańszych, których wartość sportowa (punkty) jest bardzo wysoka.

Wszystkie ograniczenia zostały uwzględnione, i udało nam się zbudować optymalną drużynę o wartości 1706 punktów i cenie równej dokładnie 100 jednostek.