class: center, middle, inverse, title-slide .title[ # Optymalizacja dyskretna
(w tym algorytmy heurystyczne) ] .subtitle[ ## Programowanie matematyczne ] .author[ ### Jakub Nowosad
https://jakubnowosad.com/
] --- <!-- https://www.youtube.com/watch?v=haLz9CFRqQs --> <!-- https://en.wikipedia.org/wiki/Mathematical_optimization --> <!-- https://www.informs.org/Explore/History-of-O.R.-Excellence/O.R.-Methodologies/Optimization-Mathematical-Programming --> <!-- https://dirkschumacher.github.io/ompr/articles/index.html --> <!-- https://dirkschumacher.github.io/rmpk/ --> <!-- http://www.cs.put.poznan.pl/kmiazga/students/alai/guide_opt.pdf --> # Programowanie matematyczne Typy programowania matematycznego: - Optymalizacja (programowanie) liniowa (ang. *linear programming (LP); linear optimization*) - Optymalizacja (programowanie) nieliniowa (ang. *nonlinear programming (NLP)*) <!-- - Optymalizacja (programowanie) ciągła (ang. *nonlinear programming (NLP)*) --> - Optymalizacja (programowanie) całkowitoliczbowa (ang. *integer programming*) - Inne Narzędzia: - http://lpsolve.sourceforge.net/5.5/ - https://cran.r-project.org/package=lpSolve - https://cran.r-project.org/web/views/Optimization.html - https://coin-or.github.io/pulp/ --- # Formalizacja - Jaki jest cel/są cele? - Jakie decyzje trzeba podjąć? - Jakie istnieją ograniczenia? - Jak ocenić wpływ decyzji na cel/e? <!-- Formalizacja - przykład - https://www.youtube.com/watch?v=haLz9CFRqQs min 11 --> --- # Formalizacja - Jaki jest cel/są cele? - **Kryteria. Funkcje celu** - Jakie decyzje trzeba podjąć? - **Zmienne decyzyjne** - Jakie istnieją ograniczenia? - **Ograniczenia. Przestrzeń rozwiązań dopuszczalnych** - Jak ocenić wpływ decyzji na cel/e? - **Sposób obliczania funkcji celu** <!-- Przykład - https://www.youtube.com/watch?v=haLz9CFRqQs min 17 - https://www.youtube.com/watch?v=haLz9CFRqQs min 20 --> <!-- płaszczyzny wielowymiarowe --> <!-- https://en.wikipedia.org/wiki/Linear_programming --> <!-- # Analiza wrażliwości --> <!-- # Analiza parametryczna --> --- # Zmienne ciągłe, dyskretne, binarne <!-- - https://www.youtube.com/watch?v=haLz9CFRqQs min 68 --> - Zmienne ciągłe - Zmienne dyskretne - utrudnienie problemu (*Branch and Bound*) - Zmienne binarne - utrudnienie problemu --- class: inverse, left, bottom # Programowanie liniowe --- # Programowanie liniowe <!-- - Technika optymalizacyjna --> - Przydatne w problemach optymalizacji zasobów: - Przydzielenie odpowiednio ludzi i sprzętu, aby zminimalizować koszty - Zdecydowanie jakie produkty i w jakiej ilości wyprodukować, aby otrzymać największy zysk --- # Przykład https://brilliant.org/wiki/linear-programming/ - Fabryka produkuje śróbokręty i młotki. - Produkcja śróbokrętu kosztuje 2$ i trwa 3 godziny. - Wyprodukowanie młotka kosztuje 4$ i trwa 2 godziny. - Fabryka ma 220 dolarów i 150 godzin w tygodniu, aby wyprodukować te produkty. - Jeśli każdy śróbokręt sprzedaje się za 6 dolarów i każdy młotek sprzedaje się za 7 dolarów, to ile każdego produktu powinno się produkować w tygodniu, aby zmaksymalizować zysk? -- Jest to problem pasujący do programowania liniowego, bo: 1. Wszystkie zależności numeryczne mają charakter liniowy 2. Wartości zmiennych są ograniczone 3. Celem jest znalezionie wartości zmiennych, które maksymalizują pewien aspekt --- # Przykład - formalizacja - Jaki jest cel/są cele? - **Kryteria. Funkcje celu** - Maksymalizacja zysku -- - Jakie decyzje trzeba podjąć? - **Zmienne decyzyjne** - Określenie liczby wyprodukowanych młotków i śróbokrętów -- - Jakie istnieją ograniczenia? - **Ograniczenia. Przestrzeń rozwiązań dopuszczalnych** - 220 dolarów - 150 godzin -- - Jak ocenić wpływ decyzji na cel/e? - **Sposób obliczania funkcji celu** - Funkcja liniowa --- # Przykład - relacje Koszty produkcji a zasoby: $$ 2x + 4y \le 220 $$ -- Czas produkcji a dostępny czas: $$ 3x + 2y \le 150 $$ -- Inne ograniczenia (czasem oczywiste dla nas): $$ x \ge 0 \\ y \ge 0 $$ --- # Przykład - relacje .lc[ Razem: $$ `\begin{cases} 2x + 4y \le 220 \\ 3x + 2y \le 150 \\ x \ge 0 \\ y \ge 0 \end{cases}` $$ ] -- .rc[ <div class="figure" style="text-align: center"> <img src="images/inequality-constraints.png" alt="https://brilliant.org/wiki/linear-programming/" width="90%" /> <p class="caption">https://brilliant.org/wiki/linear-programming/</p> </div> ] --- # Przykład - funkcja celu - Wykonanie każdego śróbokręta kosztuje $2 i sprzedaje się go za $6. - Daje to zysk w wysokości $4 za śróbokręt. - Wykonanie każdego młotka kosztuje 4$ i sprzedaje się go za 7$. - Daje to zysk w wysokości 3$ za młotek. -- Funkcja celu (funkcja zysku) może być zdefiniowana jako: $$ p(x,y) = 4x + 3y $$ --- # Przykład - funkcja celu - `\(P\)` - maksymalny możliwy do uzyskania zysk: $$ P = 4x + 3y $$ - Rozwiązanie `\(y\)` $$ y = -\frac{4}{3}x + \frac{P}{3} $$ - Oznacza to, że `\(x\)` jest nachylony `\(-\frac{4}{3}\)` w stosunku do `\(y\)` --- # Przykład - funkcja celu .lc[ - Rozwiązanie `\(y\)` $$ y = -\frac{4}{3}x + \frac{P}{3} $$ - Oznacza to, że `\(x\)` jest nachylony `\(-\frac{4}{3}\)` w stosunku do `\(y\)` ] .rc[ <div class="figure" style="text-align: center"> <img src="images/inequality-constraints2.png" alt="https://brilliant.org/wiki/linear-programming/" width="80%" /> <p class="caption">https://brilliant.org/wiki/linear-programming/</p> </div> ] --- # Przykład - funkcja celu .lc[ Miejsca przecięcia czerwonych linii z niebieską powierzchnią określają możliwe rozwiązania - Przecięcie (0, 55): `\(0 * 4 + 55 * 3 = 165\)` - Przecięcie (12, 48): `\(12 * 4 + 48 * 3 = 192\)` - **Przecięcie (20, 45): `\(20 * 4 + 45 * 3 = 215\)`** ] .rc[ <div class="figure" style="text-align: center"> <img src="images/inequality-constraints2.png" alt="https://brilliant.org/wiki/linear-programming/" width="80%" /> <p class="caption">https://brilliant.org/wiki/linear-programming/</p> </div> ] --- # Przykład - funkcja celu .lc[ Miejsca przecięcia czerwonych linii z niebieską powierzchnią określają możliwe rozwiązania - Jedna z nich maksymalizuje możliwe rozwiązanie - wierzchołek na przecięciu (20, 45) - W problemach liniowych optymalne rozwiązanie, będzie zawsze znajdować się na jednym z wierzchołków możliwego obszaru ] .rc[ <div class="figure" style="text-align: center"> <img src="images/inequality-constraints2.png" alt="https://brilliant.org/wiki/linear-programming/" width="80%" /> <p class="caption">https://brilliant.org/wiki/linear-programming/</p> </div> ] --- # Przykład II - Fabryka produkuje śróbokręty i młotki. - Produkcja śróbokrętu kosztuje 3$ i trwa 3 godziny. - Wyprodukowanie młotka kosztuje 6$ i trwa 2 godziny. - Fabryka ma 300 dolarów i 200 godzin w tygodniu, aby wyprodukować te produkty. - Jeśli każdy śróbokręt sprzedaje się za 5 dolarów i każdy młotek sprzedaje się za 10 dolarów, to ile każdego produktu powinno się produkować w tygodniu, aby zmaksymalizować zysk? --- class: inverse, left, bottom # Metoda sympleksów --- # Metoda sympleksów - https://www.wikiwand.com/en/Simplex_algorithm .pull-left[ *Simplex Algorithm*. Procedura systematycznego sprawdzania wierzchołków w celu znalezienia optymalnego rozwiązania. Idea: - Zacznij w którymś krańcowym punkcie - Obrót (ang. *pivot*) z jednego krańcowego punktu do leżącego krańcowego punktu obok (który nie daje gorszego wyniku) - Powtarzaj do otrzymania optymalnego rozwiązania ] .pull-right[ <div class="figure" style="text-align: center"> <img src="images/simplex3d.png" alt="https://pl.wikipedia.org/wiki/Plik:Simplex-method-3-dimensions.png" width="683" /> <p class="caption">https://pl.wikipedia.org/wiki/Plik:Simplex-method-3-dimensions.png</p> </div> ] <!-- The simplex method is a systematic procedure for testing the vertices as possible solutions. --> <!-- - https://pl.wikipedia.org/wiki/Algorytm_sympleksowy --> <!-- http://www.cs.put.poznan.pl/jjozefowska/wyklady/bo/bo1.pdf --> <!-- - https://brilliant.org/wiki/linear-programming/ --> <!-- --> <!-- Inne --> <!-- MIP --> --- class: inverse, left, bottom # R --- # R <!-- https://towardsdatascience.com/linear-programming-in-r-444e9c199280 --> .pull-left[ $$ p(x,y) = 4x + 3y $$ $$ `\begin{cases} 2x + 4y \le 220 \\ 3x + 2y \le 150 \\ x \ge 0 \\ y \ge 0 \end{cases}` $$ - Ograniczenie do wartości nieujemnych jest domyślne ] .pull-right[ ```r library(lpSolve) obj_fun = c(4, 3) obj_fun ``` ``` ## [1] 4 3 ``` ```r constraints = matrix(c(2, 4, 3, 2), nrow = 2, byrow = TRUE) constraints ``` ``` ## [,1] [,2] ## [1,] 2 4 ## [2,] 3 2 ``` ```r dir_fun = c("<=", "<=") dir_fun ``` ``` ## [1] "<=" "<=" ``` ```r rhs_fun = c(220, 150) rhs_fun ``` ``` ## [1] 220 150 ``` ] --- # R ```r # Rozwiązanie (wartość) result = lp("max", obj_fun, constraints, dir_fun, rhs_fun) result ``` ``` ## Success: the objective function is 215 ``` ```r # Rozwiązanie (liczba elementów) result$solution ``` ``` ## [1] 20 45 ``` --- class: inverse, left, bottom # Przykłady <!-- --- --> <!-- # Logistyka --> <!-- - Pięc lokalizacji początkowych (np. fabryki lub magazyny): Gdańsk, Kraków, Poznań, Warszawa, Wrocław --> <!-- -- --> <!-- - Dziewięć lokalizacji końcowych (np. hurtownie lub sklepy): Gdańsk, Kraków, Poznań, Warszawa, Wrocław, Łódź, Katowice, Białystok --> <!-- -- --> <!-- - Produkcja (np. miesięczna) w jednostkach (np. palety czy tony): --> <!-- - Gdańsk - 2000 --> <!-- - Kraków - 1500 --> <!-- - Poznań - 1500 --> <!-- - Warszawa - 2000 --> <!-- - Wrocław - 1300 --> <!-- --- --> <!-- # Logistyka --> <!-- - Zapotrzebowanie (miesięczne) w jednostkach (np. palety czy tony): --> <!-- - Gdańsk - 1000 --> <!-- - Kraków - 1300 --> <!-- - Poznań - 800 --> <!-- - Warszawa - 1400 --> <!-- - Wrocław - 700 --> <!-- - Łódź - 500 --> <!-- - Katowice - 1200 --> <!-- - Białystok - 400 --> <!-- -- --> <!-- - Znamy odległości pomiędzy lokalizacjami --> <!-- - Koszt transportu jednej jednostki wynosi 0.25 zł za kilometr --> <!-- - Każda lokalizacja końcowa powinna korzystać z produkcji lokalnej --> <!-- - Nie można przekroczyć możliwości produkcyjnych ale też nie należy produkować nadmiaru niepotrzebnego towaru --> <!-- - Nalezy ustalić ile jednostek należy dostarczyć rocznie z każdej fabryki do każdej hurtowni minimalizując koszty transportu --> --- # Problem plecakowy Integer Programming .pull-left[ <div class="figure" style="text-align: center"> <img src="images/knapsack.png" alt="https://commons.wikimedia.org/wiki/File:Knapsack.svg" width="924" /> <p class="caption">https://commons.wikimedia.org/wiki/File:Knapsack.svg</p> </div> ] .pull-right[ Liczba elementów: - `\(I = 5\)` Ograniczenie (ang. *constraint*): - `\(W = 15\)` Wagi: - `\(w_1 = 12\)`, `\(w_2 = 2\)`, `\(w_3 = 1\)`, `\(w_4 = 1\)`, `\(w_5 = 4\)` Wartości: - `\(c_1 = 4\)`, `\(c_2 = 2\)`, `\(c_3 = 2\)`, `\(c_4 = 1\)`, `\(c_5 = 10\)` ] --- # Problem plecakowy .pull-left[ Liczba elementów: - `\(I = 5\)` Ograniczenie (ang. *constraint*): - `\(W = 15\)` Wagi: - `\(w_1 = 12\)`, `\(w_2 = 2\)`, `\(w_3 = 1\)`, `\(w_4 = 1\)`, `\(w_5 = 4\)` Wartości: - `\(c_1 = 4\)`, `\(c_2 = 2\)`, `\(c_3 = 2\)`, `\(c_4 = 1\)`, `\(c_5 = 10\)` ] .pull-right[ ```r library(lpSolve) wartosci = c(4, 2, 2, 1, 10) wagi = c(12, 2, 1, 1, 4) W = 15 mod = lp(direction = "max", objective.in = wartosci, const.mat = rbind(wagi), const.dir = c("<="), const.rhs = c(W), all.bin = TRUE) # Rozwiązanie mod$solution ``` ``` ## [1] 0 1 1 1 1 ``` ```r # Zysk mod$objval ``` ``` ## [1] 15 ``` ] --- # Problem plecakowy II ```r library(dplyr) library(ROI) library(ROI.plugin.glpk) library(ompr) library(ompr.roi) wartosci = c(4, 2, 2, 1, 10) wagi = c(12, 2, 1, 1, 4) n = length(wagi) W = 15 MIPModel() %>% add_variable(x[i], i = 1:n, type = "binary") %>% set_objective(sum_expr(wartosci[i] * x[i], i = 1:n), "max") %>% add_constraint(sum_expr(wagi[i] * x[i], i = 1:n) <= W) %>% solve_model(with_ROI(solver = "glpk")) %>% get_solution(x[i]) %>% filter(value > 0) ``` ``` ## variable i value ## 1 x 2 1 ## 2 x 3 1 ## 3 x 4 1 ## 4 x 5 1 ``` --- # Inne https://dirkschumacher.github.io/ompr/ --- class: inverse, left, bottom # Dodatkowe informacje --- # Dodatkowe informacje - https://www.youtube.com/watch?v=haLz9CFRqQs - https://cran.r-project.org/web/views/Optimization.html - https://brilliant.org/wiki/linear-programming/ - https://towardsdatascience.com/linear-programming-in-r-444e9c199280 - https://upcommons.upc.edu/bitstream/handle/2117/78335/Modeling+and+Solving+Linear+Programming+with+R.pdf;jsessionid=6932D84F471E2CD236AD5400A5A08340?sequence=1 - https://www.youtube.com/watch?v=da7r3Qyn6ag - https://www.esri.com/news/arcuser/0402/files/optimize.pdf - https://gistbok.ucgis.org/bok-topics/linear-programming-and-gis