Jednym z najbardziej znanych problemów z optymalizacją kombinacyjną jest problem z przypisywaniem. Oto przykład: załóżmy, że grupa instancji roboczych musi wykonać zestaw zadań, a w przypadku każdej instancji roboczej i zadania jej przypisanie wiąże się z kosztem. Problem polega na tym, że każdy z nich należy przypisać maksymalnie do 1 zadania, a 2 innych nie może wykonywać tego samego zadania przy jednoczesnym zminimalizowaniu całkowitego kosztu.
Możesz zwizualizować ten problem na wykresie poniżej, na którym znajdują się 4 instancje robocze i 4 zadania. Krawędzie przedstawiają wszystkie możliwe sposoby przypisywania instancji roboczych do zadań. Etykiety na krawędziach to koszty przypisywania instancji roboczych do zadań.
Przypisanie odpowiada podzbiorze krawędzi, w którym każda instancja robocza ma co najmniej 1 krawędź wystającą i żadne 2 instancje robocze nie mają krawędzi prowadzących do tego samego zadania. Poniżej znajdziesz jedno z możliwych przypisań.
Łączny koszt przypisania wynosi 70 + 55 + 95 + 45 = 265.
W następnej sekcji pokazujemy, jak rozwiązywać problemy z projektami przy użyciu zarówno rozwiązań MIP, jak i CP-SAT.
Inne narzędzia do rozwiązywania problemów z projektami
LUB oferuje też kilka innych narzędzi do rozwiązywania problemów z projektami, które mogą być szybsze niż rozwiązania MIP lub CP:
- Narzędzie do rozwiązywania problemów z przypisywaniem sumy liniowej
- Narzędzie do rozwiązywania problemów z minimalnymi kosztami
Te narzędzia rozwiązują jednak tylko proste problemy z projektami. Jeśli więc masz ogólne rozwiązania, które mogą obsłużyć szeroką gamę problemów (i które są szybkie w większości zastosowań), zalecamy rozwiązania MIP i CP-SAT.