método simplex Archivos - Gestión de Operaciones

Programación Lineal (Método Gráfico)

El Método Gráfico (resolución gráfica) constituye una excelente alternativa de representación y resolución de modelos de Programación Lineal que tienen 2 variables de decisión. Para estos efectos existen herramientas computacionales que facilitan la aplicación del método gráfico como los softwares TORA, IORTutorial y Geogebra, los cuales se pueden consultar en detalle en Cómo Resolver Gráficamente un Modelo de Programación Lineal con TORA, Cómo Resolver Gráficamente un Modelo de Programación Lineal con IORTutorial y Cómo Resolver Gráficamente un modelo de Programación Lineal con Geogebra, respectivamente. En este contexto a continuación presentamos un compendio de ejercicios de Programación Lineal resueltos a través del método gráfico.

Ejercicios Resueltos del Método Gráfico en Programación Lineal

Ejercicio N°1: Una empresa vitivinícola ha adquirido recientemente un terreno de 110 hectáreas. Debido a la calidad del sol y el excelente clima de la región, se puede vender toda la producción de uvas Sauvignon Blanc y Chardonay. Se desea conocer cuánto plantar de cada variedad en las 110 hectáreas, dado los costos, beneficios netos y requerimientos de mano de obra según los datos que se muestran a continuación:

Suponga que se posee un presupuesto de US$10.000 y una disponibilidad de 1.200 días hombre durante el horizonte de planificación. Formule y resuelva gráficamente un modelo de Programación Lineal para este problema. Detalle claramente el dominio de soluciones factibles y el procedimiento utilizado para encontrar la solución óptima y valor óptimo.

Variables de Decisión:

$X_{1}$ : Hectáreas destinadas al cultivo de de Sauvignon Blanc
$X_{2}$ : Hectáreas destinadas al cultivo de Chardonay

Función Objetivo:

Maximizar $50X_{1}+120X_{2}$

Restricciones:

$X_{1}+X_{2}\leq 110$
$100X_{1}+200X_{2}\leq 10.000$
$10X_{1}+30X_{2}\leq 1.200$
$X_{1},X_{2}\geq 0$

Donde las restricciones están asociadas a la disponibilidad máxima de hectáreas para la plantación, presupuesto disponible, horas hombre en el período de planificación y no negatividad, respectivamente.

El siguiente gráfico muestra la representación del problema de la empresa vitivinícola. El área achurada corresponde al dominio de soluciones factibles, donde la solución básica factible óptima se alcanza en el vértice C, donde se encuentran activas las restricciones de presupuestos y días hombre. De esta forma resolviendo dicho sistema de ecuaciones se encuentra la coordenada de la solución óptima donde $X_{1}=60$ y $X_{2}=20$ (hectáreas). El valor óptimo es $V(P)=50(60)+120(20)=5.400$ (dólares).

Ejercicio N°2: Un taller tiene tres (3) tipos de máquinas A, B y C; puede fabricar dos (2) productos 1 y 2, todos los productos tienen que ir a cada máquina y cada uno va en el mismo orden: Primero a la máquina A, luego a la B y luego a la C. La siguiente tabla muestra:

Las horas requeridas en cada máquina, por unidad de producto
Las horas totales disponibles para cada máquina, por semana
La ganancia por unidad vendida de cada producto

Formule y resuelva a través del método gráfico un modelo de Programación Lineal para la situación anterior que permite obtener la máxima ganancia para el taller.

Variables de Decisión:

$X_{1}$ : Unidades a producir del Producto 1 semanalmente
$X_{2}$ : Unidades a producir del Producto 2 semanalmente

Función Objetivo:

Maximizar $X_{1}+1,5X_{2}$

Restricciones:

$2X_{1}+2X_{2}\leq 16$
$X_{1}+2X_{2}\leq 12$
$4X_{1}+2X_{2}\leq 28$
$X_{1},X_{2}\geq 0$

Las restricciones representan la disponibilidad de horas semanales para las máquinas A, B y C, respectivamente, además de incorporar las condiciones de no negatividad.

Para la resolución gráfica de este modelo utilizaremos el software GLP cual abordamos en el artículo Problema de Planificación Forestal resuelto con Graphic Linear Optimizer (GLP). El área de color verde corresponde al conjunto de soluciones factibles y la curva de nivel de la función objetivo que pasa por el vértice óptimo se muestra con una línea punteada de color rojo.

La solución óptima es $X_{1}=4$ y $X_{2}=4$ con valor óptimo $V(P)=1(4)+1,5(4)=10$ que representa la ganancia para el taller.

Ejercicio N°3: Una compañía elabora dos productos diferentes. Uno de ellos requiere por unidad 1/4 de hora en labores de armado, 1/8 de hora en labores de control de calidad y US$1,2 en materias primas. El otro producto requiere por unidad 1/3 de hora en labores de armado, 1/3 de hora en labores de control de calidad y US$0,9 en materias primas. Dada las actuales disponibilidades de personal en la compañía, existe a lo más un total de 90 horas para armado y 80 horas para control de calidad, cada día. El primer producto descrito tiene un valor de mercado (precio de venta) de US$9,0 por unidad y para el segundo este valor corresponde a US$8,0 por unidad. Adicionalmente se ha estimado que el límite máximo de ventas diarias para el primer producto descrito es de 200 unidades, no existiendo un límite máximo de ventas diarias para el segundo producto.

Formule y resuelva gráficamente un modelo de Programación Lineal que permita maximizar las utilidades de la compañía.

Variables de Decisión:

$X_{1}$ : Unidades a producir diariamente del Producto 1
$X_{2}$ : Unidades a producir diariamente del Producto 2

Función Objetivo:

Maximizar $(9-1,2)X_{1}+(8-0,9)X_{2}=7,8X_{1}+7,1X_{2}$

Restricciones:

$\frac{X_{1}}{4}+\frac{X_{2}}{3}\leq 90$
$\frac{X_{1}}{8}+\frac{X_{2}}{3}\leq 80$
$X_{1}\leq 200$
$X_{1},X_{2}\geq 0$

La primera restricción representa las limitantes de horas de armado diariamente. La segunda restricción la disponibilidad de horas para labores de control de calidad (también diariamente). La tercera restricción establece una cota superior para la producción y ventas diarias del Producto 1. Adicionalmente se incluyen las condiciones de no negatividad para las variables de decisión.

El dominio de soluciones factibles tiene 5 vértices que corresponden a los candidatos a óptimos del problema. En particular el vértice óptimo es D de modo que la solución óptima es $X_{1}=200$ y $X_{2}=120$ con valor óptimo $V(P)=7,8(200)+7,1(120)=2.412$ que corresponde a la utilidad máxima para la empresa.

Importante: A la fecha de esta publicación disponemos de más de 70 artículos relativos a la Programación Lineal los cuales recomendamos revisar, donde se aborda la resolución gráfica de este tipo de modelos como también la resolución a través de algoritmos como el Método Simplex y la implementación computacional con herramientas como Solver, What’sBest! y OpenSolver, entre otras.

En el siguiente tutorial de nuestro canal de Youtube se explica un ejemplo adicional con todos los elementos del método gráfico en Programación Lineal:

Ejemplo del Método Simplex (Tutorial y Cómo Funciona)

En el siguiente artículo detallaremos cómo funciona el Método Simplex a través de un ejemplo sencillo correspondiente a un modelo de Programación Lineal que considera 3 variables de decisión.

El Método Simplex corresponde a un algoritmo iterativo publicado por George Bernard Dantzig en el año 1947 en donde se busca alcanzar el máximo (o mínimo) de una función lineal compuesta por un conjunto de variables que deben satisfacer condiciones impuestas por restricciones lineales en forma de inecuaciones.

En este contexto, el objetivo de este artículo es definir en detalle distintas aproximaciones para la resolución de un modelo de Programación Lineal utilizando el Método Simplex, además de discutir sobre sus principales características.

Con tal propósito en perspectiva consideremos el siguiente modelo de optimización lineal:

Ejemplo del Método Simplex (Utilizando Diccionarios)

Un paso preliminar consiste en incorporar las denominadas variables de holgura. De modo de comprender este concepto consideremos la primera restricción:

$2x_{1}+3x_{2}+x_{3}\leq 5$

Para cada solución factible $x_{1},x_{2},x_{3}$ , el valor del lado izquierdo será a lo más el valor del lado derecho; o eventualmente existirá una diferencia (holgura) entre estos 2 valores.

De esta forma definimos $x_{4}$ como variable de holgura de dicha restricción, la cual se puede denotar por $x_{4}=5-2x_{1}-3x_{2}-x_{3}$ , donde $x_{4}\geq 0$ . De forma análoga se pueden definir las variables de holgura (no negativas) $x_{5}$ y $x_{6}$ para las restricciones 2 y 3, respectivamente. Finalmente podemos describir la función objetivo $5x_{1}+4x_{2}+3x_{3}$ utilizando $z$ de forma compacta.

En resumen, para cada selección de valores de las variables $x_{1},x_{2}$ y $x_{3}$ podemos definir valores para las variables $x_{4},x_{5},x_{6}$ , y $z$ utilizando las siguientes fórmulas (conocido comúnmente como diccionarios según la terminología utilizada en el libro Linear Programming de Vasek Chvátal):

$x_{4}=5-2x_{1}-3x_{2}-x_{3}$
$x_{5}=11-4x_{1}-x_{2}-2x_{3}$
$x_{6}=8-3x_{1}-4x_{2}-2x_{3}$
$z=5x_{1}+4x_{2}+3x_{3}$

El objetivo del Método Simplex es lograr sucesivas mejoras para el valor de la función objetivo asociada a la selección de alguna solución factible. Repetir dicho procedimiento un numero finito de veces debería permitir eventualmente alcanzar la solución óptima del problema lineal en estudio.

Para inicializar el Método Simplex necesitamos una solución factible. En nuestro ejemplo esto es sencillo y se puede alcanzar simplemente fijando las variables $x_{1},x_{2},x_{3}$ en cero. De esta forma se alcanzan los siguientes resultados:

$x_{1}=0,x_{2}=0,x_{3}=0,x_{4}=5,x_{5}=11,x_{6}=8,z=0$

En el contexto del objetivo planteado anteriormente, debemos buscar una solución factible que permita alcanzar un mayor valor para $z$ . Si, por ejemplo, mantenemos $x_{2}=x_{3}=0$ e incrementamos el valor de $x_{1}$ obtenemos $z=5x_{1}>0$ , de modo que si $x_{1}=1$ se obtiene $z=5$ (y $x_{4}=3,x_{5}=7,x_{6}=5$ ). Mejor aún, si $x_{1}=2$ (manteniendo $x_{2}=x_{3}=0$ ), se obtiene $z=10$ (y $x_{4}=1,x_{5}=3,x_{6}=2$ ).

Sin embargo, si asumimos $x_{1}=3$ (conservando $x_{2}=x_{3}=0$ ) el valor de la función objetivo ahora es $z=15$ , pero $x_{4}=-1,x_{5}=-1,x_{6}=-1$ que claramente no satisface las condiciones de no negatividad para las variables.

Por tanto la pregunta relevante es: ¿cuánto se puede incrementar el valor de $x_{1}$ (manteniendo $x_{2}=x_{3}=0$ al mismo tiempo) y seguir conservando la factibilidad ( $x_{4},x_{5},x_{6}\geq 0$ )?.

La condición $x_{4}=5-2x_{1}-3x_{2}-x_{3}\geq 0$ implica $x_{1}\leq \frac{5}{2}$ ; de forma similar $x_{5}\geq 0$ implica $x_{1}\leq \frac{11}{4}$ y $x_{6}\geq 0$ implica $x_{1}\leq \frac{8}{3}$ . Claramente de estas 3 cotas para la variable $x_{1}$ la más restrictiva es $x_{1}\leq \frac{5}{2}$ , de modo que incrementamos el valor de $x_{1}$ hasta ese valor de modo de obtener una nueva solución:

$x_{1}=\frac{5}{2},x_{2}=0,x_{3}=0,x_{4}=0,x_{5}=1,x_{6}=1/2,z=\frac{25}{2}$

Que claramente constituye una mejora para el valor de la función objetivo en comparación al valor inicial $z=0$ .

A continuación debemos buscar una nueva solución factible que sea aún mejor que la que acabamos de encontrar. Para ello la variable $x_{1}$ que cambió su valor desde cero a un número positivo (12,5), debe cambiar su lugar desde el lado derecho al lado izquierdo del sistema de ecuaciones. De forma análoga, la variable $x_{4}$ que cambio su valor de un número positivo a cero debe cambiar de lugar desde el lado derecho al lado izquierdo.

De esta forma y luego de cierta manipulación algebraica podemos reescribir $x_{1}$ en términos de $x_{2},x_{3},x_{4}$ según se observa a continuación:

$x_{1}=\frac{5}{2}-\frac{3}{2}x_{2}-\frac{1}{2}x_{3}-\frac{1}{2}x_{4}$

Luego, con el objetivo de expresar $x_{5},x_{6}$ y $z$ en términos de $x_{2},x_{3},x_{4}$ , simplemente substituimos el resultado anterior en las filas correspondientes:

$x_{5}=11-4(\frac{5}{2}-\frac{3}{2}x_{2}-\frac{1}{2}x_{3}-\frac{1}{2}x_{4})-x_{2}-2x_{3}$
$x_{5}=1+5x_{2}+2x_{4}$

$x_{6}=8-3(\frac{5}{2}-\frac{3}{2}x_{2}-\frac{1}{2}x_{3}-\frac{1}{2}x_{4})-4x_{2}-2x_{3}$
$x_{6}=\frac{1}{2}+\frac{1}{2}x_{2}-\frac{1}{2}x_{3}+\frac{3}{2}x_{4}$

$z=5(\frac{5}{2}-\frac{3}{2}x_{2}-\frac{1}{2}x_{3}-\frac{1}{2}x_{4})+4x_{2}+3x_{3}$
$z=\frac{25}{2}-\frac{7}{2}x_{2}+\frac{1}{2}x_{3}-\frac{5}{2}x_{4}$

De esta forma nuestro sistema de ecuaciones (diccionario) queda definido por:

$x_{1}=\frac{5}{2}-\frac{3}{2}x_{2}-\frac{1}{2}x_{3}-\frac{1}{2}x_{4}$
$x_{5}=1+5x_{2}+2x_{4}$
$x_{6}=\frac{1}{2}+\frac{1}{2}x_{2}-\frac{1}{2}x_{3}+\frac{3}{2}x_{4}$
$z=\frac{25}{2}-\frac{7}{2}x_{2}+\frac{1}{2}x_{3}-\frac{5}{2}x_{4}$

Como lo hicimos en la primera iteración debemos intentar incrementar el valor de la función objetivo ( $z$ ) seleccionando una variable adecuada en el lado derecho, mientras que al mismo tiempo mantenemos las restantes variables del lado derecho en cero. En este sentido se puede observar que aumentar el valor de las variables $x_{2}$ o $x_{4}$ generaría una disminución en el valor de $z$ que va en sentido contrario a nuestro objetivo de maximizar el valor de la función objetivo.

Por tanto, la única selección de una variable en el lado derecho que permitirá aumentar el valor de $z$ es seleccionar la variable $x_{3}$ .

¿Cuánto debemos incrementar el valor de $x_{3}$ ?. La respuesta se puede obtener directamente del sistema de ecuaciones anterior, considerando $x_{2}=x_{4}=0$ , la restricción $x_{1}\geq 0$ implica que $x_{3}\leq 5$ ; la restricción $x_{5}\geq 0$ no impone condiciones adicionales y la restricción $x_{6}\geq 0$ implica $x_{3}\leq 1$ . En consecuencia $x_{3}=1$ es el mejor valor que puede adoptar dicha variable.

La nueva solución corresponde a:

$x_{1}=2,x_{2}=0,x_{3}=1,x_{4}=0,x_{5}=1,x_{6}=0,z=13$

El valor de $z$ paso de 12,5 a 13 al cabo de una iteración del Método Simplex.

A continuación actualizamos el sistema de ecuaciones donde las variables que adoptan valores positivos $x_{1},x_{3},x_{5}$ se encontraran en el lado izquierdo, mientras las variables igual a cero estarán en el lado derecho. De este modo pasamos la variable $x_{3}$ al lado izquierdo, donde $x_{3}=1+x_{2}+3x_{4}-2x_{6}$ que permite substituir en el resto de las ecuaciones:

$x_{3}=1+x_{2}+3x_{4}-2x_{6}$
$x_{1}=2-2x_{2}-2x_{4}+x_{6}$
$x_{5}=1+5x_{2}+2x_{4}$
$z=13-3x_{2}-x_{4}-x_{6}$

Notar que no es posible seguir aumentando el valor de la función objetivo $z$ mediante un incremento de las variables del lado derecho $x_{2},x_{4},x_{6}$ (en efecto, el valor de $z$ decrecería). En consecuencia estamos en presencia de la solución óptima del problema: $x_{1}=2,x_{2}=0,x_{3}=1,x_{4}=0,x_{5}=1,x_{6}=0$ con valor óptimo $z=13$ .

El procedimiento anterior basado en diccionarios favorece una mejor comprensión conceptual de los fundamentos sobre los que se basa el Método Simplex. De forma complementaria a continuación presentaremos a modo de contraste las iteraciones del Método Simplex utilizando tablas (o tableau) que comúnmente corresponde a la forma en la cual se presenta el algoritmo en cursos de pregrado.

Ejemplo del Método Simplex (Utilizando Tableau)

Consideremos nuevamente nuestro problema de Programación Lineal:

A continuación incorporamos las variables de holgura (no negativas) $x_{4},x_{5},x_{6}$ que por definición tienen coeficiente nulo (cero) en la función objetivo. De esta forma obtenemos la forma estándar (*):

(*). Para nuestros efectos consideraremos que la forma estándar de un modelo de Programación Lineal esta dada por $Minimizar[c^{t}x, Ax=b,x\geq 0]$ , siendo este formato el que preferentemente hemos utilizado para desarrollar las iteraciones del Método Simplex en otros artículos relacionados en nuestro sitio. En consecuencia la selección de dicho formato es meramente convencional.

Retomando nuestro ejemplo, el tableau inicial queda definido por:

Las variables de holgura definen una Solución Básica Factible Inicial, con $x_{4}=5,x_{5}=11,x_{6}=8$ (las variables no básicas inicialmente corresponden a las variables originales del modelo, es decir, $x_{1},x_{2},x_{3}$ que por definición adoptan un valor igual a cero.

¿Cómo verificar que el tableau inicial representa una solución básica factible óptima para el problema?.

Criterio de Optimalidad: Si en una iteración del Método Simplex se dispone de una solución básica factible y adicionalmente todos los costos reducidos son mayores o iguales que cero, parar ya que la actual solución básica factible es óptima.

En el ejemplo propuesto si bien nos encontramos frente a una solución básica factible el costo reducido de las variables no básicas son negativos, por tanto no se cumple el criterio de optimalidad, es decir, se puede seguir mejorando el valor de la función objetivo.

En este sentido consideraremos arbitrariamente $x_{1}$ como la variable que ingresa a la base, aun cuando no hay certeza que la selección de la variable no básica con el costo reducido más negativo contribuya necesariamente a la Rapidez de Convergencia del Método Simplex.

La variable que deja la base para dar lugar a $x_{1}$ se obtiene del criterio de factibilidad:

Criterio de Factibilidad: Para decidir que variable básica deja la base, es necesario calcular el mayor valor que puede tomar la variable no básica que entra a la base que garantice la factibilidad de la nueva solución básica. Para ello se considera un cuociente entre el valor de la solución básica factible actual y los coeficientes mayores a cero en la columna de la variable entrante. Si todos los cuocientes son negativos el Problema es No Acotado y por tanto no existe solución óptima.

En el ejemplo el criterio de factibilidad para la presente iteración esta dado por:

$Min[\frac{5}{2},\frac{11}{4},\frac{8}{3}]=\frac{5}{2}$

El menor cuociente se alcanza en la primera fila (restricción) que determina la variable que debe abandonar la base, en este caso, la variable $x_{4}$ . Luego se actualiza la tabla realizando operaciones filas considerando el denominador del mínimo cuociente como pivote. El objetivo es alcanzar en la columna de la variable $x_{1}$ lo que actualmente disponemos en la columna de la variable $x_{4}$ .

Por ejemplo, podemos dividir la fila 1 por 2 de modo de obtener un 1 en la posición del pivote. Luego sobre esta nueva fila 1 podemos multiplicarla por -4 y sumarla a la fila 2. También se puede alcanzar un cero para la variable $x_{1}$ en la fila 3 multiplicando por -3 la nueva fila 1 y sumándola a la fila 3. Finalmente para lograr un cero en el costo reducido de $x_{1}$ se multiplica por 5 la nueva fila 1 y se suma a la fila 4.

De este modo el tableau del Método Simplex al cabo de una iteración queda de la siguiente forma:

La solución básica factible actual corresponde a: $x_{1}=\frac{5}{2},x_{2}=0,x_{3}=0,x_{4}=0,x_{5}=1,x_{6}=1/2$ con valor en la función objetivo $z=\frac{25}{2}$ . Se puede apreciar que dicho resultado es consistente con el enfoque de diccionarios utilizado inicialmente.

Claramente no se satisface el criterio de optimalidad dado que la variable no básica $x_{3}$ tiene costo reducido negativo. Por ello $x_{3}$ ingresa a la base y por tanto debemos calcular nuevamente el criterio de factibilidad para determinar la variable que deberá dejar la base:

$Min[\frac{5/2}{1/2},\frac{1/2}{1/2}]=1$

El pivote ahora se encuentra en la fila 3 y en consecuencia la variable básica $x_{6}$ debe dejar la base. Notar que no se ha considerado para el cálculo del criterio de factibilidad el coeficiente de la variable $x_{3}$ correspondiente a la fila 2 del tableau anterior (cuyo valor es cero y por tanto el cuociente se indefine).

Actualizamos el tableau del Método Simplex obteniendo los siguientes resultados:

Los valores que adoptan las variables básicas correspondientes a esta nueva iteración es $x_{1}=2,x_{2}=0,x_{3}=1,x_{4}=0,x_{5}=1,x_{6}=0$ que además representa la solución óptima del modelo de Programación Lineal (dado el cumplimiento del criterio de optimalidad). Luego el valor óptimo corresponde a $z=13$ .

Importante: Existen herramientas computacionales y aplicaciones que permiten resolver online un problema de Programación Lineal mediante el Método Simplex. A continuación se presenta un extracto de los resultados alcanzados para nuestro ejemplo utilizando la aplicación disponible en http://www.programacionlineal.net/simplex.html.

Método Simplex (Conclusiones)

El ejemplo que hemos desarrollado en este artículo busca presentar de forma sencilla y didáctica los principales fundamentos asociados al Método Simplex. Cabe destacar que ha sido necesario para la aplicación del algoritmo llevar el modelo original a su forma estándar que como se discutió anteriormente puede tener distintas representaciones según la bibliografía que se consulte.

En este contexto, cada problema de Programación Lineal en su forma estándar cumple con las siguientes propiedades establecidas en el Teorema Fundamental de la Programación Lineal:

Si el problema no tiene solución óptima entonces es no-acotado o infactible.
Si tiene una solución factible, tiene una solución básica factible.
Si el problema tiene solución óptima, tiene una solución básica factible óptima.

Cabe destacar que no siempre se dispone de una solución básica factible en las variables originales del modelo (luego de llevar el problema a su forma estándar). Si bien existen diversas estrategias algorítmicas para enfrentar esta dificultad, se propone al lector revisar los tutoriales que hemos desarrollado sobre esta problemática, en particular respecto al Método Simplex de 2 Fases, Método de la M Grande y Método Simplex Dual.

Adicionalmente con el objetivo de resumir algunas ideas principales del algoritmo hemos preparado una infografía que hemos llamado 10 Cosas que Necesitas saber sobre el Método Simplex.

Finalmente quisiéramos recordar a nuestros usuarios que en el Blog de Gestión de Operaciones se pueden encontrar a la fecha más de 80 publicaciones relativas a la Programación Lineal y la Investigación de Operaciones. De modo de favorecer una rápida búsqueda ingresa al menú Cómo Comenzar. Por último agradeceríamos compartir y difundir este material en la medida que haya sido considerado útil y evaluar este tutorial utilizando las estrellas al final de esta publicación.

10 Cosas que Necesitas Saber sobre el Método Simplex

El Método Simplex desarrollado por George B. Dantzig en 1947 es sin duda el algoritmo más popular a la hora de enfrentar la resolución de un modelo de Programación Lineal y ocupa un lugar destacado en los cursos introductorios a la Investigación de Operaciones.

En esta oportunidad hemos buscado resumir 10 conceptos principales sobre el uso y la aplicación del Método Simplex con el objetivo de que nuestros usuarios puedan tener una primera aproximación al método observando algunos aspectos característicos. Esta recopilación se basa sobre nuestra experiencia docente dictando cursos de Investigación Operativa y las preguntas que frecuentemente recibimos por parte de los alumnos de pregrado.

10 Cosas que Necesitas Saber sobre el Método Simplex

Te invitamos a revisar y compartir esta infografía en las redes sociales. Adicionalmente si consideras si un elemento importante quedo fuera de la lista anterior utiliza la herramienta de comentarios al pie de la página para hacernos saber tu opinión. De esta forma podremos ir actualizando periódicamente el artículo con las características principales del Método Simplex.

Cambio en el Lado Izquierdo de las Restricciones en Programación Lineal

El el contexto del Análisis de Sensibilidad en Programación Lineal es usual analizar el impacto que tiene la modificación en la disponibilidad de los recursos en la solución óptima alcanzada originalmente. Esto corresponde al Cambio en el Lado Derecho de las Restricciones (Análisis de Sensibilidad en Programación Lineal). En el siguiente artículo abordaremos el caso cuando cambia un coeficiente o parámetro en el lado izquierdo de las restricciones, generalmente asociado a un coeficiente tecnológico o factor de productividad (por ejemplo, la cantidad de horas hombre que puede requerir la fabricación de un producto, la cantidad de dinero requerido por unidad a producir dada una restricción presupuestaria, entre otras). En relación a lo anterior consideremos el caso de una empresa la cual tiene un plan de producción representado por:

Donde $x_{j}$ es la cantidad a producir del bien j, z la utilidad de la empresa (en unidades monetarias u.m) y los coeficientes $a_{ij}$ de las restricciones, la cantidad de recurso i por unidad del producto j. Al aplicar el Método Simplex al modelo anterior incorporando $x_{4}$ y $x_{5}$ como variables de holgura de las restricciones del recurso 1 y 2 respectivamente, resulta la siguiente tabla final:

Si el requerimiento del primer recurso por parte del producto j=2 cambia de 5 a 2 debido a la incorporación de una nueva tecnología ¿Cambia la actual solución óptima? ( $x_{1}=\frac{20}{3}$ , $x_{2}=\frac{4}{3}$ y $x_{3}=0$ ). Sabemos que:

Luego al cambiar un coeficiente en el lado izquierdo asociado a la variable básica $x_{2}$ , es necesario actualizar la matriz de base inversa o $B^{-1}$ . Lo anterior se deduce del cálculo de la matriz inversa asociada a la matriz $B$ donde los elementos en la columna correspondiente a los coeficientes en el lado izquierdo (forma estándar del Método Simplex) asociadas a las variables básicas $x_{1}$ y $x_{2}$ , respectivamente. Finalmente obtenemos la nueva solución básica y verificamos si es factible, esto es si el valor que adopta cada una de las variables básicas satisface las condiciones de no negatividad (en caso que una de las variables básicas alcance un valor negativo se puede continuar las iteraciones con el Método Simplex Dual luego de actualizar el valor de la función objetivo).

En nuestro ejemplo $x_{1}=\frac{28}{3}$ , $x_{2}=\frac{2}{3}$ y $x_{3}=0$ lo cual implica que se modifica la solución óptima original pero se conserva la actual base óptima (las mismas variables básicas originales). El nuevo valor óptimo será:

Criterios para la Rapidez de Convergencia del Método Simplex

En un artículo previo respecto a Cómo resolver un modelo de Programación Lineal con el Método Simplex de 2 Fases, se consideró en una iteración intermedia (es decir, en un tableau que representa una solución básica factible no óptima) la entrada a la base de una variable no básica que no era aquella con el costo reducido más negativo. Dicha situación por cierto no tuvo incidencia respecto a alcanzar los resultados del modelo en cuanto a su solución óptima y valor óptimo, no obstante, dicha situación afecto la rapidez de convergencia del Método Simplex.

Entendemos por rapidez de convergencia en este caso, el número de iteraciones necesarias en la aplicación del Método Simplex para, comenzando en una solución básica factible inicial llegar a una solución básica factible óptima.

Se debe destacar que si bien es frecuente que en la bibliografía básica asociada a cursos de Investigación de Operaciones se considere como criterio privilegiar la entrada a la base de aquella variable no básica con el costo reducido más negativo esto NO garantiza un menor número de iteraciones en el Método Simplex.

Ejemplo Criterio Costo Reducido Más Negativo en el Método Simplex

Como forma de corroborar lo anterior retomaremos el modelo de Programación Lineal que fue presentado en el artículo mencionado anteriormente:

La resolución del problema anterior se aborda a través del Método Simplex de 2 Fases, incorporando $X_{4}$ y $X_{5}$ como variables de exceso y $X_{6}$ y $X_{7}$ como variables auxiliares, de las restricciones 1 y 2, respectivamente. Esto da origen al siguiente problema de la Fase 1.

Luego de algunas iteraciones del Método Simplex se alcanza la siguiente tabla:

A continuación podríamos seleccionar como variable que ingresa a la base tanto a $X_{1}$ , $X_{2}$ o $X_{4}$ , al tener cada una de estas variables no básicas un costo reducido negativo.

Luego, y según lo descrito anteriormente, podemos privilegiar la entrada a la base de la variable $X_{2}$ que tiene el costo reducido más negativo. En consecuencia el mínimo cuociente se calcula en la columna de la variable $X_{2}$ , siendo éste: $Min\begin{Bmatrix}\frac{1/4}{1/4};\frac{1}{3/2}\end{Bmatrix}=2/3$ , por tanto $X_{1}$ deja la base. Se actualiza la tabla con esta nueva información obteniendo lo siguiente que representa el fin de la Fase I:

Eliminamos las columnas de las variables auxiliares $X_{6}$ y $X_{7}$ y adicionalmente actualizamos el vector de costos reducidos considerando la función objetivo original.

Luego llevamos a cero los costos reducidos de las variables $X_{3}$ y $X_{2}$ :

Ahora entra la variable $X_{1}$ a la base. El criterio de factibilidad o mínimo cuociente determina que $Min\begin{Bmatrix}\frac{1/12}{1/3};\frac{2/3}{2/3}\end{Bmatrix}=1/4$ la variable $X_{3}$ deja la base. Se actualiza la tabla:

Que corresponde a la tabla final de la Fase II donde $X_{1}=1/4$ , $X_{2}=1/2$ y $X_{3}=0$ y que por cierto demuestra la equivalencia en los resultados obtenidos cuando en la tabla intermedia de la Fase I se ingresa a la base a la variable $X_{1}$ . Cabe destacar que una forma alternativa de resolver el problema anterior que evita la aplicación de las 2 Fases del Método Simplex es a través del Método Simplex Dual.

Ejemplo Criterio Costo Reducido Negativo en el Método Simplex

Consideremos el siguiente problema de Programación Lineal:

El lector puede corroborar que luego de llevar a la forma estándar el problema anterior, pasando a minimización la función objetivo y agregando como variables de holgura las variables $x_{3}$ y $x_{4}$ se dispone de una solución básica factible inicial en el origen (vértice A de la siguiente gráfica).

Si se privilegia la entrada a la base de aquella variable no básica con el costo reducido más negativo se debería seleccionar inicialmente la variable $x_{2}$ la cual permite concluir con las iteraciones del Método Simplex y alcanzar la solución óptima al cabo de 3 iteraciones (vértice D). Por el contrario si inicialmente se ingresa a la base la variable $x_{1}$ se alcanza la solución óptima al cabo de 1 iteración. Se recomienda al lector verificar estos resultados.

Este sencillo ejemplo demuestra que NO necesariamente garantiza una mayor rapidez de convergencia del Método Simplex el considerar como criterio de entrada a la base aquella variable no básica con el costo reducido más negativo.