Podręcznik
Wersja podręcznika: 1.0
Data publikacji: 01.01.2022 r.
Wykłady
W1…WN, odpowiadające w sumie ok. 10-12 godz. standardowego wykładu
1. Klasy problemów i pakiety optymalizujące
1.2. Modele najważniejszych klas problemów
Różnorodność problemów dyskretnych jest w zasadzie nieskończona. Wynika ona m.in. z niezwykle szerokiej gamy dziedzin, w której problemy optymalizacji dyskretnej mają zastosowanie. Jednocześnie, na najbardziej ogólnym poziomie problemy te łączy podobny cel: zwiększenie efektywności przy zachowaniu wymagań i ograniczeń na zasoby. Co więcej, często okazuje się, że problemy z różnych dziedzin wykorzystują podobne zestawy zmiennych decyzyjnych i ograniczeń, czyli dzielą podobną strukturę. Pomocne jest zatem przestudiowanie reprezentatywnych przykładów, które mogą służyć jako paradygmaty podczas modelowania i rozwiązywania innych problemów o podobnej strukturze.
Przypomnijmy przy tym, że w przypadku rozwiązywania problemów dyskretnych gotowymi solwerami duże znaczenie może mieć sformułowanie modelu, w szczególności nierzadkie są przypadki niepotrzebnie złożonego sformułowania, wprowadzającego np. nieliniowości do modelu. Tym samym, zapoznanie się z klasycznymi problemami pomoże wypracować dobre praktyki tworzenia modeli optymalizacyjnych programowania matematycznego.
Klasy problemów
Wiele problemów dyskretnych może być przedstawianych jako zadania wyznaczania przepływów w sieci, należą do nich klasyczne problemy grafowe, takie jak:
- Najkrótsze i najtańsze ścieżki, przepływy w grafach,
- Cykl komiwojażera: Traveling Salesperson Problem (TSP),
- Przydziały i skojarzenia: Assignment Problem,
- Minimalne drzewo rozpinające: Minimum spanning tree.
W tym rozdziale przedstawiamy jedynie kilka wybranych, klasycznych problemów alokacji zasobów.
Problem plecakowy: Knapsack problem
Problem plecakowy/ zadanie załadunku polega na jak najlepszym wykorzystaniu zasobu (plecaka), w którym należy upakować jak najwięcej przedmiotów.
Oznaczenia:
Ograniczenia dotyczą dostępności zasobu, oraz przedmiotów:
Warianty problemu plecakowego
Problem typu plecakowego ma szerokie zastosowania w różnych dziedzinach, np. do tej kategorii zaliczamy problemy inwestycyjne i zadania alokacjai budżetu. Dodatkowe uwarunkowania prowadzą do wariantów podstawowego problemu, wyróżniamy np.:
- 0-1 Knapsack - tylko po jednej sztuce każdego towaru jest dostępne,
- Bounded knapsack - dostępna jest ograniczona liczba sztuk każdego towaru,
- Change-making - pojemność plecaka musi być w pełni wykorzystana (czyli ograniczenia na zasób w postaci równości),
- Multiple Knapsack - wiele różnych plecaków, inaczej problemy typu bin-packing, które dalej mogą być rozważane wraz z ograniczeniami kolejnościowymi, oknami czasowymi, itd.
Problem bin-packing
Problemy pakowania (i rozkroju, czyli w wariancie Cutting stock problem) najczęściej skupiają się na wykorzystaniu jak najmniejszej liczby zasobów.
Oznaczenia:
Ograniczenia:
Dodatkowe ograniczenie zapewnia, że każdy przedmiot
Przydział zadań do procesorów/dostawców do odbiorców
Szeroka klasa problemów przydziału może być postrzegana jako wariant bin-packingu. W problemie takim zasoby to np. maszyny, dostawcy, itp. Natomiast zbiór
reprezentuje zbiór zdań do realizacji/obsłużenia.
Oznaczenia:
jest zapotrzebowaniem zadania
, w wersji
zróżnicowanym ze względu na zasoby, np. odpowiada czasowi wykonania zadania
na maszynie
,
jest kosztem wykonania zadania
na maszynie
.
Funkcja celu minimalizuje koszty:
Przy ograniczeniach jak w zadaniu bin-packingu, przy czym o ile w zadaniu nie ma kosztów stałych powiązanych z wykorzystaniem maszyny to nie podrzebujemy zmiennej binarnej :
Problemy lokalizacyjne/dystrybucyjne
Klasycznym rozszerzenime problemu przydziału zadań do procesorów jest dodatkowe uwzględnie stałego kosztu użycia procesora. Problem tego typu jest określany jako problem lokalizacyjny, gdyż ma naturalne odzwierciedlenie w sytuacji wyboru punktów obsługi (klientów, pacjentów, mieszkańców, etc.). Problem ten posłuży nam do omówienia sposobu implementacji modeli w środowisku IBM Ilog Cplex w kolejnych rozdziałach.
Oznaczenia dodatkowe:
Funkcja celu minimalizuje wszystkie koszty:
Przy ograniczeniach jak w zadaniu bin-packingu: