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:

Modelo de Programación Lineal

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

Tabla Optima Metodo Simplex

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:

tabla-simplex-nueva-restric

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:

simplex-nueva-restriccion

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.

solucion-grafica-nueva-rest

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.

dominio-nueva-restriccion

Rating: 5.0. From 1 vote.
Please wait...

, , , , , , ,

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

  1. René 16/06/2013 en 21:32 #

    Buen material muy fácil como se muestra la solución del problema.

Deja un comentario