Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2024/2025

Linear Programming

The course is not on the list Without time-table
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. 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:
Data valid to 2024-05-28
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet6531506.html