Linear Programming: Theory and Applications
Course duration: 8 h
We begin with concrete optimization problems such as the use of resources, the transportation problem, the shortest path problem on graphs, matrix games, and distribution of investments. All of them can be reformulated as extremal problems for linear functions on polyhedra.
Having this in mind, we introduce basic notions and results from convex geometry. Convex sets, polyhedra, polytopes and cones will be defined and illustrated by examples.
Besides elementary properties we present fundamental theorems due to Farkas, von Neumann and Weyl. This base allows us to introduce the simplex algorithm of Dantzing. The idea is to pass along edges from one vertex to another in such a way that the value of a given linear function increases. This naive approach leads to an efficient tool to solve linear optimization problems. We provide explicit computations and variations on simplex method.
In the last part we plan to discuss duality, integer linear programming, and related practical problems.
Prof. Ivan Arzhantsev
Place of employment: Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Associate Professor; School of Applied Mathematics and Information Science, Higher School of Economics, Moscow, Professor; Yandex
Spheres of researches: Pure and Applied Algebra, Algebraic and Convex Geometry, Invariant Theory, Representation Theory and Combinatorics