Usuario:Heinrich Puschmann/Algoritmo Símplex (Borrador)

Este artículo se refiere a los algoritmos Símplex de la optimización lineal. Para el algoritmo de Nelder-Mead, véase en ese lugar.
Artículo publicado (desplazar hacia "Algoritmo Símplex")

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

Ejemplo gráfico de la solución óptima

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 se busca el máximo de una función lineal sobre un conjunto de variables que satisfaga un conjunto de inecuaciones lineales. Un algoritmo Símplex es un caso particular de algoritmo de pivote.

El primero de estos algoritmos fue desarrollado por el matemático norteamericano George Dantzig en 1947, y procede examinando vértices adyacentes del poliedro de soluciones. En la revista SIAM News (Volumen 33, número 4), el método Símplex fue elegido como uno de los 10 algoritmos más importantes del siglo veinte.

Un método llamado de manera similar, pero no relacionado al anterior, es el método 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 simplex.

Preparación del problema

Aislamiento de inecuaciones

En su esencia, un algoritmo Símplex busca soluciones a un sistema de inecuaciones y ecuaciones lineales, o sea, un sistema que consiste en desigualdades e igualdades entre expresiones lineal afines de variables, por ejemplo:

${\begin{matrix}3\,x_{1}~+~4\,x_{2}~-~x_{3}&\leq &5\,x_{1}~+~8\\[3pt]1~+~3\,x_{3}&=&2\,x_{1}~+~2\,x_{2}\\[3pt]x_{2}&\geq &0\end{matrix}}$

Tal sistema se debe llevar a una forma adecuada para la aplicación del algoritmo. Agrupando los términos de igual variable, estas restricciones pueden ordenarse para dejarlas en la forma

${\begin{matrix}\ 8~+~2\,x_{1}~-~4\,x_{2}~+~~\,x_{3}&\geq &0\\[3pt]-1~+~2\,x_{1}~+~2\,x_{2}~-~3\,x_{3}&=&0\\[3pt]x_{2}&\geq &0\end{matrix}}$

Procedemos ahora a separar las restricciones en igualdades, cuyo manejo es bien conocido, y en inecuaciones en su forma más simple posible, que son condiciones de nonegatividad de variables:

${\begin{matrix}x_{4}&=&~8&+~2\,x_{1}&-~4\,x_{2}&+~x_{3}\\[3pt]x_{5}&=&-1&+~2\,x_{1}&+~2\,x_{2}&-~3\,x_{3}\end{matrix}}$

${\begin{matrix}x_{1}\in \mathbb {R} ,\ x_{2}\geq 0,\ x_{3}\in \mathbb {R} ,\ x_{4}\geq 0,\ x_{5}=0\end{matrix}}$

Para problemas no demasiado grandes, ésta es una forma adecuada para implementar el algoritmo Símplex en el computador. Sin embargo, para fines teóricos y para ilustrar mejor los pasos del algoritmo, el problema se puede llevar también a una forma más simétrica, donde todas las variables deben cumplir las mismas condiciones de nonegatividad, $x_{k}\geq 0$.

Forma estándar diccionario

En un sentido minimalista, las especificaciones "y ecuaciones", "e igualdades" podrían omitirse, ya que toda igualdad entre dos expresiones puede sustiuirse de manera trivial por dos desigualdades, obteniendose un sistema de inecuaciones solamente. Para permitir que variables básicas nulas como $x_{5}$ tomen valores nonegativos, se duplican las ecuaciones correspondientes en el sistema:

${\begin{matrix}x_{5}^{+}&=&-1&+~2\,x_{1}&+~2\,x_{2}&-~3\,x_{3}\\[3pt]x_{5}^{-}&=&~1&-~2\,x_{1}&-~2\,x_{2}&+~3\,x_{3}\end{matrix}}$

${\begin{matrix}x_{5}^{+}\geq 0,~x_{5}^{-}\geq 0\end{matrix}}$.

Para restringir las variables independientes libres como $x_{1},x_{3}$ a valores nonegativos, se sustituyen estas por diferencias de dos variables auxiliares:

$x_{1}~=~x_{1}^{+}~-~x_{1}^{-},\qquad \ x_{1}^{+}\geq 0,~x_{1}^{-}\geq 0$    y

$x_{3}~=~x_{3}^{+}~-~x_{3}^{-},\qquad \ x_{3}^{+}\geq 0,~x_{3}^{-}\geq 0$.

Aplicando todas estas transformaciones al ejemplo anterior se obteniene el sistema

${\begin{matrix}x_{4}&=&~8&+~2\,x_{1}^{+}&-~2\,x_{1}^{-}&-~4\,x_{2}&+~x_{3}^{+}&-~x_{3}^{-}\\[3pt]x_{5}^{+}&=&-1&+~2\,x_{1}^{+}&-~2\,x_{1}^{-}&+~2\,x_{2}&-~3\,x_{3}^{+}&+~3\,x_{3}^{-}\\[3pt]x_{5}^{-}&=&~1&-~2\,x_{1}^{+}&+~2\,x_{1}^{-}&-~2\,x_{2}&+~3\,x_{3}^{+}&-~3\,x_{3}^{-}\end{matrix}}$

${\begin{matrix}x_{1}^{+}\geq 0,\ x_{1}^{-}\geq 0,\ x_{2}\geq 0,\ x_{3}^{+}\geq 0,\ x_{3}^{-}\geq 0,\\x_{4}\geq 0,\ x_{5}^{+}\geq 0,\ x_{5}^{-}\geq 0\end{matrix}}$

Con el sistema de ecuaciones e inecuaciones en esta última forma, llamada forma diccionario​, se procede a aplicar el algoritmo en su llamada "Fase 1" para encontrar una solución que satisfaga las restricciones. Como tal solución (si es que existe) habitualmente no es única, a menudo se trata de "mejorarla", continuando con una "Fase 2" del algoritmo. En ella se define una función lineal especial de las variables, llamada función objetivo, y se busca de entre todas las soluciones que cumplan con las restricciones alguna que maximice el valor de tal función objetivo.

Procedimiento general

Un algoritmo Símplex Primal en su forma más simple parte de un sistema especialmente arreglado de ecuaciones lineales, cuyas variables todas, excepto tal vez una, deben tomar valores no negativos. Para aplicar el algoritmo, el sistema de ecuaciones debe tener una forma especial, la más simple de ellas siendo la siguiente forma diccionario:​​

${\begin{matrix}z&=&f&+&d_{1}\,x_{1}&+&\cdots &+&d_{n}\,x_{n}\\[3pt]x_{n+1}&=&b_{n+1}&+&G_{n+1,1}\,x_{1}&+&\cdots &+&G_{n+1,n}\,x_{n}\\\vdots &&\vdots &&\vdots &&&&\vdots \\x_{n+m}&=&b_{n+m}&+&G_{n+m,1}\,x_{1}&+&\cdots &+&G_{n+m,n}\,x_{n}\end{matrix}}$

${\begin{matrix}\max ~z,\quad x_{1}\geq 0,\ \ldots \ x_{n+m}\geq 0,\end{matrix}}$

donde los $f,\;d_{j},\;b_{i},\;G_{i,j}$ son números reales (en la práctica casi siempre números racionales). Este formato especifica que se busca valores para las incógnitas $\,x_{1},\ldots x_{n+m},\ z\,$, que satisfagan las ecuaciones e inecuaciones del sistema anterior de modo tal que la variable objetivo $\,z$ tome el mayor valor posible.

Todo sistema de inecuaciones o ecuaciones lineales, con variables nonegativas o irrestrictas, puede siempre convertirse a la forma diccionario. Al convertir un problema a esa forma no disminuye el número de desigualdades; estas permanecen en su totalidad y sólo se convierten en condiciones de no-negatividad de algunas variables.

Definiendo los conjuntos de índices

$D=\{1,\ldots ,n\},\quad B=\{n+1,\ldots ,n+m\}$

se escribirá esto en lo que sigue de la forma más compacta

${\begin{matrix}&&z&=&f&+&\sum _{j\in D}\,d_{j}\,x_{j}\\[6pt]\forall ~i\in B&&x_{i}&=&b_{i}&+&\sum _{j\in D}\,G_{i,j}\,x_{j}\end{matrix}}$

${\begin{matrix}\max ~z\,,\quad \forall ~k\in D\cup B\quad x_{k}\geq 0\end{matrix}}$

En adición a la forma diccionario, el algoritmo Símplex requiere que se cumpla $b_{1}\geq 0,\;\ldots ,\;b_{m}\geq 0$.   Es fácil llevar un problema de optimización lineal a la forma diccionario general, donde los $b_{i}$ tienen signos arbitrarios; la dificultad reside en lograr las condiciones de factibilidad,   $b_{i}\geq 0$.

En cada iteración de un algoritmo de pivote se destaca un conjunto de variables independientes, mientras que las restantes son variables dependientes y se expresan como funciones lineales de las primeras. Al pasar de una iteración a la siguiente se intercambia una variable independiente por una dependiente; tales pares de variables se denominan pivotes.

Condiciones de optimalidad

En caso de que se cumpla la siguiente condición de optimalidad,

• $d_{j}\leq 0$  para todo  $j\in D$,

podemos obtener una solución óptima al problema anterior, asignando a las variables independientes del sistema los valores $\,x_{1}=0,\ldots ,x_{n}=0\,$. Ello es así porque las variables independientes de toda solución alternativa al problema deben tomar valores nonegativos, con lo cual esa solución alternativa satisface la relación $\,z\leq f\,$.

( Por ejemplo, en el siguiente sistema,

${\begin{matrix}z&=&~~~~0&+~3x_{1}&+~2x_{2}\\[2pt]x_{3}&=&~~~3&-~2x_{1}&-~~x_{2}\\[2pt]x_{4}&=&~~~7&-~2x_{1}&-~3x_{2}\\[2pt]x_{5}&=&~~~4&-~3x_{1}&-~~x_{2}\end{matrix}}$

las condiciones de optimalidad son violadas en ambas variables independientes, ya que  $d_{1}=+3>0$  y  $d_{2}=+2>0$.  Por tanto, no podemos descartar la posibilidad de aumentar el valor que adopta la variable objetivo  $\;z=3x_{1}+2x_{2}\;$  eligiendo conjuntos de variables independientes como $x_{1}=1,\;x_{2}=0$.)

Transformación de las ecuaciones

En el caso habitual de que las condiciones de optimalidad no se cumplan, puede reformularse el sistema de ecuaciones, eligiendo adecuadamente un nuevo subconjunto $\,B\,$ de entre las $\,n+m\,$ incógnitas, y expresando las incógnitas elegidas en función de las incógnitas restantes.  Sea $x_{\pi (1)},~\ldots ,~x_{\pi (n+m)}$ un reordenamiento de las variables. A partir de los conjuntos de índices

$D(\pi )=\{\;\pi (1),\ldots ,\pi (n)\;\},\quad B(\pi )=\{\;\pi (n+1),\ldots ,\pi (n+m)\;\},$

que dividen las variables del sistema en variables independientes $x_{j}$ con $j\in D(\pi )$ y las llamadas variables básicas $x_{i}$ con $i\in B(\pi )$, se construye entonces el sistema:

${\begin{matrix}&&z&=&f^{\pi }&+&\sum _{j\in D(\pi )}\,d_{j}^{\pi }\,x_{j}\\[6pt]\forall ~i\in B(\pi )&&x_{i}&=&b_{i}^{\pi }&+&\sum _{j\in D(\pi )}\,G_{i,j}^{\pi }\,x_{j}\end{matrix}}$

${\begin{matrix}\max ~z\,,\quad \forall ~k\in D\cup B\quad x_{k}\geq 0\end{matrix}}$

Nótese que coeficientes como $G_{i,j}^{\pi }$ existen sólo para pares de subíndices con $i\in B(\pi )$ y con $j\in D(\pi )$. En cada iteración, los coeficientes del sistema así modificado vuelven a examinarse para ver si satisfacen las condiciones de optimalidad

• $d_{j}^{\pi }\leq 0$  para todo  $j\in D(\pi )$,

y de este modo generan una posible solución al problema. Un resultado estándar de la Programación Lineal establece que todo problema que tiene soluciones óptimas también posee un conjunto de variables básicas que genera a una de ellas.​​ Si los coeficientes del sistema satisfacen las condiciones de optimalidad, se dice que las variables básicas forman una base optimal del problema.

Elección de los pivotes

Un coeficiente no nulo $\,G_{rs}^{\pi }\neq 0\,$ del sistema de ecuaciones se llama elemento pivote, porque permite despejar la variable independiente $\,x_{s}\,$ en lugar de la variable básica $\,x_{r}\,,$ para así seguir buscando una solución al problema. Sin embargo, un algoritmo Símplex primal de no eligen un elemento pivote cualquiera, sino solamente aquellos que garanticen los siguiente dos objetivos:

• La solución básica generada por el nuevo sistema debe tener un valor objetivo $f^{\pi \prime }$ no inferior al del sistema anterior. Para que ello se cumpla se elige algún $x_{s},\;s\!\in \!D(\pi )$ con $d_{s}^{\pi }>0$. Si no existe tal coeficiente, el sistema obtenido es optimal y genera uns solución básica óptima.
• El nuevo sistema es factible, es decir, también satisface $b^{\pi \prime }\geq 0$. Para que ello se cumpla se elige algún $x_{r},\;r\!\in \!B(\pi )$ con $b_{r}^{\pi }/(-G_{rs}^{\pi })~=~\min\{b_{i}^{\pi }/(-G_{is}^{\pi })~|~G_{is}^{\pi }<0\}$. Si no existe ningún $G_{is}^{\pi }<0$ el problema tiene valores objetivos arbitrariamente grandes por lo que no hay solución óptima.

( En el ejemplo anterior,

${\begin{matrix}z&=&~~~~0&+~3x_{1}&+~2x_{2}\\[2pt]x_{3}&=&~~~3&-~2x_{1}&-~~x_{2}\\[2pt]x_{4}&=&~~~7&-~2x_{1}&-~3x_{2}\\[2pt]x_{5}&=&~~~4&-~3x_{1}&-~~x_{2}\end{matrix}}$

podemos elegir la variable independiente $x_{1}$ para ser despejada, por cumplirse $d_{1}=3>0$, ó también la variable independiente $x_{2}$ por cumplirse $d_{2}=2>0$. En caso de elegir $x_{1}$, esa variable debe obligadamente sustituír a la variable básica $x_{5}$, ya que $b_{5}/(-G_{51})=\min\{b_{3}/(-G_{31})=3/2,b_{4}/(-G_{41})=7/2,b_{5}/(-G_{51})=4/3\}$.)

Las reglas según las cuales el pivote es elegido dependen del algoritmo Símplex particular. La elección descrita impide que en dos iteraciones sucesivas se elija el mismo pivote. No obstante, es posible la existencia de ciclos más largos, y debe imponerse que el algoritmo termine en un número finito de pasos, lo que no sucede con una elección de pivotes inadecuada.

Como se puede observar de las definiciones anteriores, una base optimal no tiene pivotes admisibles, por lo que el algoritmo no puede ser continuado a partir de una base optimal. Por otro lado, es fácil demostrar con argumentos similares a los expuestos que una base no optimal sin pivotes admisibles siempre pertenece a un problema sin solución; sea esto, porque el sistema de ecuaciones e inecuaciones no tiene solución alguna (problema infactible), o porque existen soluciones con un valor objetivo $z\,$ arbitrariamente grande (problema no acotado).

Cuadros Símplex

Considerar un problema de programación lineal,

maximizar $z=\mathbf {c} ^{T}\mathbf {x}$

sujeto a $\mathbf {A} \mathbf {x} \leq \mathbf {b} ,\,\mathbf {x} \geq 0$

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 de pivotes 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 esta de excedente y hay que quitar para convertirla en igualdad; en caso se maneje el =, se manejan las variables artificiales.

Ejemplo de algoritmo Símplex

En el siguiente ejemplo buscamos valores no negativos para las variables $\,x_{1}\geq 0,\ldots \ x_{5}\geq 0\,$ que satisfagan el sistema de ecuaciones

${\begin{matrix}z&=\!\!&~~~0&+~3\,x_{1}&+~2\,x_{2}\\[2pt]\,\,x_{3}&=\!\!&~~~3&-~2\,x_{1}&-~~\,x_{2}\\[2pt]x_{4}&=\!\!&~~~7&-~2\,x_{1}&-~3\,x_{2}\\[2pt]x_{5}&=\!\!&~~~4&-~3\,x_{1}&-~~\,x_{2}\end{matrix}}$

de modo que la variable adicional $z\,$, llamada variable objetivo, alcance el máximo valor posible. El sistema presentado aquí ya tiene la forma de diccionario y es factible, es decir satisface $\forall ~i\!\in \!B~~b_{i}\geq 0$, por lo que podemos obviar la búsqueda de un sistema inicial adecuado, y proceder directamente a aplicar un algoritmo Símplex Primal propiamente tal. Usaremos para ello las reglas de Bland​ para elegir el pivote en cada uno de los pasos:

1. Elija el menor $s\in D(\pi )$ que satisfaga $d_{s}^{\pi }>0$.   (Otros algoritmos Símplex eligen siempre algún $s\in D(\pi )$ que satisfaga esa propiedad)
2. Elija el menor $r\in B(\pi )$ que satisfaga $b_{r}^{\pi }/(-G_{r,s}^{\pi })=\min {}_{i\in B(\pi )}\{b_{i}^{\pi }/(-G_{i,s}^{\pi })~|~G_{i,s}^{\pi }<0\}$.   (Otros algoritmos Símplex eligen siempre algún $r\in B(\pi )$ que satisfaga esa propiedad)

Para no incurrir en errores de redondeo, trabajaremos en lo que sigue con números enteros, y evitaremos dividir por el coeficiente de las variables despejadas en los sistemas de ecuaciones. Habrá casos en que alguna de las ecuaciones se pueda simplificar dividiéndola por un factor común, pero no es aconsejable hacer esto, sino llevar un mismo denominador común para todos los coeficientes del sistema. De este modo, las divisiones que figuran en las transformaciones sucesivas darán siempre resultados enteros.​​

El siguiente esquema muestra cómo cambian los coeficientes de un sistema de ecuaciones al pasar de una iteración a la siguiente:

${\begin{matrix}\delta \,x_{i}&\!=\!&(~~\alpha )&\!\!\!x_{j}&\!+\!&(~~\sigma )&\!\!\!x_{s}\\[6pt]\delta \,x_{r}&\!=\!&(~~\zeta )&\!\!\!x_{j}&\!+\!&(~~p)&\!\!\!x_{s}\end{matrix}}$

${x_{r}\leftrightarrow x_{s}}$

${\begin{matrix}p\,x_{i}&\!=\!&(\textstyle {\frac {\alpha p\,-\,\zeta \sigma }{\delta }})&\!\!\!x_{j}&\!+\!\!&(~\sigma )&\!\!\!x_{r}\\[6pt]p\,x_{s}&\!=\!&(~-\zeta ~)&\!\!\!x_{j}&\!+\!\!&(~\delta )&\!\!\!x_{r}\\\end{matrix}}$

En este esquema, el símbolo $\delta$ es el único y común denominador del sistema de ecuaciones, el símbolo $p\,$ es el numerador del elemento pivote, el símbolo $\zeta \,$ representa cualquier otro coeficiente correspondiente a la ecuación de la variable básica del pivote, el $\sigma \,$ representa cualquier otro coeficiente que multiplica la variable independiente que corresponde al pivote, y $\alpha \,$ representa cualquiera de los coeficientes restantes. Los coeficientes de la función a maximizarse ($x_{i}\!=\!z\,$) y de los términos constantes del sistema ($x_{j}\!=\!1\,$) se modifican de la misma manera.

El sistema de ecuaciones inicial del ejemplo es

${\begin{matrix}1\,z\,~&=&~~~0&\mathbf {+~3\,x_{1}} &+~2\,x_{2}&\qquad &d_{1}=3>0\qquad \qquad \\[2pt]1\,x_{3}&=&~~~3&-~2\,x_{1}&-~~\,x_{2}&\qquad &b_{3}/(-G_{3,1})=3/2=1.500\\[2pt]1\,x_{4}&=&~~~7&-~2\,x_{1}&-~3\,x_{2}&\qquad &b_{4}/(-G_{4,1})=7/2=3.500\\[2pt]1\,x_{5}&=&~~~4&{\underline {\mathbf {-~3\,x_{1}} }}&-~~\,x_{2}&\qquad &b_{5}/(-G_{5,1})=4/3={\underline {1.333}}\end{matrix}}$

Para el sistema de ecuaciones inicial, un algoritmo Símplex Primal admite dos pivotes posibles: despejar la variable independiente $\,x_{1}\,$ en lugar de la variable básica $\,x_{5}$, o bien despejar la variable $\,x_{2}\,$ en lugar de la variable $\,x_{4}$. Sin embargo, la regla de Bland prescribe que elijamos la primera de estas alternativas, por contener esta la variable independiente con subíndice menor que la segunda. De ese modo se obtiene un nuevo sistema

${\begin{matrix}3\,z\,&=&~~12&-~3\,x_{5}&\mathbf {+~3\,x_{2}} &\qquad &d_{2}^{\pi }=3>0\qquad \qquad \\[2pt]3\,x_{3}&=&~~~1&+~2\,x_{5}&\,{\underline {\mathbf {-~~\,x_{2}} }}&\qquad &b_{3}^{\pi }/(-G_{3,2}^{\pi })=1/1={\underline {1.000}}\\[2pt]3\,x_{4}&=&~~13&+~2\,x_{5}&-~7\,x_{2}&\qquad &b_{4}^{\pi }/(-G_{4,2}^{\pi })=13/7=1.857\\[2pt]3\,x_{1}&=&~~~4&-~~\,x_{5}&-~~\,x_{2}&\qquad &b_{1}^{\pi }/(-G_{1,2}^{\pi })=4/1=4.000\end{matrix}}$

En este sistema el único pivote posible para un algoritmo Símplex Primal consiste en despejar la variable independiente $\,x_{2}\,$ en lugar de la variable básica $\,x_{3}\,$. El nuevo sistema obtenido es

${\begin{matrix}1\,z\,&=&~~~5&\,\mathbf {+~~\,x_{5}} &-~3\,x_{3}&\qquad &d_{5}^{\pi }=1>0\qquad \qquad \\[2pt]1\,x_{2}&=&~~~1&+~2\,x_{5}&-~3\,x_{3}&\qquad &G_{2,5}^{\pi }=2\not <0\qquad \qquad \\[2pt]1\,x_{4}&=&~~~2&{\underline {\mathbf {-~4\,x_{5}} }}&+~7\,x_{3}&\qquad &b_{4}^{\pi }/(-G_{4,5}^{\pi })=2/4={\underline {0.500}}\\[2pt]1\,x_{1}&=&~~~1&-~~\,x_{5}&+~~\,x_{3}&\qquad &b_{1}^{\pi }/(-G_{1,5}^{\pi })=1/1=1.000\end{matrix}}$

Aquí el sistema de ecuaciones nuevamente presenta un único pivote posible, que consiste en cambiar la variable independiente $\,x_{5}\,$ por la variable básica $\,x_{4}\,$. Ahora obtenemos el sistema

${\begin{matrix}4\,z\,&=&~~22&-~~\,x_{4}&-~5\,x_{3}\\[2pt]4\,x_{2}&=&~~~8&-~2\,x_{4}&+~2\,x_{3}\\[2pt]4\,x_{5}&=&~~~2&-~~\,x_{4}&+~7\,x_{3}\\[2pt]4\,x_{1}&=&~~~2&+~~\,x_{4}&-~3\,x_{3}\end{matrix}}$

Este sistema de ecuaciones es optimal, y los valores de las variables en la solución óptima correspondiente son

$z=22/4=5.5\,,$   $x_{1}=2/4=0.5\,,$  $x_{2}=8/4=2.0\,,$  $x_{3}=0,$  $x_{4}=0,$  $x_{5}=2/4=0.5\,.$

Formas alternativas de presentación

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.

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 restricciones son del tipo ≤.

- Las variables de decisión son mayores o iguales a cero.

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

- La función objetivo es minimizada.

- Las restricciones son de tipo ≥.

- Las variables de decisión son mayores o iguales a cero.

Modelo Ampliado

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

[Introducir un ejemplo con ecuaciones en este lugar]

Conceptos varios

Tabla Símplex: Es una de varias estructuras de datos posibles que contiene los coeficientes de un sistema de pivoteo.

Variable de entrada: Es la variable independiente que se despeja en cada iteración y con ello se convierte en variable básica. En la primera iteración del ejemplo anterior, la variale de entrada es $x_{1}$.

Variable de salida: Es la variable básica que se sustituye por una variable independiente en cada iteración y se convierte en independiente ella misma. En la primera iteración del ejemplo anterior, la variale de entrada es $x_{5}$.

Base: Es el conjunto de las variables básicas. En la primera iteración del ejemplo anterior, la base está formada por las variables en $\{x_{3},x_{4},x_{5}\}$.

Solución básica: Es la solución que se obtiene a partir de un sistema de pivoteo cuando las variables independientes adopten el valor cero. Corresponde a un vértice del conjunto de soluciones que satisfacen las restricciones del problema.

Solución básica degenerada: Es una solución básica con una variable básica igual a cero. Corresponde a un vértice sobredefinido del conjunto de soluciones del problema, en el sentido de que por él pasan más planos delimitadores que los estrictamente necesarios.

Variable libre o no restringida: Es una variable en la formulación original del problema que puede tomar cualquier valor real, y no está restringida a valores nonegativos. A excepción de la variable objetivo, variables libres no pueden aparecer en la forma diccionario de un problema, ni en otras formas estándar. Una manera de eliminarlas es sustituyéndo un $x_{j}$ libre por $x_{j}^{\prime }-x_{j}^{\prime \prime },~x_{j}^{\prime }\geq 0,~x_{j}^{\prime \prime }\geq 0$.

Variable artificial : Es una variable que no figura en la formulación original del problema, y que se introduce para dar al problema una forma canónica, como por ejemplo la forma diccionario. Estas variables se usan a menudo en una fase 1 del algoritmo, para obtener una sistema factible inicial.

Función objetivo: Es la función lineal afín que define la variable objetivo, es decir una variable que se maximiza (o minimiza). A menudo representa el beneficio (o el costo) de algún proyecto.

Solución óptima: Satisface todas las restricciones si se evalúa en ellas, y (en el caso de maximización) hace que el valor de la variable objetivo $z$ sea el máximo posible de entre todas las soluciones factibles.

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 un sistema de pivoteo optimal este debe tener alguna variable independiente con coeficiente nulo en la función objetivo; sin embargo, tal requisito es sólo necesaria y no suficiente.

Véase también

• Programación lineal
• Algoritmo de pivote
• George Dantzig
• Conjetura de Hirsch

Enlaces externos

• 10 cosas que necesitas saber sobre el Método Simplex
• Tutoriales y Artículos del Método Simplex
• PHPSimplex Programa para resolver problemas con el Método Simplex desarrollado por alumnos de Ingeniería de Telecomunicaciones. Universidad de Málaga, UMA
• Actualización en Wikipedia del Método Simplex Conceptos y ejemplo elaborado por alumnos de la Licenciatura en Matemáticas Aplicadas y Computación. FES Acatlán UNAM.
• A2 Actualización en Wikipedia del Método Simplex Conceptos y ejemplo elaborado por alumnos de la Licenciatura en Matemáticas Aplicadas y Computación. FES Acatlán UNAM.
• 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.

• Ejemplo del método simplex Conceptos y ejemplo elaborado por alumnos de la Licenciatura en Matemáticas Aplicadas y Computación. FES Acatlán UNAM.
• Conceptos y Ejemplo del Método Simplex aplicado a un problema de programación lineal. Documento elaborado por estudiantes de la carrera de Matemáticas aplicadas y computación. FES Acatlán UNAM.

• Conceptos y ejemplo del Método Simplex Conceptos y ejemplo elaborado por alumnos de la Licenciatura en Matemáticas Aplicadas y Computación. FES Acatlán UNAM.