Paweł Zieliński's Home Page

Metody Optymalizacji

Tablica ogłoszeń

Terminy egzaminów

Termin podstawowy dn. 27.06.2025, godz. 8:00, sala 29 bud. D1.
Termin poprawkowy dn. 4.07.2025, godz. 8:00, sala 21 bud. C3.

Warunki zaliczenia kursu

warunki

Zarezerwowane problemy optymalizacyjne do opracowania

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.

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

Ćwiczenia

lista nr 1

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

Powrót do strony głównej