Politechnika Warszawska - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Podstawy badań operacyjnych

Informacje ogólne

Kod przedmiotu: 103B-ARxxx-ISP-POBO Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Podstawy badań operacyjnych
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Podstawy automatyki i robotyki )-Automatyka i robotyka-inż.-EITI
( Podstawy systemów )-Informatyka-inż.-EITI
( Przedmioty podstawowe )-Systemy informacyjno-decyzyjne-mgr.-EITI
( Przedmioty techniczne )---EITI
Punkty ECTS i inne: 4.00
Język prowadzenia: polski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

POBO

Numer wersji:

2

Skrócony opis:

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.

Pełny opis:

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ść 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.

Literatura:

    1. Toczyłowski E.: Podstawy Badań Operacyjnych, preskrypt do wykładu POBO.
    2. Ignasiak E. (red.): Badania operacyjne, PWE.
    3. Sysło M. M., Deo N., Kowalik J.S.: Algorytmy optymalizacji dyskretnej, PWN.
    4. Jędrzejczyk Z., Kukuła K., Skrzypek J., Walkosz A.: Badania operacyjne w przykładach i zadaniach, PWN.

Metody i kryteria oceniania:

Liczba punktów do zdobycia na kolokwiach: 40.

Liczba punktów do zdobycia na laboratoriach: 40.

Warunkiem zaliczenia przedmiotu POBO jest uzyskanie w sumie co najmniej
41 punktów oraz zdobycie co najmniej połowy punktów na
przynajmniej jednym kolokwium.


Zajęcia w cyklu "rok akademicki 2019/2020 - sem. letni" (jeszcze nie rozpoczęty)

Okres: 2020-02-22 - 2020-09-30

Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 120 miejsc więcej informacji
Wykład, 30 godzin, 120 miejsc więcej informacji
Koordynatorzy: Krzysztof Pieńkosz
Prowadzący grup: Krzysztof Pieńkosz
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. zimowy" (w trakcie)

Okres: 2019-10-01 - 2020-02-21
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 120 miejsc więcej informacji
Wykład, 30 godzin, 120 miejsc więcej informacji
Koordynatorzy: Krzysztof Pieńkosz
Prowadzący grup: Mariusz Kaleta, Krzysztof Pieńkosz
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. letni" (zakończony)

Okres: 2019-02-18 - 2019-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 120 miejsc więcej informacji
Wykład, 30 godzin, 120 miejsc więcej informacji
Koordynatorzy: Krzysztof Pieńkosz
Prowadzący grup: Andrzej Karbowski, Adam Krzemienowski, Krzysztof Pieńkosz, Tomasz Śliwiński
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. zimowy" (zakończony)

Okres: 2018-10-01 - 2019-02-17
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 120 miejsc więcej informacji
Wykład, 30 godzin, 120 miejsc więcej informacji
Koordynatorzy: Eugeniusz Toczyłowski
Prowadzący grup: Mariusz Kaleta, Krzysztof Pieńkosz, Eugeniusz Toczyłowski, Alicja Trojanowska, Izabela Żółtowska
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2017/2018 - sem. letni" (zakończony)

Okres: 2018-02-19 - 2018-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 120 miejsc więcej informacji
Wykład, 30 godzin, 120 miejsc więcej informacji
Koordynatorzy: Krzysztof Pieńkosz
Prowadzący grup: Mariusz Kaleta, Piotr Pałka, Krzysztof Pieńkosz
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2017/2018 - sem. zimowy" (zakończony)

Okres: 2017-10-01 - 2018-02-18
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 115 miejsc więcej informacji
Wykład, 30 godzin, 115 miejsc więcej informacji
Koordynatorzy: Eugeniusz Toczyłowski
Prowadzący grup: Eugeniusz Toczyłowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2016/2017 - sem. letni" (zakończony)

Okres: 2017-02-20 - 2017-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 156 miejsc więcej informacji
Wykład, 30 godzin, 156 miejsc więcej informacji
Koordynatorzy: Krzysztof Pieńkosz
Prowadzący grup: Krzysztof Pieńkosz
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2016/2017 - sem. zimowy" (zakończony)

Okres: 2016-10-01 - 2017-02-19
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 60 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: Eugeniusz Toczyłowski
Prowadzący grup: Eugeniusz Toczyłowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2015/2016 - sem. letni" (zakończony)

Okres: 2016-02-23 - 2016-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 150 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Krzysztof Pieńkosz
Prowadzący grup: Krzysztof Pieńkosz
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2015/2016 - sem. zimowy" (zakończony)

Okres: 2015-10-01 - 2016-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 115 miejsc więcej informacji
Wykład, 30 godzin, 115 miejsc więcej informacji
Koordynatorzy: Eugeniusz Toczyłowski
Prowadzący grup: Eugeniusz Toczyłowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2014/2015 - sem. letni" (zakończony)

Okres: 2015-02-23 - 2015-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 135 miejsc więcej informacji
Wykład, 30 godzin, 135 miejsc więcej informacji
Koordynatorzy: Krzysztof Pieńkosz
Prowadzący grup: Krzysztof Pieńkosz
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2014/2015 - sem. zimowy" (zakończony)

Okres: 2014-09-29 - 2015-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 115 miejsc więcej informacji
Wykład, 30 godzin, 115 miejsc więcej informacji
Koordynatorzy: Grzegorz Płoszajski
Prowadzący grup: Grzegorz Płoszajski
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2013/2014 - sem. letni" (zakończony)

Okres: 2014-02-24 - 2014-09-28
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 115 miejsc więcej informacji
Wykład, 30 godzin, 115 miejsc więcej informacji
Koordynatorzy: Krzysztof Pieńkosz
Prowadzący grup: Krzysztof Pieńkosz
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2013/2014 - sem. zimowy" (zakończony)

Okres: 2013-10-01 - 2014-02-23
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 115 miejsc więcej informacji
Wykład, 30 godzin, 115 miejsc więcej informacji
Koordynatorzy: Grzegorz Płoszajski
Prowadzący grup: Grzegorz Płoszajski
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2012/2013 - sem. letni" (zakończony)

Okres: 2013-02-20 - 2013-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 115 miejsc więcej informacji
Wykład, 30 godzin, 115 miejsc więcej informacji
Koordynatorzy: Krzysztof Pieńkosz
Prowadzący grup: Krzysztof Pieńkosz
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2012/2013 - sem. zimowy" (zakończony)

Okres: 2012-10-01 - 2013-02-19
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin, 60 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: Grzegorz Płoszajski
Prowadzący grup: Grzegorz Płoszajski
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.