Linear Programming

Course guarantor:

Jan Volec

Lecturer:

Jan Volec

Tutor:

Adam Blažek, Jan Volec

Supervisor:

Department of Mathematics

Synopsis:

The course deals with special problems concerning bound extremes of functions of several variables (the function is linear and the constraints are in the form of linear equations and inequalities).

Requirements:

Credit: Awarded for attendance and successful completion of the credit test.

Exam: Theoretical and practical part selected from the content covered in lectures.

Syllabus of lectures:

1. Formulation of linear programming problems, conversion of constraints, examples of problems

2. Properties of linear programming problems, set of feasible and optimal solutions and their properties, geometry of LP problems

3. Fundamental theorem of LP, graphical solution of LP problems

4. Simplex algorithm single-phase method, unbounded problems, multiple optimal solutions

5. Simplex algorithm two-phase method (auxiliary basis technique), M-problem

6. Properties of the simplex method degeneration, cycling, time complexity of the algorithm

7. Duality of linear programming problems formulation of dual problems, duality theorems

8. Dual simplex method algorithm

9. Transportation problem MODI method

10. Applications in game theory zero-sum matrix games, mixed strategies, minmax theorem

11. Algorithms of integer programming typical LIP problems, branch and bound method

12. Algorithms of integer programming Gomory cuts

Syllabus of tutorials:

1. Solving LP problems on a computer software tools and their use

2. Linear programming problems, optimality conditions, and unconstrained problems

3. Simplex method basic steps of the algorithm, various situations when solving

4. Two-phase simplex method - auxiliary basis technique algorithm, solution variant using M-task.

5. Dual simplex method.

6. Example from game theory - searching for mixed strategies.

7. Gomory's algorithm and other LIP algorithms (branch and bound method).

8. Quadratic programming.

Study Objective:

Knowledge:

Mathematical foundation of systems of linear equations and inequalities.

Skills:

Ability to use the algorithms discussed to solve specific practical problems.

Study materials:

Required reading:

[1] J. Rohn: Lineární programování. Skripta 2004

[2] J. Rohn: Lineární a nelineární programování. Skripta 1997

Recommended reading:

[3] J. Matoušek: Lineární programování, Úvod pro informatiky. Skripta 2006

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

Note:

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)
• Mathematical Engineering - Mathematical Modelling (PS)
• Mathematical Engineering - Mathematical Informatics (PS)