PřF:M4110 Linear programming - Course Information
M4110 Linear programming
Faculty of ScienceSpring 2014
- Extent and Intensity
- 2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).
- Teacher(s)
- doc. Mgr. Michal Kunc, Ph.D. (lecturer)
- Guaranteed by
- doc. RNDr. Jiří Kaďourek, CSc.
Department of Mathematics and Statistics – Departments – Faculty of Science
Contact Person: doc. Mgr. Michal Kunc, Ph.D.
Supplier department: Department of Mathematics and Statistics – Departments – Faculty of Science - Timetable
- Thu 16:00–17:50 M2,01021
- Timetable of Seminar Groups:
- Prerequisites
- M2110 Linear Algebra II || (( M1110 Linear Algebra I || M1115 Linear Algebra I ) && M3521 Geometry 2 ) || PROGRAM(N-MA) || PROGRAM(N-AM) || PROGRAM(N-SS) || ( FI:MA004 Linear Algebra and Geometry II ) || SOUHLAS
Knowledge of affine geometry within the scope of the course M2110 Linear Algebra and Geometry II. - Course Enrolment Limitations
- The course is also offered to the students of the fields other than those the course is directly associated with.
- fields of study / plans the course is directly associated with
- there are 9 fields of study the course is directly associated with, display
- Course objectives
- Linear programming represents one of the basic optimization methods
having a wide range of applications. This course starts with the
theoretical foundations of this subject consisting of the study of
systems of linear inequalities and leading further to the Duality
theorem of linear programming. Next, the basic technique of linear
programming, that is, the simplex method is explained, and some of its
variants are discussed.
After passing the course the student should be able to: apply theoretical results about systems of linear inequalities and linear programming problems; understand the algebraic derivation of the simplex method and the dual simplex method relying on the underlying geometric view; use computational techniques based on the simplex method and the dual simplex method. - Syllabus
- Linear programming problems.
- Systems of linear inequalities - Farkas' lemma.
- The Duality theorem of linear programming.
- Convex cones and polyhedra.
- The Decomposition theorem for polyhedra.
- The structure of polyhedra - faces, facets and vertices.
- The geometric description of the simplex method.
- The simplex method in tableau form.
- The Bland's rule.
- The two-phase method.
- The geometric description of the dual simplex method.
- The dual simplex method in tableau form.
- The transportation problem.
- Solving the transportation problem by an adaptation of the simplex method.
- Literature
- PLESNÍK, Ján, Jitka DUPAČOVÁ and Milan VLACH. Lineárne programovanie. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1990, 314 s. ISBN 80-05-00679-9. info
- SCHRIJVER, Alexander. Theory of Linear and Integer Programming. Chichester: John Wiley & Sons, 1986, 471 pp. ISBN 0 471 90854 1. info
- Teaching methods
- lectures, seminars
- Assessment methods
- Written examination: pass mark 50%.
- Language of instruction
- Czech
- Follow-Up Courses
- Further comments (probably available only in Czech)
- Study Materials
The course is taught annually.
- Enrolment Statistics (Spring 2014, recent)
- Permalink: https://is.muni.cz/course/sci/spring2014/M4110