Celem ćwiczenia jest zapoznanie się z zagadnieniem programowania całkowitoliczbowego oraz pakietu Python MIP (Mixed-Integer Linear Programming Tools) do rozwiązywania problemów optymalizacji całkowitoliczbowej. Zadania należy rozwiązać w Google Colab
Ogólnie programowanie całkowitoliczbowe możemy zapisać następująco: \begin{align} \max \, &c^Tx,\\ &Ax=b,\quad x \in {0,1} \end{align}
lub
\begin{align}
\max \, &\sum_{j=1}^mc_jx_j, \\
&\sum_{j=1}^ma_{i,j}x_{j}=b_j, \quad i\in 1,2,\ldots, n,\\
&x \in {0,1}, \quad j\in 1,2,\ldots, m
\end{align}
Wszystkie elementy w $c$, $A$, $b$ z założenia są liczbami całkowitymi. To założenie gwarantuje, ze wszystkie elementy są liczbami wymiernymi, ponieważ przemnożenie funkcji celu przez dowolna całkowita liczbę dodatnia oraz pomnożenie jakiegokolwiek ograniczenia przez liczbę różna od zera nie zmieni charakteru rozpatrywanego zadania. Zadanie programowania całkowitoliczbowego liniowego może być przedstawiane w wielu postaciach. Najczęściej jest przedstawiane w postaci jak wyżej. Wymienione zapisy wykorzystywane są przez oprogramowanie (solver) do rozwiązywania problemu programowanie całkowitoliczbowego.
Na potrzeby laboratorium należy pamiętać dwie główne kwestie:
Na wydziale obróbki mamy dwie maszyny (M1, M2) oraz dwóch obsługujących je robotników (R1, R2). Znamy wydajność każdego robotnika na poszczególnych stanowiskach według poniższej tabeli
\begin{array}{p{5cm}|p{5cm}|p{4.5cm}} W_{i,j} & R1 & R2 \\\hline M1 & 6 & 7\\\hline M2 & 12 & 6 \end{array}Wydajność tą określa liczba detali, które dany robotnik może wykonać na danej maszynie w ciągu jednej godziny. Należy ustalić taki przydział robotników do poszczególnych stanowisk, aby łączna wydajność całego zespołu była maksymalna przy czym:
Wyżej wymieniony problem, jest problemem optymalnego przydziału który możemy rozwiązać za pomocą następującego problemu optymalizacji:
Funkcja celu: Maksymalizacja łącznej wydajności całego zespołu: \begin{equation} \max \sum_{i=1}^{n}\sum_{j=1}^{m} W_{i,j}x_{i,j} \end{equation}
Ograniczenie 1: Na danej maszynie może pracować jeden i tylko jeden pracownik: \begin{equation} \sum_{j=1}^{m} x_{i,j} = 1 \quad i\in 1,2,\ldots, n \end{equation}
Ograniczenie 2: Każdy pracownik może pracować na jednej i tylko jednej maszynie:
\begin{equation}
\sum_{i=1}^{n} x_{i,j} = 1 \quad j\in 1,2,\ldots, m
\end{equation}
Ograniczenie 3: Ograniczenia co do wartości zmiennych decyzyjnych: \begin{equation} x_{i,j} \in \{0,1\} \quad i\in 1,2,\ldots n \quad j\in 1,2 \ldots, m, \end{equation} co oznacza iż \begin{equation} x_{i,j} = \begin{cases} 1, \quad \text{jeżeli $j$-ty pracownik został przydzielony do $i$-tego stanowiska }\\ 0, \quad \text{w przeciwnym razie}\\ \end{cases} \end{equation}
UWAGA: Zmienna $x$ jest zmienną decyzyjną której wartość (wartości) zostaną ustalone po rozwiązaniu problemu optymalizacji przez solver. Wartości jakie może przyjmować zmienna $x$ to zero lub jeden i to solver decyduje jaka to będzie wartość przy uwzględnieniu ograniczeń oraz charakteru funkcji celu.
Przedstawiony problem optymalizacji może być niejasny na pierwszy rzut oka. W celu wyjaśnienia poszczególnych elementów pomnimy funkcję celu (wrócimy do niej w dalszej części opisu) i przejdźmy do ograniczeń. Według tabeli wydajności, ilość zmiennych decyzyjnych wynosi cztery, odpowiednio: \begin{equation} x_{i,j} = [x_{1,1},\, x_{1,2},\, x_{2,1},\, x_{2,2}] \quad i\in 1,2 \quad j\in 1,2. \end{equation}
W zapisie tabelarycznym:
\begin{array}{c|c|c} W_{i,j} & R1 & R2 \\\hline M1 & 6 & 7\\\hline M2 & 12 & 6 \end{array}$\longrightarrow$ \begin{array}{c|c|c} x_{i,j} & j=1 & j=2 \\\hline i=1 & x_{1,1} & x_{1,2}\\\hline i=2 & x_{2,1} & x_{2,2} \end{array}
Pierwsze ograniczenie wprowadza warunek iż na danej maszynie $i\in 1,2,\ldots, n$ może pracować jedn i tylko jeden pracownik. Tak więc mamy (suma po kolumnach):
Drugie ograniczenie wprowadza warunek iż każdy pracownik $j\in 1,2,\ldots, m$ może pracować na jednej i tylko jednej maszynie. Tak więc mamy (suma po wierszach):
Powyższy opis ograniczeń można zapisać tabelarycznie: \begin{array}{c|c|c|c} x_{i,j} & j=1 & j=2 & \\\hline i=1 & x_{1,1} & x_{1,2} & \sum_{j=1}^m x_{1,j}\\\hline i=2 & x_{2,1} & x_{2,2} & \sum_{j=1}^m x_{2,j}\\\hline & \sum_{i=1}^n x_{i,1} & \sum_{i=1}^n x_{i,2} \end{array}
Ograniczenie trzecie zostało już opisane. Ostatnim elementem jest funkcja celu która jest sumą iloczynów poszczególnych wydajności oraz zmiennych decyzyjnych która powinna być jak największa (maksymalizujemy wydajność): \begin{align} \max \sum_{i=1}^{n}\sum_{j=1}^{m} W_{i,j}x_{i,j} \longrightarrow \max 6x_{1,1} + 7x_{1,2} + 12x_{2,1} + 6x_{2,2} \end{align} Podsumowując, przedstawiony wcześniej problem optymalizacji można zapisać następująco:
W wyniku rozwiązania problemu optymalizacji otrzymujemy następujące wyniki: \begin{array}{c|c|c} W_{i,j} & R1 & R2 \\\hline M1 & 6 & 7\\\hline M2 & 12 & 6 \end{array} $\longrightarrow$ \begin{array}{c|c|c} x_{i,j} & j=1 & j=2 \\\hline i=1 & 0 & 1\\\hline i=2 & 1 & 0 \end{array} $\longrightarrow$ Funkcja celu = 19. Uzyskane rozwiązanie spełnia ograniczenia postawione na etapie formułowania problemu optymalizacji. Dodatkowo widać iż w tym przykładzie wyniki jest oczywisty. Została wybrana taka konfiguracja która odpowiada największej wydajności danego robotnika na danej maszynie.
xsum oraz zastosuj polecenie for do obsługi list.