cambio de variables Archivos - Gestión de Operaciones

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:

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.

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

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.

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 0$ y $Z=C-60\geq 0$ . Luego $A=X+100$ , $B=Y+60$ y $C=Z+60$ , obteniendo la siguiente instancia de modelamiento equivalente:

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:

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

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:

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:

La solución óptima es $X=5$ , $Y=0$ y $Z=30$ que al remplazar en las variables originales permite obtener $A=X+100=5+100=105$ , $B=Y+60=0+60=60$ y $C=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.

Informe de Confidencialidad de Celdas de Variables y Restricciones de Solver

El siguiente problema tiene por objetivo mostrar la interpretación del Informe de Confidencialidad (o Informe de Sensibilidad) de Solver de Excel en los distintos escenarios que de éste se pueden considerar. Una empresa fabrica 3 productos (A, B y C) y desea planificar la producción semanal de cada uno de estos productos. Para ello dispone de 200 horas semanales en el departamento de corte, 350 horas semanales en el departamento de ensamblaje y 250 horas semanales en el departamento de terminado. Cada producto utiliza una determinada cantidad de horas en estos departamentos según lo muestran los parámetros en el lado izquierdo de las respectivas restricciones. Adicionalmente la empresa ha adquirido contratos con clientes que compran el producto B y C para producir al menos 50 y 30 unidades semanales, respectivamente. Finalmente según el departamento de ventas se ha estimado que la demanda máxima semanal para los productos A, B y C son 60, 120 y 80 unidades respectivamente.

Un modelo de Programación Lineal para la situación anterior es:

Luego de implementar en Solver de Excel el modelo anterior se obtiene el siguiente Informe de Confidencialidad (Informe de Sensibilidad):

1. ¿Cuánto estaría dispuesto a pagar para cancelar el contrato que obliga a producir al menos 30 unidades de C?

El Precio Sombra de la restricción de contrato del producto C es de -2 y su disminución permisible es de 30 unidades. Por tanto podemos utilizar el precio sombra para predecir el cambio en el valor óptimo ante la eliminación de este contrato (que sería equivalente a reemplazar $C\geq 30$ por $C\geq 0$ ). El valor óptimo en consecuencia aumentaría en -2*(0-30)=$60 que determina la máxima disposición a pagar para eliminar este contrato.

2. Suponga que se elimina el contrato que obliga producir al menos 50 unidades de B. ¿Cuál es el impacto en el impacto en el valor óptimo?

El Precio Sombra de la restricción de contrato del producto B es de -19 y su disminución permisible es de 10 unidades. Esto determina que reemplazar $B\geq 50$ por $B\geq 0$ no llevaría la producción de B a cero sino que sólo disminuiría a 40 unidades. Por tanto al eliminar este contrato el valor óptimo aumentaría en -19*(40-50)=$190 que determina la máxima disposición a pagar para eliminar este contrato.

3. Suponga que la empresa tiene $100 para invertir en capacidad. El costo de una hora extra de capacidad en los departamentos de Corte, Ensamblaje y Terminación es de $7, $5, y $6 respectivamente. ¿Cómo invertiría los fondos?. Asuma que sólo puede invertir en una de las 3 alternativas.

No tiene sentido destinar fondos adicionales para contratar horas extraordinarias en los departamentos de ensamblaje y terminado dado que en la actual solución óptima éstas restricciones no se encuentran activas y por tanto existen horas ociosas en dichos departamentos (70 y 80 horas semanales, respectivamente).

Por el contrario el departamento de corte se encuentra operando a máxima capacidad y dispone de un precio sombra de $9 que es mayor al costo de la hora extra de $7, por lo tanto conviene comprar capacidad adicional.

Con un presupuesto de $100 se pueden adquirir 14,2857 horas adicionales en el departamento de corte ($100/7) lo cual está dentro del aumento permisible para el precio sombra (23,3 horas) por tanto se destina la totalidad del presupuesto para dicho propósito.

4. ¿Cuál es el rango de variación para el coeficiente asociado a la variable B en la función objetivo que conserva la actual solución óptima?

Notar que la solución óptima actual es A=20, B=50, C=30. Adicionalmente el valor actual del parámetro en la función objetivo que pondera la variable B es 8, con un aumento permisible de 19 y una reducción permisible de 1E+30 (infinito). Es decir, el intervalo de variación para el parámetro que conserva la solución óptima es ]-1E+30,27]. La cota inferior del intervalo anterior cobra sentido al considerar la restricción de Contrato de B, que, independiente del beneficio (o pérdida) que reporte dicho producto al plan de producción, se debe fabricar de todos modos.

Cambio de Variables en un Modelo de Programación Lineal

Cuando se desea resolver un modelo de Programación Lineal es importante tener en cuenta que generalmente se dispone de varias alternativas las cuales difieren en dificultad y por tanto es necesario evaluar cada una en su mérito para luego decidir qué estrategia algorítmica utilizar.

Este concepto es válido tanto para la resolución de pequeños modelos de optimización lineales como los que usualmente se consideran para fines académicos, como también para modelos de mayor tamaño, donde seleccionar una estrategia adecuada favorece los tiempos y confiabilidad de la resolución computacional.

A continuación presentaremos un problema de Programación Lineal en 2 variables que resulta de interés su resolución:

Notar que existen distintas estrategias que nos permiten abordar el problema anterior. Por ejemplo, lo podríamos resolver gráficamente (Método Gráfico en Programación Lineal) o utilizar el Método Simplex de 2 Fases, agregando variables de holgura para las restricciones 1, 2 y 3 y variables de exceso y auxiliares para las restricciones 4 y 5. También por cierto se podría definir el Problema Dual del ejemplo anterior y luego intentar su resolución, lo que a primera vista no sería de mayor ayuda.

Ahora bien, si una variable de decisión x debe cumplir la restricción x≥a, para una constante a positiva, se puede imponer un cambio de variables y=x-a, que define una nueva variable y que tiene solo una restricción de no negatividad y simplifica imponer la primera como una restricción general en la aplicación del Método Simplex.

El concepto anterior nos permite hacer lo siguiente: Y1=X1-20>=0; Y2=X2-20>=0. Es decir X1=Y1+20 y X2=Y2+20. En consecuencia podemos reescribir el modelo original de la siguiente forma:

Reduciendo términos semejantes se obtiene:

Notar que este nuevo modelo de optimización se puede resolver de forma directa a través del Método Simplex, incorporando las variables no negativas Y3, Y4 e Y5 como holguras de las restricciones 1, 2 y 3, respectivamente. De esta forma el problema en su forma estándar proporciona la siguiente tabla inicial: (Notar que el valor de la función objetivo inicialmente es 1.100 debido a que dicha constante se obtiene luego de realizar el cambio de variables)

La variable Y1 entra a la base al ser la variable no básica con el costo reducido más negativo. Luego para determinar la variable básica que deja la base calculamos el mínimo cuociente: Min {420/6; 140/1; 160/2} = 70 ==>Y3 sale de la base. Se realiza una iteración del Método Simplex:

Ahora Y2 entra a la base al ser la única variable no básica con costo reducido negativo. A continuación la variable que deja la base se determina a través del criterio del mínimo cuociente: Min {70/1/2; 70/3/2; 20/1} = 20 ==>Y5 sale de la base. Se realiza una nueva iteración:

Se ha alcanzado la tabla óptima donde Y1=60 e Y2=20 con valor óptimo V(P)=3.400. Reemplazando en las variables originales se obtiene la solución óptima del problema original: X1=60+20=80 y X2=20+20=40. Se puede corroborar que esta solución óptima al ser evaluada en la función objetivo del problema inicial proporciona el valor óptimo del modelo de programación lineal: Max 30*(80)+25*(40)=3.400, lo que permite garantizar la equivalencia del procedimiento utilizado.