Linear Programming

Question 1

Fundamental theorem of Linear Programming

Answer 1

Given a LP problem in standard form:

min c^Tx

Ax = b

x >= 0

With A matrix m x n of rank m:

1. If a feasible solution to the problem exist, then also a basic feasible solution exists.
2. If an optimal feasible solution exists, then also a basic optimal feasible solution exists.

This theorem is important, because it shows that we can find an optimal solution to a problem (if it exists) in a finite number of steps.

Question 2

Simplex method

Answer 2

The feasible region defined by all values of x such that A x = b and ∀ i , x_i ≥ 0 is a (possibly unbounded) convex polytope.

An extreme point or vertex of this polytope is known as basic feasible solution (BFS).

It can be shown that for a linear program in standard form, if the objective function has an optimal value on the feasible region, then it has this value on (at least) one of the extreme points.

If the edge is finite, then the edge connects to another extreme point where the objective function has a greater value, otherwise the objective function is unbounded and the linear program has no solution.

The simplex algorithm applies this insight by walking along edges of the polytope to extreme points with better and better objective values.

Question 3

Complexity of the simplex algorithm

Answer 3

O(max(|V|))

Where V is the set of vertices of the Polytope K.

max(|V|) is the maximum number of vertices the Polytope K can have, it is equal to the number ways we can select m vectors from A, that is made out of n vectors.

O(n!/((n-m)!m!))

Question 4

Logical constraints

Answer 4