Politechnika
Warszawska

Katalog
ECTS

Nazwa przedmiotu:

Podstawy optymalizacji

Koordynator przedmiotu:

dr hab. inż. Andrzej Stachurski

Status przedmiotu:

Fakultatywny ograniczonego wyboru

Poziom kształcenia:

Studia I stopnia

Program:

Informatyka

Grupa przedmiotów:

Przedmioty techniczne

Kod przedmiotu:

POPTY

Semestr nominalny:

6 / rok ak. 2018/2019

Liczba punktów ECTS:

4

Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:

120 godz. łącznie, co obejmuje: 30 godz. - uczestnictwo w wykładach, 6 godz. - praca w laboratorium, zaznajomienie z pracą z pakietami AMPL i MATLAB, 24 godz. - praca w laboratorium; obejmuje realizację krótkich zadań ocenianych bezpośrednio po zajęciach oraz częściową realizację większych zadań typu projektowego, 30 godz. - praca własna przy realizacji większych zadań projektowych, 10 godz. - praca własna: przygotowanie do zajęć laboratoryjnych, 20 godz. - praca własna studenta: przygotowanie do kolokwiów i egzaminu końcowego, (w razie potrzeby uczestnictwo w konsultacjach)..

Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:

30 godz. - uczestnictwo w wykładach, 6 godz. - praca w laboratorium, zaznajomienie z pracą z pakietami AMPL i MATLAB, 24 godz. - praca w laboratorium; obejmuje realizację krótkich zadań ocenianych bezpośrednio po zajęciach oraz częściową realizację większych zadań typu projektowego, w sumie 60 godz. co daje 2 ECTS

Język prowadzenia zajęć:

polski

Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:

6 godz. - praca w laboratorium, zaznajomienie z pracą z pakietami AMPL i MATLAB, 24 godz. - praca w laboratorium; obejmuje realizację krótkich zadań ocenianych bezpośrednio po zajęciach oraz częściową realizację większych zadań typu projektowego, 30 godz. - praca własna przy realizacji większych zadań projektowych, 10 godz. - praca własna: przygotowanie do zajęć laboratoryjnych, w sumie 70 godz. co daje ok. 2,5 ECTS

Formy zajęć i ich wymiar w semestrze:

• Wykład30h
• Ćwiczenia0h
• Laboratorium30h
• Projekt0h
• Lekcje komputerowe0h

Wymagania wstępne:

Potrzebna jest podstawowa wiedza z zakresu analizy matematycznej oraz algebry liniowej.

Limit liczby studentów:

60

Cel przedmiotu:

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.

Treści kształcenia:

Treść wykładu: 1. Zastosowania metod optymalizacyjnych, pojęcia i działy optymalizacji i programowania matematycznego. PROGRAMOWANIE LINIOWE 2. Postać standardowa zadania programowania liniowego, zadania sprzeczne, nieograniczone, warunki optymalności, algebraiczne, sformułowanie metody sympleks, zrewidowana metoda sympleks. 3. Dwufazowa metoda sympleks, znajdowanie początkowego bazowego rozwiązania dopuszczalnego, jednofazowa metoda sympleks (metoda wielkiego "M"). 4. Dualność w zadaniach programowania liniowego. 5. Dualna metoda sympleks, informacja o algorytmach wielomianowych do rozwiązywania zadań programowania liniowego, idea metody Karmarkara. OPTYMALIZACJA NIELINIOWA BEZ OGRANICZEŃ 6. 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. 7. 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ść Q-superliniowa. 8. Metody jednostajnych kierunków poprawy, testy stopu w minimalizacji kierunkowej - testy Goldsteina, reguła Armijo, warunki Wolfe’a, gradientowe metody minimalizacji kierunkowej. 9. Bezgradientowe metody minimizacji kierunkowej, metoda sympleks Neldera-Meada jako przykład metody poszukiwań prostych do znalezienia minimum funkcji wielu zmiennych. OPTYMALIZACJA NIELINIOWA Z OGRANICZENIAMI 10. Warunki konieczne optymalności I rzędu (Karusha-Kuhna-Tuckera) i II rzędu dla zadań optymalizacji z ograniczeniami nierównościowymi oraz równościowymi, warunki regularności. Warunki dostateczne optymalności dla zadań optymalizacji nieliniowej z ograniczeniami. 11. Teoria dualności Lagrange'a, pojęcie odstępu dualności, twierdzenia o słabej i silnej dualności. Zadania dualne dla różnych typów zadań programowania liniowego oraz w zadaniach programowania kwadratowego 12. 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. 13.. Metody zewnętrznej funkcji kary i wewnętrznej (barierowej) funkcji kary. 14. Metody przesuwanej funkcji kary (metoda rozszerzonej funkcji Lagrange’a), dokładne funkcje kary. 15. 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 Rozwiązanie prostego zadania programowania liniowego przy pomocy dwufazowej tablicowej metody sympleks. 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. 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ń: Metody minimalizacji w kierunku. Metody gradientów sprzężonych, metoda Newtona i metody quasinewtonowskie. 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: Rozwiązanie w środowisku MATLAB-a prostego zadania programowania kwadratowego z ograniczeniami równościowymi przy pomocy metody uogólnionej eliminacji. Rozwiązanie w środowisku MATLAB-a prostego zadania programowania kwadratowego z ograniczeniami nierównościowymi przy pomocy metody ograniczeń aktywnych. 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.

Metody oceny:

Stosowany jest system punktowy: - punkty za wykonanie zadań laboratoryjnych i przygotowanie sprawozdań z ich realizacji (punkty są równo rozdzielone pomiędzy trzy bloki tematyczne: programowanie liniowe, optymalizacja nieliniowa bez ograniczeń, optymalizacja nieliniowa z ograniczeniami, - punkty za egzamin

Egzamin:

tak

Literatura:

Pozycje podstawowe: 1. Stachurski A.: Wprowadzenie do optymalizacji. Oficyna Wydawnicza PW, 2009. 2. Stachurski A., A.P. Wierzbicki: Podstawy optymalizacji, Oficyna Wydawnicza PW, 1999. 3. Brdyś J., A. Ruszczyński: Metody optymalizacji w zadaniach, WNT 1985. 4. Findeisen W., J. Szymanowski i A. Wierzbicki: Teoria i metody optymalizacji. PWN 1977. Pozycje uzupełniające: 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. 5. Ruszczyński A.: Nonlinear Optimization. Princeton University Press, 2006. 6. Nocedal J., Wright S.J.:Numerical Optimization. Springer Verlag, Berlin, (first ed. 2000), sec. ed. 2006. 7. Bonans, J.F., Gilbert J.C., Lemarechal C., C.A. Sagastizabal: Numerical Optimization: Theoretical and Practical Aspects. Springer Verlag, Berlin, 2006.

Witryna www przedmiotu:

https://usosweb.usos.pw.edu.pl/kontroler.php?_action=katalog2/przedmioty/pokazPrzedmiot&prz_kod=103C-INSID-ISP-POPTY

Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka W01

Zna metody sprowadzania zadania programowania liniowego do postaci standardowej oraz metodę sympleks do rozwiązywania zadania w postaci standardowej
Weryfikacja: Egzamin
Powiązane charakterystyki kierunkowe: K_W09, K_W11
Powiązane charakterystyki obszarowe: I.P6S_WG

Charakterystyka W02

Zna teoriię dualności Lagrange’a dla zadań programowania liniowego oraz ogólnych zadań optymalizacji nieliniowej z ograniczeniami
Weryfikacja: Egzamin
Powiązane charakterystyki kierunkowe: K_W09, K_W11
Powiązane charakterystyki obszarowe: I.P6S_WG

Charakterystyka W03

Zna warunki konieczne i dostateczne optymalności dla różniczkowalnych zadań optymalizacji nieliniowej bez ograniczeń
Weryfikacja: Egzamin
Powiązane charakterystyki kierunkowe: K_W09, K_W11
Powiązane charakterystyki obszarowe: I.P6S_WG

Charakterystyka W04

Zna postawowe metody gradientowe i bezgradientowe poszukiwania minimum bez ograniczeń
Weryfikacja: Egzamin
Powiązane charakterystyki kierunkowe: K_W09, K_W11
Powiązane charakterystyki obszarowe: I.P6S_WG

Charakterystyka W05

Zna warunki konieczne idstateczne optymalności dla regularnych, różniczkowalnych zadań optymalizacji z ogranizceniami
Weryfikacja: Egzamin
Powiązane charakterystyki kierunkowe: K_W09, K_W11
Powiązane charakterystyki obszarowe: I.P6S_WG

Charakterystyka W06

Zna metody ograniczeń aktywnych oraz funkcji kary do rozwiązywania zadań optymalizacji nieliniowej z ograniczeniami
Weryfikacja: Egzamin
Powiązane charakterystyki kierunkowe: K_W09, K_W11
Powiązane charakterystyki obszarowe: I.P6S_WG

Profil ogólnoakademicki - umiejętności

Charakterystyka U01

Potrafi sprowadzić zadanie programowania liniowego do postaci standardowej i rozwiiązać je za pomocą metody sympleks
Weryfikacja: Egzamin/Sprawozdanie z zadania laboratoryjnego
Powiązane charakterystyki kierunkowe: K_U07, K_U25
Powiązane charakterystyki obszarowe: I.P6S_UK, I.P6S_UW, III.P6S_UW.2.o

Charakterystyka U02

Umie znaleźć minimum/maksimum funkcji nieliniowej metodami gradientowymi albo bezgradientowymi
Weryfikacja: Egzamin/Sprawozdanie z zadania laboratoryjnego
Powiązane charakterystyki kierunkowe: K_U07, K_U25
Powiązane charakterystyki obszarowe: I.P6S_UK, I.P6S_UW, III.P6S_UW.2.o

Charakterystyka U03

Potrafi sprawdzić, czy dany punkt jest rozwiązaniem różniczkowalnego zadania optymalizacji bez ograniczeń
Weryfikacja: Egzamin/Sprawozdanie z zadania laboratoryjnego
Powiązane charakterystyki kierunkowe: K_U07, K_U25
Powiązane charakterystyki obszarowe: I.P6S_UK, I.P6S_UW, III.P6S_UW.2.o

Charakterystyka U04

Potrafi sformułować dualne zadanie Lagrange’a do danego zadania programowania liniowego albo kwadratowego
Weryfikacja: Egzamin
Powiązane charakterystyki kierunkowe: K_U07, K_U25
Powiązane charakterystyki obszarowe: I.P6S_UK, I.P6S_UW, III.P6S_UW.2.o

Charakterystyka U05

Potrafi znaleźć rozwiązanie zadania z ograniczeniami za pomocą metod ograniczeń aktywnych oraz metod funkcji kary
Weryfikacja: Egzamin/Sprawozdanie z zadania laboratoryjnego
Powiązane charakterystyki kierunkowe: K_U07, K_U25
Powiązane charakterystyki obszarowe: I.P6S_UK, I.P6S_UW, III.P6S_UW.2.o

Charakterystyka U06

Potrafi sprawdzić, czy dany punkt jest rozwiązaniem regularnego, różniczkowalnego zadania optymalizacji z ograniczeniami
Weryfikacja: Egzamin/Sprawozdanie z zadania laboratoryjnego
Powiązane charakterystyki kierunkowe: K_U07, K_U25
Powiązane charakterystyki obszarowe: I.P6S_UK, I.P6S_UW, III.P6S_UW.2.o

Charakterystyka U07

Potrafi formułować model optymalizacyjny (liniowy albo nieliniowy) opisujący pewne typowe problemy praktyczne, zapisać model matematyczny w języku pakietu AMPL albo w języku pakietu MATLAB
Weryfikacja: Sprawozdanie z zadania laboratoryjnego
Powiązane charakterystyki kierunkowe: K_UK04
Powiązane charakterystyki obszarowe: I.P6S_UO

Charakterystyka U08

Potrafi znaleźć rozwiązanie za pomocą narzędzi ze skrzynki narzędziowej MATLAB-a, albo odpowiedniego, dołączonego do AMPL solwera (MINOS lub CPLEX) albo programu LP_SOLVE
Weryfikacja: Sprawozdanie z zadania laboratoryjnego
Powiązane charakterystyki kierunkowe: K_UK04
Powiązane charakterystyki obszarowe: I.P6S_UO