Linear Programming

Course guarantor:

Jan Volec

Lecturer:

Jan Volec

Tutor:

Jan Volec

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 foundation for solving systems of linear inequalities.

Skills:

1) Understand the simplex method and the duality of linear programming.

2) Understand linear relaxations of integer programming problems, particularly total unimodularity.

3) Be able to solve practical linear optimization problems and use LP solvers on a computer.

Study materials:

Textbook:

[1] B. Gärtner, J. Matoušek : Understanding and Using Linear Programming. Springer, 2007.

Note:

Further information:

http://honza.ucw.cz/LIP

Time-table for winter semester 2024/2025:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue	roomTR:208 Blažek J. 10:00–11:50 EVEN WEEK (parallel nr.101) Trojanova 13 učebna 208
Wed
Thu
Fri	roomTR:209 Volec J. 10:00–11:50 (lecture parallel1) Trojanova 13 učebna 209

Time-table for summer semester 2024/2025:

Time-table is not available yet

The course is a part of the following study plans:

• Aplikovaná algebra a analýza (elective course)
• Aplikace informatiky v přírodních vědách (compulsory course in the program)
• Aplikované matematicko-stochastické metody (compulsory course in the program)
• Matematické inženýrství - Matematická informatika (PS)
• Matematické inženýrství - Matematické modelování (PS)