geogebra Archivos - Página 6 de 7 - Gestión de Operaciones

Incorporar Nueva Restricción (Análisis Postoptimal Programación Lineal)

Una vez resuelto un modelo de Programación Lineal puede resultar de interés si la actual solución óptima y valor óptimo se conservaran si se decide incorporar una nueva restricción al problema. Esta restricción generalmente representa una condición que en primera instancia se omite de forma voluntaria para dar una mayor flexibilidad a la resolución del modelo original o alternativamente su no inclusión en el modelo original puede también deberse a una simple omisión (involuntaria).

Consideremos el siguiente modelo de Programación Lineal que hemos resuelto en un artículo previo a través del Método Simplex:

La tabla final óptima que considera las variables s1, s2 y s3 como las respectivas holguras de las restricciones del problema es:

Por ejemplo, consideremos que se desea incorporar una nueva restricción definida por la siguiente expresión: 3X+Y<=600. ¿Cambia la actual solución óptima y valor óptimo?.

Para responder a lo anterior se recomienda evaluar la actual solución óptima en la nueva restricción; si ésta se cumple entonces el modelo conserva su solución óptima y valor óptimo; en caso contrario la solución óptima actual será infactible y se debe incorporar esta situación en el modelo original para encontrar la nueva solución del mismo. Notar que también puede suceder que al agregar una nueva restricción que no satisface la solución actual el problema podría resultar ser infactible al tener un dominio de soluciones factibles vacío.

En nuestro ejemplo al evaluar obtenemos: 3(100)+(350)<=600, es decir, la solución óptima actual es infactible al incorporar esta nueva restricción.

Para incorporar esta modificación en la tabla final del Método Simplex agregamos una nueva fila y una nueva columna asociada a una variable s4>=0 que será la holgura de la nueva restricción. La tabla queda de la siguiente forma:

Las variables básicas del problema original son x, s2 e y, respectivamente. Al incorporar la nueva restricción (fila) tanto x como y pierden la estructura de la identidad característica de las variables básicas. Por ello para formar la base podemos realizar operaciones fila multiplicando por -3 la fila 1 y sumando ésta a la fila 4. Posteriormente multiplicar por -1 la fila 3 y sumar a la fila 4:

Ahora las variables básicas son x, s2, y, s4 (enumeradas en el orden en el cual aparecen en la identidad), sin embargo, la variable s4 toma un valor de -50 lo cual no corresponde a una solución básica factible.

¿Cómo continuar con las iteraciones?. Utilizando el Método Simplex Dual se recomienda corroborar que la nueva solución óptima corresponde a x=250/3 e y=350.

Adicionalmente podemos utilizar un enfoque de Resolución Gráfica para el problema anterior. El siguiente gráfico representa la resolución del escenario inicial donde la solución básica factible óptima se alcanza en el vértice C con x=100 e y=350.

Al incorporar la nueva restricción (recta color rojo) el dominio de soluciones factibles se ve reducido, donde ahora ya no son factibles los puntos en el polígono con área achurada color verde (donde se puede verificar que el vértice C es infactible).

Si se resuelve gráficamente sobre el nuevo dominio (área achurada color naranjo) las curvas de nivel de la función objetivo (recta punteada color azul) pasa por última vez en el vértice F donde x=250/3 e y=350 como solución óptima del nuevo problema.

Cambio en el Lado Derecho de las Restricciones (Programación Lineal)

El vector del lado derecho asociado a las restricciones de un modelo de Programación Lineal puede tener distintas interpretaciones prácticas como, por ejemplo, la disponibilidad de insumos para la fabricación de determinados productos, limitantes de capacidad, requisitos de demanda, entre otros.

En consecuencia resulta de interés analizar el impacto del cambio de uno o varios coeficientes del vector de lado derecho sobre los resultados originales del modelo sin la necesidad de reoptimizar, es decir, sin que tener que resolver nuevamente un modelo que incorpore los cambios propuestos.

En este contexto, si en particular se verifica que:

Se puede afirmar que se conserva la actual base óptima. Lo anterior implica que las variables básicas del modelo lo seguirán siendo bajo este nuevo escenario y por tanto la nueva solución óptima del problema se podrá encontrar a través de la resolución del mismo sistema de ecuaciones original (se conservan las restricciones activas originales).

Ahora bien, si alguno de los coeficientes en el cálculo del vector de variables básicas adopta un valor negativo, estamos frente a una solución básica infactible, lo que nos obliga a realizar una actualización de los resultados del modelo para encontrar la nueva solución, base óptima y valor óptimo, pero que no pase por la reoptimización del mismo.

Consideremos el siguiente modelo de optimización:

Al resolver este modelo de Programación Lineal con el Método Simplex se alcanza la siguiente tabla final, donde s1, s2 y s3 son las variables de holgura de las restricciones 1, 2 y 3, respectivamente:

Las variables básicas son x=100, s2=400, y=350, donde todas satisfacen las condiciones de no negatividad (es decir es una solución básica factible) y además el costo reducido de las variables no básicas (s1 y s3) son mayores o iguales a cero, condición necesaria y suficiente junto a lo anterior para garantizar que nos encontramos frente a la solución óptima del problema (solución básica factible óptima).

Adicionalmente y en relación a la proposición anterior se pueden corroborar los resultados obtenidos:

Consideremos ahora que el lado derecho de la restricción 1 cambia de su valor original 1600 a 1650. ¿Cambia la actual base óptima?. Para ello recalculamos el vector de las variables básicas:

Se puede apreciar que todos los coeficientes del vector de variables básicas (Xb) son mayores o iguales a cero, es decir, se conserva la base óptima (idénticas variables básicas) pero la solución óptima cambia a x=125, s2=250, y=350.

Adicionalmente el valor óptimo ahora es V(P)=3.175. Sin embargo, no es necesario seguir realizando iteraciones del Método Simplex (dado que estamos frente a una solución básica factible óptima) y nos ahorramos el trabajo de la reoptimización.

La pregunta natural es ¿Qué sucede si al actualizar el vector de las variables básicas al menos una de las variables toma un valor negativo?. Modifiquemos ahora en forma simultanea los lados derechos de las restricciones 1 y 2 a 2.000 y 1.500, respectivamente. El nuevo vector de variables básicas queda definido de la siguiente forma:

Notar que ahora la variables básica s2=-1.000 adopta un valor que no satisface la condición de no negatividad para las variables de decisión. Al definir lo anterior una situación de infactibilidad es necesario actualizar la tabla final del Método Simplex con el valor de las variables básicas y el valor de la función objetivo:

Para encontrar la solución óptima de este problema a partir de la tabla anterior se puede aplicar el Método Simplex Dual. La variable básica que deja la base es s2 (variable básica asociada a la fila 2 donde encontramos el “lado derecho” negativo).

Para determinar la variable que entra a la base calculamos el mínimo cuociente: Min{-3/2/-3}=1/2 ==> s1 entra a la base. Actualizamos la tabla del Método Simplex obteniendo lo siguiente:

Se puede apreciar que sólo fue necesario realizar una iteración adicional para poder obtener la solución óptima del nuevo escenario (x=400/3, s1=1.000/3, y=350) con un valor óptimo de V(P)=3.200.

El siguiente gráfico realizado con el software Geogebra permite visualizar la nueva solución óptima y estructura del problema, donde ahora la solución óptima se encuentra con las restricciones 2 y 3 activas (el problema original en su solución óptima consideraba la restricción 1 y 3 como activas):

Problema de Construcción de Viviendas resuelto Gráficamente

El siguiente problema fue enviado por uno de nuestros usuarios de la ciudad de Bogotá, Colombia:

En la ciudad de Armenia se va a demoler un barrio de 10 acres y la alcaldía debe decidir sobre el nuevo plan de desarrollo. Se van a considerar dos proyectos habitacionales: viviendas a bajo costo y viviendas a medio costo. Se pueden construir 20 y 15 unidades de cada vivienda por acre, respectivamente. Los costos por unidad de las viviendas a bajo y medio costo son $13.000 y $18.000, respectivamente. Los límites inferior y superior establecidos por la alcaldía sobre el número de viviendas de bajo costo son 60 y 100 respectivamente. De igual manera, el número de viviendas de costo medio debe estar entre 30 y 70. Se estima que el mercado potencial combinado máximo para las viviendas es de 150 (que es menor que la suma de los límites de los mercados individuales debido al traslapo entre los dos mercados). Se desea que la hipoteca total comprometida al nuevo plan de desarrollo no exceda los $2 millones. Finalmente, el asesor de la obra sugirió que el número de viviendas de bajo costo sea por lo menos de 50 unidades mayor que la mitad del número de viviendas de costo medio.

Formule como un Programa Lineal el problema del nuevo plan de desarrollo a costo mínimo y resuelvalo gráficamente.

A continuación detallamos la resolución de este problema de Programación Lineal utilizando el Método Gráfico:

1. Variables de Decisión:

X1: Viviendas de bajo costo a construir
X2: Viviendas de costo medio a construir

2. Función Objetivo: Minimizar 13.000X1 + 18.000X2

3. Restricciones:

Disponibilidad de acres: (X1/20) + (X2/15) <= 10
Límites de viviendas de bajo costo: 60 <= X1 <= 100
Límites de viviendas de costo medio: 30 <= X2 <= 70
Límite mercado combinado: X1 + X2 <= 150
Límite hipoteca total: 13.000X1 + 18.000X2 <= 2.000.0000
Sugerencia asesor de obra: X1 >= 50 + (X2/2)
No Negatividad: X1>=0 X2>=0

La resolución gráfica del modelo de programación lineal anterior se muestra a continuación utilizando el software Geogebra:

Solución Básica Factible Óptima: X1=65 y X2=30
Valor Óptimo: V(P)=$1.385.000

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:

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.

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

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:

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).

¿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:

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).

Cómo calcular Gráficamente el Precio Sombra de una Restricción

El Precio Sombra de una restricción en Programación Lineal indica cuánto cambia el valor de la función objetivo (óptimo) ante una variación marginal del lado derecho de una restricción. Se asume que el resto de los parámetros del modelo permanecen constantes. De antemano es conveniente señalar que el Precio Sombra puede ser positivo, cero o negativo y en el Blog iremos discutiendo estos distintos escenarios.

Para obtener los Informes de Sensibilidad de un modelo de Programación Lineal se puede hacer uso de herramientas computacionales como Solver de Excel, sin embargo, en esta oportunidad nos enfocaremos en el cálculo del precio sombra de una restricción en forma gráfica, lo que nos ayudará más adelante a entender los conceptos que fundamentan los resultados de Solver.

Cálculo del Precio Sombra de una Restricción con el Método Gráfico

A continuación calcularemos el precio sombra de una restricción del siguiente modelo de Programación Lineal:

La solución óptima de este modelo es X=100 e Y=350 con valor óptimo V(P)=3.100 según su resolución gráfica con Geogebra o su resolución con Solver de Excel. El siguiente diagrama muestra la solución óptima obtenida gráficamente en el vértice C, que corresponde a la intersección de la restricción 1 (R1: color rojo) y la restricción 3 (R3: color gris), siendo ésta una solución básica factible óptima.

Supongamos que deseamos saber cuánto cambiará el valor óptimo (respecto a su valor actual) si aumenta en una unidad el lado derecho de la restricción 1 pero sin resolver nuevamente el problema. El precio sombra nos permite dar respuesta a dicha interrogante y permite anticipar el nuevo valor óptimo ante una variación marginal del lado derecho de una restricción.

Un variación marginal de un lado derecho implica que la nueva solución óptima se seguirá encontrando con las actuales restricciones activas, es decir, aquellas que se cumplen en igualdad en el óptimo (esto es se conserva la base óptima).

En el caso de la restricción 1 si aumentamos su lado derecho, ésta se desplazará en forma paralela hacia arriba. Si buscamos garantizar que la nueva solución óptima aún se encontrará con R1 y R3 activas llegaremos al vértice donde actualmente se interceptan la R2 y R3 que corresponde a la coordenada X=166,67 e Y=350 (ésta será la máxima variación).

En forma análoga si disminuimos el lado derecho de la restricción 1 y buscamos mantener R1 y R3 activas en el nuevo óptimo, el último punto donde se garantiza esto es el vértice B cuyas coordenadas son X=0 e Y=350 (ésta será la menor variación). Con esta información calculamos el precio sombra de la restricción 1:

Este precio sombra es válido si el lado derecho de la restricción 1 (actualmente b1=1.600) varía entre [1.400,1.733,33]. Por ejemplo, si el lado derecho de R1 aumenta de 1.600 a 1.700 el nuevo valor óptimo será V(P)=3.100+100*1,5=3.250. Análogamente si el lado derecho de R1 disminuye de 1.600 a 1.550 el nuevo valor óptimo será V(P)=3.100-50*1,5=3.025. (Se recomienda corroborar estos resultados gráficamente con TORA o IORTutorial). Notar que si la variación del lado derecho de la restricción 1 está por fuera del intervalo [1.400,1.733,33], no se puede utilizar el precio sombra para predecir cuál será el nuevo valor óptimo.

En un próximo análisis complementaremos el cálculo del precio sombra de las restricciones 2 y 3 en conjunto con otros Análisis de Sensibilidad en la resolución de modelos de programación lineal. Hasta entonces!