# 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

# Materials

- Linear Programming. in V. Lempitsky optimization course.
- Simplex method. in V. Lempitsky optimization course.
- Overview of different LP solvers
- TED talks watching optimization