Programowanie liniowe
1000-M1-ProgLin
Zbiory wypukłe.
Topologiczne własności zbiorów wypukłych.
Twierdzenia o rozdzielaniu.
Punkty ekstremalne oraz kierunkowe wektory ekstremalne zbioru wypukłego:
- charakteryzacja punktów ekstremalnych,
- charakteryzacja kierunków ekstremalnych,
- twierdzenie o reprezentacji.
Algorytm sympleks.
Problem znalezienia pierwszego punktu ekstremalnego.
Dualna metoda programowania liniowego (twierdzenie o różnicach dopełniających, algorytm dualny sympleks).
Leksykograficzna postać dualnej metody sympleks.
Całkowitoliczbowy algorytm dualny Gomory'ego.
Zagadnienie maksymalnego przepływu (twierdzenie Forda-Fulkersona).
Redukcja ograniczeń zagadnienia całkowitoliczbowego.
Wielościany całkowite, baza Hilberta oraz twierdzenie Doignona.
Odległości rozwiązań optymalnych oraz skończony zbiór testów dla zagadnienia całkowitoliczbowego programowania liniowego.
Całkowity nakład pracy studenta
Godziny kontaktowe:
30 godz. - wykład
4 godz. - egzamin
30 godz. - ćwiczenia
15 godz. laboratorium
Praca własna:
60 godz. praca własna - bieżące przygotowanie do zajęć, studiowanie literatury,
20 godz. praca własna - przygotowanie do egzaminu.
RAZEM: 159 godz.
6 pkt. ECTS
Efekty uczenia się - wiedza
Po ukończeniu kursu student:
W1: zna podstawowe własności zbiorów wypukłych w przestrzeniach euklidesowych [K_W02]
W2: potrafi sformułować zagadnienie programowania liniowego [K_W02]
W3: zna algorytm sympleks [K_W03, K_W04]
W4: potrafi sformułować zagadnienie dualne programowania liniowego [K_W02]
W5: zna dualny algorytm sympleks [K_W03, K_W04]
W6: potrafi sformułować zagadnienie całkowitoliczbowego programowania liniowego [K_W02]
W7: zna całkowitoliczbowy algorytm dualny Gomory’ego [K_W03, K_W04]
W8: potrafi sformułować zagadnienie maksymalnego przepływu [K_W02]
W9: zna algorytm pozwalający na znalezienie maksymalnego przepływu w grafach skierowanych [K_W03, K_W04]
Efekty uczenia się - umiejętności
Po ukończeniu kursu student:
U1: stosuje algorytm sympleks do rozwiązywania konkretnych problemów [K_U02, K_U03, K_U13]
U2: stosuje dualny algorytm sympleks do rozwiązywania konkretnych problemów [K_U02, K_U03, K_U13]
U3: stosuje całkowitoliczbowy algorytm dualny Gomory’ego do rozwiązywania konkretnych problemów [K_U02, K_U03, K_U13]
U4: stosuje algorytm pozwalający na znalezienie maksymalnego przepływu w grafach skierowanych [K_U02, K_U03, K_U13]
Efekty uczenia się - kompetencje społeczne
Po ukończeniu kursu student:
K1: potrafi przekazać innym swoją wiedzę i przemyślenia w zrozumiały sposób [K_K03]
K2: właściwie rozumie sformułowania pytań i problemów [K_K03]
K3: poprawnie posługuje się terminologią fachową [K_K03]
K4: potrafi samodzielnie rozwiązać prosty problem związany z optymalizacją liniową [K_K02]
Koordynatorzy przedmiotu
Metody dydaktyczne
Wykład informacyjny (konwencjonalny).
Ćwiczenia praktyczne umożliwiające kształtowanie umiejętności zastosowania przyswojonej wiedzy w praktyce, obejmowały będą rozwiązywanie zadań. Laboratoria umożliwiać będą nabycie umiejętności korzystania z pakietów matematycznych pozwalających na rozwiązywanie praktycznych problemów związanych z programowaniem liniowym.
Metody dydaktyczne podające
- wykład informacyjny (konwencjonalny)
Metody dydaktyczne poszukujące
- ćwiczeniowa
Wymagania wstępne
Algebra liniowa. Geometria analityczna.
Kryteria oceniania
Egzamin pisemny – W3, W5, W7, W9, U1, U2, U3, U4
Kolokwium – U1, U2, U3, U4
Prezentacje K1, K2, K3
Aktywność – K1, K3
Praktyki zawodowe
Literatura
Literatura podstawowa:
1. M. S. Bazaraa, C. M. Shetty, "Nonlinear Programming Theory and Algorithms", 1979 (istnieje tłumaczenie rosyjskie 1982).
2. N. Deo, J. S. Kowalik, M. M. Sysło, ,,Algorytmy optymalizacji dyskretnej", PWN, Warszawa 1995.
3. P. Malicki, ,,Programowanie liniowe i całkowitoliczbowe", UMK Toruń 2012.
4. A. Schrijver, "Theory of linear and integer programming", John Wiley & Sons, Chichester 2000.
Literatura uzupełniająca:
S. I. Gass, ,,Programowanie liniowe", PWN, Warszawa 1980.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i
terminach zajęć) mogą być dostępne w serwisie USOSweb: