# 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 $c \in \mathbb{R}^n$, $b \in \mathbb{R}^m$ and matrix $A \in \mathbb{R}^{m \times n}$.

## 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 $W$. Let also assume, that we have the vector of requirements for each of nutrients $r \in \mathbb{R}^n$. We need to find the cheapest configuration of the diet, which meets all the requirements:

# How to retrieve LP

## Basic transformations

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

unsigned variables to nonnegative variables.

# Idea of simplex algorithm

• The Simplex Algorithm walks along the edges of the polytope, at every corner choosing the edge that decreases $c^\top x$ most
• This either terminates at a corner, or leads to an unconstrained edge ($-\infty$ optimum)

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

Definition: a basis $B$ is a subset of $n$ (integer) numbers between $1$ and $m$, so that $\text{rank} A_B = n$. Note, that we can associate submatrix $A_B$ and corresponding right-hand side $b_B$ with the basis $B$. Also, we can derive a point of intersection of all these hyperplanes from basis: $x_B = A^{-1}_B b_B$.

If $A x_B \leq b$, then basis $B$ is feasible.

A basis $B$ is optimal if $x_B$ is an optimum of the $\text{LP.Inequality}$.

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

## Main lemma

If all components of $\lambda_B$ are non-positive and $B$ is feasible, then $B$ is optimal.

Proof:

## Changing basis

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

In the following problem simplex algorithm needs to check $2^n - 1$ vertexes with $x_0 = 0$.