Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Badania operacyjne 2
Tok studiów:
2019/2020
Kod:
EAiR-1-505-s
Wydział:
Elektrotechniki, Automatyki, Informatyki i Inżynierii Biomedycznej
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Automatyka i Robotyka
Semestr:
5
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Stacjonarne
Strona www:
 
Prowadzący moduł:
dr hab. inż. Kwiecień Joanna (kwiecien@agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

Celem przedmiotu jest poznanie modeli i metod z zakresu badań operacyjnych oraz uzyskanie umiejętności właściwego ich wykorzystania do optymalizacji problemów dyskretnych.

Opis efektów uczenia się dla modułu zajęć
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Powiązania z KEU Sposób weryfikacji i oceny efektów uczenia się osiągniętych przez studenta w ramach poszczególnych form zajęć i dla całego modułu zajęć
Wiedza: zna i rozumie
M_W001 Zna metody badań operacyjnych oraz ich wybrane zastosowania. AiR1A_W04 Aktywność na zajęciach,
Kolokwium
M_W002 Zna i rozumie metodykę tworzenia modeli matematycznych rzeczywistych problemów optymalizacji. AiR1A_W04 Wykonanie ćwiczeń laboratoryjnych,
Kolokwium
M_W003 Posiada umiejętność implementacji i testowania algorytmu przybliżonego dla określonego zbioru instancji testowych. AiR1A_W04 Wykonanie ćwiczeń laboratoryjnych
Umiejętności: potrafi
M_U001 Umie zastosować właściwe metody dla określonych problemów optymalizacji, w tym optymalizacji kombinatorycznej. AiR1A_U01 Wykonanie ćwiczeń laboratoryjnych,
Udział w dyskusji,
Kolokwium
M_U002 Umie pracować indywidualnie i w zespole AiR1A_U03 Wykonanie ćwiczeń laboratoryjnych
M_U003 Potrafi wykorzystać posiadaną wiedzę do formułowania rzeczywistego zagadnienia optymalizacyjnego oraz dokonać oceny przydatności tych informacji. AiR1A_U01 Wykonanie ćwiczeń laboratoryjnych
Kompetencje społeczne: jest gotów do
M_K001 Dostrzega możliwość wykorzystania poznanej wiedzy w praktyce AiR1A_K01 Wykonanie ćwiczeń laboratoryjnych
M_K002 Rozumie potrzebę śledzenia najnowszych osiągnięć w zakresie badań operacyjnych. AiR1A_K01 Wykonanie ćwiczeń laboratoryjnych,
Aktywność na zajęciach
Liczba godzin zajęć w ramach poszczególnych form zajęć:
SUMA (godz.)
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
56 28 0 28 0 0 0 0 0 0 0 0
Matryca kierunkowych efektów uczenia się w odniesieniu do form zajęć i sposobu zaliczenia, które pozwalają na ich uzyskanie
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Forma zajęć dydaktycznych
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Wiedza
M_W001 Zna metody badań operacyjnych oraz ich wybrane zastosowania. + - - - - - - - - - -
M_W002 Zna i rozumie metodykę tworzenia modeli matematycznych rzeczywistych problemów optymalizacji. + - + - - - - - - - -
M_W003 Posiada umiejętność implementacji i testowania algorytmu przybliżonego dla określonego zbioru instancji testowych. - - + - - - - - - - -
Umiejętności
M_U001 Umie zastosować właściwe metody dla określonych problemów optymalizacji, w tym optymalizacji kombinatorycznej. + - + - - - - - - - -
M_U002 Umie pracować indywidualnie i w zespole - - + - - - - - - - -
M_U003 Potrafi wykorzystać posiadaną wiedzę do formułowania rzeczywistego zagadnienia optymalizacyjnego oraz dokonać oceny przydatności tych informacji. + - + - - - - - - - -
Kompetencje społeczne
M_K001 Dostrzega możliwość wykorzystania poznanej wiedzy w praktyce + - + - - - - - - - -
M_K002 Rozumie potrzebę śledzenia najnowszych osiągnięć w zakresie badań operacyjnych. - - + - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 110 godz
Punkty ECTS za moduł 4 ECTS
Udział w zajęciach dydaktycznych/praktyka 56 godz
Przygotowanie do zajęć 20 godz
przygotowanie projektu, prezentacji, pracy pisemnej, sprawozdania 10 godz
Samodzielne studiowanie tematyki zajęć 24 godz
Szczegółowe treści kształcenia w ramach poszczególnych form zajęć (szczegółowy program wykładów i pozostałych zajęć)
Wykład (28h):

WYKŁAD
1. Modelowanie problemów rzeczywistych – klasyfikacja algorytmów.
2. Metoda programowania dynamicznego – zasada optymalności Bellmana, przykłady: binarne i całkowitoliczbowe zagadnienie załadunku (liniowe, nieliniowe), zagadnienie alokacji zasobów, wyznaczanie wielkości partii produkcyjnej.
3. Metoda podziału i ograniczeń – Zasady tworzenia algorytmów dokładnych i przybliżonych w oparciu o tę metodę. Przykłady zastosowań – algorytm Landa i Doiga, algorytm podziału i ograniczeń o binarnym drzewie rozwiązań dla problemu plecakowego, zagadnienia komiwojażera (otwartego i zamkniętego).
4. Metody przybliżone przeszukiwania przestrzeni rozwiązań – algorytm optymalizacji lokalnej, wielostartu, poszukiwania z zabronieniami.
5. Algorytmy ewolucyjne – zarys teorii, podstawowe pojęcia, algorytm genetyczny,
6. Algorytmy inspirowane przez naturę w optymalizacji kombinatorycznej:
algorytmy stadne (PSO, algorytm pszczeli, algorytm mrówkowy, algorytm świetlika, algorytm karalucha)
7. Teoria kolejek – podstawowe modele kolejkowe.

Ćwiczenia laboratoryjne (28h):

ĆWICZENIA LABORATORYJNE

1. Wprowadzenie. Harmonogram zajęć. Metody ścisłe i przybliżone w optymalizacji dyskretnej
2. Metoda podziału i ograniczeń – zagadnienie komiwojażera.
3. Algorytm genetyczny
4. Modelowanie problemów rzeczywistych.
5. Formalizacja modelu matematycznego dla NP-trudnego problemu rzeczywistego
6. Zastosowanie metod przybliżonych w rozwiązywaniu złożonych problemów dyskretnych
7. Definiowanie reprezentatywnego zbioru instancji testowych problemu
8. Testowanie efektywności algorytmów i opracowanie wyników eksperymentów obliczeniowych.
9.Charakterystyka przebiegu algorytmu.
10. Kolokwium zaliczeniowe.

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Treści prezentowane na wykładzie są przekazywane w formie prezentacji multimedialnej w połączeniu z klasycznym wykładem tablicowym.
  • Ćwiczenia laboratoryjne: W trakcie zajęć laboratoryjnych studenci samodzielnie rozwiązują zadany problem praktyczny, dobierając odpowiednie narzędzia. Prowadzący stymuluje grupę do refleksji nad problemem, tak by otrzymane wyniki miały wysoką wartość merytoryczną.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

W ramach ćwiczeń laboratoryjnych przewidziane są do realizacji zagadnienia praktyczne. Ponadto przewidziane jest kolokwium. Ocena z ćwiczeń laboratoryjnych jest wyznaczana na podstawie punktów uzyskanych z kolokwium (30%) i realizowanych zagadnień laboratoryjnych (70%). Suma punktów uzyskanych z ćwiczeń przeliczana jest na ocenę końcową zgodnie z regulaminem studiów AGH.
Student ma prawo do jednego terminu poprawkowego kolokwium. Oceny pozytywnej nie można poprawiać.

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Nie
    – Zasady udziału w zajęciach: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci winni na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
  • Ćwiczenia laboratoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci wykonują ćwiczenia laboratoryjne zgodnie z materiałami udostępnionymi przez prowadzącego. Student jest zobowiązany do przygotowania się w przedmiocie wykonywanego ćwiczenia, co może zostać zweryfikowane kolokwium w formie ustnej lub pisemnej. Zaliczenie zajęć odbywa się na podstawie zaprezentowania rozwiązania postawionego problemu.
Sposób obliczania oceny końcowej:

Ocena końcowa pokrywa się z oceną uzyskaną z ćwiczeń laboratoryjnych. Za aktywny udział w dyskusjach na wykładzie ocena ta może być podwyższona o 0.5 stopnia.
W przypadku zaliczenia w terminie poprawkowym, ocena końcowa wyznaczana jest jako średnia arytmetyczna z ocen z wszystkich dotychczasowych terminów.

Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Obecność na ćwiczeniach laboratoryjnych jest obowiązkowa. Więcej niż jedna nieobecność nieusprawiedliwiona powoduje brak zaliczenia przedmiotu, przy czym nieobecności usprawiedliwić należy w terminie do 2 tygodni. Nieobecności na zajęciach laboratoryjnych student może uzupełnić z inną grupą laboratoryjną realizującą ten sam temat, przy czym termin powinien zostać uzgodniony z prowadzącym. W przypadku 3 lub większej liczby nieobecności (usprawiedliwionych) należy zgłosić się do prowadzącego w celu ustalenia sposobu nadrobienia zaległości.

Wymagania wstępne i dodatkowe, z uwzględnieniem sekwencyjności modułów :

Znajomość języka programowania C/C++/C#, Java lub Matlab

Zalecana literatura i pomoce naukowe:

1. Burkard R.E., Çela E., Pardalos P.M., Pitsoulis L., The quadratic assignment problem, Handbook of Combinatorial Optimization, 1998. Kluwer Academic Publishers, Dordrecht.
2. Cormen T.C., Leiserson Ch.E., Rivest R.L., Stein C.: Wprowadzenie do algorytmów. WNT, Warszawa 2007
3. Filipowicz B.: Badania operacyjne. Wybrane metody obliczeniowe i algorytmy. Cz. 1. Wydawnictwo ABART, Kraków 2007.
4. Filipowicz B.: Matematyczne modelowanie zagadnień decyzyjnych. Cz 1. Wydawnictwa AGH, Kraków 1998.
5. Michalewicz Z., Fogel D. B.: How to Solve It: Modern Heuristics, Springer Verlag, 2000, tłum. WNT.
6. Michalewicz Z.: Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT, Warszawa 1996
7. Goldberg D. E.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company, 1989; tłum. Algorytmy genetyczne i ich zastosowania. WNT, Warszawa, 1995.

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. Chmiel W., Kadłuczka P., Kwiecień J., Filipowicz B., Pukocz P.: Strategic planning optimisation using tabu search algorithm. Proceedings of VIII international conference on Knowledge, Information and Creativity Support Systems, Kraków 2013.
2. Chmiel W., Kadłuczka P., Packanik G.:Zastosowanie algorytmów rojowych w rozwiązywaniu zagadnień permutacyjnych. Automatyka, 15(2), 2011.
3. Filipowicz B., Kwiecień J.: Algorytmy stadne w optymalizacji problemów przydziału przy kwadratowym wskaźniku jakości (QAP). Automatyka 15(2), 2011.
4. Kwiecień J., Filipowicz B.: Comparison of firefly and cockroach algorithms in selected discrete and combinatorial problems. Bulletin of the Polish Academy of Sciences. Technical Sciences, 62(4), 2014.
5. Szwed P., Chmiel W.: Multi-swarm PSO algorithm for the Quadratic Assignment Problem: a massive parallel implementation on the OpenCL platform. Neural and Evolutionary Computing (cs.NE), http://arxiv.org/abs/1504.05158
6. Szwed P., Chmiel W., Kadłuczka P.: OpenCL implementation of PSO algorithm for the quadratic assignment problem. Artificial Intelligence and Soft Computing : 14th International Conference, ICAISC 2015, Springer, Lecture Notes in Computer Science, Lecture Notes in Artificial Intelligence; LNAI 9120, 223–234, 2015.

Informacje dodatkowe:

Brak