Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Optymalizacja dyskretna i sieciowa
Koordynator przedmiotu:
Eugeniusz Toczyłowski
Status przedmiotu:
Fakultatywny dowolnego wyboru
Poziom kształcenia:
Studia II stopnia
Program:
Informatyka
Grupa przedmiotów:
Przedmioty techniczne - zaawansowane
Kod przedmiotu:
ODS
Semestr nominalny:
4 / rok ak. 2018/2019
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
30 godzin zajec wykladowych,60 godzin pracy własnej związanej z nabyciem wiedzy i umiejętnosci prezentowanych na wykładzie, 45 godzin na wykonanie zadań projektowych
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
3
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
1 - na rozwiązanie zadań projektowych
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia0h
  • Laboratorium0h
  • Projekt15h
  • Lekcje komputerowe0h
Wymagania wstępne:
podstawowa wiedza z zakresu algebry liniowej, badań operacyjnych, zwłaszcza programowania liniowego, złożonosci i teorii grafów.
Limit liczby studentów:
30
Cel przedmiotu:
Celem przedmiotu jest przedstawienie podstawowych metod i technik optymalizacji dyskretnej i sieciowej wykorzystywanych w systemach wspomagania decyzji, w projektowaniu systemów informatycznych i teleinformatycznych, w optymalizacji informatycznych systemów zarządzania, systemów logistycznych, dystrybucyjnych, projektowaniu sieci i systemów rozproszonych oraz optymalizacji rynkowych procesów rozdziału zasobów.
Treści kształcenia:
Metody programowania liniowego. Algorytmy programowania liniowego dla zadań o specjalnej strukturze (zmienne ograniczone, GUB). (4h) Minimalnokosztowe zadania przepływów jednotowarowych w sieciach (2h) Podstawowe metody dokładne optymalizacji dyskretnej. Metoda podziału i ograniczeń. Metody odcięć. Techniki restrykcyjne i relaksacyjne. Metody podziału i odcięć. Algorytmy wielomianowe programowania dynamicznego. (6h) Podstawowe metody przybliżone optymalizacji dyskretnej. Metody przeszukiwań przestrzeni rozwiązań: symulowane wyżarzanie, tabu search, algorytmy ewolucyjne. (4h) Metody strukturalne optymalizacji. Relaksacje Lagrange'a. Metody subgradientowe. Metody dekompozycyjne: techniki generacji kolumn, dekompozycje Dantziga-Wolfe'a, Bendersa. (6h) Minimalnokosztowe zadania przepływów wielotowarowych w sieciach. (2h) Optymalizacja rozdziału zasobów w warunkach konkurencji, projektowanie mechanizmów i procesów rynkowych. Zagadnienia dystrybucyjne. (4h) Projekty Projekt 1: modelowanie zadanego problemu optymalizacji i rozwiązanie go za pomocą komercyjnego pakietu optymalizacyjnego CPLEX, ILOG. Projekt 2: Analiza problemu praktycznego, zaprojektowanie, zaprogramowanie i uruchomienie algorytmu rozwiązującego wybrane zagadnienia praktyczne, wymagające zastosowania metod optymalizacji. Tematy projektów i narzędzia programowe wymagane do Projektu 2 są dobierane indywidualnie, zgodnie z zainteresowaniami studentów. Przykładowe dziedziny - sterowanie i harmonogramowanie produkcji w dyskretnych systemach wytwarzania (w systemach CIM), projektowanie systemów informacyjnych, zarządzanie i projektowanie sieci komputerowych i sieci telekomunikacyjnych, sieci dystrybucyjnych i komunikacyjnych, systemów CAD/CAM, itp.
Metody oceny:
dwa kolokwia w czasie semestru, dwa projekty; egzamin w części pisemnej i ustnej
Egzamin:
tak
Literatura:
Podstawowa: 1. E. Toczyłowski, Optymalizacja dyskretna i sieciowa, materiał wykładu dostępny w formie preskryptu, książka w przygotowaniu Uzupełniająca: 2. E. Toczyłowski, Optymalizacja procesów rynkowych przy ograniczeniach, EXIT, Warszawa, 2002 3. R. Ahuja, T. Magnanti, J. Orlin, Network Flows, Prentice Hall, 1993 4. Deo, N., Teoria grafów i jej zastosowania w informatyce i technice, PWN, Warszawa, 1983. 5. S. Walukiewicz, Programowanie dyskretne, PWN, Warszawa, 1988.
Witryna www przedmiotu:
studia.elka.pw.edu.pl, materiały dostępne studentom na serwerze dydaktycznym
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka ODSW1
nabycie zaawansowanej wiedzy w zakresie najwazniejszych metod i technik optymalizacji dyskretnej i sieciowej
Weryfikacja: rozwiązywanie problemow projektowych i praktycznych zadań optymalizacyjnych
Powiązane charakterystyki kierunkowe: K_W01, K_W08, K_W09
Powiązane charakterystyki obszarowe: I.P7S_WG, III.P7S_WG.o

Profil ogólnoakademicki - umiejętności

Charakterystyka
nabycie umiejętności modelowania problemów decyzyjnych i optymalizacyjnych, z uwzględnieniem różnorodnych wymagań funkcjonalnych oraz pod kątem możliwości skutecznego ich rozwiązywania
Weryfikacja: rozwiązywanie wielu zadań optymalizacyjnych oraz zadań projektowych
Powiązane charakterystyki kierunkowe: K_U12, K_U13, K_U14
Powiązane charakterystyki obszarowe: I.P7S_UW, I.P7S_UO, III.P7S_UW.4.o, III.P7S_UW.3.o

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka ODS_KS
doskonalenie umiejętność współpracy przy realizacji trudnego projektu
Weryfikacja: przy realizacji trudnego projektu Nr 2 w zespole 2-osobowym
Powiązane charakterystyki kierunkowe: K_K01
Powiązane charakterystyki obszarowe: I.P7S_KO