Linear Programming

Course guarantor:

Jan Volec

Lecturer:

Jan Volec

Tutor:

Adam Blažek, Jan Volec

Supervisor:

Department of Mathematics

Synopsis:

We study special problems about constrained extremal problems for multivariable functions, where the function is linear and the constraints are given by linear equations and/or linear inequalities.

Requirements:

Introductory Analysis and Linear Algebra courses, covered by 01MA1, 01MAA2-4, 01LA1, 01LAA2 at the FNSPE CTU in Prague.

Syllabus of lectures:

1. Linear programming formulation, LP in the equational form

2. LP relaxations of combinatorial problems, total unimodularity

3. Basic feasible solutions, inefficient algorithm for solving LPs

4. Solving LPs using free software

5. Introduction to Simplex Method, auxiliary LP for finding basic feasible solutions

6. Simplex Method (details)

7. Blandt's rule, example of cycling

8. Linear programming duality, Farkas lemma

9. Proof of the strong duality theorem, complementary slackness

10. Applications in Game Theory - zero-sum games

11. Transportation Problem

12. Integer programming, Gomory cuts

Syllabus of tutorials:

1. Reductions between variants of LP formulations, examples (e.g. cutting paper rolls, separation of points)

2. Combinatorial problems and their LP relaxations, total unimodularity

3. Removing the absolute value functions, Linear-fractional programming

4. Solving LPs using the simplex method

5. Using LP duality, versions of Farkas lemma

6. Integer programming

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
Wed
Thu
Fri	roomTR:209 Volec J. 10:00–11:50 (lecture parallel1) Trojanova 13

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)