Politechnika Warszawska - Centralny System Uwierzytelniania
Strona główna

Podstawy optymalizacji

Informacje ogólne

Kod przedmiotu: 103B-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
Punkty ECTS i inne: (brak) 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.

zobacz reguły punktacji
Język prowadzenia: polski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

POPTY

Numer wersji:

2

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

81-90 ocena 4,5

91-100 ocena 5

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
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 7.0.0.0-7 (2024-03-18)