Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowaniaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Programowanie liniowe

Informacje ogólne

Kod przedmiotu: 1000-MS1-ProgLin Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji
Nazwa przedmiotu: Programowanie liniowe
Jednostka: Wydział Matematyki i Informatyki
Grupy: Matematyka stosowana, 2 rok, studia I stopnia
Punkty ECTS i inne: 6.00
Język prowadzenia: polski
Wymagania wstępne:

Algebra liniowa. Geometria analityczna.

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

Skrócony opis:

Przedmiot przeznaczony jest głównie dla studentów kierunku matematyka stosowana. Celem wykładu jest zapoznanie się z pojęciami matematycznymi oraz metodami obliczeniowymi używanymi do rozwiązywania problemów programowania liniowego. Ćwiczenia mają charakter rachunkowy. Ich zadaniem jest pomoc w zrozumieniu materiału wykładu. Laboratoria mają charakter praktyczny. Ich zadaniem jest nabycie umiejętności korzystania z pakietów matematycznych pozwalających na rozwiązywanie praktycznych problemów związanych z programowaniem liniowym. Przedmiot prowadzony w języku polskim.

Pełny opis:

  • 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.
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.

Metody i 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.

Zajęcia w cyklu "Semestr zimowy 2018/19" (zakończony)

Okres: 2018-10-01 - 2019-02-24
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Laboratorium, 15 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 50 miejsc więcej informacji
Koordynatorzy: Piotr Malicki
Prowadzący grup: Bartosz Makuracki, Piotr Malicki
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Laboratorium - Zaliczenie
Wykład - Egzamin

Zajęcia w cyklu "Semestr zimowy 2019/20" (zakończony)

Okres: 2019-10-01 - 2020-02-28
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Laboratorium, 15 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: Piotr Malicki
Prowadzący grup: Bartosz Makuracki, Piotr Malicki
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Laboratorium - Zaliczenie
Wykład - Egzamin

Zajęcia w cyklu "Semestr zimowy 2020/21" (zakończony)

Okres: 2020-10-01 - 2021-02-21
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Laboratorium, 15 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: Piotr Malicki
Prowadzący grup: Marcin Gąsiorek, Piotr Malicki
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Laboratorium - Zaliczenie
Wykład - Egzamin
Uwagi:

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

Zajęcia w cyklu "Semestr zimowy 2021/22" (jeszcze nie rozpoczęty)

Okres: 2021-10-01 - 2022-02-20
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Laboratorium, 15 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: Piotr Malicki
Prowadzący grup: Marcin Gąsiorek, Adam Hajduk, Piotr Malicki
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Laboratorium - Zaliczenie
Wykład - Egzamin
Uwagi:

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

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.