#
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} \)

Donde

\( 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 will be 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), in particular is a convex set. The convex theory join linear programming theorems says that
if P has finite optimal solution it will be into 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 submatrix of A with dimension mxm then we can write

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

and we can write too

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

And solutiion can be written as

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

**Theorem 2 (Extreme points characterization)**

Lets 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.

**Corolary **

The maximum number of extreme points of S is

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

As we will see, not every linear programming problem has finite optimal solution, but if one then there is a characterization for it in the next theorema:

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

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

Extreme points of S and lets

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

Extreme directions of S.

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

In adittion one of
And one of the

Extreme points is the solution for the problem P.