dualidad Archivos - Gestión de Operaciones

Método de Descomposición de Benders

La Descomposición de Benders es, como su nombre lo dice, un Método de Descomposición. La idea de este método es bastante simple: dividir para conquistar. El objetivo es literalmente descomponer el problema en dos partes: El Master Problem (Problema Maestro) y el Subproblem (Subproblema) (también llamado Slave Problem o Problema Esclavo). En el siguiente artículo revisaremos de qué se trata el Método de Descomposición de Benders, en conjunto con la presentación de su uso en un pequeño ejemplo.

Esta metodología fue propuesta por J.F. Benders en 1962, su nombre original es Partitioning procedures for solving mixed-variables programming problems, y como su nombre bien lo dice el método está pensado originalmente para problemas de Programación Entera Mixta. Sin embargo, también se puede aplicar en problemas de Programación Lineal.

El Método de Descomposición de Benders trabaja bajo el concepto de las “variables complicadas”, es decir las variables que hacen que nuestro problema se «complique». Si estas variables no existieran (o más bien, conociéramos su valor de forma anticipada) entonces el problema resultante se supone que es considerablemente más fácil de resolver.

En Programación Entera Mixta, se espera que estas variables “complicadas” sean las enteras, las cuales al fijar su valor, dejan un problema resultante que cumple con una característica muy conveniente: es lineal. Y como cumple con esto, entonces podemos hacer uso de todo lo que conocemos sobre Programación Lineal para realizar la optimización de las variables que (en un principio) fijamos.

Veamos entonces brevemente de que se trata el Método de Descomposición de Benders. Supongamos que tenemos un problema que tiene la siguiente estructura:

Como mencionamos al principio, entonces podemos separar este problema en dos partes. A continuación se muestra el Master Problem (Problema Maestro) a la izquierda y el Subproblem (Subproblema) a la derecha:

Como se puede ver, el Master Problem contiene las variables que son enteras, y el Subproblem contiene las variables continuas, por lo que este último cumple con ser un problema de Programación Lineal.

Notar que el lado derecho de las restricciones del problema esclavo son números, ya que los valores de las variables enteras están fijos.

Iniciamos este artículo diciendo que el concepto central es dividir para conquistar: en este caso lo que se hace es resolver el Problema Maestro para obtener los valores de y; con esto, podemos resolver entonces el Subproblema. Se puede observar que el valor de la función objetivo del Subproblema se encuentra en la función objetivo del Problema Maestro, lo anterior se reformulará más adelante.

Una nota relevante: Si te das cuenta, el Problema Maestro para esta formulación no tiene ninguna restricción más que las de dominio. Nada impide que el Problema Maestro también tenga restricciones. Esto estará dado por la estructura del problema que estemos estudiando.

Recuerda siempre: ambos problemas están conectados, por lo que el resultado de uno influye directamente en el resultado del otro. Con esto en consideración, se cumple la siguiente propiedad:

Si el Subproblema es no acotado, entonces el Problema Maestro también lo es, resultando en que el problema original es no acotado.

Si tenemos un problema de Programación Lineal, entonces tenemos que aprovecharlo. ¿Qué es lo primero que se nos viene a la mente con un problema lineal? La respuesta es dualidad. Cada problema lineal (primal) tiene su problema dual asociado, el cual para el caso del problema esclavo enunciado anteriormente, tiene la siguiente estructura:

¿Qué es lo que podemos ver en este problema dual?: Que la región factible (es decir el sub-espacio definido por las restricciones y el dominio del problema) no depende del valor que tomen las variables enteras, y sólo influye en el valor de la función objetivo (notar que están en ella).

Lo anterior entonces nos lleva a la siguiente pregunta: ¿Qué sucede cuando la región factible del problema es vacía? (recuerda que al ser vacía estamos diciendo que nuestro problema dual es infactible). Dos cosas pueden ocurrir:

Al ser el problema dual infactible, entonces su primal es no acotado para algún valor de las variables enteras, en cuyo caso el problema original también es no acotado, o bien
La región factible del problema primal es también infactible para todo valor de las variables enteras, llevando a la conclusión de que el problema original es infactible.

¿Por qué revisamos todo esto?: Porque es importante tenerlo en consideración, ya que como mencionamos anteriormente, al tener un problema esclavo lineal, entonces podemos hacer el uso de los conceptos de dualidad.

¿Para qué la usaremos?: Para reformular nuestro Problema Maestro, y transformarlo en lo que usualmente se conoce como Relaxed Master Problem (RMP). Esta reformulación utiliza las variables duales asociadas a las restricciones del Slave Problem primal.

El Relaxed Master Problem (Problema Maestro Relajado) se puede escribir de la siguiente forma:

A las restricciones (1) y (2) se les conoce como restricciones de factibilidad y optimalidad, respectivamente. Además, existe una variable auxiliar z, la cual permite es la responsable de hacer la “conexión” entre el Problema Maestro y el Subproblema (esto se puede ver en las restricciones del tipo (1) y (2)).

Al resolver el RMP vamos a obtener los valores de las variables enteras, las cuales utilizaremos para resolver el Subproblema, como resultado podemos obtener dos cosas:

El sub-problema es infactible, lo cual implica que el problema dual es no acotado. Si esto ocurre, debemos agregar un corte de factibilidad al RMP.
El sub-problema tiene una solución óptima, lo cual implica que el problema dual también la tiene. Si esto ocurre, entonces hay que agregar un corte de optimalidad al RMP.

La última pregunta que nos queda por responder es: ¿Cuántas veces iterar?. Para responder lo anterior debemos definir la cota superior e inferior.

La cota superior corresponde al valor de la función objetivo original de nuestro problema; la cota inferior corresponde a la función objetivo del Master Problem, por lo tanto, debemos continuar hasta que ambos valores sean iguales.

Como la teoría de esta descomposición puede ser un poco compleja, veamos un ejemplo.

Ejemplo Método de Descomposición de Benders (Programación Lineal)

El ejemplo que veremos a continuación corresponde a un problema de Programación Lineal. La aplicación es similar para los problemas de Programación Entera Mixta.

Supongamos que tenemos que resolver el siguiente problema:

La solución óptima para este problema es: $x_{1}=0$ , $x_{2}=0,714$ e $y=1,571$ con un valor para la función objetivo (valor óptimo) de 5,285. La solución óptima del problema anterior se puede alcanzar de forma sencilla a través del Método Simplex Dual o el Método Simplex de 2 Fases (y por cierto a través de otros procedimientos y herramientas computacionales como Solver de Excel).

Vamos a descomponer el problema de la siguiente forma: recuerda que utilizaremos el RMP (Problema Maestro Relajado). Sea esta la primera iteración, K=1.

Al resolver el RMP de la primera iteración, obtenemos como solución óptima $y=0$ y $z=0$ ; lo cual utilizaremos para resolver el Subproblema. Con $y=0$ , el resultado del Subproblema es: $x_{1}=2,2$ y $x_{2}=0,4$ con un valor en la función objetivo de 5,6.

Ahora debemos calcular la cota superior (UB) y cota inferior (LB):

Como difieren el valor de las cotas, debemos continuar. Gracias a la herramienta “Análisis de Sensibilidad” del Solver en Excel, podemos obtener el valor de las variables duales asociadas a las restricciones del Subproblema (también podríamos obtener el valor de las variables duales óptimas al utilizar el Teorema de Holguras Complementarias). Esos valores son: $\lambda_{1}=-1,6$ y $\lambda_{2}=-0,2$ .

Estos valores nos permiten crear el siguiente corte de optimalidad: $-1,6(-3+y)-0,2(-4+3y)\leq z$ , el cual agregamos al Problema Maestro:

Hacemos K=2 (contador de iteraciones) y resolvemos el Problema Maestro nuevamente. Este corte nos permite encontrar una nueva solución óptima: $y=2,545$ y $z=0$ . Con este valor de y, el resultado del Subproblema es: $x_{1}=0$ y $x_{2}=0,227$ con un valor en la función objetivo de 0,68.

Ahora debemos calcular la cota superior (UB) y cota inferior (LB):

Al ver las variables duales para las restricciones del Subproblema tenemos que: $\lambda_{1}=-1,5$ y $\lambda_{2}=0$ , lo cual permite crear el siguiente corte de optimalidad el cual agregamos al Problema Maestro:

Hacemos K=3 y resolvemos el Problema Maestro nuevamente. La nueva solución óptima para el Problema Maestro es $y=1,571$ y $z=2,142$ con un valor óptimo de 5,285. Con $y=1,571$ la solución del Subproblema es: $x_{1}=0$ y $x_{2}=0,714$ con un valor en la función objetivo de 2,148.

Ahora debemos calcular la cota superior e inferior:

Como ambas cotas (superior e inferior) son iguales, podemos detenernos. Hemos encontrado la solución óptima para nuestro problema de Programación Lineal. (Mis sinceros agradecimientos a mi amigo Javier Maturana Ross por su contribución con este detallado tutorial y los créditos correspondientes al profesor Yuping Huang por el ejemplo presentado en este artículo).

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

Relaciones de Dualidad en Programación Lineal (Pasar de Primal a Dual)

El modelo dual de un problema de Programación Lineal consiste en una instancia alternativa de modelamiento matemático que nos permite rescatar la información del problema original conocido comúnmente como modelo primal.

En consecuencia es suficiente con resolver uno de ellos (primal o dual) para poder obtener la solución óptima y valor óptimo del problema equivalente (primal o dual según sea el caso). Para ello se puede utilizar, por ejemplo, las condiciones establecidas en el Teorema de Holguras Complementarias.

Las relaciones de dualidad se pueden resumir en el siguiente cuadro:

La tabla anterior se puede interpretar tanto de izquierda a derecha como de derecha a izquierda.

Primal Minimización – Dual Maximización

Por ejemplo, leyendo la tabla desde izquierda a derecha, es decir, pasar de un problema primal de minimización a un problema dual de maximización, tenemos:

Si el problema primal es de minimización, entonces su correspondiente dual será uno de maximización.
Si el problema primal tiene una restricción del tipo >=, la variable dual asociada a dicha restricción debe ser >=0.
Si el problema primal tiene una restricción del tipo <=, la variable dual asociada a dicha restricción debe ser <=0.
Si el problema primal tiene una restricción del tipo =, la variable dual asociada a dicha restricción debe ser irrestricta (libre de signo).
Si el problema primal tiene una variable >=0, la correspondiente restricción asociada en el dual debe ser <=.
Si el problema primal tiene una variable <=0, la correspondiente restricción asociada en el dual debe ser >=.
Si el problema primal tiene una variable irrestricta (libre de signo), la correspondiente restricción asociada en el dual debe ser =.

Primal Maximización – Dual Minimización

De forma análoga, interpretando la tabla desde derecha a izquierda, es decir, pasar de un problema primal de maximización a un problema dual de minimización, tenemos:

Si el problema primal es de maximización, entonces su correspondiente dual será uno de minimización.
Si el problema primal tiene una restricción del tipo <=, la variable dual asociada a dicha restricción debe ser >=0.
Si el problema primal tiene una restricción del tipo >=, la variable dual asociada a dicha restricción debe ser <=0.
Si el problema primal tiene una restricción del tipo =, la variable dual asociada a dicha restricción debe ser irrestricta (libre de signo).
Si el problema primal tiene una variable >=0, la correspondiente restricción asociada en el dual debe ser >=.
Si el problema primal tiene una variable <=0, la correspondiente restricción asociada en el dual debe ser <=.
Si el problema primal tiene una variable irrestricta (libre de signo), la correspondiente restricción asociada en el dual debe ser =.

Ejemplo Relaciones de Dualidad en Programación Lineal

A continuación presentamos un modelo de optimización que consideraremos como el problema primal y que en un artículo previo fue resuelto a través del Método Simplex de 2 Fases.

Como en este caso el problema primal es de minimización, para definir su respectivo problema dual leeremos la tabla que resume las relaciones de dualidad desde izquierda a derecha. En consecuencia, el problema dual será uno de maximización.

Adicionalmente la primera y segunda restricción del problema primal definirán las variables de decisiones (variables duales) en el problema dual (Y1 e Y2, respectivamente), siendo los coeficientes en la función objetivo los actuales valores de los lados derechos de las restricciones del problema primal.

De esta forma la función objetivo del problema dual queda definida por la siguiente expresión:

Luego por cada variable en el problema primal vamos a tener la misma cantidad de restricciones en el problema dual. En este caso las variables X1, X2 y X3 definirán la estructura de las restricciones 1, 2 y 3 en nuestro problema dual. Por ejemplo la primera restricción del problema dual (asociada a la variable primal X1) sería 2Y1+2Y2<=160.

Notar que los coeficientes que ponderan a las variables duales son los parámetros asociados a la variable X1 en el primal en la primera y segunda restricción, respectivamente. La restricción en el dual es del tipo «<=» debido a que la variable X1 en el problema primal de minimización tiene la condición de no negatividad («>=0»). Por último el lado derecho de la restricción es el coeficiente que tiene la variable X1 en la función objetivo del problema primal. Siguiendo el procedimiento las restricciones del problema dual serían:

Finalmente como las 2 primeras restricciones del problema primal son del tipo «>=» en el problema primal de minimización, las respectivas variables duales asociadas en el problema de maximización serán no negativas. De esta forma el problema dual es:

Ejercicio Propuesto: Utilizando las relaciones de dualidad en Programación Lineal, dado un problema primal P, demuestre que su correspondiente dual D queda definido de acuerdo a:

En lo que sigue, combinaremos las distintas restricciones del problema primal, ponderando por los valores no negativos $\pi_{1},\pi_{2}$ y $\pi_{3}$ cada una, respectivamente, de modo de obtener la mejor cota superior del valor óptimo del problema P). Vale decir:

De modo de garantizar que el lado derecho de esta última desigualdad sea una cota superior de la función objetivo del problema primal se debe cumplir que:

$2\pi_{1}+\pi_{2}+\pi_{3}\geq 40$

$\pi_{1}+\pi_{2}+3\pi_{3}\geq 60$

La mejor elección de esta cota se obtendría al resolver el siguiente problema de optimización:

Este problema se conoce como el problema “Dual” D) asociado al problema “Primal” P).

También resulta que al formular el problema dual de D) se obtiene el problema primal P) (o uno equivalente). Cualquiera de los dos entrega la misma información y el valor óptimo alcanzado es el mismo.

Método Simplex Dual en Programación Lineal (Ejercicios Resueltos)

El Método Simplex Dual nos ofrece una alternativa algorítmica para abordar la resolución de modelos de Programación Lineal. En particular este método se puede utilizar cuando luego de llevar a la forma estándar un modelo de Programación Lineal no se dispone de una solución básica factible inicial con la cual se pueda dar inicio a las iteraciones del algoritmo. En este contexto a continuación se presenta un ejemplo con los detalles de la aplicación de este procedimiento.

Ejemplo del Método Simplex Dual

Consideremos el siguiente problema para ilustrar sobre la aplicación del Método Simplex Dual:

Para llevar el problema anterior a la forma estándar se requiere agregar 2 variables de exceso no negativas para la restricción 1 y 2, que llamaremos respectivamente X4 y X5. De esta forma el problema en su formato estándar queda definido por:

Luego construimos la tabla inicial del Método Simplex:

¿Cómo continuar con las iteraciones del Método Simplex?. Antes de ello es necesario disponer de una solución básica factible inicial. En este contexto si quisiéramos usar X4 y X5 como variables básicas (y en consecuencia X1, X2 y X3 como variables no básicas) se requiere que X4 y X5 sean mayores o iguales a cero, sin embargo, sus coeficientes en las respectivas filas son negativos y por tanto no se dispone de la identidad (matriz con «1» como diagonal y el resto de coeficientes igual a cero).

En consecuencia para formar la identidad podemos multiplicar por «-1» la fila 1 y 2, obteniendo lo siguiente:

En la tabla anterior se tiene una solución básica (infactible en las variables primales), pero al tener costos reducidos no negativos esto define una solución básica factible en el dual.

Ahora X4 y X5 son variables básicas y adoptan los valores de -1 y -3/2, respectivamente, lo que claramente no satisface las condiciones de no negatividad para las variables de decisión, es decir, no corresponde a una solución básica factible.

Sin embargo, en esta instancia podemos aplicar el Método Simplex Dual como alternativa de resolución. Para ello seleccionaremos una variable que deje la base y adoptaremos como criterio de selección aquella variable básica asociada al lado derecho «más negativo» (con esto se busca favorecer la rapidez de convergencia).

En el ejemplo dicha variable es X5. Luego para determinar que variable entra a la base realizamos un mínimo cuociente entre el negativo del costo reducido de las variables no básicas y las entradas estrictamente menores a cero para las variables no básicas en la fila 2 (fila asociada al lado derecho más negativo).

Es decir: Min{-160/-2; -120/-2; -280/-2}=60 ==> el cuociente mínimo se alcanza en la segunda columna asociada a la variable no básica X2, por tanto dicha variable entra a la base.

En cada iteración del Método Simplex Dual se escoge un lado derecho con valor negativo, identificando la respectiva variable básica primal, quien deja la base.

Finalmente se realiza una iteración realizando las operaciones filas que sean necesarias, de modo de ingresar X2 a la base al mismo tiempo que X5 deja la base. Los resultados serían:

Notar que ahora las variables básicas son X4 y X2 donde sólo X4=-1/4 lo que no satisface la condición de ser una solución básica factible. Por lo tanto realizamos una nueva iteración, en este caso sacando de la base a la variable X4 y calculamos el mínimo cuociente: Min{-40/-1; -160/-3; -60/-1/2}=40 ==> el cuociente mínimo está en la primera columna por tanto la variable X1 entra a la base.

En consecuencia se actualiza la tabla quedando lo siguiente:

Las variables básicas ahora son X1=1/4 y X2=1/2 (que cumplen las condiciones de no negatividad). Adicionalmente el costo reducido de las variables no básicas también es mayor o igual a cero, por tanto estamos frente a la solución óptima del problema.

Se puede reconocer adicionalmente que el valor óptimo es V(P)=100 que se obtendría al evaluar la solución óptima del problema en la función objetivo, sin embargo, en el procedimiento dicho valor se obtiene con signo cambiado.

El ejemplo anterior nos permitió apreciar cómo a través del Método Simplex Dual se puede abordar la resolución de un modelo de Programación Lineal que luego de ser llevado a la forma estándar no provee una solución básica factible inicial.

Cabe destacar que el Método Simplex Dual que no es la única alternativa algorítmica a la cual podemos recurrir para resolver el problema propuesto. Por ejemplo, podríamos haber alcanzado idénticos resultados aplicando el Método Simplex de 2 Fases con algo más de trabajo.

Alternativamente podríamos definir el modelo dual al problema propuesto y resolverlo por el Método Simplex para posteriormente utilizar las condiciones del Teorema de Holguras Complementarias.

En resumen ante un modelo de optimización contamos con varias alternativas de resolución y es deber de quien resuelve evaluar los distintos caminos en términos de su complejidad y representación.

Teorema de Holguras Complementarias: Dualidad en Programación Lineal

Uno de los teoremas principales en la Teoría de Dualidad en Programación Lineal es el Teorema de Holguras Complementarias.

El Teorema de Holguras Complementarias nos permite encontrar la solución óptima del Problema Dual cuando conocemos la solución óptima del Problema Primal (y viceversa) a través de la resolución de un sistema de ecuaciones conformado por las variables de decisión (primales y duales) y las restricciones (del modelo primal y dual).

La importancia de este teorema radica en que facilita la resolución de los modelos de optimización lineal, permitiendo a quién los resuelve buscar el modelo más sencillo para abordar (desde el punto de vista algorítmico) dado que de cualquier forma podrá obtener los resultados del modelo equivalente asociado (sea éste el modelo primal o dual).

Ejemplo Teorema de Holguras Complementarias

Consideremos el siguiente modelo de Programación Lineal (en adelante Primal) en 2 variables cuya solución óptima obtenida por el Método Gráfico es X=14/5 e Y=8/5 con valor óptimo V(P)=20,8.

El modelo Dual asociado al modelo primal es: (ante dudas de cómo pasar del problema primal al problema dual se recomienda revisar el artículo Relaciones de Dualidad en Programación Lineal (Cómo pasar de Primal a Dual))

Luego, el Teorema de Holguras Complementarias plantea las siguientes relaciones:

Como sabemos X=14/5 e Y=8/5 (Solución Básica Factible Óptima del modelo primal). Si reemplazamos estos valores de X e Y en la tercera y cuarta ecuación generamos un sistema de ecuaciones de 2×2 en términos de A y B cuya solución corresponde a A=6/5 y B=2/5 (solución óptima del modelo dual). Si posteriormente evaluamos en la función objetivo del problema dual dicha solución obtenemos: V(D)=12(6/5)+16(2/5)=20,8 que es similar al valor óptimo del problema primal (Teorema de Dualidad Fuerte).

Siendo A=6/5 y B=2/5 una solución factible para el problema dual, ésta es la solución optima de dicho problema.

Observaciones: Notar que la restricción 1 y 2 del problema primal son activas en el óptimo, es decir, se cumplen en igualdad. Esto permite descartar que A y B (variables duales asociadas a dichas restricciones) son iguales a cero. Si por ejemplo, la restricción 1 del modelo primal no fuese activa en el óptimo se podría afirmar que A es igual a cero en el dual.

Ejercicio Teorema de Holguras Complementarias en Programación Lineal

Una empresa que fabrica muebles desea estudiar la producción de varios tipos de mesas de madera. Las mesas a fabricar son mesas de comedor, de centro y de arrimo, las que deben ser procesadas por 3 tipos de máquinas, una cortadora, una ensambladora y una pulidora. Se dispone de a lo mas de 80 horas de trabajo en cada una de las máquinas y 2.000 unidades de madera. La siguiente tabla muestra los tiempos y la madera necesaria para la fabricación de cada mesa, así como la utilidad que reporta cada una de ellas.

Dadas las siguientes soluciones del Problema Primal S1=(900,100,0), S2=(176,496,656), S3=(200,400,550) y S4=(800,0,400). Determine mediante el Teorema de Holguras Complementarias si alguna de estas soluciones es óptima para el Problema Primal planteado.

Sea el Problema Primal el siguiente:

Variables de Decisión:

X1 : Cantidad de mesas de comedor a producir
X2 : Cantidad de mesas de centro a producir
X3 : Cantidad de mesas de arrimo a producir

Función Objetivo:

MAX Z = 3 X1 + 3 X2 + 2 X3

Restricciones:

5 X1 + 3 X2 + 2 X3 <= 4.800 (tiempo cortadora)
2 X1 + 5 X2 + 3 X3 <= 4.800 (tiempo ensambladora)
3 X1 + 2 X2 + 5 X3 <= 4.800 (tiempo pulidora)
2 X1 + 2 X2 + 1 X3 <= 2.000 (disponibilidad de madera)
X1>=0, X2>=0, X3>=0

Su correspondiente Problema Dual asociado es:

MIN W = 4.800 Y1 + 4.800 Y2 + 4.800 Y3 + 2.000 Y4
S.A.

5 Y1 + 2 Y2 + 3 Y3 + 2 Y4 >= 3
3 Y1 + 5 Y2 + 2 Y3 + 2 Y4 >= 3
2 Y1 + 3 Y2 + 5 Y3 + 1 Y4 >= 2
Y1>= 0, Y2>=0, Y3>=0, Y4>=0

A continuación verificamos la factibilidad de las soluciones propuestas para el Problema Primal:

S1=(900,100,0), V(S1)=3.000 Satisface todas las restricciones
S2=(176,496,656) V(S2)=3.328 Satisface todas las restricciones
S3=(200,400,550) V(S3)=2.900 Satisface todas las restricciones
S4=(800,0,400) V(S4)=3.200 Satisface todas las restricciones

Todas las soluciones satisfacen todas las restricciones por lo que son todas soluciones factibles. De ellas se escoge S2 ya que entrega la mayor utilidad para verificar si es solución óptima: X1=176, X2=496, X3=656.

En restricción (1) holgura X4 = 1.120
En restricción (2) holgura X5 = 0
En restricción (3) holgura X6 = 0
En restricción (4) holgura X7 = 0

De esta forma el Teorema de Holguras Complementarias permite obtener lo siguiente:

Que al ser reducido permite obtener un sistema de ecuaciones de 3×3:

2 Y2 + 3 Y3 + 2 Y4 = 3
5 Y2 + 2 Y3 + 2 Y4 = 3
3 Y2 + 5 Y3 + 1 Y4 = 2

Solución Problema Dual : Y1=0, Y2=1/25, Y3=3/25, Y4=32/25. Al evaluar la solución alcanzada en la función objetivo del dual se obtiene: W=4.800*0+4.800*1/25+4.800*3/25+2.000*32/25=3.328. Por el Teorema de Dualidad Fuerte W=Z por lo tanto S2 es solución óptima del Problema Dual.