Podręcznik

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:

• \(i\in N\) zbiór typów przedmiotów o wartości \(w_i\) i wielkości \(a_i\),

• \(p\) pojemność plecaka (zasobu)
  

• \(x_i\) zmienna decyzyjna ile przedmiotów typu \(i\) zapakować.

Funkcja celu: \(\max\sum_i w_i x_i\)

Ograniczenia dotyczą dostępności zasobu, oraz przedmiotów:

\( \begin{matrix} &&\sum_i a_i x_i\leq p,\\ && x_i \subset C,\; \forall i\end{matrix} \)

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:

• \(p_j\) pojemność pojemnika \(j\in M\),

• \(x_{ij}\) zmienna decyzyjna ile przedmiotów typu \(i\) zapakować do pojemnika \(j\),

• \(y_{j}\) zmienna decyzyjna czy wykorzystać pojemnik  \(j\).
  

Funkcja celu: \(\min\sum_j y_j\)

Ograniczenia:

\( \begin{matrix} &&\sum_i a_i x_{ij}\leq p_jy_j\;\;\;\forall j\in M,\\ && \sum_jx_{ij}=1\;\forall i\in N\\ && x_{ij} \subset C,\; \forall i,j\end{matrix} \)

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 \(j\in M\) to np. maszyny, dostawcy, itp. Natomiast zbiór \(i\in N\) reprezentuje zbiór zdań do realizacji/obsłużenia.

Oznaczenia:

• \(a_{i}\) jest zapotrzebowaniem zadania \(i\), w wersji \(a_{ij}\) zróżnicowanym ze względu na zasoby, np. odpowiada czasowi wykonania zadania \(i\) na maszynie \(j\),
• \(f_{ij}\) jest kosztem wykonania zadania \(i\) na maszynie \(j\).
  

Funkcja celu minimalizuje koszty: \(\min\sum_{ij}f_{ij} x_{ij}\)

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 \(y_j\):

\( \begin{matrix} &&\sum_{ij} a_{ij} x_{ij}\leq p_j\;\;\;\forall j\in M,\\ && \sum_jx_{ij}=1\;\forall i\in N\\ && x_{ij} \subset \{0,1\},\; \forall i,j\end{matrix} \)

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:

• \(c_{j}\) jest stałym kosztem wykorzystania zasobu \(j\) (ustanowienia zasobu w lokalizacji  \(j\))

Przy ograniczeniach jak w zadaniu bin-packingu:

\( \begin{matrix} &&\sum_{ij} a_{ij} x_{ij}\leq p_jy_j\;\;\;\forall j\in M,\\ && \sum_jx_{ij}=1\;\forall i\in N\\ && x_{ij} \subset \{0,1\},\; \forall i,j\end{matrix} \)