Programowanie liniowe 1000-MS1-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]

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.

Koordynatorzy przedmiotu

Piotr Malicki

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

Nie dotyczy.

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.

Uwagi

W cyklu 2022/23Z:

Wykład oraz ćwiczenia prowadzone w sposób stacjonarny. Pisemny sprawdzian z ćwiczeń oraz egzamin pisemny z wykładu przeprowadzone zostaną w sposób tradycyjny.

W cyklu 2023/24Z:

Wykład oraz ćwiczenia prowadzone w sposób stacjonarny. Pisemny sprawdzian z ćwiczeń oraz egzamin pisemny z wykładu przeprowadzone zostaną w sposób tradycyjny.

Więcej informacji

Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb:

Strona przedmiotu 1000-MS1-ProgLin w USOSweb