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.
This form seems to be the most intuitive and geometric in terms of visualization. Let us have vectors , and matrix .
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:
Inequality to equality by increasing the dimension of the problem by .
unsigned variables to nonnegative variables.
- 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 :
If all components of are non-positive and is feasible, then is optimal.
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)
Klee Minty example
In the following problem simplex algorithm needs to check vertexes with .