Politechnika Warszawska - Centralny System Uwierzytelniania
Strona główna

Metody optymalizacji dyskretnej

Informacje ogólne

Kod przedmiotu: 103A-INISY-MSP-MOD
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Metody optymalizacji dyskretnej
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Metody )-Inteligentne systemy-mgr.-EITI
( Przedmioty techniczne )---EITI
( Przedmioty zaawansowane techniczne )--mgr.-EITI
Punkty ECTS i inne: 4.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.
Język prowadzenia: polski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

MOD

Numer wersji:

1

Skrócony opis:

Problemy kombinatoryczne, czyli takie w których natura zmiennych jest dyskretna, są powszechne w wielu praktycznych obszarach działalności współczesnych przedsiębiorstw (problemy logistyczne, inwestycyjne, lokalizacyjne, szeregowania) ale też leżą u podstaw wielu dziedzin nauki, szczególnie ekonomii, techniki i biologii. Takie problemy w skali rzeczywistej wymagają operowania na dużej ilości danych i mogą być trudne do rozwiązywania. Tradycyjnie stosowane były w takich obszarach metaheurystyki czerpiące z rozwoju metod sztucznej inteligencji. Jednak w ostatnich latach obserwujemy również rosnącą rolę metod i narzędzi optymalizacji przy rozwiązywaniu wielkoskalowych problemów dyskretnych. Dostrzegane są też różnorodne związki optymalizacji ze sztuczną inteligencją. Wzrost zainteresowania dokładnymi algorytmami optymalizacji dyskretnej przekłada się na ich dalszy rozwój i poszerzanie zakresu...

Pełny opis:

Wykład:

  1. Wprowadzenie. Sprawy organizacyjne, cele i program zajęć, zasady zaliczania. Modele matematycznego programowania liniowego, mieszanego, kwadratowego. Modelowanie dyskretne.
  2. 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)
  3. 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
      • algorytmy grafowe i sieciowe: badanie wgłąb, spójność, najkrótsza ścieżka, najlżejsze drzewo; skojarzenia, pokrycia, podział; algorytm Forda-Fulkersona
  4. Narzędzia programistyczne modelowania i implementacji metod obliczeniowych dla problemów decyzyjnych
    • aimms, opl, ampl, cplex, matlab, python-api



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.
Literatura:

  1. Appa, G. M., Pitsoulis, L., & Williams, H. P. (Eds.). (2006). Handbook on modelling for discrete optimization (Vol. 88). Springer Science & Business Media.
  2. Korte, B., Vygen, J., Korte, B., & Vygen, J. (2012). Combinatorial optimization (Vol. 2). Heidelberg: Springer.
  3. Lau, L. C., Ravi, R., & Singh, M. (2011). Iterative methods in combinatorial optimization (Vol. 46). Cambridge University Press.
  4. Sysło Maciej M., Narsingh Deo, Janusz S. Kowalik (1999). Algorytmy optymalizacji dyskretnej, PWN, Warszawa.

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

Okres: 2021-10-01 - 2022-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Projekt, 15 godzin, 45 miejsc więcej informacji
Wykład, 30 godzin, 45 miejsc więcej informacji
Koordynatorzy: Izabela Żółtowska
Prowadzący grup: Mariusz Kaleta, Krzysztof Pieńkosz, Tomasz Śliwiński, Izabela Żółtowska
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.
pl. Politechniki 1, 00-661 Warszawa tel: (22) 234 7211 https://pw.edu.pl kontakt deklaracja dostępności USOSweb 6.8.0.0-4 (2022-09-16)