University of Warsaw - Central Authentication System

Linear optimization

General data

Course ID:	1000-135OPL
Erasmus code / ISCED:	11.912 The subject classification code consists of three to five digits, where the first three represent the classification of the discipline according to the Discipline code list applicable to the Socrates/Erasmus program, the fourth (usually 0) - possible further specification of discipline information, the fifth - the degree of subject determined based on the year of study for which the subject is intended. / (0619) Information and Communication Technologies (ICTs), not elsewhere classified The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
Course title:	Linear optimization
Name in Polish:	Optymalizacja liniowa
Organizational unit:	Faculty of Mathematics, Informatics, and Mechanics
Course groups:	Elective courses for 1st degree studies in mathematics
ECTS credit allocation (and other scores):	6.00 Basic information on ECTS credits allocation principles: the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS; the student’s weekly hourly workload is 45 h; 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes; weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS; work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load. view allocation of credits
Language:	Polish
Type of course:	elective courses
Short description:	We will focus on solving linear programming problems mainly by applying various simplex methods . Special attention will be given to duality in linear programming and to geometric interpretations.
Full description:	inear programming problems. Some examples. The simplex tableau . Basic feasible solutions . Optimal basic solutions. The simplex methods : the simplex algorithm , the two phase simplex algorithm , the big-M method, the dual simplex algorithm . Geometry of linear programming . Duality in linear programming. The duality theorems. Transportation problems. Depending on time, we will also look at some related problems/techniques: network flows, integer programming
Bibliography:	M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear Programming and Network Flows. John Wiley and Sons, 1990.
Learning outcomes:	(in Polish) Student 1. zna podstawowe pojęcia przestrzeni metrycznej Euklidesowej, przestrzeni liniowej i afinicznej; 2. zna pojęcia półprzestrzeni, wielościanu i wielościanu uogólnionego. Potrafi udowodnić, że są to podzbiory wypukłe i domknięte; 3. umie budować modele matematyczne typowych problemów optymalizacji liniowych i zapisywać je jako badanie ekstremów funkcji liniowych na wielościanach uogólnionych; 3. umie posługiwać się algorytmami metody sympleks: prostym, dwufazowym i dualnym. Wie jakie mogą być wyniki i kiedy jaki stosować; 4. zna teorię dualności: Potrafi opisywać wielościany uogólnione zarówno jako przecięcia półprzestrzeni jak i uwypuklenie punktów i prostych. Potrafi zadaniu programowania liniowego przyporządkować zadanie dualne i opisywać punkty optymalne jednego z zadań, znając rozwiązanie drugiego; 5. potrafi rozwiązywać zadania programowania liniowego w liczbach całkowitych. Zna metodę odcięć, w szczególności odcięcie Gomorego; 6. zna metodę rozgałęzień i odcięć ( B&B ). Umie stosować podziały Dakina; 7. zna kilka specyficznych algorytmów jak algorytm obliczania optymalnego przepływu w sieciach, zagadnienie transportowe czy problem przyporządkowania.
Assessment methods and assessment criteria:	(in Polish) Na podstawie wykonania i prezentacji dwóch projektów, zadań domowych i egzaminu ustnego.

Classes in period "Summer semester 2024/25" (past)

Time span:	2025-02-17 - 2025-06-08	Selected timetable range: weekly course term Go to timetable MO TU W WYK CW TH FR
Type of class:	Classes, 30 hours more information Lecture, 30 hours more information
Coordinators:	Andrzej Nagórko
Group instructors:	Tomasz Gogacz, Andrzej Nagórko
Students list:	(inaccessible to you)
Credit:	Examination

Classes in period "Summer semester 2025/26" (future)

Time span:	2026-02-16 - 2026-06-07	Selected timetable range: weekly course term Go to timetable
Type of class:	Classes, 30 hours more information Lecture, 30 hours more information
Coordinators:	Andrzej Nagórko
Group instructors:	Tomasz Gogacz, Andrzej Nagórko
Students list:	(inaccessible to you)
Credit:	Course - Examination Lecture - Examination

Course descriptions are protected by copyright.
Copyright by University of Warsaw.