Cambio de Variables como alternativa al Método Simplex de 2 Fases

Una empresa que fabrica tres artículos A, B y C, desea encontrar un Plan de Producción semanal que le permita maximizar sus beneficios netos totales. Los productos son procesados en tres máquinas siendo la producción mínima semanal de 100, 60 y 60 unidades respectivamente. El beneficio neto por unidad vendida de estos artículos son 2, 2 y 4 mil pesos para los artículos A, B y C, respectivamente. Las horas que se necesitan por unidad y máquina son:

maquinas-tiempos-de-producc

Siendo el número de horas disponibles de cada máquina 240, 400 y 360 respectivamente. Formule un modelo de Programación Lineal para abordar el problema propuesto. Resuelva a través del Método Simplex dicho modelo, indicando cuántas unidades de A, B y C se deben fabricar semanalmente y el beneficio final de este plan.

Variables de Decisión: Se debe definir cuántas unidades de cada uno de los 3 productos se fabricarán durante el período de evaluación.

variables-produccion-abc

Función Objetivo: Consiste en maximizar el beneficio neto asociado al plan de producción.

funcion-objetivo-abc

Restricciones: Se debe garantizar que se fabrique los mínimos semanales exigidos para cada producto como también que se respete la disponibilidad de horas máquinas.

restricciones-abc

El problema anterior se puede resolver por el Método Simplex de 2 Fases agregando variables de exceso y auxiliares para cada una de las restricciones que establecen los mínimos semanales de producción. Además se debe agregar variables de holguras para cada una de las restricciones de disponibilidad de horas máquinas. En consecuencia el problema de la Fase 1 tendría 3 variables auxiliares (cuya sumatoria se minimiza en la función objetivo) lo cual genera una instancia de resolución al menos tediosa para este problema (en caso se ser abordada manualmente).

Una alternativa más eficiente de resolución se alcanza al imponer un cambio de variables, lo que permite simplificar las restricciones de mínimos de producción semanal. Sea X=A-100\geq 0, Y=B-60\geq 0Z=C-60\geq 0. Luego A=X+100B=Y+60C=Z+60, obteniendo la siguiente instancia de modelamiento equivalente:

modelo-lineal-con-cambio-de

A continuación llevamos a la forma estándar el modelo anterior, transformando la función objetivo a minimización y agregando s_{1},s_{2},s_{3} como variables de holgura de las restricciones 1, 2 y 3, respectivamente:

forma-estandar-cambio-de-va

Lo que da origen a la siguiente tabla inicial del Método Simplex:

tabla-inicial-forma-estanda

A continuación incorporamos a la base a la variable Z considerando el criterio que favorece la rapidez de convergencia del algoritmo. Luego calculamos el criterio de factibilidad o mínimo cuociente en la columna de la variable Z: Min\begin{Bmatrix}\frac{60}{2}; \frac{180}{1}; \frac{40}{1}\end{Bmatrix}=30, lo que determina que la variable s_{1} deja la base. Se actualiza la tabla realizando una iteración del Método Simplex:

iteracion-1-cambio-de-varia

Se procede a incorporar a la variable X a la base y s_{3} abandona la base dado que Min\begin{Bmatrix}\frac{150}{1}; \frac{10}{2}\end{Bmatrix}=5. Se realiza una iteración adicional que permite alcanzar la siguiente solución básica factible óptima:

solucion-optima-cambio-de-v

La solución óptima es X=5Y=0Z=30 que al remplazar en las variables originales permite obtener A=X+100=5+100=105B=Y+60=0+60=60C=Z+60=30+60=90. Notar que el valor óptimo es V(P)=130+560=690 luego de sumar el valor de la constante 560 al valor obtenido para la función objetivo del problema auxiliar. Se propone al lector corroborar los resultados anterior a través de la aplicación del Método Simplex de 2 Fases que por cierto permite alcanzar idénticos resultados pero con una mayor esfuerzo en la resolución.

Cálculo del Intervalo de Variación del Lado Derecho que conserva la Base Óptima

Una vez concluidas las iteraciones del Método Simplex y en el caso de alcanzar una solución básica factible óptima, puede resultar de interés determinar un intervalo de variación para un parámetro del vector de los lados derechos de las restricciones que permita conservar la geometría del problema. Esto implica que se conservan las restricciones activas originales en el nuevo escenario (es decir, se mantiene la base óptima) que se genera a partir de la modificación (individual) de un parámetro o coeficiente del lado derecho. Para ilustrar el resultado anterior consideremos el siguiente modelo de Programación Lineal.

modelo-lineal-cambio-lado-d

Luego de llevar a la forma estándar el modelo anterior agregando x_{3}, x_{4} y x_{5} como las variables de holgura de las restricciones 1, 2 y 3, respectivamente, y aplicar las iteraciones necesarias del Método Simplex, se alcanza la siguiente tabla final (óptima):

tabla-optima-simplex-lado-d

La solución óptima es x_{1}=15x_{2}=40 con valor óptimo V(P)=615. El valor de las variables de holgura en el óptimo x_{3}, x_{4} y x_{5} es 0, 0 y 20, respectivamente. Luego se puede concluir que la solución óptima del problema se alcanza con las restricciones 1 y 2 activas (notar que sus respectivas holguras con variables no básicas en el óptimo) y la base actual esta conformada por las variables x_{1}, x_{2} y x_{5}.

Sabemos adicionalmente que, por ejemplo, el costo reducido de la variable de holgura x_{3} representa el precio sombra asociado a la primera restricción (\pi_{1}=1/2). No obstante desconocemos en qué intervalo puede variar el parámetro del lado derecho de la restricción 1 (actualmente b_{1}=180) de modo que se conserve la base óptima y por tanto nos permita hacer un correcto uso de la información del precio sombra.

Para ello se propone la siguiente fórmula que permite encontrar el intervalo de variación para un lado derecho que conserva la base óptima:

Max {-bj/yij con yij>0} <= D <= Min {-bj/yij con yij<0}

Por ejemplo determinemos el intervalo para el parámetro b_{1}:

intervalo-variacion-lado-de

En consecuencia b_{1} puede disminuir en 30 unidades y aumentar en 15 unidades y se conserva la base óptima. Es decir, si b_{1}\epsilon [150,195] se mantiene la base óptima.

intervalo-parametro-b1

El resultado anterior se puede corroborar gráficamente. La solución óptima se encuentra en el vértice C donde las restricciones 1 y 2 son activas (notar la curva de nivel que pasa por el vértice óptimo es la línea punteada de color azul). Si para el lado derecho de la restricción 1 consideramos b_{1}=150 se obtiene la línea de color verde y para b_{1}=195 la línea de color rojo. En estos casos si bien se modifica el dominio de soluciones factibles, la solución óptima conserva las actuales restricciones activas (y por ende cuando b_{1} adopta un valor fuera de este intervalo cambia la geometría del problema o base óptima).

intervalo-grafico-lado-dere

Esto es consistente con el Informe de Confidencialidad de Solver. En particular el reporte de restricciones donde se aprecia el aumento y reducción permisible que conserva la actual base óptima:

informe-lado-derecho-solver

Por ejemplo, ¿cuál es el nuevo valor óptimo si el lado derecho de la restricción 1 ahora es b_{1}=190?. Como b_{1}=190\epsilon[150,195], entonces V(P)=615+\Delta b_{1}\pi _{1}=615+(190-180)*(1/2)=620. ¿Cuál es la nueva solución óptima?. Como sabemos que se conservan las restricciones activas en el óptimo para la variación propuesta, la solución óptima del nuevo escenario se obtiene simplemente resolviendo el siguiente sistema de ecuaciones (notar que la restricción 1 y 2 se conservan activas):

sistema-ecuaciones-restricc

De donde x_{1}=20x_{2}=110/3, que al evaluar en la función objetivo se obtiene: V(P)=9*(20)+12*(110/3)=620 corroborando el resultado anterior. Dejamos al lector el desafío de aplicar los conceptos presentados en este articulo para encontrar un intervalo para b_{2}b_{3} que conserve la base óptima.

Casos Especiales en la Programación Lineal detectados con el Método Simplex

En la resolución de un modelo de Programación Lineal se pueden enfrentar ciertos casos especiales que merecen particular atención. Estos casos (infinitas soluciones óptimas, problema no acotado sin solución óptima, problema infactible, solución óptima degenerada) se pueden detectar a través de la aplicación del Método Simplex según hemos tratado previamente en el Blog. A continuación un resumen de dichos escenarios:

Infinitas Soluciones Óptimas: Se detecta cuando luego de alcanzar una solución básica factible óptima, al menos una variable no básica tiene costo reducido igual a cero. La siguiente imagen representa esta situación donde la solución óptima (infinitas) se alcanza en el tramo entre los vértices B y C. En efecto se puede representar de forma general las soluciones óptimas como: (x,y)=\lambda (0,3)+(1-\lambda )(2,2) con 0\leq \lambda\leq 1.

Grafico Infinitas Soluciones Optimas

Problema No Acotado: En las iteraciones del Método Simplex un problema no acotado se detecta cuando al calcular el criterio de factibilidad o mínimo cuociente que determina la variable que deja la base, todas las entradas en la columna de la variable no básica entrante son negativas o cero, por tanto no existe denominador válido (mayor a cero) que permita determinar el pivote. En la siguiente representación gráfica se puede apreciar que las curvas de nivel de la función objetivo crecen en la dirección del vector gradiente, donde en particular el dominio de soluciones factibles es no acotado para los valores que puede adoptar la variable x_{2}.

problema no acotado

Es importante destacar que el hecho que un dominio de soluciones factibles sea no acotado no implica necesariamente que el problema de Programación Lineal no tiene solución.

Problema Infactible: Si al finalizar la Fase I del Método Simplex de 2 Fases el valor de la función objetivo es distinto a cero, entonces el problema lineal es infactible, es decir, el dominio de soluciones factibles es vacío al existir restricciones incompatibles (por ejemplo en el gráfico a continuación el área azul no se intersecta con el área color rojo).

dominio-infactible-problema

Solución Óptima Degenerada: Cuando se presenta un empate el el cálculo de la condición de factibilidad del Método Simplex, al menos una variable básica será cero en la siguiente iteración, caso en el cual se dice que la nueva solución es degenerada. Esto implica que el modelo tiene al menos una restricción redundante.

solucion-optima-degenerada-

Método de la M Grande (o Gran M) en Programación Lineal

En el contexto de la aplicación del Método Simplex no siempre es inmediata la obtención de una solución básica factible inicial, en las variables originales del modelo. Para conseguir esto existen varios procedimientos como son el Método Simplex de 2 Fases y el Método de la M Grande (o Gran M) el cual abordaremos en este artículo. Para ello consideremos el siguiente modelo de Programación Lineal en 2 variables:

modelo-m-grande

A continuación agregamos las variables no negativas x_{3} (holgura restricción 1), r_{1} (auxiliar restricción 2), x_{4} (exceso restricción 3) y r_{2} (auxiliar restricción 3). El modelo ahora es:

formato-m-grande

Donde el parámetro M es una constante positiva suficientemente grande para representar una penalización adecuada en la función objetivo. La tabla inicial del método esta dada por:

tabla-inicial-m-grande

Antes de continuar con las iteraciones se debe procurar que el costo reducido de las variables r_{1}r_{2} sean ceros. Para ello multiplicamos por -M la fila 2 y la fila 3 y luego sumamos a la fila 4, obteniendo lo siguiente:

iteracion-1-m-grande

Ahora debemos seleccionar que variable no básica ingresa a la base. El menor costo reducido corresponde a la variable x_{1} en consecuencia dicha variable ingresa a la base. Luego calculamos el mínimo cuociente en dicha columna: Min \begin{Bmatrix}{\frac{27/10}{3/10}, \frac{6}{1/2}, \frac{6}{3/5}}\end{Bmatrix}=9, el cual se alcanza en la fila 1, por tanto la variable x_{3} deja la base. Se actualiza la tabla:

segunda-iteracion-m-grande

Siguiendo con las iteraciones ahora la variable x_{2} entra a la base. El criterio de factibilidad indica que: Min \begin{Bmatrix}{\frac{9}{1/3}, \frac{3/2}{1/3}, \frac{3/5}{1/5}}\end{Bmatrix}=3 la variable r_{2} abandona la base (el pivote se encuentra en la fila 3). Actualizamos la tabla:

tercera-iteracion-gran-m

Una nueva iteración indica que x_{3} ingresa a la base. El mínimo cuociente en la respectiva columna es: Min \begin{Bmatrix}{\frac{8}{20/3}, \frac{1/2}{5/3}}\end{Bmatrix}=3/10 (recordar que se omiten denominadores menores a cero). Ahora el pivote se encuentra en la fila 2 y en consecuencia x_{4} deja la base. Se actualiza la tabla:

tabla-optima-m-grande

Se ha alcanzado la solución óptima con x_{1}=15/2x_{2}=9/2. Notar que las variables auxiliares (r1 y r2) son no básicas en el óptimo. El valor óptimo es 21/4 (notar que el signo esta cambiado).

Para una mejor comprensión de los resultados alcanzados a continuación se presenta la resolución gráfica del problema haciendo uso del software Geogebra. El dominio de soluciones factibles corresponde a la recta que une los vértices A y B. Adicionalmente se muestra la curva de nivel que pasa por la solución óptima (vértice B).

solucion-grafica-m-grande

Teóricamente se espera que en la aplicación del Método de la M Grande las variables auxiliares sean no básicas en el óptimo. Si el modelo de Programación Lineal es infactible (es decir, si las restricciones no son consistentes), la iteración del Método Simplex final incluirá al menos una variable artificial como básica.

Adicionalmente la aplicación de la técnica de la M Grande implica teóricamente que M tiende a infinito. Sin embargo al usar la computadora M debe ser finito, pero suficientemente grande. En específico M debe ser lo bastante grande como para funcionar como penalización, al mismo tiempo no debe ser tan grande como para perjudicar la exactitud de los cálculos del Método Simplex, al manipular una mezcla de números muy grandes y muy pequeños.

Problema de Producción de Trajes y Vestidos resuelto con el Método Simplex

La empresa Trajes y Vestidos tiene en un momento dado que tomar una decisión sobre cómo maximizar el ingreso en la confección y venta de un tipo de traje y un tipo de vestido específico, que está teniendo demanda por la clientela. Al momento se tiene 80 yardas de tela de algodón y 120 yardas de tela de lana para la confección de los trajes y de los vestidos. Para la confección del traje se necesita 1 yarda de tela de algodón y 3 yardas de tela de lana. Mientras que para el vestido se necesita 2 yardas de tela de algodón y 2 yardas de tela de lana.

Para tomar la decisión de la mezcla de producto óptima para el Problema de Producción de Trajes y Vestidos, hace 3 tipos de escenarios:

  1. Cuando ambas confecciones tienen un precio unitario de $30.
  2. Cuando los trajes valen $40 y los vestidos $20.
  3. Cuando los trajes valen $30 y los vestidos $20.

¿Cuántos vestidos y trajes hay que hacer para maximizar los ingresos?. Esto es, ¿con cuál mezcla de productos se maximiza los ingresos?. Resuelva el problema de Programación Lineal utilizando el Método Simplex.

Sea x_{1} la cantidad de trajes a fabricar y x_{2} la cantidad de vestidos a fabricar, se formulan los siguientes modelos de optimización para los 2 primeros escenarios (notar que por simple inspección se descarta inmediatamente el escenario 3 dado que de todos modos no podrá reportar ingresos mayores que el escenario 1 o 2).

problema-trajes-y-vestidos

En primera instancia resolveremos por el Método Simplex el problema correspondiente al escenario 1. Para ello agregamos las variables de holgura x_{3}, x_{4} para la restricción de disponibilidad de yardas de algodón y disponibilidad de yardas de lana, respectivamente. De esta forma el problema en su forma estándar es:

forma-estandar-escenario-1

El cual da origen a la siguiente tabla inicial del algoritmo:

tabla-inicial-escenario-1

Tanto la variable no básica x_{1} como la variable no básica x_{2} tienen costo reducido negativo de la misma magnitud. En este caso seleccionaremos de forma arbitraria la variable x_{1} como aquella que ingresa a la base. Luego calculamos el cuociente mínimo en dicha columna: Min \begin{Bmatrix}{\frac{80}{1}, \frac{120}{3}}\end{Bmatrix}=40, en consecuencia la variable x_{4} deja la base.

iteracion-1-escenario-1

Ahora ingresa a la base la variable x_{2}. Calculamos nuevamente el criterio de factibilidad o mínimo cuociente en la columna de la variable x_{2} obteniendo: Min \begin{Bmatrix}{\frac{40}{4/3}, \frac{40}{2/3}}\end{Bmatrix}=30 que determina que la variable x_{3} deja la base.

tabla-optima-escenario-1

La solución óptima es x_{1}=20, x_{2}=30 con valor óptimo (ingreso) de $1.500.

A continuación resolvemos el problema del escenario 2. Para ello llevamos el modelo a su forma estándar lo que da origen a la siguiente tabla inicial del Método Simplex:

problema-escenario-2

Naturalmente la variable no básica x_{1} ingresa a la base al tener ésta el costo reducido más negativo. Por otra parte la variable que deja la base de obtiene de Min \begin{Bmatrix}{\frac{80}{1}, \frac{120}{3}}\end{Bmatrix}=40, por tanto x_{4} deja la base y se actualiza la tabla.

tabla-optima-escenario-2

Notar que estamos frente a la tabla óptima del segundo escenario donde la política de producción de trajes y vestidos que maximiza los ingresos es x_{1}=40, x_{2}=0 con valor óptimo (ingreso) de $1.600. En consecuencia se propone implementar la solución del escenario 2 que desde el punto de vista de los ingresos es la que logra una mayor recaudación dado los datos del problema.