Manual del estudiante de Ingeniería en Sistemas de UTN/Investigación Operativa/Programación Lineal

Método Simplex

Descripción

Este método requiere contar con una solución básica factible inicial. A partir de este vértice se mueve a través de una secuencia de soluciones básicas factibles, que mejoran o mantienen el valor de la función objetivo anterior. En cada paso deben cumplirse las siguientes condiciones:

Condición de optimalidad

Significa que debe garantizarse que durante el procedimiento, ninguna solución puede ser peor que la anterior.

Condición de factibilidad

Significa que debe garantizarse que si se parte de una solución factible, sólo se hallarán soluciones factibles. El método requiere que el problema esté en su forma estándar.

	$[Max|Min]X_{0}={\underline {c}}^{T}{\underline {x}}$
S.a:
	${\underline {\underline {A}}}{\underline {x}}$	$={\underline {b}}$
	${\underline {x}}\geq {\underline {0}}$

Proceso iterativo

Para comenzar a trabajar, hace falta una solución básica factible. Si las restricciones son de menor o igual, una variable de holgura se sumará al lado izquierdo, ya que a ese lado, a lo sumo le sobrará algo para equiparar al derecho:

$\sum _{i=1}^{n}x_{i}a_{ij}\leq b_{j}$	$\forall j$
$\Downarrow$
$\sum _{i=1}^{n}x_{i}a_{ij}+s_{j}=b_{j}$	$\forall j$

En este caso, una solución factible es $x_{i}=0\forall i$, de manera que:

$\sum _{i=1}^{n}x_{i}a_{ij}+s_{j}=b_{j}\forall j\Rightarrow$

$0+s_{j}=b_{j}\forall j$

Entonces:

$s_{j}=b_{j}\forall j$

De manera que se cumple la restricción de no negatividad, ya que

$s_{j}=b_{j}\geq 0\forall j$

Si, en cambio, aparece una restricción de mayor o igual, una variable de holgura se restará al lado izquierdo, ya que a ese lado, a lo sumo le faltará algo para equiparar al derecho:

$\sum _{i=1}^{n}x_{i}a_{ij}\geq b_{j}$	$\forall j$
$\Downarrow$
$\sum _{i=1}^{n}x_{i}a_{ij}-s_{j}=b_{j}$	$\forall j$

En este caso, $x_{i}=0\forall i$ no es una solución factible, ya que:

$\sum _{i=1}^{n}x_{i}a_{ij}-s_{j}=b_{j}\forall j\Rightarrow$

$0-s_{j}=b_{j}\forall j$

Entonces:

$s_{j}=-b_{j}\leq 0\forall j$

De manera que no se cumple la restricción de no negatividad, entonces el punto resulta no factible.

Por último, si la restricción fuera de igualdad, no se agrega ninguna variable de holgura, por lo que $x_{i}=0\forall i$ implicaría que $0=b_{j}\forall j$, lo cual resultaría inconsistente si $\exists j/b_{j}\neq 0$.

El vector de variables de decisión puede considerarse compuesto de dos vectores, uno de variables básicas y otro de variables no básicas, así como la matriz de coeficientes y el vector de costos.

${\underline {\underline {A}}}=\underbrace {\begin{bmatrix}a_{1,1}&\cdots &a_{1,n}\\a_{2,1}&\cdots &a_{2,n}\\\vdots &&\vdots \\a_{n,1}&\cdots &a_{n,n}\end{bmatrix}} _{B}^{\begin{matrix}P_{x_{1}}&\cdots &P_{x_{n}}\end{matrix}}\underbrace {\begin{bmatrix}a_{1,n+1}&\cdots &a_{1,m}\\a_{2,n+1}&\cdots &a_{2,m}\\\vdots &&\vdots \\a_{n,n+1}&\cdots &a_{n,m}\end{bmatrix}} _{N}^{\begin{matrix}P_{x_{n}+1}&\cdots &P_{x_{m}}\end{matrix}}$

${\underline {x}}=\left[{\begin{matrix}x_{1}\\\vdots \\x_{n}\\x_{n+1}\\\vdots \\x_{m}\end{matrix}}\right]{\begin{matrix}\left.{\begin{matrix}\\\\\\\end{matrix}}\right){\underline {x}}_{B}\\\left.{\begin{matrix}\\\\\\\end{matrix}}\right){\underline {x}}_{N}\end{matrix}}$

${\underline {c}}=\left[{\begin{matrix}c_{x_{1}}\\\vdots \\c_{x_{n}}\\c_{x_{n+1}}\\\vdots \\c_{x_{m}}\end{matrix}}\right]{\begin{matrix}\left.{\begin{matrix}\\\\\\\end{matrix}}\right){\underline {c}}_{B}\\\left.{\begin{matrix}\\\\\\\end{matrix}}\right){\underline {c}}_{N}\end{matrix}}$

El problema lineal puede escribirse

	$[Max|Min]X_{0}={\underline {c}}_{B}^{T}{\underline {x}}_{B}+{\underline {c}}_{N}^{T}{\underline {x}}_{N}$
S.a:
	${\underline {\underline {B}}}{\underline {x}}_{B}+{\underline {\underline {N}}}{\underline {x}}_{N}$	$={\underline {b}}$
	${\underline {x}}_{B},{\underline {x}}_{N}\geq {\underline {0}}$

El valor de las variables básicas puede obtenerse a partir de las restricciones:

${\underline {\underline {B}}}{\underline {x}}_{B}+{\underline {\underline {N}}}{\underline {x}}_{N}={\underline {b}}$

Como las variables no básicas valen cero:

${\underline {\underline {B}}}{\underline {x}}_{B}+\underbrace {{\underline {\underline {N}}}{\underline {x}}_{N}} _{0}={\underline {b}}$

${\underline {\underline {B}}}{\underline {x}}_{B}={\underline {b}}\Rightarrow$

${\underline {x}}_{B}={\underline {\underline {B}}}^{-1}{\underline {b}}$

Simplex encuentra un nuevo vértice asignando un valor no negativo a una de las variables actualmente no básicas. Esta variable que ingresa a la base, debe elegirse de tal manera que al hacerlo mejore la función objetivo. Se busca poner el nuevo valor^[1] de $X_{0}$ en función del valor anterior. Para eso, usamos los vectores ${\underline {x}}_{B}$ y ${\underline {x}}_{N}$ , que representan a las mismas variables que en la iteración anterior, pero cuyo valor será ahora un valor nuevo. Tenemos entonces la siguiente igualdad:

${\underline {\underline {B}}}{\underline {x}}_{B}+{\underline {\underline {N}}}{\underline {x}}_{N}={\underline {b}}$

Pero en este caso, las variables del vector ${\underline {x}}_{N}$ no tienen necesariamente valor 0, por lo tanto no se puede anular el término ${\underline {\underline {N}}}{\underline {x}}_{N}$, entonces:

${\underline {\underline {B}}}{\underline {x}}_{B}={\underline {b}}-{\underline {\underline {N}}}{\underline {x}}_{N}$

${\underline {x}}_{B}={\underline {\underline {B}}}^{-1}{\underline {b}}-{\underline {\underline {B}}}^{-1}{\underline {\underline {N}}}{\underline {x}}_{N}$

Quedan así los valores nuevos de ${\underline {x}}_{B}$ en función de los valores de ${\underline {x}}_{B}$ en la iteración anterior ^[2] y de ${\underline {\underline {B}}}^{-1}{\underline {\underline {N}}}{\underline {x}}_{N}$.

Se puede expresar ahora el nuevo valor de la función objetivo $X_{0}$ en función de estos vectores viejos con valores nuevos:

$X_{0}={\underline {c}}^{T}{\underline {x}}$

$X_{0}={\underline {c}}_{B}^{T}{\underline {x}}_{B}+{\underline {c}}_{N}^{T}{\underline {x}}_{N}$

$X_{0}={\underline {c}}_{B}^{T}({\underline {\underline {B}}}^{-1}{\underline {b}}-{\underline {\underline {B}}}^{-1}{\underline {\underline {N}}}{\underline {x}}_{N})+{\underline {c}}_{N}^{T}{\underline {x}}_{N}$

$X_{0}={\underline {c}}_{B}^{T}{\underline {\underline {B}}}^{-1}{\underline {b}}-{\underline {c}}_{B}^{T}{\underline {\underline {B}}}^{-1}{\underline {\underline {N}}}{\underline {x}}_{N}+{\underline {c}}_{N}^{T}{\underline {x}}_{N}$

$X_{0}={\underline {c}}_{B}^{T}{\underline {\underline {B}}}^{-1}{\underline {b}}-({\underline {c}}_{B}^{T}{\underline {\underline {B}}}^{-1}{\underline {\underline {N}}}-{\underline {c}}_{N}^{T}){\underline {x}}_{N}$

Representando el segundo término componente a componente ^[3]:

$X_{0}={\underline {c}}_{B}^{T}{\underline {\underline {B}}}^{-1}{\underline {b}}-\sum _{j\in VNB}\left[({\underline {c}}_{B}^{T}{\underline {\underline {B}}}^{-1}{\underline {P}}_{j}-c_{j})x_{j}\right]$

Donde:

$X_{0}=\underbrace {{\underline {c}}_{B}^{T}{\underline {\underline {B}}}^{-1}{\underline {b}}} _{X_{0}{\text{ de la iteracion anterior}}}-\sum _{j\in VNB}\left[(\underbrace {{\underline {c}}_{B}^{T}{\underline {\underline {B}}}^{-1}{\underline {P}}_{j}} _{z_{j}}-c_{j})x_{j}\right]$

Queda así expresado el nuevo valor de $X_{0}$ en función del valor anterior:

$X_{0}={\underline {c}}_{B}^{T}{\underline {\underline {B}}}^{-1}{\underline {b}}-\sum _{j\in VNB}\left[(z_{j}-c_{j})x_{j}\right]$

Garantizar que el segundo término no empeore el nuevo valor significa garantizar que en la nueva iteración la función objetivo no empeore. Cambiando el valor de una sola variable (en realidad, vamos a controlar el valor de cada una por separado), se puede controlar el valor del término completo. Esto es así porque entre los nuevos valores de las variables no básicas de la iteración anterior, sólo uno de ellos será diferente de 0 en la iteración nueva, y como todos los valores deben ser positivos, se puede fijar un signo para el término $z_{j}-c_{j}$ de tal manera que se garantice optimalidad.

Condición de optimalidad

Para mejorar la función objetivo respecto del valor anterior, dado que

${\underline {X}}_{0}={\underline {X}}_{0{\text{anterior}}}-\sum _{j\in VNB}\left[(z_{j}-c_{j})x_{j}\right]$, y ya que $z_{j}-c_{j}$ será diferente de cero para un solo $j$, deberá buscarse el mejor valor de $z_{j}-c_{j}$, que será:

• $z_{j}-c_{j}>0$ si es un problema de minimización, ya que esto disminuirá el valor de la función objetivo.
• $z_{j}-c_{j}<0$ si es un problema de maximización, ya que esto aumentará el valor de la función objetivo.

Se elegirá el más positivo o el más negativo en cada caso, e ingresará la variable $x_{j}$ a la base. Esto garantizará que la función objetivo no empeore al realizar este paso.

Condición de factibilidad

Luego, una de las variables que estaban en la base debe salir. Las condiciones que deben cumplirse para la variable que sale de la base son:

• Todas las variables que eran básicas en la iteración anterior deben permanecer con valores no negativos.
• La variable saliente tomará el valor de 0.

Como habíamos caracterizado a ${\underline {x}}_{B}$ como el vector viejo con valores nuevos, la primera restricción puede representarse:

${\underline {x}}_{B}={\underline {\underline {B}}}^{-1}{\underline {b}}-{\underline {\underline {B}}}^{-1}{\underline {\underline {N}}}{\underline {x}}_{N}\geq {\underline {0}}$ ^[4]

En este punto, $x_{j}$ ya está elegido, y es el único valor distinto de 0 en ${\underline {x}}_{N}$, de manera que:

${\underline {x}}_{B}={\underline {\underline {B}}}^{-1}{\underline {b}}-{\underline {\underline {B}}}^{-1}{\underline {P}}_{j}x_{j}\geq {\underline {0}}$

Tomando la condición elemento por elemento:

$\left({\underline {x}}_{B}\right)_{i}=\left({\underline {\underline {B}}}^{-1}{\underline {b}}\right)_{i}-\left({\underline {\underline {B}}}^{-1}{\underline {P}}_{j}\right)_{i}x_{j}\geq {\underline {0}}$ $\forall i\in VB$

Este conjunto de condiciones limita el valor de $x_{j}$:

$x_{j}\leq {\frac {\left({\underline {\underline {B}}}^{-1}{\underline {b}}\right)_{i}}{\left({\underline {\underline {B}}}^{-1}{\underline {P}}_{j}\right)_{i}}}$ $\forall i\in VB$

La condición que más limite el valor de $x_{j}$ será la que en definitiva fije su valor. El elemento que debe salir de la base (hacerse 0), es aquel que fija el valor de $x_{j}$. Sea $i$ la posición del elemento saliente dentro del vector ${\underline {x}}_{B}$:

$i={\stackrel {\text{min}}{_{i\in {\text{VB}}_{r}}}}\left[{\frac {\left({\underline {\underline {B}}}^{-1}{\underline {b}}\right)_{i}}{\left({\underline {\underline {B}}}^{-1}{\underline {P}}_{j}\right)_{i}}}\right]$

Siendo ${\text{VB}}_{r}$ el conjunto de variables básicas que restringen el valor de $x_{j}$, que son aquellas con índice $i$ tal que $\left({\underline {\underline {B}}}^{-1}{\underline {P}}_{j}\right)_{i}>0$. Esto es así porque, como $\left({\underline {\underline {B}}}^{-1}{\underline {b}}\right)_{i}$ es el valor anterior del vector de variables básicas en la posición $i$, es decir $\left({\underline {\underline {B}}}^{-1}{\underline {b}}\right)_{i}=({\underline {x}}_{B})_{i{\text{anterior}}}$, y por eso será siempre no-negativo, entonces, si $\left({\underline {\underline {B}}}^{-1}{\underline {P}}_{j}\right)_{i}\leq 0$, la condición $\left({\underline {x}}_{B}\right)_{i}=\left({\underline {\underline {B}}}^{-1}{\underline {b}}\right)_{i}-\left({\underline {\underline {B}}}^{-1}{\underline {P}}_{j}\right)_{i}x_{j}\geq {\underline {0}}$ se cumplirá en todo caso para ese $i$ particular, de manera que la condición en dicha posición $i$ no restringe el valor de $x_{j}$.

Si a ${\underline {\underline {B}}}^{-1}{\underline {P}}_{j}$ lo llamamos ${\underline {\alpha _{j}}}$, se puede expresar el valor del índice saliente como:

$i={\stackrel {\text{min}}{_{i}}}\left[{\frac {({\underline {x}}_{B})_{i{\text{anterior}}}}{\left({\underline {\alpha _{j}}}\right)_{i}}}\right]$ $\forall i/\left({\underline {\alpha _{j}}}\right)_{i}>0$

---

^  Es decir, el valor en el próximo punto, el de la siguiente iteración.

^  ${\underline {x}}_{Banterior}={\underline {\underline {B}}}^{-1}{\underline {b}}$

^  Siendo VNB el conjunto de los índices correspondientes a las variables no-básicas.

^  Se utiliza esta nomenclatura para expresar que todos los elementos de ${\underline {x}}_{B}$ deberán ser mayores que cero.