Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Metody optymalizacji dyskretnej
Koordynator przedmiotu:
Rajmund Kożuszek
Status przedmiotu:
Fakultatywny dowolnego wyboru
Poziom kształcenia:
Studia II stopnia
Program:
Informatyka
Grupa przedmiotów:
Przedmioty techniczne - zaawansowane
Kod przedmiotu:
MOD
Semestr nominalny:
3 / rok ak. 2021/2022
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
1. liczba godzin kontaktowych – 47 godz., w tym obecność na wykładach 30 godz., spotkania projektowe 15 godz., konsultacje 2 godz., 2. praca własna studenta – 70 godz., w tym przygotowanie do kolokwium 25 godz., przygotowanie do zadania projektowego 15 godz., realizacja projektu 30 godz. Łączny nakład pracy studenta wynosi 117 godz., co odpowiada 4 pkt. ECTS.
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
1,61 pkt. ECTS, co odpowiada 47 godz. kontaktowym
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
2,05 pkt. ECTS, co odpowiada 15 godz. spotkań projektowych plus 45 godz. przygotowania i realizacji projektu
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia0h
  • Laboratorium0h
  • Projekt15h
  • Lekcje komputerowe0h
Wymagania wstępne:
Podstawy programowania, ZBOP
Limit liczby studentów:
30
Cel przedmiotu:
Celem przedmiotu jest przekazanie podstaw teoretycznych i nauczenie w praktyce rozwiązywania różnych problemów natury dyskretnej (kombinatorycznej). Problemy te najczęściej są związane z planowaniem, optymalizacją i podejmowaniem decyzji napotykanych w systemach zarządzania, logistyki i produkcji. Dzięki zastosowaniu zaawansowanych algorytmów optymalizacji dyskretnej i sieciowej można je rozwiązywać efektywnie.
Treści kształcenia:
Wykład: I. Wprowadzenie. Sprawy organizacyjne, cele i program zajęć, zasady zaliczania. Modele matematycznego programowania liniowego, mieszanego, kwadratowego. Modelowanie dyskretne. II. Problemy i ich klasyfikacja. Specyfika problemów, które można rozwiązywać stosując metody i modele optymalizacji. Przykłady i modele znanych klas problemów: - produkcja, harmonogramowanie, magazynowanie - lokalizacja, alokacja, problemy plecakowe, inwestycje - logistyka, problemy komiwojażera (Vehicle Routing Problem) - pricing - zadania sieciowe modelowane za pomocą teorii grafów, proste (przydział, transportowe), trudniejsze (przepływy wielotowarowe, projektowanie sieci, kolorowanie grafów) - wskazanie obszarów z dużym potencjałem badawczym (np. do rozwijania w ramach indywidualnych prac dyplomowych) oraz odpowiadających na zapotrzebowanie ze strony projektów badawczo-rozwojowych prowadzonych w Zakładzie Badań Operacyjnych i Systemowych, jak i w Instytucie Automatyki i Informatyki Stosowanej. III. Techniki rozwiązywania zadań trudnych 1. Przybliżone - symulowane wyżarzanie - vns - ewolucyjne 2. Dokładne - programowanie dynamiczne, zasada optymalności Bellmana - metody podziału i oszacowań (branch-and-bound) - metody odcięć (algorytm Gomory’ego) - dekompozycje, technika generacji kolumn, dekompozycja Dantziga-Wolfe'a, Bendersa - techniki restrykcyjne i relaksacyjne, relaksacja Lagrange'a - metody prymalno-dualne, metoda Karusha-Kuhna-Tuckera, metoda dualna Lagrange’a - programowanie z ograniczeniami (constraint programming), propagacja ograniczeń zgodnie z algorytmami Backtracking i Forward Checking - algorytmy grafowe i sieciowe: badanie wgłąb, spójność, najkrótsza ścieżka, najlżejsze drzewo; skojarzenia, pokrycia, podział; algorytm Forda-Fulkersona 3. Narzędzia programistyczne modelowania i implementacji metod obliczeniowych dla problemów decyzyjnych - aimms, opl, ampl, cplex, matlab, python-api Ćwiczenia: brak Laboratorium: brak Projekt: Projekt 1: modelowanie zadanego problemu optymalizacji i rozwiązanie go za pomocą komercyjnego pakietu optymalizacyjnego CPLEX, ILOG. Projekt 2: implementacja algorytmu, interfejs, integracja z solwerami, opracowanie kompletnego rozwiązania obejmującego zaprojektowanie, zaprogramowanie i uruchomienie algorytmu rozwiązującego konkretne zadanie biznesowe. Tematy projektów i narzędzia programowe są dobierane indywidualnie, zgodnie z zainteresowaniami studentów. Przykładowe dziedziny - sterowanie i harmonogramowanie produkcji w dyskretnych systemach wytwarzania, projektowanie systemów informacyjnych, zarządzanie i planowanie zasobów w ramach smart grid, zarządzanie i projektowanie sieci komputerowych i sieci telekomunikacyjnych, sieci dystrybucyjnych i komunikacyjnych, zarządzanie zasobami w chmurze, itp. Realizacja projektu składa się z następujących etapów, dla których wyniki będą dyskutowane z prowadzącym: 1. analiza przedstawionego problemu biznesowego i zdefiniowanie zadania modelowania, 2. przygotowanie podstawowego modelu bazowego optymalizacji, 3. opracowanie i implementacja algorytmu wspomagającego rozwiązanie kompleksowego problemu, 4. analiza wyników i ocena efektywności opracowanego rozwiązania.
Metody oceny:
Wykład prowadzony w metodyce blended learning, tzn. tradycyjna forma wspomagana narzędziami internetowymi (oprogramowanie moodle). Realizacja projektów wspomagana narzędziami internetowymi (oprogramowanie moodle) będzie rozbita na kilka etapów (wyniki uzyskane po zakończeniu każdego z nich będą prezentowane i dyskutowane z prowadzącym w trakcie 2-3 godzinnego spotkania).
Egzamin:
nie
Literatura:
Appa, G. M., Pitsoulis, L., & Williams, H. P. (Eds.). (2006). Handbook on modelling for discrete optimization (Vol. 88). Springer Science & Business Media. Korte, B., Vygen, J., Korte, B., & Vygen, J. (2012). Combinatorial optimization (Vol. 2). Heidelberg: Springer. Lau, L. C., Ravi, R., & Singh, M. (2011). Iterative methods in combinatorial optimization (Vol. 46). Cambridge University Press. Sysło Maciej M., Narsingh Deo, Janusz S. Kowalik (1999). Algorytmy optymalizacji dyskretnej, PWN, Warszawa.
Witryna www przedmiotu:
https://usosweb.usos.pw.edu.pl/kontroler.php?_action=katalog2/przedmioty/pokazPrzedmiot&prz_kod=103A-INISY-MSP-MOD
Uwagi:
(-)

Efekty uczenia się