UPOZORNĚNÍ: Jsou dostupné studijní plány pro následující akademický rok.

Linear Programming

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
801LIP Z,ZK 3 2+1 Czech
Garant předmětu:
Čestmír Burdík
Petr Kubera
Petr Kubera
Department of Software Engineering

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).


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

Time-table for winter semester 2023/2024:
Time-table is not available yet
Time-table for summer semester 2023/2024:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2024-05-24
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet7694706.html