Linear Programming
Code  Completion  Credits  Range  Language 

801LIP  Z,ZK  3  2+1  Czech 
 Garant předmětu:
 Lecturer:
 Tutor:
 Supervisor:
 Department of Software Engineering
 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:

Basic course of Calculus and Linear Algebra (in the extent of the courses 01MA1, 01MAA24, 01LA1, 01LAA2 held at the FNSPE CTU in Prague).
 Syllabus of lectures:

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).
 Syllabus of tutorials:

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.
 Study Objective:

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:

 Applications of Informatics in Natural Sciences (compulsory course in the program)