Linear Programming

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:

Basic course of Calculus and Linear Algebra (in the extent of the courses 01MA1, 01MAA2-4, 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. Springer-Verlag. [2] T.C.HU, 1970, Integer Programming and Network Flows, Addison-Weslley Publishing, Menlo Park

Recommended references: [3] George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag, [4] Kattta G. Murty, Linear Programming, Wiley, 1983

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans:

• BS Matematické inženýrství - Matematické modelování (compulsory course of the specialization, elective course)
• BS Matematické inženýrství - Matematická fyzika (elective course)
• BS Matematické inženýrství - Aplikované matematicko-stochastické metody (elective course)
• BS Informatická fyzika (elective course)
• BS Aplikace softwarového inženýrství (elective course)
• BS Aplikovaná informatika (elective course)
• BS jaderné inženýrství B (elective course)
• BS Jaderné inženýrství C (elective course)
• BS Dozimetrie a aplikace ionizujícího záření (elective course)
• BS Experimentální jaderná a částicová fyzika (elective course)
• BS Inženýrství pevných látek (elective course)
• BS Diagnostika materiálů (elective course)
• BS Fyzika a technika termojaderné fúze (elective course)
• BS Fyzikální elektronika (elective course)
• BS Jaderná chemie (elective course)
• Aplikovaná algebra a analýza (compulsory course in the program)
• Aplikace informatiky v přírodních vědách (compulsory course in the program)
• Aplikované matematicko-stochastické metody (elective course)
• Matematické inženýrství - Matematická informatika (PS)
• Matematické inženýrství - Matematické modelování (PS)