Badania Operacyjne

Studia Stacjonarne, Automatyka i Robotyka, Semestr 4 - 30h.

Wykład:

Celem zajęć jest: matematyczne modelowanie sytuacji decyzyjnych - wraz z oceną przynależności do klasy złożoności obliczeniowej modeli - występujących w systemach automatyki i informatyki, analizy poprawności i złożoności obliczeniowej algorytmów optymalizacji, konstruowania ścisłych i przybliżonych algorytmów optymalizacji deterministycznych problemów decyzyjnych.

Program:

• Metodologia i zastosowania badań operacyjnych.
• Matematyczne modelowanie problemów decyzyjnych.
• Wprowadzenie do teorii złożoności obliczeniowej algorytmów i problemów.
• Przegląd klasycznych modeli i algorytmów optymalizacji problemów wielomianowych wraz z analizą własności, poprawności i złożoności obliczeniowej, w tym wielomianowych problemów sieciowych, problemów załadunku i przydziału, wielomianowych problemów harmonogramowania zadań.
• Algorytmy szeregowania listowego wybranych problemów wielomianowych wraz z oceną poprawności i złożoności obliczeniowej.
• Przegląd klasycznych NP-trudnych problemów, w tym problemów transportowych, przydziału i podziału, harmonogramowania przedsięwzięć oraz zadań (technologicznych i obliczeniowych).
• Ścisłe metody optymalizacji problemów NP-trudnych: programowanie dynamiczne, przegląd zupełny rozwiązań dopuszczalnych, metoda podziału i ograniczeń.
• Charakterystyka metod przybliżonych optymalizacji problemów NP-trudnych i problem szacowania rozwiązań przybliżonych.
• Algorytmy konstrukcyjne (stosowane reguły wyboru, algorytmy zachłanne, szeregowania listowego i wstawień, złożoność obliczeniowa algorytmów).
• Algorytmy popraw rozwiązań: klasyczne algorytmy optymalizacji lokalnej (jak np. optymalizacja lokalna z wieloma rozwiązaniami początkowymi i ze zmiennym otoczeniem) oraz klasyczne metaheurystyki (np. symulowanego wyżarzania, poszukiwania z zabronieniami, systemy ewolucyjne).

Bibliografia:

1. Notatki w internecie: http://oen.dydaktyka.agh.edu.pl/dydaktyka/automatyka/c_3_bad_operac_elektrotechnika_fizyka/badania_op.php?subpage=lit
2. Notatki w internecie; http://oen.dydaktyka.agh.edu.pl/dydaktyka/matematyka/c_badania_operacyjne/index.html
3. St. Walukiewicz, Programowanie dyskretne, PWN, W'86.
4. J. Błażewicz, W. Cellary, R. Słowiński, J. Węglarz, Badania operacyjne dla informatyków, WNT, W'83.
5. J. Błażewicz, W. Cellary, R.S łowiński, J. Węglarz, Algorytmy sterowania rozdziałem zadań i zasobów w kompleksie operacji, Wyd. Polil. Poznańskiej, Poznań'81
6. T. Kasprzak (red), Optymalizacja dyskretna. Zastosowania ekonomiczne, PWE, W'84.
7. T. Sawik, Optymalizacja dyskretna w badaniach operacyjnych, Wyd. AGH, Kraków'82.
8. T. Sawik, Badania operacyjne dla inżynierów zarządzania, Wyd. AGH, Kraków'98.
9. M. M. Syslo, N. Deo, J. S. Kowalik, Algorytmy optymalizacji dyskretnej, PWN, W'93.
10. Handbooks in operation research and management science, North-Holland, 1996.
11. Radin R., Introduction to operations research, Hertfordshire, Prentice Hall, 1997