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. 2014/2015
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:
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 i sieci teleinformatycznych, w systemach wspomagania decyzji, przy planowaniu i harmonogramowaniu procesów produkcji, dystrybucji dóbr i usług oraz w systemach zarządzania
Treści kształcenia:
Wprowadzenie do badań operacyjnych. Przykładowe zagadnienia i wybrane dziedziny zastosowań. Podstawowe pojęcia z zakresu badań operacyjnych. Opis ogólnej metodologii badań operacyjnych. Planowanie przedsięwzięć. Metoda ścieżki krytycznej. Wyznaczenie zapasów czasowych operacji. Problem planowania przedsięwzięć z ograniczeniami zasobowymi: zużywalnymi (możliwość skracania operacji przy dodatkowych kosztach) oraz odnawialnymi (ograniczony dostęp pracowników). Uwzględnianie niepewności w planowaniu przedsięwzięć – metoda PERT. Programowanie liniowe. Ogólna postać zadania programowania liniowego. Formułowanie liniowych modeli optymalizacyjnych na przykładach wybranych zagadnień. 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 prawych stron ograniczeń. Programowanie dyskretne. Formułowanie przykładowych zadań dyskretnych w postaci zadań programowania liniowego całkowitoliczbowego. Relacje pomiędzy rozwiązaniami problemu dyskretnego i jego relaksacji liniowej. Prezentacja metod rozwiązywania zadań programowania dyskretnego. Schemat metody podziału i oszacowań. Uwagi nt. złożoności obliczeniowej problemów dyskretnych. Algorytmy heurystyczne. 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. Przekroje w sieciach. Uwagi nt. rozwiązań całkowitoliczbowych w zadaniach sieciowych (unimodularność). Programowanie dynamiczne. Sformułowanie wieloetapowego problemu decyzyjnego. Zasada optymalności Bellmana. Wyznaczenie optymalnej trajektorii sterowania. Przykłady zastosowań metody programowania dynamicznego. Przekształcanie problemów decyzyjnych do zagadnień wieloetapowych. Wprowadzenie do zagadnień szeregowania zadań. Klasyczne problemy szeregowania: problem przepływowy, gniazdowy, systemy otwarte. Wybrane algorytmy szeregowania: szeregowanie zadań na jednym procesorze, na dwóch procesorach – algorytm Johnsona, na procesorach równoległych. Dynamiczne reguły szeregowania. Systemy masowej obsługi. Charakterystyki funkcjonowania systemów obsługi w stanie równowagi. Analiza prostego systemu obsługi typu (M|M|c). Systemy obsługi o bardziej złożonej strukturze – otwarte sieci kolejkowe.
Metody oceny:
oceniane są zadania domowe, ćwiczenia laboratoryjne wykonywane indywidualnie oraz kolokwia
Egzamin:
nie
Literatura:
1.Ignasiak E. (red.): Badania operacyjne, PWE. 2.Sysło M. M., Deo N., Kowalik J.S.: Algorytmy optymalizacji dyskretnej, PWN. 3.Kukuła K. (red.): Badania operacyjne w przykładach i zadaniach, PWN.
Witryna www przedmiotu:
studia.elka.pw.edu.pl
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt 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 efekty kierunkowe: K_W08, K_W09
Powiązane efekty obszarowe: T2A_W07, T2A_W03
Efekt 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 efekty kierunkowe: K_W01, K_W09
Powiązane efekty obszarowe: T2A_W01, T2A_W03
Efekt 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 efekty kierunkowe: K_W09
Powiązane efekty obszarowe: T2A_W03

Profil ogólnoakademicki - umiejętności

Efekt 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 efekty kierunkowe: K_U12
Powiązane efekty obszarowe: T2A_U17
Efekt U2POBO-I
potrafi sformułować model programowania liniowego (PL) dla prostego problemu decyzyjnego
Weryfikacja: zadanie domowe 3, laboratorium 3, kolokwia 1-2
Powiązane efekty kierunkowe: K_U09
Powiązane efekty obszarowe: T2A_U11
Efekt 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 efekty kierunkowe: K_U09
Powiązane efekty obszarowe: T2A_U11
Efekt 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 efekty kierunkowe: K_U09
Powiązane efekty obszarowe: T2A_U11
Efekt 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 efekty kierunkowe: K_U09, K_U10
Powiązane efekty obszarowe: T2A_U11, T2A_U15