Optymalizacja liniowa 1000-135OPL
Zadanie programowania liniowego. Przykłady praktycznych modeli optymalizacji liniowej. Zadanie standardowe, zbiór dopuszczalny, rozwiązania optymalne. (1 wykład)
Podstawowe wiadomości o zbiorach wypukłych. Geometria zbioru dopuszczalnego, wielościany wypukłe. Punkty, kierunki i promienie ekstremalne, procedury ich generowania. Uwypuklenie zbioru wierzchołków
i promieni ekstremalnych. Twierdzenie Caratheodory'ego. Lemat Farkasa. (3 wykłady)
Zadanie kanoniczne, tablica sympleks, bazowe rozwiązanie dopuszczalne, dopuszczalność i optymalność tablicy. Pierwotna metoda sympleks. Różne wersje dwufazowej metody sympleks. Metoda dużego M. (3 wykłady)
Zadanie dualne. Twierdzenia o dualności. Warunki równowagi. Interpretacja ekonomiczna dualności, ceny dualne. Wrażliwość zadania. (2 wykłady)
Dualna metoda sympleks, jej ograniczenia i zastosowania. (1 wykład)
Grafy i przepływy w sieciach. (2 wykłady)
Zagadnienie transportu. (1 wykład)
Metoda podziału i ograniczeń. Zagadnienia całkowitoliczbowe. (2 wykłady)
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
Student
1. zna podstawowe pojęcia przestrzeni metrycznej Euklidesowej, przestrzeni liniowej i afinicznej;
2. zna pojęcia półprzestrzeni, wielościanu i wielościanu uogólnionego. Potrafi udowodnić, że są to podzbiory wypukłe i domknięte;
3. umie budować modele matematyczne typowych problemów optymalizacji liniowych i zapisywać je jako badanie ekstremów funkcji liniowych na wielościanach uogólnionych;
3. umie posługiwać się algorytmami metody sympleks: prostym, dwufazowym i dualnym. Wie jakie mogą być wyniki i kiedy jaki stosować;
4. zna teorię dualności: Potrafi opisywać wielościany uogólnione zarówno jako przecięcia półprzestrzeni jak i uwypuklenie punktów i prostych. Potrafi zadaniu programowania liniowego przyporządkować zadanie dualne i opisywać punkty optymalne jednego z zadań, znając rozwiązanie drugiego;
5. potrafi rozwiązywać zadania programowania liniowego w liczbach całkowitych. Zna metodę odcięć, w szczególności odcięcie Gomorego;
6. zna metodę rozgałęzień i odcięć ( B&B ). Umie stosować podziały Dakina;
7. zna kilka specyficznych algorytmów jak algorytm obliczania optymalnego przepływu w sieciach, zagadnienie transportowe czy problem przyporządkowania.
Kryteria oceniania
Na podstawie wykonania i prezentacji dwóch projektów, zadań domowych i egzaminu ustnego.
Literatura
M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear Programming and Network Flows. John Wiley and Sons, 1990.
S. Gass, Programowanie liniowe. PWN, Warszawa 1980.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: