Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Podstawy badań operacyjnych
Koordynator przedmiotu:
Krzysztof Pieńkosz
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia II stopnia
Program:
Informatyka
Grupa przedmiotów:
Przedmioty techniczne - podstawowe
Kod przedmiotu:
POBO
Semestr nominalny:
1 / rok ak. 2018/2019
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
82 udział w wykładach: 15*2 godz. = 30 godz., udział w zajęciach laboratoryjnych: 5* 3 godz. = 15 godz., przygotowanie do kolejnych wykładów (przejrzenie materiałów z wykładu i literatury): 4 godz., udział w konsultacjach: 2 godz. w semestrze, przygotowanie do kolokwiów 2 * 8 godz. = 16 godz., przygotowanie do laboratoriów, w tym rozwiązanie zadań domowych: 5 * 3 godz.= 15 godz.
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
2 udział w wykładach: 15*2 godz. = 30 godz., udział w zajęciach laboratoryjnych: 5* 3 godz. = 15 godz., udział w konsultacjach: 2 godz., w sumie: 30 + 15 + 2 = 47 godz. – ok. 2 punkty ECTS.
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
2 udział w zajęciach laboratoryjnych: 5* 3 godz. = 15 godz., przygotowanie do kolejnych wykładów: 4 godz., przygotowanie do laboratoriów, w tym rozwiązanie zadań domowych: 5 * 3 godz.= 15 godz. przygotowanie do kolokwiów 2 * 8 godz. = 16 godz., w sumie: 15 + 4+15 + 16 = 50 godz. – ok. 2 punkty ECTS.
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia0h
  • Laboratorium15h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
znajomość matematyki na poziomie I roku studiów: zbiory, grafy, szeregi, układy równań liniowych, podstawowe pojęcia rachunku prawdopodobieństwa
Limit liczby studentów:
80
Cel przedmiotu:
Celem przedmiotu jest syntetyczne przedstawienie podstawowych modeli matematycznych, metod i narzędzi badań operacyjnych stosowanych do formułowania i rozwiązywania problemów decyzyjnych w różnorodnych zastosowaniach informatyki - przy projektowaniu i analizie systemów komputerowych oraz sieci teleinformatycznych, w systemach wspomagania decyzji, przy planowaniu i harmonogramowaniu procesów produkcji i dystrybucji dóbr i usług oraz w systemach zarządzania. W ramach wykładu kładzie się nacisk na analizę różnorodnych praktycznych zagadnień decyzyjnych oraz umiejętność ich modelowania.
Treści kształcenia:
Treść wykładu Wprowadzenie do Badań Operacyjnych (2h). Przedmiot Badań Operacyjnych - przykładowe zagadnienia i wybrane dziedziny zastosowań. Zdefiniowanie podstawowych pojęć z zakresu Badań Operacyjnych. Opis ogólnej metodologii Badań Operacyjnych: identyfikacja problemu, budowa modelu, opracowanie metody (algorytmu) rozwiązywania, proces rozwiązywania, analiza rozwiązań, weryfikacja i walidacja modelu, wdrożenie. Modele planowanie przedsięwzięć (4h). Metoda ścieżki krytycznej. Określenie najwcześniejszych i najpóźniejszych terminów realizacji zadań. Wyznaczenie ścieżki krytycznej i zapasów czasu. Problem planowania przedsięwzięć z ograniczeniami zasobowymi. Uwzględnienie możliwości skracania operacji przy dodatkowych kosztach. Analiza problemu planowania przedsięwzięć przy ograniczonym dostępie zasobów odnawialnych (pracowników, pamięci komputerowej itp.). Uwzględnienie niepewności w planowaniu przedsięwzięć - metoda PERT. Programowanie liniowe (4h). Podstawowe pojęcia z zakresu Programowania liniowego. Formułowanie modeli programowania liniowego na przykładach wybranych problemów decyzyjnych. Interpretacja graficzna Zadania Programowania Liniowego przy dwóch zmiennych decyzyjnych. Analiza parametryczna rozwiązań w zależności od wartości współczynników funkcji celu i ograniczeń. Omówienie algorytmu sympleks. Dualność w programowaniu liniowym, interpretacja cen dualnych. Modele programowania nieliniowego i optymalizacji dyskretnej (3h). Praktyczne ograniczenia w stosowaniu modeli programowania liniowego. Przykładowe problemy decyzyjne prowadzące do zadań programowania nieliniowego i dyskretnego. Relacje pomiędzy rozwiązaniami problemu dyskretnego i jego relaksacji ciągłej. Charakterystyka metod rozwiązywania zadań optymalizacji dyskretnej. Uwagi nt. złożoności obliczeniowej problemów i algorytmów. Programowanie dynamiczne (2h). Sformułowanie wieloetapowego problemu decyzyjnego. Definicja etapu i stanu. Zasada optymalności Bellmana. Reprezentacja problemu z dyskretną i skończoną przestrzenią stanów za pomocą grafu. Wyznaczenie optymalnej trajektorii sterowania. Przykłady zastosowań metody programowania dynamicznego. Przekształcanie problemów decyzyjnych do zagadnień wieloetapowych. Modele sieciowe (4h). Modele sieci przepływowych: zagadnienie maksymalnego i najtańszego przepływu. Właściwości modeli sieciowych. Formułowanie przykładowych zadań transportowych, przydziału, harmonogramowania w postaci zadań sieciowych. Reprezentacja zadań przepływu w sieciach w postaci zadania programowania liniowego. Omówienie przykładowych problemów decyzyjnych modelowanych za pomocą sieci przepływowych. Problemy szeregowania zadań na procesorach (2h). Wprowadzenie do zagadnień szeregowania: zadania podzielne i niepodzielne, zależności czasowe między operacjami i zadaniami, typowe kryteria szeregowania. Klasyczne problemy szeregowania: problem przepływowy, gniazdowy, systemy otwarte. Wybrane metody szeregowania: reguły priorytetowe szeregowania zadań na jednym procesorze, szeregowanie zadań na dwóch procesorach - algorytm Johnsona. Dynamiczne reguły szeregowania. Systemy masowej obsługi (3h). Modele systemów masowej obsługi: źródła zgłoszeń, stanowiska obsługi, kolejki, czasy zgłoszeń i obsługi. Charakterystyki funkcjonowania systemów obsługi w stanie ustalonym. Analiza prostego systemu obsługi typu (M|M|c) o ograniczonej pojemności i zadanych parametrach. Wyprowadzenie wzorów na charakterystyki funkcjonowania systemu. Sieci kolejkowe (4h). Modele otwartych sieci kolejkowych. Analiza sieci z dwoma szeregowymi stanowiskami. Twierdzenie Jacksona o dekompozycji sieci. Przykłady analizy modeli otwartych sieci kolejkowych o różnych strukturach. Modele zamkniętych sieci kolejkowych. Metoda analizy wartości średnich. Przykłady zastosowań. Zakres laboratorium Ćwiczenie 1 - Modele symulacyjne procesów dyskretnych Analiza deterministycznego systemu obsługi składającego się z kilku stanowisk. Formułowanie modelu symulacyjnego przy wykorzystaniu programu Micro Saint. Symulacja procesu obsługi i weryfikacja modelu symulacyjnego. Dobór reguł sterujących przy różnych kryteriach szeregowania. Ćwiczenie 2 - Planowanie przedsięwzięć Formułowanie modelu przedsięwzięcia w postaci sieci projektu. Wyznaczenie najwcześniejszych i najpóźniejszych terminów realizacji zadań. Określenie ścieżki krytycznej i zapasów czasowych dla poszczególnych zadań. Wprowadzenie i rozwiązanie zadania za pomocą programu MS Project. Analiza i modyfikacja harmonogramu realizacji przedsięwzięcia przy uwzględnieniu ograniczeń na zasoby odnawialne. Uwzględnianie możliwości skracania czasu wykonywania zadań przy dodatkowych nakładach finansowych. Ćwiczenie 3 - Programowanie liniowe i całkowitoliczbowe Formułowanie modeli liniowych dla przykładowych problemów decyzyjnych. Rozwiązanie problemów przy wykorzystaniu programu AMPL Plus. Analiza rozwiązań i weryfikacja modeli. Badanie wrażliwości rozwiązań optymalnych na zmianę wskazanych parametrów. Ćwiczenie 4 - Modele sieciowe Analiza różnych wariantów zadania przydziału: formułowanie modelu sieciowego, rozwiązanie przy użyciu programu ModGraf, formułowanie modelu liniowego i rozwiązywanie za pomocą programu AMPL Plus, porównanie wyników. Analiza i rozwiązywanie zadania transportowego.
Metody oceny:
oceniane są zadania domowe, ćwiczenia laboratoryjne wykonywane indywidualnie oraz kolokwia
Egzamin:
nie
Literatura:
Toczyłowski E.: Podstawy Badań Operacyjnych, preskrypt do wykładu POBO. Ignasiak E. (red.): Badania operacyjne, PWE. Sysło M. M., Deo N., Kowalik J.S.: Algorytmy optymalizacji dyskretnej, PWN. Jędrzejczyk Z., Kukuła K., Skrzypek J., Walkosz A.: Badania operacyjne w przykładach i zadaniach, PWN.
Witryna www przedmiotu:
https://usosweb.usos.pw.edu.pl/kontroler.php?_action=katalog2/przedmioty/pokazPrzedmiot&prz_kod=103B-ARxxx-ISP-POBO
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka W1POBO-I
zna metodologię badań operacyjnych i podstawowe modele stosowane do rozwiązywania zadań decyzyjnych
Weryfikacja: zadania domowe 1-5, laboratoria 1-5, kolokwia 1-2
Powiązane charakterystyki kierunkowe: K_W08, K_W09
Powiązane charakterystyki obszarowe: I.P7S_WG, III.P7S_WG.o
Charakterystyka W2POBO-I
zna pojęcia z zakresu optymalizacji umożliwiające modelowanie zadań decyzyjnych
Weryfikacja: zadania domowe 1-4, laboratoria 1-4, kolokwia 1-2
Powiązane charakterystyki kierunkowe: K_W01, K_W09
Powiązane charakterystyki obszarowe: I.P7S_WG
Charakterystyka W3POBO-I
ma podstawową wiedzę z zakresu systemów masowej obsługi umożliwiającą przeprowadzenie analizy oraz symulacji prostego systemu
Weryfikacja: zadania domowe 1 i 5, laboratorium 1 i 5, kolokwium 2
Powiązane charakterystyki kierunkowe: K_W09
Powiązane charakterystyki obszarowe: I.P7S_WG

Profil ogólnoakademicki - umiejętności

Charakterystyka U1POBO-I
potrafi zaplanować przedsięwzięcie metodą ścieżki krytycznej, wyznaczyć zapasy czasu poszczególnych operacji i utworzyć harmonogram realizacji przedsięwzięcia z uwzględnieniem standardowych wymagań
Weryfikacja: zadanie domowe 2, laboratorium 2, kolokwium 1
Powiązane charakterystyki kierunkowe: K_U12
Powiązane charakterystyki obszarowe: I.P7S_UW, I.P7S_UO, III.P7S_UW.4.o
Charakterystyka U2POBO-I
potrafi sformułować model programowania liniowego (PL) dla prostego problemu decyzyjnego
Weryfikacja: zadanie domowe 3, laboratorium 3, kolokwia 1-2
Powiązane charakterystyki kierunkowe: K_U09
Powiązane charakterystyki obszarowe: I.P7S_UW, III.P7S_UW.1.o
Charakterystyka U3POBO-I
rozwiązać zadanie PL za pomocą standardowego oprogramowania i przeprowadzić analizę postoptymalizacyjną
Weryfikacja: zadanie domowe 3, laboratorium 3, kolokwia 1-2
Powiązane charakterystyki kierunkowe: K_U09
Powiązane charakterystyki obszarowe: I.P7S_UW, III.P7S_UW.1.o
Charakterystyka U4POBO-I
umie sformułować i rozwiązać za pomocą standardowego oprogramowania problem decyzyjny dyskretny
Weryfikacja: zadanie domowe 3, laboratorium 3, kolokwium 1-2
Powiązane charakterystyki kierunkowe: K_U09
Powiązane charakterystyki obszarowe: I.P7S_UW, III.P7S_UW.1.o
Charakterystyka U5POBO-I
potrafi przeprowadzić symulację procesu dyskretnego dla różnych reguł szeregowania zadań
Weryfikacja: zadania domowe 1 i 5, laboratoria 1 i 5
Powiązane charakterystyki kierunkowe: K_U09, K_U10
Powiązane charakterystyki obszarowe: I.P7S_UW, III.P7S_UW.1.o, III.P7S_UW.3.o