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

Zajęcia modułu prowadzone są w postaci wykładu (28 godzin) i laboratorium (28 godzin).
Celem wykładu jest zaznajomienie z metodami optymalizacji ciągłej i dyskretnej oraz zdobycia umiejętności w tworzeniu modeli matematycznych rzeczywistych zagadnień optymalizacyjnych. W ramach laboratorium przewiduje się praktyczną implementację różnych algorytmów dokładnych i przybliżonych.

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 i rozumie pojęcia związane z badaniami operacyjnymi AiR1A_W04 Kolokwium
M_W002 Zna modele matematyczne typowych problemów decyzyjnych AiR1A_W04, AiR1A_W01 Kolokwium
M_W003 Dysponuje podstawową wiedzą z zakresu złożoności obliczeniowej AiR1A_W04 Kolokwium
Umiejętności: potrafi
M_U001 Potrafi samodzielnie tworzyć modele matematyczne problemów decyzyjnych AiR1A_U01, AiR1A_U09 Wykonanie ćwiczeń laboratoryjnych,
Kolokwium
M_U002 Posiada umiejętność rozwiązywania problemów decyzyjnych z wykorzystaniem odpowiednich metod badań operacyjnych. AiR1A_U01, AiR1A_U09, AiR1A_U05 Wykonanie ćwiczeń laboratoryjnych,
Kolokwium
Kompetencje społeczne: jest gotów do
M_K001 Zna zastosowanie poznanych metod i algorytmów badań operacyjnych we współczesnym świecie. AiR1A_K01, AiR1A_K03 Wykonanie ćwiczeń laboratoryjnych,
Kolokwium
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 i rozumie pojęcia związane z badaniami operacyjnymi + - - - - - - - - - -
M_W002 Zna modele matematyczne typowych problemów decyzyjnych + - - - - - - - - - -
M_W003 Dysponuje podstawową wiedzą z zakresu złożoności obliczeniowej + - - - - - - - - - -
Umiejętności
M_U001 Potrafi samodzielnie tworzyć modele matematyczne problemów decyzyjnych - - + - - - - - - - -
M_U002 Posiada umiejętność rozwiązywania problemów decyzyjnych z wykorzystaniem odpowiednich metod badań operacyjnych. - - + - - - - - - - -
Kompetencje społeczne
M_K001 Zna zastosowanie poznanych metod i algorytmów badań operacyjnych we współczesnym świecie. - - + - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 90 godz
Punkty ECTS za moduł 3 ECTS
Udział w zajęciach dydaktycznych/praktyka 56 godz
Samodzielne studiowanie tematyki zajęć 34 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):
  1. Wprowadzenie do badań operacyjnych – rys historyczny, sformułowanie zadań badań operacyjnych, przykładowe problemy.

  2. Podstawowe pojęcia złożoności obliczeniowej. Modele obliczeń (maszyna Turinga), klasy złożoności problemów, metodyka dowodzenia NP-zupełności i NP-trudności problemów. Rodzaje decyzji. Warunki podejmowania decyzji. Modele decyzyjne. Budowa modelu matematycznego. Zagadnienie pierwotne/dualne

  3. Programowanie liniowe (PL).
    Model matematyczny programowania liniowego. Metody rozwiązywania problemów programowania liniowego: metoda graficzna, metoda Simpleks. Dualność – twierdzenie o dualności, zasady budowy modelu dualnego, interpretacja zmiennych dualnych. Przykłady praktyczne zastosowania.

  4. Algorytmy grafowe.
    Podstawowe pojęcia teorii grafów, problemy i dedykowane algorytmy grafowe (wyznaczania najkrótszej ścieżki w grafie, minimalne drzewo rozpinające grafu, zagadnienie podziału grafu, zagadnienie komiwojażera, izomorfizm, kolorowanie grafów, skojarzenia).

  5. Problemy sieciowe. Planowanie sieciowe – metody amerykańskie, metoda potencjałów MPM, wykres Gantta, graf stochastyczny PERT5.

  6. Zagadnienia przydziału i organizacji produkcji (szeregowanie zadań) – sformułowanie zagadnień, kryteria optymalności uszeregowania zadań, klasyfikacja problemów przydziału i szeregowania, wybrane problemy jednomaszynowe, wybrane problemy wielomaszynowe, algorytmy przydziału (metoda węgierska) i szeregowania (algorytmy dokładne – Johnsona, Browna-Łomnickiego, metody przybliżone – Palmera, Gupty, CDS , NEH).

  7. Drzewa decyzyjne
    Reguły konstrukcji drzewa i wyznaczania decyzji optymalnej. Metody klasyczne i heurystyczne przeszukiwania drzew.

  8. Metoda programowania dynamicznego – zasada optymalności Bellmana, binarne i całkowitoliczbowe zagadnienie załadunku (liniowe, nieliniowe).

Ćwiczenia laboratoryjne (28h):
  1. Spotkanie organizacyjne. Harmonogram zajęć. Zasady zaliczania przedmiotu. Wprowadzenie do badań operacyjnych. Rodzaje decyzji. Warunki podejmowania d
  2. Metoda programowania liniowego.
  3. Metoda Simpleks.
  4. Algorytmy grafowe – modele grafowe, własności grafów, algorytmy przeszukiwania wszerz i w głąb.
  5. Algorytmy grafowe – Minimalne drzewo rozpinające grafu, najkrótsza ścieżka w grafie.
  6. Algorytmy grafowe – zagadnienia podziału grafu, izomorfizm, kolorowanie grafu.
  7. Algorytmy grafowe – zagadnienia komiwojażera.
  8. Zagadnienie komiwojażera II.
  9. Programowanie sieciowe – metoda ścieżki krytycznej.
  10. Metoda programowania dynamicznego – zagadnienia załadunku.
  11. Metoda programowania dynamicznego – zagadnienia alokacji zasobów i wyznaczania wielkości partii produkcyjnej.
  12. Algorytmy szeregowania zadań – algorytmy dokładne – Johnsona, Browna-Łomnickiego, metody przybliżone – Palmera, Gupty, CDS , NEH).
  13. Metoda węgierska – zagadnienie przydziału.
  14. 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 wzbogaconymi o pokazy odnoszące się do prezentowanych zagadnień.
  • Ć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:

1.Warunkiem uzyskania zaliczenia jest uzyskanie pozytywnych ocen z laboratoriów i kolokwium z wykładu.
2. Obecność laboratoriach jest obowiązkowa. Więcej niż dwie nieobecności nieusprawiedliwione powoduje brak zaliczenia przedmiotu, przy czym nieobecności usprawiedliwić należy w terminie do 2 tygodni. Student ma prawo do jednego terminu poprawkowego kolokwium. Oceny pozytywnej nie można poprawiać.
3. Obecność na wykładzie jest zalecana.

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. Zaliczenie modułu jest możliwe po zaliczeniu wszystkich zajęć laboratoryjnych.
Sposób obliczania oceny końcowej:

1.Ocena końcowa jest średnią ważoną z laboratoriów (waga 0,7) i kolokwium zaliczeniowego (waga 0,3). Oceny z laboratorium i wykładu (średnia z 2 kolokwiów) muszą być pozytywne
2. W przypadku zaliczenia labolatorium w terminie poprawkowym, ocena końcowa wyznaczana jest jako średnia arytmetyczna z ocen z wszystkich dotychczasowych terminów, przy czym wystawiana jest ocena co najmniej 3,0.
3. 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:

1. Więcej niż jedna nieobecność nieusprawiedliwiona powoduje brak zaliczenia przedmiotu, przy czym nieobecności usprawiedliwić należy w terminie do 2 tygodni (licząc od końca okresu nieobecności).
2. W przypadku dłuższych lub częstych nieobecności usprawiedliwionych (3 lub więcej) należy zgłosić się do prowadzącego w celu ustalenia sposobu nadrobienia i zaliczenia zaległości.

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

Znajomość dowolnego języka programowania wysokopoziomowego.

Zalecana literatura i pomoce naukowe:

1. Błażewicz J., Celary W., Słowiński R.,Węglarz J., Badania operacyjne dla informatyków. WNT, Warszawa 1983
2. Sawik T., Badania operacyjne dla inżynierów zarządzania. Wydawnictwo AGH, Kraków1998
3. Smutnicki C., Algorytmy szeregowania. Akademicka Oficyna Wydawnicza EXIT, Warszawa 2002
4. Mikołajczak B., Stokłosa J., Złożoność obliczeniowa algorytmów. Wydawnictwo Politechniki Poznańskiej, Poznań 1986
5. Sysło M., Deo N., Kowalik J. S., Algorytmy optymalizacji dyskretnej z programami w języku Pascal. PWN, W-wa 1995
6. Lawrence Davis: Handbook of Genetic Algorithms
7. Cormen T.C., Leiserson Ch.E., Rivest R.L., Stein C.: Wprowadzenie do algorytmów. WNT, Warszawa 2007

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

1. W. Chmiel. Evolutionary algorithm using conditional expectation value
for quadratic assignment problem. Swarm and Evolutionary Computation, 46:1 – 27,
2019
2. W. Chmiel and J. Kwiecień. Quantum-Inspired Evolutionary Approach for the Quadratic Assignment Problem. Entropy, 20(10), 2018
3. W. Chmiel, P. Kadłuczka, K.Wala, and S.Jedrusik. Algorytmy heurystyczne w trójwymiarowym zagadnieniu pakowania—heuristic algorithm for threedimensional packing problem. Automatyka/Automatics, 14(3/2):827–840, 2010
4. Chmiel W., Kadłuczka P., Packanik G.:Zastosowanie algorytmów rojowych w rozwiązywaniu zagadnień permutacyjnych. 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.

Informacje dodatkowe:

Brak