Course: Linear Programming

« Back
Course title Linear Programming
Course code KMA/LPB
Organizational form of instruction Lecture + Exercise
Level of course Bachelor
Year of study not specified
Semester Winter
Number of ECTS credits 4
Language of instruction Czech
Status of course Compulsory-optional
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
Lecturer(s)
  • Ženčák Pavel, RNDr. Ph.D.
Course content
1. Historical overview of linear programming, general formulation of linear programming problems. 2. Graphic solution of simple problems. Application of linear programming. 3. Selected pieces of knowledge of convex analysis. 4. Basic theoretical concepts of linear programming and geometrical view to solution. 5. Fundamentals of nonlinear optimization and convex programming. 6. The duality theory in linear programming and its economic interpretation. 7. Algorithm of simplex method in standard form and spreadsheet computation. 8. Derivation of the simplex method using linear algebra and geometry, treatment for degenerate problems, computational complexity of the simplex method. 9. Derivation of the simplex method using convex programming, the revised simplex method and its comparison with the standard simplex method. 10. Dual simplex method and its application. 11. The transportation problem: Formulation of the problem, special methods for computing the initial and optimal solutions. 12. Interior points methods. Integer linear programming: Introduction to principles of basic methods (branch and bound method, cutting plane methods).

Learning activities and teaching methods
Monologic Lecture(Interpretation, Training), Demonstration, Projection (static, dynamic)
  • Attendace - 39 hours per semester
  • Homework for Teaching - 25 hours per semester
  • Preparation for the Exam - 55 hours per semester
Learning outcomes
The course introduces the theory and methods for solutin of linear programming problems.
Comprehension Understand the basic terms in optimization and the methods for solution of linear programming problems.
Prerequisites
Basic knowledge of mathematical analysis and linear algebra.
KMA/M2
----- or -----
KMA/M2N

Assessment methods and criteria
Written exam, Dialog

Colloquium: the student has to pass written tests, understand the subject and program a given algorithm.
Recommended literature
  • G.B. Dantzig. (1963). Linear programming and extensions. North Holland.
  • G.B. Dantzig. (1966). Lineárne programovanie a jeho rozvoj. SVTL Bratislava.
  • J. Nocedal, S. Wright. (1999). Numerical Optimization. Springer.
  • J.Plesník, J Dupačová, M. Vlach. (1990). Lineárne programovanie. ALFA, Bratislava.
  • J.Švrček. (1995). Lineární programování v úlohách. Vydavatelství UP Olomouc.
  • Ženčák, P. (2013). Lineární programování. Olomouc: Univerzita Palackého v Olomouci.


Study plans that include the course
Faculty Study plan (Version) Branch of study Category Recommended year of study Recommended semester