resolución gráfica Archivos - Página 4 de 5

Teorema de Dualidad Fuerte y Dualidad Débil (Dualidad en Programación Lineal)

En el contexto de las relaciones de dualidad en Programación Lineal, los teoremas de dualidad fuerte y dualidad débil constituyen importantes resultados teóricos que contribuye a la comprensión y resolución de modelos de optimización lineales. En el siguiente artículo ilustraremos su utilización haciendo uso de un ejemplo sencillo para fines académicos que por supuesto puede ser extendido a problemas de mayor tamaño.

Consideremos los siguientes problemas Primal (P) y Dual (D) en su formato matricial:

Lo anterior no constituye una pérdida de generalidad dado que el problema primal puede ser de maximización o de minimización con la consecuente incidencia en la interpretación de los resultados.

Teorema de Dualidad Débil

El Teorema de Dualidad Débil establece que si x є IRn, es una solución factible del problema Primal P) y ∏ є IRm, una solución factible del problema Dual D), entonces:

Es decir, en el formato descrito anteriormente, el valor que reporta una solución factible del problema dual de minimización al ser evaluada en su respectiva función objetivo, representa una cota superior del valor óptimo del problema primal de maximización.

Análogamente, una solución factible del problema primal de maximización al ser evaluada en dicha función objetivo representa una cota inferior del valor óptimo del problema dual de minimización. En conclusión: V(P)<=V(D).

En general si el problema primal tiene un dominio de soluciones factibles no acotado sin solución óptima (es decir, es un problema no acotado) el respectivo problema dual resultará ser infactible (y viceversa).

Para corroborar el Teorema de Dualidad Débil consideraremos un problema primal y su respectivo dual: (si tienes dudas respecto a las relaciones de dualidad te recomendamos leer previamente el artículo Cómo pasar de Primal a Dual y viceversa).

Una representación gráfica realizada con Geogebra del problema primal permite apreciar que el dominio de factibilidad es no acotado y su solución óptima se encuentra en el vértice C donde X1=2/5 y X2=6/5 con valor óptimo V(P)=16/5.

Notar adicionalmente que cualquier par ordenado que pertenece al área achurada es factible, por ejemplo X1=2 y X2=2 es una Solución Básica Factible para el problema primal con V(P)=8 (cota superior del valor óptimo del problema dual de maximización).

En cuanto al problema dual su dominio de factibilidad es acotado y su solución óptima se encuentra en el vértice C con Y1=2/5 e Y2=2/5 y valor óptimo V(D)=16/5. Adicionalmente existen otros puntos factibles como el origen (Y1=0 e Y2=0) con V(D)=0 lo cual permite corroborar que cualquier solución factible del problema dual al ser evaluada en la función objetivo (de minimización) genera una cota inferior del valor óptimo del problema primal de minimización.

Teorema de Dualidad Fuerte

Si un problema (Primal) de Programación Lineal tiene una solución óptima, entonces el correspondiente problema Dual también tiene una solución óptima, y los respectivos valores en la función objetivo son idénticos.

En consecuencia, del Teorema de Dualidad Fuerte se deduce que ambos problemas (primal y dual) al ser evaluados en sus respectivas soluciones óptimas (en caso de existir) proveen idéntico valor óptimo, es decir, V(P)=V(D). Es más, resulta suficiente resolver uno de ellos y luego utilizar las propiedades del Teorema de Holguras Complementarias para encontrar la solución óptima (y valor óptimo) de su problema equivalente. En nuestro ejemplo V(P)=16/5=V(D).

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.

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 que un Problema es No Acotado con el Método Simplex

El Método Simplex es un algoritmo que nos permite resolver modelos de Programación Lineal que en ciertas ocasiones permite identificar casos excepcionales como infinitas soluciones óptimas o que el problema es no acotado. En este contexto el Método Simplex rescata las condiciones establecidas en el Teorema Fundamental de la Programación Lineal.

En la aplicación del Método Simplex, un problema no acotado se detecta cuando en una iteración cualquiera existe una variable no básica con costo reducido negativo y todos los elementos en la columna de dicha variable son negativos o cero. Es decir, no se puede seleccionar un pivote para determinar la variable que debe dejar la base.

Consideremos el siguiente modelo de Programación Lineal:

Si resolvemos gráficamente dicho modelo nos podemos percatar que éste es no acotado. Notar que el dominio de soluciones factibles (área sombreada o achurada) es no acotado dado que crece indefinidamente en la dirección de la variable X2.

Las curvas de nivel de la función objetivo crecen a su mayor tasa en la dirección del vector gradiente $\triangledown f(X_{1},X_{2})=(4,6)$ lo que indica que se podría desplazar indefinidamente en esa dirección y siempre interceptar el dominio de soluciones factibles.

¿Cómo podemos detectar esta situación (Problema No Acotado? utilizando el Método Simplex?

Para ello llevamos el modelo a su forma estándar, agregando X3 y X4 como variables de holgura de la restricción 1 y 2, respectivamente. Lo anterior define la siguiente tabla inicial del método:

Notar que X2 es la variable no básica con el costo reducido más negativo y siguiendo ese criterio debería ser aquella que ingresamos a la base. Sin embargo, no es factible hacer el criterio de factibilidad o mínimo cuociente debido a que los elementos en la columna de X2 son negativos o cero. En esta instancia ya se puede afirmar que el problema es no acotado.

Observación: Se puede verificar que si seleccionamos X1 como la variable que entra a la base y se aplica una iteración del Método Simplex se llegara a una conclusión similar a la presentada anteriormente.

Diferencias entre la Programación No Lineal y la Programación Lineal

El supuesto de la proporcionalidad de la Programación Lineal (PL) no siempre es adecuado para representar de buena forma situaciones de naturaleza real que requieren de un modelo de optimización como apoyo para el proceso de toma de decisiones.

Cabe señalar que un modelo de Programación No Lineal (PNL) es aquel donde la función objetivo y/o las restricciones son funciones no lineales de las variables de decisión.

En este sentido la Programación No Lineal permite enfrentar una serie de aplicaciones prácticas que requieren una representación a través de funciones no lineales.

Algunos casos característicos de la Programación No Lineal son los problemas de minimización de distancia, economías o deseconomías de escala, carteras de inversión, ajuste de curva, entre otros.

En general cuando formulamos un modelo de optimización no lineal esperamos que éste sea más representativo de una situación real en comparación a un modelo lineal, sin embargo, a la vez asumimos que es probable que la complejidad de la resolución aumente. Por ello quien formule un modelo debe equilibrar la representatividad del mismo con la dificultad de la resolución.

A continuación presentaremos dos modelos de optimización que comparten las mismas restricciones (que asumiremos por simplicidad que son funciones lineales) y se diferencian por la naturaleza de la función objetivo (lineal y no lineal, respectivamente). Estos ejemplos nos ayudarán a explicar algunas diferencias entre la Programación Lineal y Programación No Lineal:

Si Resolvemos Gráficamente el modelo de Programación Lineal obtenemos la solución óptima en el vértice C (X=14/5 Y=8/5 y valor óptimo V(P)=20,8) lo cual corresponde a una Solución Básica Factible Óptima.

En efecto, una de las propiedades básicas de la Programación Lineal es que cuando un modelo admite solución, ésta se encontrará en un vértice (o tramo frontera en el caso Infinitas Soluciones Óptimas) del dominio de soluciones factibles. (Recomendación: Ver Teorema Fundamental de la Programación Lineal).

En cuanto a la resolución del modelo de Programación No Lineal, las curvas de nivel de la función objetivo no lineal tiene la forma de circunferencias concéntricas desde la coordenada (X,Y)=(2,4). Como la función objetivo es de minimización, buscamos la circunferencias de menor radio (o diámetro) que intercepte por primera vez el dominio de soluciones factibles. Esto se alcanza en (X,Y)=(1,2,2,4).

El resultado anterior se puede verificar mediante la aplicación de las condiciones de optimalidad que establece el Teorema de Karush-Kuhn-Tucker (KKT) al ser éste un problema de Programación No Lineal restringido.

Conclusión: Si un modelo de Programación No Lineal admite solución óptima, ésta se puede encontrar en cualquier punto del dominio de soluciones factibles.

Por ejemplo, si la función objetivo estuviese centrada en la coordenada (X,Y)=(2,1) ésta ya sería la solución óptima del problema. Notar que esta situación (solución en un punto interno del dominio factible) NO sería posible en la resolución de un modelo de Programación Lineal.

En los artículos de la categoría de Programación No Lineal analizamos algunos algoritmos especializados para la resolución de modelos no lineales como también herramientas computacionales para enfrentar este tipo de problemas.