#
Linear programming

###
Basic Concepts and principles

A Linear programming problem in standard formulation is a problem in the form:

Minimize \( C^t x \)

Subject to

\( \begin{matrix} Ax=b \\ x\geqslant 0 \end{matrix} \)

Where

\( A \in \mathbb M _{mxn}, \, rnk(A)=m ,\,\, \)\( b \in R^{m}, \, C \in R^{n}, \,\, n \geqslant m \)

From now on we will call P to this problem.

C is called the costs vector, A the constraints matrix and b the constraints vector.

The feasible set

\(S = \{ x\in\mathbb{R}^n : Ax=b, x\geq 0 \} \)

is a polyhedral set (semi-spaces intersection) also called a polytope, in particular it is a convex set. We will see here that if P has finite optimal solution it is within the

extreme points set of S.

###
Extended Theory

The feasible Set

\(S = \{ x\in\mathbb{R}^n : Ax=b, x \geq 0 \} \)

Can be characterized in terms of its

extreme points and its

extreme directions.

**Theorem 1 (extreme points existence)**

The feasible set, se has at least one extreme point.

If B is a square submatrix of A with mxm dimension then we can write:

\( A=\begin{bmatrix} B \\ N\end{bmatrix} \)

N is the matrix formed by the remaining colums of A from B, remember that \(n \geqslant m \)m. This allows to write the system as:

\( Bw_{B} + Nw_{N} = b \)

So any x solution can be written as

\( x=\begin{bmatrix} X_{B} \\ X_{N}\end{bmatrix} \)

**Theorem 2 (Extreme points characterization)**

Let the set:

\( S = \{ x\in\mathbb{R}^n : Ax=b, x\geq 0 \} \)\( \subset \mathbb{R}^n \)

Where

\( A\in\mathbb{M}_{mxn} : rnk(A)=m, b \)\( \in \mathbb{R}^m , C \in \mathbb{R}^n \)

then
x is an extreme point if and only if \( \exists B \) submatrix of A with rank(B) = m such as

\( x=\begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix} \)

The following corollary gives us an upper bound for the number of extreme points.

**Corollary **

The maximum number of extreme points of S is

\( \binom{n}{m} = \frac{n!}{(n-m)!} \)

As we will see, not all linear programming problem has finite optimal solution, but if it do exists then there is a characterization for it in the next theorem:

**Theorem 3 (Finite optimal solutions characterization for problem P)**
Let

\( x_{1}, x_{2}, ..., x_{k} \)

Extreme points of S and let

\( d_{1}, d_{2}, ..., d_{r} \)

Extreme directions of S. Then:

\( C^t d_{j} \geq 0 ,\:\:\: \forall j =1,2, ...,r\)

In adittion one of the

extreme points is solution of the problem P.