- 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. 2012/2013
- Liczba punktów ECTS:
- 4
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- 82
- Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- 2
- Język prowadzenia zajęć:
- polski
- Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
- 2
- 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 4-5, laboratoria 4-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 1, laboratorium 1, 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 2, laboratorium 2, 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 2, laboratorium 2, 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 4, laboratoria 4, kolokwium 2
Powiązane efekty kierunkowe:
K_U09, K_U10
Powiązane efekty obszarowe:
T2A_U11, T2A_U15