What is LP

Generally speaking, all problems with linear objective and linear equalities\inequalities constraints could be considered as Linear Programming. However, there are some widely accepted formulations.

Standard form

This form seems to be the most intuitive and geometric in terms of visualization. Let us have vectors , and matrix .

Canonical form

Real world problems

Diet problem

Imagine, that you have to construct a diet plan from some set of products: ๐ŸŒ๐Ÿฐ๐Ÿ—๐Ÿฅš๐ŸŸ. Each of the products has its own vector of nutrients. Thus, all the food information could be processed through the matrix . Let also assume, that we have the vector of requirements for each of nutrients . We need to find the cheapest configuration of the diet, which meets all the requirements:

Radiation treatment

How to retrieve LP

Basic transformations

Inequality to equality by increasing the dimension of the problem by .

unsigned variables to nonnegative variables.

Chebyshev approximation problem

approximation problem

Idea of simplex algorithm

  • The Simplex Algorithm walks along the edges of the polytope, at every corner choosing the edge that decreases most
  • This either terminates at a corner, or leads to an unconstrained edge ( optimum)

We will illustrate simplex algorithm for the simple inequality form of LP:

Definition: a basis is a subset of (integer) numbers between and , so that . Note, that we can associate submatrix and corresponding right-hand side with the basis . Also, we can derive a point of intersection of all these hyperplanes from basis: .

If , then basis is feasible.

A basis is optimal if is an optimum of the .

Since we have a basis, we can decompose our objective vector in this basis and find the scalar coefficients :

Main lemma

If all components of are non-positive and is feasible, then is optimal.

Proof:

Changing basis

Suppose, some of the coefficients of are positive. Then we need to go through the edge of the polytope to the new vertex (i.e., switch the basis)

About convergence

Klee Minty example

In the following problem simplex algorithm needs to check vertexes with .

Code

Open In Colab

Materials