Método Simplex Dual en Programación Lineal (Ejercicios Resueltos)

El Método Simplex Dual nos ofrece una alternativa algorítmica para abordar la resolución de modelos de Programación Lineal. En particular este método se puede utilizar cuando luego de llevar a la forma estándar un modelo de Programación Lineal no se dispone de una solución básica factible inicial con la cual se pueda dar inicio a las iteraciones del algoritmo. En este contexto a continuación se presenta un ejemplo con los detalles de la aplicación de este procedimiento.

Ejemplo del Método Simplex Dual

Consideremos el siguiente problema para ilustrar sobre la aplicación del Método Simplex Dual:

ejemplo-simplex-dual

Para llevar el problema anterior a la forma estándar se requiere agregar 2 variables de exceso no negativas para la restricción 1 y 2, que llamaremos respectivamente X4 y X5. De esta forma el problema en su formato estándar queda definido por:

forma-estandar-simplexdual

Luego construimos la tabla inicial del Método Simplex:

t1-simplex-dual

¿Cómo continuar con las iteraciones del Método Simplex?. Antes de ello es necesario disponer de una solución básica factible inicial. En este contexto si quisiéramos usar X4 y X5 como variables básicas (y en consecuencia X1, X2 y X3 como variables no básicas) se requiere que X4 y X5 sean mayores o iguales a cero, sin embargo, sus coeficientes en las respectivas filas son negativos y por tanto no se dispone de la identidad (matriz con «1» como diagonal y el resto de coeficientes igual a cero).

En consecuencia para formar la identidad podemos multiplicar por «-1» la fila 1 y 2, obteniendo lo siguiente:

t2-simplex-dual

En la tabla anterior se tiene una solución básica (infactible en las variables primales), pero al tener costos reducidos no negativos esto define una solución básica factible en el dual.

Ahora X4 y X5 son variables básicas y adoptan los valores de -1 y -3/2, respectivamente, lo que claramente no satisface las condiciones de no negatividad para las variables de decisión, es decir, no corresponde a una solución básica factible.

Sin embargo, en esta instancia podemos aplicar el Método Simplex Dual como alternativa de resolución. Para ello seleccionaremos una variable que deje la base y adoptaremos como criterio de selección aquella variable básica asociada al lado derecho «más negativo» (con esto se busca favorecer la rapidez de convergencia).

En el ejemplo dicha variable es X5. Luego para determinar que variable entra a la base realizamos un mínimo cuociente entre el negativo del costo reducido de las variables no básicas y las entradas estrictamente menores a cero para las variables no básicas en la fila 2 (fila asociada al lado derecho más negativo).

Es decir: Min{-160/-2; -120/-2; -280/-2}=60 ==> el cuociente mínimo se alcanza en la segunda columna asociada a la variable no básica X2, por tanto dicha variable entra a la base.

En cada iteración del Método Simplex Dual se escoge un lado derecho con valor negativo, identificando la respectiva variable básica primal, quien deja la base.

Finalmente se realiza una iteración realizando las operaciones filas que sean necesarias, de modo de ingresar X2 a la base al mismo tiempo que X5 deja la base. Los resultados serían:

t3-simplex-dual-v3

Notar que ahora las variables básicas son X4 y X2 donde sólo X4=-1/4 lo que no satisface la condición de ser una solución básica factible. Por lo tanto realizamos una nueva iteración, en este caso sacando de la base a la variable X4 y calculamos el mínimo cuociente: Min{-40/-1; -160/-3; -60/-1/2}=40 ==> el cuociente mínimo está en la primera columna por tanto la variable X1 entra a la base.

En consecuencia se actualiza la tabla quedando lo siguiente:

t4-simplex-dual

Las variables básicas ahora son X1=1/4 y X2=1/2 (que cumplen las condiciones de no negatividad). Adicionalmente el costo reducido de las variables no básicas también es mayor o igual a cero, por tanto estamos frente a la solución óptima del problema.

Se puede reconocer adicionalmente que el valor óptimo es V(P)=100 que se obtendría al evaluar la solución óptima del problema en la función objetivo, sin embargo, en el procedimiento dicho valor se obtiene con signo cambiado.

El ejemplo anterior nos permitió apreciar cómo a través del Método Simplex Dual se puede abordar la resolución de un modelo de Programación Lineal que luego de ser llevado a la forma estándar no provee una solución básica factible inicial.

Cabe destacar que el Método Simplex Dual que no es la única alternativa algorítmica a la cual podemos recurrir para resolver el problema propuesto. Por ejemplo, podríamos haber alcanzado idénticos resultados aplicando el Método Simplex de 2 Fases con algo más de trabajo.

Alternativamente podríamos definir el modelo dual al problema propuesto y resolverlo por el Método Simplex para posteriormente utilizar las condiciones del Teorema de Holguras Complementarias.

En resumen ante un modelo de optimización contamos con varias alternativas de resolución y es deber de quien resuelve evaluar los distintos caminos en términos de su complejidad y representación.

Programas del Método Simplex para una calculadora Texas Instruments

Luego de publicar un artículo sobre Cómo instalar una aplicación del Método Simplex en una calculadora HP 48 hemos recibido varias consultas respecto a cómo instalar el Método Simplex en una calculadora marca Texas Instruments (conocidas popularmente como TI).

En el siguiente artículo nos referiremos a esto recomendándote dónde adquirir una calculadora TI (en caso que no dispongas de una de ellas) y qué debes hacer para descargar un programa del Método Simplex compatible con tu calculadora.

Por supuesto se requiere en primer instancia disponer de una calculadora TI. La pregunta que sigue es ¿cuál es la mejor calculadora para mi caso?. Esta no es una pregunta fácil de responder pero claramente dependerá de para qué la queremos, es decir, qué tipo de cálculos y operaciones deseamos llevar a cabo con ella. Muchas veces (al igual que nuestro cerebro) utilizamos la calculadora sólo a una pequeña fracción de su máximo potencial y aún sabiendo bien para qué la queremos tomar una decisión sobre cuál comprar no es fácil.

En nuestra experiencia docente hemos podido verificar que actualmente los modelos más populares de calculadoras Texas Instruments son TI-89 Titanium y TI Voyage 200 las cuales puedes comprar buscando por el modelo de tu interés en Mercadolibre


TI-mercadolibre

También puedes ver las ofertas de calculadoras Texas Instruments en

¿Dónde buscar programas del Método Simplex compatibles con una calculadora Texas Instruments?

Te recomendamos utilizar la herramienta de búsqueda en TICalc.org utilizando la palabra «Simplex«. De esta forma puedes obtener resultados relevantes tanto en español como inglés.

simplex-ti

A la fecha de este artículo han encontrado 23 programas sobre el Método Simplex. Los resultados de la búsqueda están ordenados por la evaluación de los propios usuarios («Score»).

simplex-en-ti

La recomendación es sencilla. Descarga e instala algunas versiones del programa y pruébalos con un ejemplo de Programación Lineal sencillo del cual conozcas su solución. De esta forma podrás escoger el que consideres más confiable y sencillo.

La mayoría de los programas viene con un archivo de texto con las instrucciones paso a paso para la instalación. Recuerda eso sí de verificar que al seleccionar uno de ellos el programa sea compatible para tu calculadora TI. Por ejemplo, el programa «SIMPLEX v.2.02 (English/Spanish)» (marcado con color rojo en la imagen anterior) es compatible para la calculadora TI-89 Titanium.

categoria-ti

A continuación unas capturas de pantalla de esta versión del programa «SIMPLEX v.2.02 (English/Spanish)» para resolver un modelo de Programación Lineal con el Método Simplex:

pantalla-simplex-ti

Cómo instalar una aplicación del Método Simplex en una calculadora HP 48

En el siguiente tutorial te mostraremos cómo instalar una aplicación del Método Simplex a tu calculadora Hewlett-Packard (en adelante HP) de la serie HP 48G, HP 48G+, HP 48GX, HP 48S, HP 48SX. Esto es de gran ayuda cuando se intenta resolver un modelo de Programación Lineal que es no trivial y que por tanto requiere de un número importante de iteraciones o cálculos tediosos.

Si bien el principal objetivo de este tutorial es instalar un programa en tu calculadora sobre el Método Simplex, los pasos descritos te permiten incorporar otro tipo de programas útiles para tus estudios.

¿Qué necesitas?

1.- Una calculadora HP de alguno de los siguientes modelos: HP 48G, HP 48G+, HP 48GX, HP 48S, HP 48SX. Si no tienes una puedes comprar una de forma económica aquí:

48series

2.- Un cable serial para conectar la calculadora con tu computador:

cable-hp-48g

3.- Un conector que convierte un serial DB9 (Adaptador de 9 pines) a USB:

rs232-a-usb

4.- Kit de Conectividad de la Calculadora HP 48G, HP 49G y HP 50G serie. Este programa te permitirá traspasar información y programas desde tu computador a tu calculadora y viceversa. Descárgalo gratuitamente desde HPcalc.org.

Importante: Puedes reemplazar el cable serial para conectar la calculadora a tu computador y el conector que convierte un serial RS232 a USB por un único cable de conexión que te permite conectar directamente tu calculadora al computador.

usb-a-hp-48g

Instalar el Kit de Conectividad en tu Computador

Ejecuta el archivo “conn4x_english.exe” y sigue los sencillos pasos del instalador.

programa-conectividad-hp

Una vez instalado el programa en tu computador podrás traspasar programas e información desde tu computador a tu calculadora HP 48 como viceversa. Todos los aspectos relativos a la conexión están cubiertos con bastante detalle y de forma muy sencilla en el menú Ayuda del Kit de Conectividad en la sección «Contenido e Indice».

ayuda-kit-hp48

Para instalar en tu calculadora una aplicación del Método Simplex que sea compatible con tu calculadora de la serie HP 48 te recomendamos buscar alguna alternativa que te acomode en HPCalc.org filtrando por el modelo y utilizando como criterio de búsqueda «Simplex». De esta forma te aseguras de obtener resultados pertinentes no sólo en español.

simplex-hpcal

Luego selecciona uno de los programas del listado y sigue con detalle los pasos para la instalación. Como los programas son gratuitos puedes intentar instalar varios de ellos y finalmente utilizar el que más te acomode. Cuéntanos tu experiencia utilizando alguno de estos programas!.

simplexpy

Cómo detectar que un Problema es No Acotado con el Método Simplex

El Método Simplex es un algoritmo que nos permite resolver modelos de Programación Lineal que en ciertas ocasiones permite identificar casos excepcionales como infinitas soluciones óptimas o que el problema es no acotado. En este contexto el Método Simplex rescata las condiciones establecidas en el Teorema Fundamental de la Programación Lineal.

En la aplicación del Método Simplex, un problema no acotado se detecta cuando en una iteración cualquiera existe una variable no básica con costo reducido negativo y todos los elementos en la columna de dicha variable son negativos o cero. Es decir, no se puede seleccionar un pivote para determinar la variable que debe dejar la base.

Consideremos el siguiente modelo de Programación Lineal:

modelo lineal no acotado

Si resolvemos gráficamente dicho modelo nos podemos percatar que éste es no acotado. Notar que el dominio de soluciones factibles (área sombreada o achurada) es no acotado dado que crece indefinidamente en la dirección de la variable X2.

Las curvas de nivel de la función objetivo crecen a su mayor tasa en la dirección del vector gradiente \triangledown f(X_{1},X_{2})=(4,6) lo que indica que se podría desplazar indefinidamente en esa dirección y siempre interceptar el dominio de soluciones factibles.

problema no acotado

¿Cómo podemos detectar esta situación (Problema No Acotado? utilizando el Método Simplex?

Para ello llevamos el modelo a su forma estándar, agregando X3 y X4 como variables de holgura de la restricción 1 y 2, respectivamente. Lo anterior define la siguiente tabla inicial del método:

método simplex no acotado

Notar que X2 es la variable no básica con el costo reducido más negativo y siguiendo ese criterio debería ser aquella que ingresamos a la base. Sin embargo, no es factible hacer el criterio de factibilidad o mínimo cuociente debido a que los elementos en la columna de X2 son negativos o cero. En esta instancia ya se puede afirmar que el problema es no acotado.

Observación: Se puede verificar que si seleccionamos X1 como la variable que entra a la base y se aplica una iteración del Método Simplex se llegara a una conclusión similar a la presentada anteriormente.

Cómo detectar Infinitas Soluciones con el Método Simplex

Una de las posibilidades a las que nos podemos enfrentar cuando resolvemos un modelo de Programación Lineal a través del Método Simplex es el caso de múltiples o infinitas soluciones óptimas.

Esto significa que existe un tramo de soluciones factibles que reportan idéntico valor para la función objetivo y que no es posible mejorar.

En este contexto si luego de aplicar las iteraciones que resulten necesarias por el Método Simplex a un modelo de Programación Lineal (tabla óptima o tableau óptimo) se verifica que una variable no básica óptima tiene costo reducido igual a cero, esto permitirá afirmar que estamos ante el caso de infinitas soluciones.

Ejemplo Infinitas Soluciones Óptimas Método Simplex

Consideremos el siguiente modelo de Programación Lineal:

Modelo de Programación Lineal

Llevamos el modelo a su forma estándar para proceder con la aplicación del Método Simplex, con S1 y S2 como variables de holgura de la restricción 1 y 2, respectivamente.

Formato Estandar

La tabla inicial con S1 y S2 como variables básicas iniciales es:

Tabla Inicial Método Simplex

Y entra a la base. Luego para determinar la variable que deja la base utilizamos el criterio del mínimo cuociente: Min {12/4 ; 16/3} = 3 ==> S1 deja la base. Con esta información actualizamos la tabla realizando operaciones fila:

Infinitas Soluciones

Luego de una iteración encontramos la solución óptima, donde Y y S2 son variables básicas. La solución básica factible óptima es X=0 Y=3 S1=0 S2=7. El valor óptimo es V(P)=6.

Notar que X (variable no básica) tiene costo reducido igual a cero lo que determina la existencia de múltiples o infinitas soluciones óptimas, de modo que la solución actual es uno de los vértices óptimos.

El siguiente diagrama muestra la Resolución Gráfica del problema con el software Geogebra donde la solución óptima que hemos encontrado en la aplicación del Método Simplex corresponde al vértice B.

Notar que la línea punteada de color azul corresponde a una curva de nivel de la función objetivo que tiene la misma pendiente que la restricción 1 (pendiente -1/2).

Grafico Infinitas Soluciones Optimas

¿Cómo podemos obtener el vértice C que es solución óptima a través del Método Simplex? Una alternativa sería forzando la entrada a la base de la variable X en la tabla óptima. Luego calculamos cuál de las actuales variables básicas deja la base según el criterio del mínimo cuociente: Min {3/1/2 ; 7/5/2} = 14/5 ==> S2 deja la base. Actualizando la tabla obtenemos:

Infinitas Soluciones Caso 2

La nueva solución óptima (con idéntico valor óptimo) es X=14/5 Y=8/5 S1=0 S2=0, que corresponde al vértice C en el gráfico anterior. Ahora la variable no básica S2 tiene costo reducido igual a cero en la tabla óptima que señala el caso de múltiples soluciones óptimas (en este ejemplo el tramo BC).