MV026 Linear Programming

Faculty of Informatics
Spring 2003
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
doc. RNDr. Jiří Kaďourek, CSc. (lecturer)
doc. Mgr. Ondřej Klíma, Ph.D. (lecturer)
Guaranteed by
doc. RNDr. Jiří Kaďourek, CSc.
Departments – Faculty of Science
Contact Person: doc. RNDr. Jiří Kaďourek, CSc.
Prerequisites
! M026 Linear Programming && ( M004 Linear Algebra and Geometry II || MA004 Linear Algebra and Geometry II || SOUHLAS)
Before enrolling this course, the students should go 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
Course objectives
Linear programming represents one of the basic optimization methods having a wide range of applications. The technique of linear programming, namely the so-called simplex method, is one of the mathematical algorithms most widely exploited on computers. 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 simplex method is explained, and some its variants are discussed.
Syllabus
  • Linear programming problems.
  • The theory of 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 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
Assessment methods (in Czech)
Předmět je ukončen písemnou zkouškou.
Language of instruction
Czech
Further comments (probably available only in Czech)
The course is taught annually.
The course is taught: every week.
The course is also listed under the following terms Spring 2004, Spring 2005.
  • Enrolment Statistics (Spring 2003, recent)
  • Permalink: https://is.muni.cz/course/fi/spring2003/MV026