Module also offered within study programmes:
General information:
Name:
Linear Programming
Course of study:
2019/2020
Code:
AMAT-2-209-MU-s
Faculty of:
Applied Mathematics
Study level:
Second-cycle studies
Specialty:
Insurance Mathematics
Field of study:
Mathematics
Semester:
2
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Responsible teacher:
dr Zioło Irmina (zioloirm@wms.mat.agh.edu.pl)
Module summary

Algorytmy programowania liniowego. Zastosowania.

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Skills: he can
M_U001 Zna i umie stosować metody sieciowe. MAT2A_U20, MAT2A_U19, MAT2A_U21, MAT2A_U17 Activity during classes,
Examination,
Test,
Oral answer
Knowledge: he knows and understands
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 Activity during classes,
Examination,
Test,
Oral answer
M_W002 Zna algorytm sympleks, jego wlasności i zastosowania. MAT2A_W11, MAT2A_W08 Activity during classes,
Examination,
Test
M_W003 Zna przykłady modeli matematycznych prowadzących do zadań programowania liniowego. MAT2A_W08 Activity during classes,
Examination,
Test,
Oral answer
Number of hours for each form of classes:
Sum (hours)
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
60 30 30 0 0 0 0 0 0 0 0 0
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Skills
M_U001 Zna i umie stosować metody sieciowe. + + - - - - - - - - -
Knowledge
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. + + - - - - - - - - -
Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 152 h
Module ECTS credits 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 h
Preparation for classes 40 h
Realization of independently performed tasks 50 h
Examination or Final test 2 h
Module content
Lectures (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.

Auditorium classes (30h):

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

Additional information
Teaching methods and techniques:
  • Lectures: 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ń.
  • Auditorium classes: 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ń.

Participation rules in classes:
  • Lectures:
    – Attendance is mandatory: Yes
    – Participation rules in classes: 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.
  • Auditorium classes:
    – Attendance is mandatory: Yes
    – Participation rules in classes: 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ęć.
Method of calculating the final grade:
  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.

Prerequisites and additional requirements:

brak

Recommended literature and teaching resources:

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.

Scientific publications of module course instructors related to the topic of the module:

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

Additional information:

None