Linear Programming
Code  Completion  Credits  Range 

01LIPO  Z,ZK  4  2P+2C 
 Garant předmětu:
 Lecturer:
 Tutor:
 Supervisor:
 Department of Mathematics
 Synopsis:

We study special problems about constrained extremum problems for multivariable functions (the function is linear and the constraint equations are given by linear equations and linear inequalities).
 Requirements:
 Syllabus of lectures:

Outline:Forms of the LP problem, duality. Linear equations and inequalities, convex polytope, basic feasible solution, complementary slackness. Algorithms: simplex, dual simplex, primal  dual, revised. Decomposition principle, transportation problem. Discrete LP (algorithm Gomory's). Application of LP in the theory of games  matrix games. Polynomial  time algorithms for LP (Khachian, Karmarkar).
Outline (exercises):1. Optimality test of feasible solution, identify the extreme point of the set of admissible solutions, build a dual problem. 2. Simplex method, dual simplex method, primary  dual simplex method. 3. Gomory algorithm for integer programming. 4. Applications in game theory.
 Syllabus of tutorials:
 Study Objective:

We study special problems about constrained extremum problems for multivariable functions (the function is linear and the constraint equations are given by linear equations and linear inequalities).
Knowledge: The mathematical basis for systems of linear equations and inequalities. Skills: To be able to use memorized algorithms to solve specific problems of practice.
 Study materials:

Key references
:[1] George B. Dantzig and Mukund N. Thapa. 1997. Linear programming 1:Introduction. SpringerVerlag.
[2] T.C.HU, 1970, Integer Programming and Network Flows, AddisonWeslley Publishing, Menlo Park
Recommended references:
[3] George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. SpringerVerlag,
[4] Kattta G. Murty, Linear Programming, Wiley, 1983
 Note:
 Further information:
 No timetable has been prepared for this course
 The course is a part of the following study plans: