Metody Optymalizacji

Tablica ogłoszeń

Organizacja sprawdzianów i egzaminów w trybie on-line

1. Student przygotowuję kartkę A4 (czystopis) oraz urządzenie do digitalizacji (skaner, aparat fotograficzny, itp...).
2. W ustalonym terminie na eportalu będą umieszczone treści zadań i podany będzie czas na rozwiązanie zadań.
   Podczas sprawdzianów, egzaminów prowadzący będzie dostępny na platformie MS teams w celu wyjaśnienia możliwych niejasności.
3. Po upływie ustalonego czasu student skanuje (fotografuje) stronę A4 (czystopis) z rozwiązaniami zadań napisanymi ręcznym pismem i niezwłocznie umieszcza plik w formacie pdf ze skanem (fotografią) na eportalu

Terminy egzaminów

• Termin podstawowy 26.06.2024, 08:00-10:00, sala 22, C-3
• Termin poprawkowy 9.07.2024, 15:00-17:00, sala 22, C-3

Warunki zaliczenia kursu

• warunki

Zarezerwowane problemy optymalizacyjne do opracowania

• Zarezerwowane tematy.
  Termin wyboru tematu: 31.03.2024 r, termin oddania: 15.05.2024 r. godzina 6:00, - dwa pliki: pdf (opracowanie), zip (ze źródłami *.tex, *.bib). Pliki umieszczamy na eportal.pwr.edu.pl (w grupie wykładowej).

Wykład

• Wykład nr 1
  1. Problemy optymalizacyjne (egzemplarz, problem optymalizacyjny, przykłady).
  2. Otoczenie.
  3. Lokalne i globalne optima.
  4. Zbiory i funkcje wypukłe.
  5. Problem wypukłego programowania.
  6. Slajdy, notatki.
• Wykłady nr 2, 3
  1. Postacie zadania programowania liniowego.
  2. Interpretacja geometryczna zadania programowania liniowego.
  3. Własności zadania programowania liniowego (wierzchołek,rozwiązanie bazowe dopuszczalne).
  4. Teoretyczne podstawy algorytmu sympleks.
  5. Slajdy 2, Slajdy 3 Notatki.
• Wykłady nr 4, 5
  1. Algorytm sympleks (przejście od rozwiązania bazowego dopuszczalnego do innego rozwiązania bazowego dopuszczalnego, wybór kolumny wchodzącej do bazy, wybór kolumny wychodzącej z bazy, kryterium optymalności).
  2. Degeneracja rozwiązania bazowego dopuszczalnego.
  3. Wyznaczanie pierszego rozwiązania bazowego dopuszczalnego - metoda kar i metoda dwóch faz.
  4. Slajdy 4, Slajdy 5, Notatki.
• Wykład nr 6
  1. Zagadnienie dualne.
  2. Twierdzenia o dualności.
  3. Twierdzenie o różnicach dopełniających.
  4. Slajdy 6, Notatki.
• Wykład nr 7
  1. Dualny algorytm sympleks.
  2. Slajdy 7, Notatki.
  Wykład nr 8
  1. Zrewidowany algorytm sympleks.
  2. Slajdy 8, Notatki.
• Wykład nr 9
  1. Algorytm prymalno-dualny.
  2. Slajdy 9, Notatki.
• Wykład nr 9 cd.
  1. Algorytm prymalno-dualny dla problemu najkrótszej ścieżki w grafie.
  2. Slajdy 9 cd., Notatki.
• Wykład nr 10
  1. Programowanie całkowitoliczbowe PCL.
  2. Metody programowania całkowitoliczbowego: metoda podziału i ograniczeń dla PCL i dla problemów 0-1.
  3. Slajdy 10, Notatki.
• Wykład nr 11
  1. Metoda podziału i ograniczeń dla zagadnień komiwojażera i plecakowego.
  2. Unimodularność, problem najtańszego przepływu.
  3. Slajdy 11, Notatki.
• Wykład nr 12
  1. Relaksacja Lagrange'a I.
  2. Slajdy 12, Notatki.
• Wykład nr 13
  1. Relaksacja Lagrange'a II.
  2. Slajdy 13, Notatki, Materiały pomocnicze II.
• Wykład nr 14
  1. D. Bertsimas and M. Sim. Robust discrete optimization and network flows. Mathematical Programming, 98:49–71, 2003. (pdf dostępny z domeny PWr).

Laboratorium

• Przykładowe modele w formacie lp_solve
  • Przykład 1 z materiałów do wykładu.
    przyklad1.lp
  • Przykład 2 z materiałów do wykładu.
    przyklad2.lp
  • Przykład 3 z materiałów do wykładu.
    przyklad3.lp
  • Funkcja celu nieograniczona w zbiorze rozwiązań dopuszczalnych.
    przyklad4.lp
  • Przykładowy model programowania całkowitoliczbowego (IP).
    przyklad5.lp
  • Przykładowy model programowania mieszanego (LP+IP=MIP).
    przyklad6.lp
  • Przykładowy model programowania binarnego (0-1).
    przyklad7.lp
  • Zagadnienie diety.
    Przykładowy problem. platki.lp
  • Zagadnienie optymalnego wyboru asortymentu.
    Przykładowy problem. aparaty.lp
  • Zagadnienie optymalnego wyboru asortymentu + zagadnienie diety
    Przykładowy problem. pub.lp
• Modeling Language GNU MathProg ( Modeling in GNU MathProg language - a short introduction (slides))
  • Example 1: feasible.mod
  • Example 2: infeasible.mod
  • Exercise: the set of feasible solutions is unbounded, unbounded.mod
  • Example 3:
    • the model for one instance of the problem.: camera.mod
    • arrays and sets: camera_arrays.mod
    • isolating data from model: camera_isolation.mod
    • displaying results, the data section in a separated file: camera_isolation1.mod, camera_isolation1.dat
  • Example 4: LP+IP=MIP, mip.mod
  • Example 5: the selecting items problem, selecting.mod
  • Example 6: the multidimensional zero-one knapsack problem, knapsack.mod
  • Example 7:
    • the dynamic lot sizing with backorders: lotsizing.mod, lotsizing.dat
    • a modified dynamic lot sizing with backorders: lotsizing1.mod
  • Example 8: the minimum cost flow problem, mincostflow.mod
  • Example 9: the shortest path problem, path.mod
  • Example 10: the shortest path problem - randomly generated costs, path1.mod, path1.dat
  • Example 11: the flow shop problem, flowshop.mod
  • Model for solving the minimum spanning tree problem.
    tree.mod, Paper page 5 (the second column)
  • Examples from the glpk 5.0 distribution - very useful for learning the package.
    examples.zip
• Przykładowe modele w języku OPL (zob. również manual w pdf'ie, modelowanie w OPL)
  • Przykłady z materiałów do wykładu:
    przyklady.mod, jedno_rozwiazanie.dat, nieskonczenie_wiele.dat, ograniczona_z_dolu.dat, unbounded.dat, sprzeczny.dat, przyklady.zip
  • Model dla jednego egzemplarza problemu:
    volsay.mod, volsay.zip
  • Tablice, zbiory, izolacja danych od modelu
    
    • gas1.mod,
    • gas.mod, gas.dat, gasn.dat,
    gas.zip
  • Zagadnienie optymalnego wyboru asortymentu + zagadnienie : diety
    opis problemu,
    • pub.mod,
    • pub_gen.mod, pub_gen.dat,
    pub.zip
  • Model dla wielowymiarowego zagadnienia plecakowego:
    knapsack.mod, knapsack.dat, knapsack.zip
  • Model dla pewnego zagadnienia szeregowania:
    job.mod, job.dat, job.zip
  • Model dla zagadnienia najkrótszej ścieżki:
    Model formalny sciezka.mod, sciezka.dat, sciezka.zip
  • Model dla zagadnienia najkrótszej ścieżki - generowanie grafu z losowymi kosztami:
    sciezka1.mod, sciezka1.dat, sciezka.zip
  • Model dla zagadnienia minimalnego drzewa rozpinającego:
    Artykuł str. 5 (druga kolumna) drzewo.mod, drzewo.dat, drzewo.zip
• Przykładowe modele w JuMP (zob. również JuMP)
  • Przykłady z materiałów do wykładu:
    przyklady.jl
  • Model dla wielowymiarowego zagadnienia plecakowego:
    knapsack.jl
  • Model dla zagadnienia szeregowania F||Cmax:
    job.jl,
  • Model dla zagadnienia najkrótszej ścieżki:
    Model formalny path.jl
  • Model dla zagadnienia minimalnego drzewa rozpinającego:
    Artykuł str. 5 (druga kolumna) tree.jl, tree1.jl
  • Model dla jednomaszynowego problemu szeregowania 1|rj|Sum wjTj:
    Model formalny singlemachine.jl,
  
  
• Zadania
  • Zestaw nr 1 termin oddania: 8.04.2024 r. godzina 6:00 - wszystkie grupy,
    - dwa pliki: pdf (sprawozdanie), zip (ze źródłami *.mod, *.dat). Prezentacja rozwiązań podczas najbliższego po terminie oddania laboratorium, pliki umieszczamy na eportal.pwr.edu.pl w swoich grupach laboratoryjnych.
    Może się przydać notatki o modelowaniu, zobacz również rozdział 9 w książce Applied Mathematical Programming - podanej w zalecanej literaturze.
  • Zestaw nr 2 termin oddania: 6.05.2024 r. godzina 6:00 - wszystkie grupy,
    - dwa pliki: pdf (sprawozdanie), zip (ze źródłami *.jl). Prezentacja rozwiązań podczas najbliższego po terminie oddania laboratorium, pliki umieszczamy na eportal.pwr.edu.pl w swoich grupach laboratoryjnych.
    
  • Zestaw nr 3 termin oddania: 3.06.2024 r. godzina 6:00 - wszystkie grupy,
    - dwa pliki: pdf (sprawozdanie), zip (ze źródłami *.jl). Prezentacja rozwiązań podczas najbliższego po terminie oddania laboratorium, pliki umieszczamy na eportal.pwr.edu.pl

Ćwiczenia

• lista nr 1
• lista nr 2
• lista nr 3
• lista nr 3 cd.
• lista nr 4
• lista nr 5
• lista nr 6

Zalecana Literatura

• C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization. Algorithms and Complexity, Dover Publication, Inc,Mineola, 1998.
• R. J. Vanderbei, Linear Programming. Foundations and Extensions, Springer-Verlag, 2008. (książka w formacie pdf dostępna z domeny PWr).
• B. Korte, J. Vygen, Combinatorial Optimization. Theory and Algorithms, Springer-Verlag, 2012. (książka w formacie pdf dostępna z domeny PWr).
• S.P. Bradley, A.C. Hax, T.L. Magnanti, Applied Mathematical Programming, Addison-Wesley Publishing Company, 1977 (książka w formacie pdf).
• Ping-Qi Pan, Linear Programming Computation, Springer-Verlag, 2014. (książka w formacie pdf dostępna z domeny PWr).
• G. Ausiello, A. Marchetti-Spaccamela, P. Crescenzi, G. Gambosi, M. Protasi, V. Kann, Complexity and Approximation. Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag, 2012. (książka w formacie pdf dostępna z domeny PWr).
• R.K. Ahuja, T.L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.
• M.M. Sysło, N. Deo, J.S. Kowalik, Algorytmy optymalizacji dyskretnej z programami w języku PASCAL, PWN, 1999.
• I. Nykowski, Programowanie liniowe, PWE Warszawa 1980.
• W. Grabowski, Programowanie matematyczne, PWE Warszawa 1980.
• R.S. Garfinkel, G.L. Nemhauser, Programowanie całkowitoliczbowe, PWN, 1978.
• G.L. Nemhauser and L.A. Wolsey. Integer and Combinatorial Optimization, John Wiley & Sons, 1988.
• F.S. Hiller, G. J. Lieberman, Introduction to operations research, The McGraw-Hill Co. New York 2001.

Użyteczne linki

• A compendium of NP optimization problems
• Strona poswięcona pakietowi lp_solve 5.5 do rozwiązywania zadań programowania liniowego i całkowitoliczbowego
• lp_solve + IDE pod Windows
• The GLPK package for solving large-scale linear programming (LP) and mixed integer programming (MIP) problems
• GUSEK (GLPK Under Scite Extended Kit): The GLPK + IDE - Windows version
• The GLPK package without IDE - Windows version
• Modeling Language GNU MathProg (html)
• JuMP
• Język Julia.
• Dokumentacja języka Julia .
• The Fast Track to Julia .
• Julia for VSCode.
• The Julia Express, przewodnik po języku Julia.
• Decision Tree for Optimization Software
• OR-LIBRARY (dane testowe dla wielu problemów optymalizacyjnych)