M4110 Linear programming

Faculty of Science
Spring 2010
Extent and Intensity
2/1/0. 3 credit(s) (fasci plus compl plus > 4). Type of Completion: zk (examination).
Teacher(s)
doc. RNDr. Jiří Kaďourek, CSc. (lecturer)
doc. Mgr. Michal Kunc, Ph.D. (lecturer)
Guaranteed by
doc. RNDr. Jiří Kaďourek, CSc.
Department of Mathematics and Statistics – Departments – Faculty of Science
Timetable
Tue 16:00–17:50 M1,01017
  • Timetable of Seminar Groups:
M4110/01: Tue 15:00–15:50 M1,01017, M. Kunc
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
The students in bachelor's degree programmes at the Faculty of Science must go in advance either through the subject M2110 Linear algebra and geometry II, or through any of the subjects M1110 Linear algebra and geometry I or M1115 Linear algebra and geometry I and, additionally, through the subject M3521 Geometry 2.
The students of the Faculty of Informatics must go in advance through the subject M2110 Linear algebra and geometry II or through the subject MA004 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 7 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 its variants are discussed.
After passing the course the student should be able to find one's way in the theoretical foundations of linear programming, he will be acquainted with the algebraic derivation of the simplex method and the dual simplex method relying on the underlying geometric view, and he should manage the arithmetical techniques based on these methods making it possible to solve by hands concrete small linear programming problems.
Syllabus
  • Linear programming problems.
  • Linear inequalities - the 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-phases method.
  • The revised simplex method.
  • The geometric description of the dual simplex method.
  • The dual simplex method in tableau form.
  • The treansportation 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
  • Robert Fourer, Linear Programming Frequently Asked Questions, Optim. Techn. Center of Northwestern Univ. and Argonne Nat. Lab., http://www-unix... (2000).
Teaching methods
Classic form of teaching consisting of lectures accompanied with seminars.
Assessment methods
The course is completed with written examination.
Language of instruction
Czech
Follow-Up Courses
Further comments (probably available only in Czech)
Study Materials
The course is taught annually.
The course is also listed under the following terms Spring 2008 - for the purpose of the accreditation, Spring 2011 - only for the accreditation, Spring 2000, Spring 2001, Spring 2002, Spring 2003, Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2011, Spring 2012, spring 2012 - acreditation, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, spring 2018, Spring 2019.
  • Enrolment Statistics (Spring 2010, recent)
  • Permalink: https://is.muni.cz/course/sci/spring2010/M4110