Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Programowanie Liniowe
Tok studiów:
2019/2020
Kod:
AMAT-2-209-MU-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Matematyka ubezpieczeniowa
Kierunek:
Matematyka
Semestr:
2
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Stacjonarne
Prowadzący moduł:
dr Zioło Irmina (zioloirm@wms.mat.agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

Algorytmy programowania liniowego. Zastosowania.

Opis efektów uczenia się dla modułu zajęć
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Powiązania z KEU Sposób weryfikacji i oceny efektów uczenia się osiągniętych przez studenta w ramach poszczególnych form zajęć i dla całego modułu zajęć
Wiedza: zna i rozumie
M_W001 Zna interpretację geometyczną układów równań i nierówności liniowych i własności zbiorów opisywane takimi układami równań i nierówności. MAT2A_W03, MAT2A_W08, MAT2A_W07 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_W002 Zna algorytm sympleks, jego wlasności i zastosowania. MAT2A_W11, MAT2A_W08 Aktywność na zajęciach,
Egzamin,
Kolokwium
M_W003 Zna przykłady modeli matematycznych prowadzących do zadań programowania liniowego. MAT2A_W08 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Umiejętności: potrafi
M_U001 Zna i umie stosować metody sieciowe. MAT2A_U20, MAT2A_U19, MAT2A_U21, MAT2A_U17 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Liczba godzin zajęć w ramach poszczególnych form zajęć:
SUMA (godz.)
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
60 30 30 0 0 0 0 0 0 0 0 0
Matryca kierunkowych efektów uczenia się w odniesieniu do form zajęć i sposobu zaliczenia, które pozwalają na ich uzyskanie
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Forma zajęć dydaktycznych
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Wiedza
M_W001 Zna interpretację geometyczną układów równań i nierówności liniowych i własności zbiorów opisywane takimi układami równań i nierówności. + + - - - - - - - - -
M_W002 Zna algorytm sympleks, jego wlasności i zastosowania. + + - - - - - - - - -
M_W003 Zna przykłady modeli matematycznych prowadzących do zadań programowania liniowego. + + - - - - - - - - -
Umiejętności
M_U001 Zna i umie stosować metody sieciowe. + + - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 152 godz
Punkty ECTS za moduł 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 godz
Przygotowanie do zajęć 40 godz
Samodzielne studiowanie tematyki zajęć 50 godz
Egzamin lub kolokwium zaliczeniowe 2 godz
Szczegółowe treści kształcenia w ramach poszczególnych form zajęć (szczegółowy program wykładów i pozostałych zajęć)
Wykład (30h):
  1. Wiadomości wstępne.

    Modele matematyczne prowadzące do zadań programowania liniowego. Przykłady. Postaci główna, standardowa i kanoniczna problemu programowania liniowego (PPL).

  2. Program:

    1. Problem programowania liniowego (6+3 godz.).
    Programowanie matematyczne i programowanie liniowe. Przykłady zadań modelowanych w języku programowania liniowego. Algorytm sympleks. Inicjalizacja i cykliczność (reguła Blanda). Złożoność obliczeniowa (przykład Klee-Minty’ego).

    2. Dualizm (4+2).
    Problem dualny. Zasada dualności. Interpretacja ekonomiczna.

    3. Zredukowana metoda sympleksowa (4+2).
    Programowanie liniowe całkowite.

    4. Interpretacje i zastosowania (6+3).
    Interpretacja geometryczna w przypadkach 1-, 2- i 3-wymiarowych. Powłoki wypukłe. Układy równań i nierówności liniowych. Metoda Fouriera-Motzkina. Wielościany i półprzestrzenie. Twierdzenie Caratheodory’ego.

    5. Metody sieciowe (10+5).
    Przepływy w sieciach – twierdzenie o maksymalnym przepływie i minimalnym przekroju. Algorytm Forda-Fulkersona . Zbieżność algorytmu FF. Poprawka Edmondsa-Karpa. Przepływ o minimalnym koszcie – metoda sympleksu sieciowego. Zastosowania: twierdzenia Halla i Mengera.

Ćwiczenia audytoryjne (30h):

Program ćwiczeń zgodny z programem wykładów.

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Treści prezentowane na wykładzie są przekazywane w formie prezentacji multimedialnej w połączeniu z klasycznym wykładem tablicowym wzbogaconymi o pokazy odnoszące się do prezentowanych zagadnień.
  • Ćwiczenia audytoryjne: Podczas zajęć audytoryjnych studenci na tablicy rozwiązują zadane wcześniej problemy. Prowadzący na bieżąco dokonuje stosowanych wyjaśnień i moderuje dyskusję z grupą nad danym problemem.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Dwa terminy zaliczeń poprawkowych są skorelowane czasowo z egzaminami poprawkowymi.Warunkiem koniecznym dopuszczenia do egzaminu jest posiadanie oceny pozytywnej z ćwiczeń.

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci winni na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
  • Ćwiczenia audytoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci przystępując do ćwiczeń są zobowiązani do przygotowania się w zakresie wskazanym każdorazowo przez prowadzącego (np. w formie zestawów zadań). Ocena pracy studenta może bazować na wypowiedziach ustnych lub pisemnych w formie kolokwium, co zgodnie z regulaminem studiów AGH przekłada się na ocenę końcową z tej formy zajęć.
Sposób obliczania oceny końcowej:
  1. Forma zaliczenia przedmiotu – zaliczenie ćwiczeń na podstawie oceny kolokwiów pisemnych i aktywności studenta na zajęciach;
  2. Egzamin pisemny
  3. Zasada wystawiania oceny końcowej – Średnia ocena z egzaminu i zaliczenia.
Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Według uzgodnienia z prowadzącym zajęcia.

Wymagania wstępne i dodatkowe, z uwzględnieniem sekwencyjności modułów :

brak

Zalecana literatura i pomoce naukowe:

1. V. Chvatal, Linear Programming, W.H. Freeman and Comp., NY 1984.

2. L.R. Ford Jr. i D.R. Fulkerson, Przepływy w sieciach, PWN Warszawa 1969.

3. A. Schrijvers, Theory of Linear and Integer Programming, Willey 1998.

4. M.M. Sysło, N. Deo i J.S. Kowalik, Algorytmy optymalizacji dyskretnej, PWN, Warszawa 1999.

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. Steiner almost self-complementary graphs and halving near-Steiner triple systems / Mariusz MESZKA, Aleksander Rosa, Irmina ZIOŁO // Discrete Mathematics ; ISSN 0012-365X. — 2009 vol. 309 iss. 18, s. 5650–5654. — Bibliogr. s. 5654, Abstr.. — tekst: http://www-1sciencedirect-1com-1sciencecitationindex.wbg2.bg.agh.edu.pl/science/article/pii/S0012365X08002197/pdfft?md5=4985f9c4ace763bfa1e52603874fefed&pid=1-s2.0-S0012365X08002197-main.pdf

2. On some families of arbitrarily vertex decomposable spiders / Tomasz Juszczyk, Irmina A. ZIOŁO // Opuscula Mathematica ; ISSN 1232-9274. — Tytuł poprz.: Scientific Bulletins of Stanisław Staszic Academy of Mining and Metallurgy. Opuscula Mathematica. — 2010 vol. 30 no. 2, s. 147 – 154. — Bibliogr. s. 153, Abstr.. — tekst: http://journals.bg.agh.edu.pl/OPUSCULA/30-2/30-2-03.pdf

3.. A. P. Wojda; Elementy programowania liniowego i metod sieciowych, Wydawnictwa AGH, 2015.

4 . Gosselin, Shonda; Szymański, Artur; Wojda, Adam Pawel
Cyclic partitions of complete nonuniform hypergraphs and complete multipartite hypergraphs;
Discrete Math. Theor. Comput. Sci. 15, No. 2, 215-222, electronic only (2013).

Informacje dodatkowe:

Brak