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.
