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

Podstawy optymalizacji

Informacje ogólne

Kod przedmiotu: 103C-INSID-ISP-POPTY Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Podstawy optymalizacji
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Podstawy optymalizacji )-Systemy informacyjno-decyzyjne-inż.-EITI
( Przedmioty podstawowe )-Systemy informacyjno-decyzyjne-mgr.-EITI
( Przedmioty techniczne )---EITI
( Systemy informacyjno decyzyjne )-Systemy informacyjno-decyzyjne-inż.-EITI
Punkty ECTS i inne: 4.00
Język prowadzenia: polski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

POPTY

Numer wersji:

3

Skrócony opis:

Podstawowym celem wykładu jest zapoznanie studentów z pewnymi pakietami modelowania i rozwiązywania zadań optymalizacyjnych (AMPL, LP_SOLVE, MATLAB) oraz z pojęciem optimum, warunkami koniecznymi i dostatecznymi optymalności dla zadań optymalizacji bez ograniczeń i z ograniczeniami pozwalającymi na weryfikację poprawności uzyskiwanych z pakietów rozwiązań. Ponadto w ramach wykładu zapoznają się z elementami teorii dualności Lagrange`a oraz niektórymi z metod numerycznego rozwiązywania zadań optymalizacji. Szczególnie dużo uwagi poświęca się zadaniom programowania liniowego i kwadratowego. Celem dodatkowym jest zapoznanie studentów z pewnymi rzeczywistymi zastosowaniami metod optymalizacyjnych, formułowaniem modeli optymalizacyjnych oraz różnymi problemami, z którymi mogą się zetknąć w trakcie ich rozwiązywania, jak również praktycznym wykorzystaniem istniejących pakietów optymalizacyjnych.
Pierwszy wykład jest zwykle poświęcony omówieniu przykładowych zastosowań (...)

Pełny opis:

Podstawowym celem wykładu jest zapoznanie studentów z pewnymi pakietami modelowania i rozwiązywania zadań optymalizacyjnych (AMPL, LP_SOLVE, MATLAB) oraz z pojęciem optimum, warunkami koniecznymi i dostatecznymi optymalności dla zadań optymalizacji bez ograniczeń i z ograniczeniami pozwalającymi na weryfikację poprawności uzyskiwanych z pakietów rozwiązań. Ponadto w ramach wykładu zapoznają się z elementami teorii dualności Lagrange`a oraz niektórymi z metod numerycznego rozwiązywania zadań optymalizacji. Szczególnie dużo uwagi poświęca się zadaniom programowania liniowego i kwadratowego. Celem dodatkowym jest zapoznanie studentów z pewnymi rzeczywistymi zastosowaniami metod optymalizacyjnych, formułowaniem modeli optymalizacyjnych oraz różnymi problemami, z którymi mogą się zetknąć w trakcie ich rozwiązywania, jak również praktycznym wykorzystaniem istniejących pakietów optymalizacyjnych.

Pierwszy wykład jest zwykle poświęcony omówieniu przykładowych zastosowań metod optymalizacyjnych oraz różnych typów zadań, które powstają w trakcie formułowania ich formalnego opisu. Następne wykłady i odpowiednio zajęcia laboratoryjne dzielą się na trzy mniej więcej równe objętościowo bloki tematyczne: programowanie liniowe, optymalizacja bez ograniczeń i optymalizacja nieliniowa z ograniczeniami.


Treść wykładu

  1. Zastosowania metod optymalizacyjnych, pojęcia i działy optymalizacji i programowania matematycznego.

  2. PROGRAMOWANIE LINIOWE

  3. Postać standardowa zadania programowania liniowego, zadania sprzeczne, nieograniczone, warunki optymalności, algebraiczne sformułowanie metody sympleks, zrewidowana metoda sympleks.

  4. Dwufazowa metoda sympleks, znajdowanie początkowego bazowego rozwiązania dopuszczalnego, jednofazowa metoda sympleks (metoda wielkiego "M").

  5. Dualność w zadaniach programowania liniowego.

  6. Dualna metoda sympleks, informacja o algorytmach wielomianowych do rozwiązywania zadań programowania liniowego, idea metody Karmarkara.

  7. OPTYMALIZACJA NIELINIOWA BEZ OGRANICZEŃ


  8. Pojęcie optimum, warunki konieczne i dostateczne optymalności pierwszego i drugiego rzędu dla różniczkowalnych zadań optymalizacji bez ograniczeń, kryteria weryfikacji warunków optymalności, własności zadań optymalizacji wypukłej.

  9. Gradientowe metody rozwiązywania zadań bez ograniczeń, model liniowy i metoda najszybszego spadku, modele kwadratowe i metoda Newtona, zbieżność drugiego rzędu, metody quasinewtonowskie, zbieżność superliniowa.

  10. Metody jednostajnych kierunków poprawy, testy stopu w minimalizacji kierunkowej - testy Goldsteina i reguła Armijo, gradientowe metody minimalizacji kierunkowej.

  11. Bezgradientowe metody minimizacji kierunkowej, metoda sympleks Neldera-Meada jako przykład metody poszukiwań prostych do znalezienia minimum funkcji wielu zmiennych.

  12. OPTYMALIZACJA NIELINIOWA Z OGRANICZENIAMI


  13. Warunki konieczne optymalności Karusha-Kuhna-Tuckera dla zadań optymalizacji z ograniczeniami nierównościowymi oraz równościowymi, warunki regularności.

  14. Warunki dostateczne optymalności dla zadań optymalizacji nieliniowej z ograniczeniami.

  15. Metody bezpośredniej i uogólnionej eliminacji do rozwiązywania zadań programowania kwadratowego z ograniczeniami równościowymi. Metoda ograniczeń aktywnych do rozwiązywania zadań programowania kwadratowego z ograniczeniami nierównościowymi.

  16. Teoria dualności Lagrange`a, pojęcie odstępu dualności, twierdzenia o słabej i silnej dualności.

  17. Zadania dualne dla różnych typów zadań programowania liniowego oraz w zadaniach programowania kwadratowego. Metody wewnętrznej (barierowej) funkcji kary.

  18. Niesympleksowe metody wielomianowe oparte na barierowej logarytmicznej funkcji kary do rozwiązywania zadań programowania liniowego.



Zakres laboratorium
Celem zajęć laboratoryjnych jest opanowanie przez studentów praktycznych umiejętności korzystania z metod optymalizacyjnych i przeprowadzania pewnych przykładowych obliczeń w środowisku MATLAB-a oraz AMPL (w ramach programowania liniowego również LP_SOLVE). Pierwsze dwa albo trzy dwugodzinne zajęcia (liczba zależy od rozkładu zajęć w danym semestrze) są poświęcone zapoznaniu studentów z pracą z MATLAB-em oraz AMPL-em. Następnie zajęcia laboratoryjne są podzielone na trzy zasadnicze bloki tematyczne, zgodne z programem wykładu: programowanie liniowe, optymalizacja nieliniowa bez ograniczeń i optymalizacja nieliniowa z ograniczeniami.

Każdy blok tematyczny składa się z trzech zasadniczych ćwiczeń - dwa z nich są realizowane w środowisku MATLAB-a, studenci mają za zadanie zastosować odpowiednie metody omawiane na wykładzie do rozwiązania prostych zadań przykładowych, trzecie zadanie polega na analizie szerszego przykładu zastosowaniowego, budowie modelu optymalizacyjnego w języku AMPL albo przy użyciu narzędzi dostępnych w środowisku MATLAB-a, rozwiązaniu go w danym środowisku i analizie uzyskanych wyników. Przykładowe tematy zadań są sformułowane poniżej:

Programowanie liniowe

  1. Rozwiązanie prostego zadania programowania liniowego przy pomocy dwufazowej tablicowej metody sympleks.

  2. Sformułowanie zadania dualnego do danego prostego zadania programowania liniowego, rozwiązanie zadania dualnego przy pomocy dwufazowej metody sympleks i określenie rozwiązania zadania prymalnego na podstawie analizy warunków komplementarności.

  3. Sformułowanie liniowego modelu optymalizacyjnego dla zadania optymalnego przydziału na zmiany pracowników obsługi tunelu pod kanałem La Manche, rozwiązanie go przy pomocy pakietu AMPL, analiza wyników.
Programowanie nieliniowe bez ograniczeń:

  1. Metody minimalizacji w kierunku.

  2. Metody gradientów sprzężonych, metoda Newtona i metody quasinewtonowskie.

  3. Sformułowanie modelu i rozwiązanie zadania ustalenia pozycji podróżnika poruszającego się po powierzchni Ziemi na podstawie sygnałów odbieranych z geostacjonarnych satelitów systemu GPS.

Programowanie nieliniowe z ograniczeniami:

  1. Rozwiązanie w środowisku MATLAB-a prostego zadania programowania kwadratowego z ograniczeniami równościowymi przy pomocy metody uogólnionej eliminacji.

  2. Rozwiązanie w środowisku MATLAB-a prostego zadania programowania kwadratowego z ograniczeniami nierównościowymi przy pomocy metody ograniczeń aktywnych.

  3. Budowa nieliniowego modelu optymalizacyjnego dla pewnego zadania mającego odniesienia do realnych zastosowań i rozwiązanie go przy pomocy pakietu AMPL lub innego swobodnie dostępnego w internecie, analiza wyników.

Literatura:

    Pozycje podstawowe:

    1. Stachurski A., A.P. Wierzbicki: Podstawy optymalizacji, Oficyna Wydawnicza PW, 1999.

    2. Brdyś J., A. Ruszczyński: Metody optymalizacji w zadaniach, WNT 1985.

    3. Findeisen W., J. Szymanowski i A. Wierzbicki: Teoria i metody optymalizacji.
    PWN 1977.
    Pozycje uzupełniające:

    1. Bazaraa M.S., Sherali H.D., C.M. Shetty: Nonlinear Programming. Theory and Algorithms. (sec. edition) John Wiley & Sons, New York 1993.

    2. Gill P., W. Murray, M. Wright: Practical Optimization. Academic Press 1981.

    3. Fletcher R.: Practical Methods of Optimization. (sec. edition) John Wiley & Sons, Chichester 1987.

    4. Bertsekas D.P.: Nonlinear Programming. Athena Scientific,Belmont, Massachusets 1995.

Metody i kryteria oceniania:

Uzyskanie powyżej połowy punktów z laboratoriów (22 z 42) oraz powyżej
połowy punktów z egzaminu (30 z 58); punkty sumują się do 100, oceny są
wystawiane zgodnie ze zwyczajową skalą:

51-60 ocena 3

61-70 ocena 3,5

71-80 ocena 4

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, 30 godzin, 60 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: Andrzej Stachurski
Prowadzący grup: (brak danych)
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
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, 30 godzin, 60 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: Andrzej Stachurski
Prowadzący grup: Andrzej Stachurski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
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, 30 godzin, 60 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: Andrzej Stachurski
Prowadzący grup: Andrzej Stachurski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
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, 30 godzin, 60 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: Andrzej Stachurski
Prowadzący grup: Andrzej Stachurski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
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, 30 godzin, 60 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: Andrzej Stachurski
Prowadzący grup: Andrzej Stachurski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
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.