Algoritmo símplex

En optimización matemática, el término algoritmo símplex habitualmente se refiere a un conjunto de métodos muy usados para resolver problemas de programación lineal, en los cuales de alguna manera se busca el máximo de una función lineal sobre un conjunto de variables que satisfaga un conjunto de inecuaciones lineales. El algoritmo símplex primal fue desarrollado por el matemático estadounidense George Dantzig en 1947, y procede examinando vértices adyacentes del poliedro de soluciones. Un algoritmo símplex es de alguna manera un algoritmo de pivote.

Un sistema de desigualdades lineales define un poliedro como una región factible. El algoritmo símplex comienza en un vértice y se mueve a lo largo de las aristas del poliedro hasta que alcanza el vértice de la solución óptima.

Un método llamado de manera similar, pero no relacionado al anterior, es el método de Nelder-Mead (1965) o método de descenso (o ascenso) símplex; un método numérico que busca un mínimo (o máximo) local de una función cualquiera examinando en cada paso los vértices de un símplex.

El algoritmo del método símplex fue elegido como uno de los 10 algoritmos más importantes del siglo XX.​

Entrada del problema

Consideremos un problema de programación lineal,

$\left\{{\begin{array}{cc}{\text{Maximizar}}&z=\mathbf {c} ^{T}\mathbf {x} \\{\text{Sujeto a:}}\\&\mathbf {A} \mathbf {x} \leq \mathbf {b} \\&\mathbf {x} \geq 0\end{array}}\right.$

El algoritmo símplex requiere que la matriz del problema esté en su forma aumentada. El problema puede ser descrito como sigue:

Maximizar $z$ en:

${\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\0&\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}z\\\mathbf {x} \\\mathbf {x} _{s}\end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}$

$\mathbf {x} ,\,\mathbf {x} _{s}\geq 0$

donde x son las variables desde la forma estándar, x_s son las variables de holgura introducidas en el proceso de aumentación, c contiene los coeficientes de optimización, describe el sistema de ecuaciones contraídas, y z es la variable a ser maximizada.

El sistema está típicamente no determinado, ya que el número de variables excede el número de ecuaciones. La diferencia entre el número de variables y el número de ecuaciones nos da los grados de libertad asociados al problema. Cualquier solución, óptima o no, incluirá un número de variables de valor arbitrario. El algoritmo símplex usa cero como valor arbitrario, y el número de variables con valor cero es igual a los grados de libertad.

Las variables con valores diferentes de cero serán llamadas "variables básicas", las demás "variables no básicas".

Esta forma simplifica el encontrar la solución factible básica inicial, dado que todas las variables de la forma estándar pueden ser elegidas para ser no básicas (cero), mientras que todas las nuevas variables introducidas en la forma aumentada, serán básicas (diferentes de cero), dado que su valor puede ser calculado trivialmente ($\mathbf {x} _{s\,i}=\mathbf {b} _{j}$ para ellas, dado que la matriz problema aumentada en diagonal es su lado derecho)

En cada una de las desigualdades que se plantean en el modelo matemático de programación lineal, se plantean desigualdades de <, >, ≤, ≥ o =; estas desigualdades se convierten en igualdades completando con variables de holgura si se trata de menor o igual que, o menor que; en el caso de que sea mayor o igual que o mayor que, se completa con variables de excedente, estas con signo negativo ya que como su nombre lo indica, es una cantidad que está de excedente y hay que quitar para convertirla en igualdad; en caso se maneje el =, se manejan las variables artificiales.

Conceptos básicos

Forma estándar

Es la igualación de las restricciones del modelo planteado, así como el aumento de variables de holgura, o bien la resta de variables de exceso.

Forma canónica

En el método símplex es de bastante utilidad la forma canónica, especialmente para explorar la relación de dualidad, donde un problema de programación lineal se encuentra en la forma canónica si se cumplen las siguientes condiciones:

Para el caso de la forma canónica de maximización:

• La función objetivo debe ser de maximización
• Las variables de decisión no negativas.
• Las restricciones son del tipo $\leq$.

Para el caso de la forma canónica de la dieta:

• La función objetivo es minimizada.
• Las restricciones son de tipo $\geq$.
• Las variables de decisión son no negativas.

Ejemplo:

Forma Canónica de Maximización

$$\left\{{\begin{array}{cc}{\text{Maximizar}}&z=2x_{1}+3x_{2}+5x_{3}\\{\text{Sujeto a:}}\\&2x_{1}+3x_{2}+8x_{3}\leq 8\\&5x_{1}+2x_{2}+4x_{3}\leq 9\\&x_{1},x_{2},x_{3}\geq 0\end{array}}\right.$$

Forma Canónica de la dieta

$$\left\{{\begin{array}{cc}{\text{Minimizar}}&z=-x_{1}-3x_{2}\\{\text{Sujeto a:}}\\&x_{1}-x_{2}\geq 6\\&-x_{1}+2x_{2}\geq 8\\&x_{1},x_{2}\geq 0\end{array}}\right.$$

Modelo ampliado

Cuando se introduce en cada restricción una variable artificial que no contenga una variable de holgura.

Ejemplo de un Modelo de Maximización en su Forma Ampliada

Variables de entrada

Estas suelen encontrarse en un criterio que se conoce como “Condición de optimalidad”, en un modelo, ya sea de maximización o minimización, y se refiere a la variable no básica en el renglón “z” con el coeficiente más negativo, si se trata de una maximización, o el coeficiente más positivo, si se trata de una minimización, la cual, en la tabla de solución anterior, a excepción de la primera tabla, esta variable era una variable básica.

Variables de salida

Esta variable es un punto extremo que se encuentra en un criterio conocido como “condición de factibilidad”, en un modelo, ya sea de optimización o minimización, y se refiere a la variable básica asociada con la mínima razón no negativa con el coeficiente más negativo, si se trata de una maximización, o el coeficiente más positivo, si se trata de una minimización, la cual, en la tabla de solución siguiente, pasará a ser variable no básica.

	Variables básicas	Variables no básicas	Variable de entrada	Variable de salida
A	X3, X4, X5, X6	X1, X2	X1	X2
B	X3, X4, X5, X1	X6, X2	X2	X3
C	X2, X4, X5, X1	X6, X3	X6	X4
D	X2, X6, X5, X1	X4, X3	X3	X1
E	X2, X6, X5, X3	X4, X1	X4	X2

Variable degenerada

Una variable degenerada es una variable básica que vale cero. Gráficamente esto puede ocurrir cuando más de dos rectas tocan una sola intersección en el mismo punto.

Base

Conjunto de variables básicas. En el ejemplo anterior, la base es {X3, X4, X5, X6}

Variable no restringida

Variable artificial

Se usa una variable artificial cuando las restricciones son = y ≥ y sucede cuando el origen no se encuentra dentro de la región factible, tratando de llevar el modelo a otra dimensión en la cual el origen si exista en la región.

Es aquella que puede tomar toda clase de valores positivos, cero y negativos puede escribirse como la diferencia de dos variables no-negativas.

Función objetivo:

Define la efectividad del modelo como función de las variables de decisión.

Solución óptima

Ejemplo gráfico de la solución óptima

Siempre está asociada a un punto extremo de la región factible y satisface todas las restricciones si se evalúa en ellas así como es el punto que en el caso de maximización hace que el valor de z sea el máximo (más grande) y el caso de minimización sea el mínimo (más pequeño).

Solución óptima múltiple

Existen problemas lineales que no tienen una solución óptima única, sino que al contrario, tienen un número infinito de soluciones.Para detectar una solución múltiple en la tabla óptima, se deberá tener al menos una variable con su Zj-Cj=0 no básica.

Algoritmo del método símplex

Este proceso que se repite una y otra vez, siempre inicia en un punto extremo de la región factible que normalmente es el origen, en cada repetición se mueve a otro punto extremo adyacente hasta llegar a la solución óptima.

Los pasos del método símplex son los siguientes:

1. Utilizando la forma estándar, determinar una solución básica factible inicial igualando a las (n-m) variables a cero (el origen).
2. Seleccionar la variable de entrada de las variables no básicas que al incrementar su valor pueda mejorar el valor en la función objetivo. Cuando no exista esta situación, la solución actual es la óptima; si no, ir al siguiente paso.
3. Seleccionar la variable de salida de las variables básicas actuales.
4. Determinar la nueva solución al hacer la variable de entrada básica y la variable de salida no básica, ir al paso 2 (actualizar).

Forma Matricial

Consideremos el modelo de programación lineal

$\left\{{\begin{array}{cc}{\text{Maximizar}}&z=c_{1}x_{1}+c_{2}x_{2}+\cdots +c_{n}x_{n}\\{\text{Sujeto a:}}\\&a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}\leq b_{1}\\&a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}\leq b_{2}\\&\vdots \\&a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}\leq b_{m}\\&x_{1},x_{2},\dots ,x_{n}\geq 0\end{array}}\right.$

puede ser representado mediante matrices de la siguiente forma

$\left\{{\begin{array}{cc}{\text{Maximizar}}&z=\mathbf {c} \mathbf {x} \\{\text{Sujeto a:}}\\&A\mathbf {x} \leq \mathbf {b} \\&\mathbf {x} \geq \mathbf {0} \end{array}}\right.$

donde

$\mathbf {c} =\left[{\begin{array}{cccc}c_{1}&c_{2}&\cdots &c_{n}\end{array}}\right]\qquad \qquad \mathbf {x} =\left[{\begin{array}{c}x_{1}\\x_{2}\\\vdots \\x_{n}\end{array}}\right]\qquad \qquad \mathbf {b} =\left[{\begin{array}{c}b_{1}\\b_{2}\\\vdots \\b_{m}\end{array}}\right]$

$A=\left[{\begin{array}{cccc}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\vdots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\end{array}}\right]\qquad \qquad \mathbf {0} =\left[{\begin{array}{c}0\\0\\\vdots \\0\end{array}}\right]$

Esto es $\mathbf {c} \in \mathbb {R} ^{1\times n}$, $\mathbf {x} \in \mathbb {R} ^{n\times 1}$, $\mathbf {b} \in \mathbb {R} ^{m\times 1}$, $A\in \mathbb {R} ^{m\times n}$ y $\mathbf {0} \in \mathbb {R} ^{n\times 1}$.

Para obtener la forma aumentada del problema de programación lineal, introducimos el vector columna de las variables de holgura, esto es

$\mathbf {x} _{s}=\left[{\begin{array}{c}x_{n+1}\\x_{n+2}\\\vdots \\x_{n+m}\end{array}}\right]$

de tal manera que las restricciones se convierten en

$\left[{\begin{array}{c|c}A&I\end{array}}\right]\left[{\begin{array}{c}\mathbf {x} \\\mathbf {x} _{s}\end{array}}\right]=\mathbf {b}$

$\left[{\begin{array}{c}\mathbf {x} \\\mathbf {x} _{s}\end{array}}\right]\geq \mathbf {0}$

donde

$I=\left[{\begin{array}{cccc}1&0&\cdots &0\\0&1&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &1\end{array}}\right]$

es la matriz identidad de orden $m\times m$.

Obtención de la Solución Básica Factible

Debemos identificar las variables básicas y no básicas de

$\left[{\begin{array}{c|c}A&I\end{array}}\right]\left[{\begin{array}{c}\mathbf {x} \\\mathbf {x} _{s}\end{array}}\right]=\mathbf {b}$

dado que se tienen que eliminar las variables no básicas al igualarlas a cero entonces queda un conjunto de $m$ ecuaciones con $m$ incógnitas (las variables básicas). Este sistema de ecuaciones lo denotamos por $B\mathbf {x} _{B}=\mathbf {b}$, donde el vector de variables básicas

$\mathbf {x} _{B}=\left[{\begin{array}{c}x_{B_{1}}\\x_{B_{2}}\\\vdots \\x_{B_{m}}\end{array}}\right]$

se obtiene al eliminar las variables no básicas de

$\left[{\begin{array}{c}\mathbf {x} \\\mathbf {x} _{s}\end{array}}\right]$

y la matriz base, denotada por $B\in \mathbb {R} ^{m\times m}$

$B=\left[{\begin{array}{cccc}B_{11}&B_{12}&\cdots &B_{1m}\\B_{21}&B_{22}&\cdots &B_{2m}\\\vdots &\vdots &\vdots &\vdots \\B_{m1}&B_{m2}&\cdots &B_{mm}\end{array}}\right]$

se obtiene al eliminar las columnas de

$\left[{\begin{array}{c|c}A&I\end{array}}\right]$

correspondientes a las variables no básicas, como la matriz base $B$ es invertible entonces la solución deseada para las variables básicas es $\mathbf {x} _{B}=B^{-1}\mathbf {b}$.

Sea $\mathbf {c} _{B}$ el vector renglón cuyos elementos son los coeficientes de la función objetivo (incluye los ceros para la variable de holgura) que corresponden a los elementos de $\mathbf {x} _{B}$. Así, el vector de la función objetivo de la solución básica $\mathbf {x} _{B}=B^{-1}\mathbf {b}$ es $\mathbf {z} =\mathbf {c} _{B}\mathbf {x} _{B}=\mathbf {c} _{B}B^{-1}\mathbf {b}$.

En el caso del conjunto de ecuaciones originales del modelo inicial aumentado, incluyendo la ecuación de la función objetivo, se puede representar como

$\left[{\begin{array}{ccc}1&-\mathbf {c} &0\\0&A&I\end{array}}\right]\left[{\begin{array}{c}\mathbf {z} \\\mathbf {x} \\\mathbf {x} _{s}\end{array}}\right]=\left[{\begin{array}{c}0\\\mathbf {b} \end{array}}\right]$

dado que $\mathbf {x} _{B}=B^{-1}\mathbf {b}$ y $\mathbf {z} =\mathbf {c} _{B}B^{-1}\mathbf {b}$ entonces

${\begin{aligned}\left[{\begin{array}{c}\mathbf {z} \\\mathbf {x} _{B}\end{array}}\right]&=\left[{\begin{array}{c}\mathbf {c} _{B}B^{-1}\mathbf {b} \\B^{-1}\mathbf {b} \end{array}}\right]\\&=\underbrace {\left[{\begin{array}{cc}1&\mathbf {c} _{B}B^{-1}\\0&B^{-1}\end{array}}\right]} _{2}\left[{\begin{array}{c}0\\\mathbf {b} \end{array}}\right]\end{aligned}}$

Premultiplicando $2$ con la expresión hallada anteriormente obtenemos

${\begin{aligned}\left[{\begin{array}{cc}1&\mathbf {c} _{B}B^{-1}\\0&B^{-1}\end{array}}\right]\left[{\begin{array}{ccc}1&-\mathbf {c} &\mathbf {0} \\0&A&I\end{array}}\right]\left[{\begin{array}{c}\mathbf {z} \\\mathbf {x} \\\mathbf {x} _{s}\end{array}}\right]&=\left[{\begin{array}{cc}1&\mathbf {c} _{B}B^{-1}\\0&B^{-1}\end{array}}\right]\left[{\begin{array}{c}0\\\mathbf {b} \end{array}}\right]\\\left[{\begin{array}{ccc}1&\mathbf {c} _{B}B^{-1}A-\mathbf {c} &\mathbf {c} _{B}B^{-1}\\0&B^{-1}A&B^{-1}\end{array}}\right]\left[{\begin{array}{c}\mathbf {z} \\\mathbf {x} \\\mathbf {x} _{s}\end{array}}\right]&=\left[{\begin{array}{c}\mathbf {c} _{B}B^{-1}\mathbf {b} \\B^{-1}\mathbf {b} \end{array}}\right]\end{aligned}}$

Está forma matricial proporciona el conjunto de ecuaciones de cualquier iteración.

Prueba de Optimalidad

Se utilizan las expresiones Matricial es $\mathbf {c} _{B}B^{-1}A-\mathbf {c}$ y $\mathbf {c} _{B}B^{-1}$ para calcular los coeficientes de las variables no básicas de la función objetivo. La solución $BF$ es óptima si y sólo si todos estos coeficientes son no negativos.

Véase también

• George Dantzig
• Investigación de Operaciones
• Programación lineal
• Conjetura de Hirsch

Enlaces externos

• Algoritmo Simplex Método Simplex paso a paso
• PHPSimplex Programa para resolver problemas con el Método Simplex desarrollado por alumnos de Ingeniería de Telecomunicaciones. Universidad de Málaga, UMA
• Ejercicios resueltos utilizando el Método Simplex Módulo de resolución para resolver modelos de Programación Lineal utilizando el Método Simplex
• Ejemplos clásicos resueltos por el Método Simplex.

Notas

• Datos: Q134164
• Multimedia: Simplex algorithm / Q134164