Informacje ogólne

Typ:obowiazkowy

Program

Badania operacyjne to nauka zajmująca się teorią podejmowania decyzji. Zadaniem badań operacyjnych jest znalezienie odpowiedniej metody rozwiązywania problemów decyzyjnych, prowadzące do optymalizacji i maksymalizacji zysków. Jest to dziedzina, która pomaga podjąć decyzję najlepszą z możliwych. Obejmuje między innymi programowanie matematyczne, zagadnienia transportowe oraz sieciowe. Celem wykładu jest zapoznanie słuchacza z częścią metod badań operacyjnych oraz przedstawienie zastosowań metod operacyjnych w informatyce.

• Złożoność obliczeniowa problemów decyzyjnych (klasy złożoności, klasy P i NP, problemy NP-zupełne).
• Metody optymalizacyjne:
  - programowanie liniowe (metoda graficzna, sympleks, dualna)
  - programowanie całkowitoliczbowe,
  - programowanie dynamiczne,
  - zagadnienia transportowe.
• Deterministyczne problemy szeregowania zadań
  - procesory równoległe oraz dedykowane (open-, job-, flow-shop)
  - minimalizacja różnych kryteriów (długość uszeregowania, średni czas przepływu, maksymalne opóźnienie, itd.)
  - zadania o różnych parametrach
  - modele szeregowania z uwzględnieniem dodatkowych zasobów.
• Zastosowania problemów szeregowania zadań.

Sposób zaliczenia

Ćwiczenia: zaliczenie dwóch kolokwiów + praca na ćwiczeniach.
Egzamin pisemny.

Literatura

• J. Błażewicz, W. Cellary, R. Słowiński, J. Węglarz, Badania operacyjne dla informatyków, WNT 1983.
• P. Brucker, Scheduling algorithms, Springer 2006.
• J. Y-T.Leung, Handbook of scheduling: algorithms, models, and performance analysis , Chapman
• M. Sysło, N. Deo, J. Kowalik, Algorytmy optymalizacji dyskretnej, PWN 1995.