Programación Lineal
Conceptos y Principios Básicos
Un problema de programación lineal en formulación estándar, es un problema de la forma
Minimizar \( C^t x \)
Sujeto a
\( \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 \)
A partir de ahora llamaremos a este problema P. Al vector C le llamamos vector de costes, A será la matriz de restricciones y B será el vector de restricciones.
Las dimensiones del problema m y n son respectivamente, el número de filas y el número de columnas de la matriz A.
La idea es que el conjunto factible
\(S = \{ x\in\mathbb{R}^n : Ax=b, x\geq 0 \} \)
es un conjunto poliédrico denominado polítopo, formado por la intersección de semiespacios generados por cada una de las restricciones y en particular es un conjunto convexo, los teoremas de programación lineal junto con la teoría de convexidad demuestran que si P tiene solución finita, ella está dentro del conjunto de sus
puntos extremos.
Teoría en extensión
El conjunto factible
\(S = \{ x\in\mathbb{R}^n : Ax=b, x\geq 0 \} \)
Se puede caracterizar S en términos de sus
puntos extremos y sus
direcciones extremas.
Teorema 1 (existencia de puntos extremos)
El conjunto S tiene al menos un punto extremo.
Si B es una submatriz de A mxm (con rango m), entonces podemos escribir
\( A=\begin{bmatrix} B \\ N\end{bmatrix} \)
y el sistema de programación lineal se puede poner
en la forma
\( Bw_{B} + Nw_{N} = b \)
y podemos escribir la solución en la forma
\( x=\begin{bmatrix} X_{B} \\ X_{N}\end{bmatrix} \)
Todo esto que aunque solo es notación ha servido para dividir el sistema de ecuaciones que forma la región
factible en dos sistemas de ecuaciones, uno para una submatriz cuadrada de A (de rango m) y otro con las ecuaciones restantes.
Existe una caracterización de los puntos extremos del conjunto factible S, la idea intuitiva es que todo punto extremo es en realidad solución
del un sistema lineal de ecuaciones construído a partir de una submatriz de A de rango m (en nuestro caso B).
Teorema 2 (Caracterización de puntos extremos)
Sea el conjunto
\( S = \{ x\in\mathbb{R}^n : Ax=b, x\geq 0 \} \)\( \subset \mathbb{R}^n \)
Donde
\( A\in\mathbb{M}_{mxn} : rnk(A)=m, \)\(b \in \mathbb{R}^m , C \in \mathbb{R}^n \)
entonces
x es un punto extremo si y solo si \( \exists B \) submatriz de A con rango(B) = m tal que
\( x=\begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix} \)
El siguiente corolario nos impone una cota superior para el número de puntos extremos de nuestro conjunto factible.
Corolario
El número máximo de puntos extremos de S es
\( \binom{n}{m} = \frac{n!}{(n-m)!} \)
Teorema 3 (Caracterización de direcciones extremas)
Sea el conjunto
\( S = \{ x\in\mathbb{R}^n : Ax=b, x\geq 0 \} \)\(\subset \mathbb{R}^n \)
Donde
\( A\in\mathbb{M}_{mxn} : rnk(A)=m,\)\(b \in \mathbb{R}^m , C \in \mathbb{R}^n \)
entonces \( \vec{d} \in \in \mathbb{R}^n \) es una dirección extrema de S si y solo si A puede descomponerse en la forma
\( A=[B,N] \) donde B submatriz mxn invertible de A con rango(B) = m tal que
\( B^{-1} a_j \leq 0 \) para alguna columna \(a_j \) de N y \(\vec{d} \) es un múltimpo positivo de de
\( \begin{bmatrix}- B^{-1}a_j \\ e_j \end{bmatrix} \).
Siendo \(e_j \) un vector de n-m coordenadas que tiene un 1 en la posición j y cero en el resto.
Finalmente el siguiente teorema nos da una caracterización de como será una solución del problema de programación lineal en caso de existir.
Como veremos, no todo problema de programación lineal tiene solución óptima finita, pero en caso de tenerla existe una caracterización en el siguiente terorema:
Teorema 4 (Caracterización de soluciones óptimas finitas del problema P)
Sean
\( x_{1}, x_{2}, ..., x_{k} \) los
puntos extremos de S y sean
\( d_{1}, d_{2}, ..., d_{r} \) las
direcciones extremas de S.
P tiene solución óptima finita si y solo si
\( C^t d_{j} \geq 0 ,\:\:\: \forall j =1,2, ...,r\)
Además uno de los puntos extremos es solución del problema
