Este tutorial ofrece varios ejercicios corregidos sobre el programa dual y el algoritmo de desviación complementaria. Los ejercicios van seguidos de correcciones.
Tutorial
Considere el siguiente programa lineal:
Resuelve el programa lineal.
Hay cuatro variables básicas para dos restricciones, es posible que el problema no esté acotado y no tenga solución. Dado que hay dos restricciones, el dual tendrá dos variables, es fácil encontrar una solución gráfica para este nuevo programa lineal.
El dual es el siguiente:
Y aquí está su representación gráfica, con un mínimo en (1,1) y para la función objetivo 15.
Veamos las desviaciones complementarias para encontrar una solución del primario.
- Las dos variables son distintas de cero, por lo tanto, las dos restricciones de la primaria están saturadas (las restricciones se vuelven igualdad).
- En el dual, las restricciones 1 y 3 están insaturadas para la solución (1,1), esto significa que la primera variable y la tercera variable del primario son cero.
Entonces tenemos las siguientes dos ecuaciones para resolver:
- X2 + 2x4 = 8
- 2x2 + x4 = 7
Lo que da como solución (0, 2, 0, 3) y como función objetivo 15. Las soluciones de la primal y la dual son iguales, existe una fuerte dualidad, por lo tanto es una solución óptima.
Ejercicio 1
Resuelva el siguiente programa lineal utilizando el dual (resolución gráfica + desviaciones simplex y complementarias):
El programa lineal está en forma canónica, por lo que podemos calcular el dual sin cambiar la forma del programa. El dual es el siguiente:
con resolución gráfica:
El óptimo global es único y se encuentra en el punto (6/5, 7/5) con función objetivo Z= 79/5.
Para el simplex, la forma estándar agrega una variable de diferencia para cada restricción del programa lineal. La mesa final es:
El vector solución del dual es (6/5, 7/5, 0, 0, 19/5, 19/5) con Z = 79/5. Las desviaciones adicionales dan la siguiente información:
- Las restricciones tercera y cuarta del dual son insaturadas, la tercera y cuarta variables del primario son cero.
- Las dos variables básicas no son cero, por lo que las dos restricciones de la primaria están saturadas.
Entonces tenemos que resolver el sistema de ecuaciones:
- x1 + 3 x2 = 5
- 2 x1 + x2 = 7
El vector (16/5, 3/5, 0, 0) es la solución del sistema, con Z= 79/5. Existe una fuerte dualidad por lo que es el óptimo global del programa lineal.
Ejercicio 2
Considere el siguiente programa lineal:
Calcular la solución óptima por resolución gráfica. La función objetivo tiene por nuevo coeficiente (3, 5), comprobar que la solución encontrada anteriormente es siempre óptima utilizando las desviaciones duales y complementarias.
El dominio de definición es el siguiente:
La solución gráfica es el vector (5, 3) con Z = 13.
Con coeficientes de la función objetivo en (3, 5), tendremos Z = 30. Comprobemos con las desviaciones complementarias si tenemos una dualidad fuerte. El programa dual es el siguiente:
Las diferencias adicionales son las siguientes:
- las dos variables básicas del primario son distintas de cero, por lo tanto, las dos restricciones del dual están saturadas
- la primera restricción del primario es insaturada, por lo que la primera variable del dual es cero.
Por tanto, debemos resolver el siguiente sistema:
- 3 x3 = 3
- x2 – x3 = 5
El vector (0, 6, 1) es la solución del sistema, con Z = 30. Existe una fuerte dualidad, por lo tanto (5, 3) es siempre la solución óptima del programa primario.
Ejercicio 3
Considere el siguiente programa lineal:
Pruebe la optimización de la solución (250, 500, 1500) utilizando las desviaciones duales y complementarias.
El modelado matemático resulta ser falso y después de la verificación el vector b de las restricciones es (950, 550, 1575, 6900). Usando el dual, verifique si la solución es admisible y si es la solución óptima.
Lo mismo ocurre con el vector (1000, 500, 1500, 9750).
El vector (250, 500, 1500) es una solución admisible porque no se viola ninguna restricción. La solución óptima tiene el valor Z = 11500. Comprobemos su optimalidad por las desviaciones duales y complementarias. El dual es el siguiente:
Las desviaciones adicionales dan la siguiente información:
- ninguna variable base del primal es cero, por lo que las restricciones del dual están saturadas
- la primera restricción del primal no está saturada, por lo que la primera variable del dual es cero
Esto da el siguiente sistema:
- 3 X4 = 4
- X2 + 6X4 = 12
- X3 + 2 X4 = 3
Con vector solución (0, 4, 1/3, 4/3) con Z = 11500. Existe una fuerte dualidad, por lo que esta es de hecho la solución óptima.
Probemos la optimalidad de nuevo con un primario con la columna b = (950, 550, 1575, 6900), solo la función objetivo de los cambios duales. La solución es admisible y las diferencias adicionales son las siguientes:
- Las tres variables básicas son distintas de cero, por lo que las restricciones de la dual están saturadas.
- Ninguna restricción está saturada, por lo que las variables base del dual son cero.
No es necesario resolver el dual porque las variables base son todas cero (Z=0), no hay solución para el dual. Esto significa que la solución del dual no está en un extremo del dominio de definición.
Lo mismo ocurre con el vector b = (1000, 500, 1500, 9750). La solución es admisible y las desviaciones adicionales dan la siguiente información:
- Las tres variables básicas son distintas de cero, por lo que las restricciones de la dual están saturadas.
- La primera y la cuarta restricciones son insaturadas, por lo tanto, la primera y la cuarta variable básica del dual son cero.
El sistema no admite solución, por lo que la solución propuesta no se encuentra en un extremo del dominio de definición. Por lo tanto no puede ser el óptimo del programa lineal.
Ejercicio 4
Cuando se inyecta una cantidad de electricidad a la red, esta energía se difunde por las líneas que ofrecen menor resistencia. Es posible conocer las líneas que serán prestadas por este flujo energético utilizando un programa lineal.
Para ello, se debe definir la red y el flujo de energía:
- el flujo parte de una sola fuente y se difunde por el camino con menor resistencia hacia el consumidor
- las líneas son unidireccionales, el flujo de energía solo puede moverse en la dirección de la corriente que ya pasa por la línea
Una red se representa en forma de gráfico de la siguiente manera: los nodos son subestaciones y los arcos representan líneas, el nodo 1 es el origen de la fuente de energía, el nodo 7 es el destino del flujo de energía.
Las variables son:
- para cada línea, una variable entre 0 y 1 da el porcentaje de uso de la línea.
La función objetivo es la siguiente:
- buscamos minimizar el costo total, es decir, la suma de los porcentajes de uso de las líneas multiplicado por el costo de la línea.
Las restricciones son las siguientes:
- para el nodo original, la suma de las variables de los arcos salientes menos la suma de las variables de los arcos entrantes es igual a 1
- para el nodo de llegada, la suma de las variables de los arcos entrantes menos la suma de las variables de los arcos salientes es igual a 1
- para los otros nodos, la suma de las variables de los arcos salientes menos la suma de las variables de los arcos entrantes es igual a 0.
Represente el programa lineal de la gráfica anterior, calcule el programa dual y resuélvalo usando Excel. Deduzca el resultado del programa Primal, tenga en cuenta que un sistema de ecuaciones se puede resolver en Excel con el comando {= PRODUCTMAT (INVERSEMAT (Sistema); Vector objetivo)} donde los coeficientes se dan en forma de matriz.
Por ejemplo :
El programa lineal que representa el problema de la ruta más corta es el siguiente:
El siguiente programa de Excel da las soluciones del Primal en verde y las soluciones del Dual en rojo (las restricciones del Primal están en línea mientras que las restricciones del Dual están en la columna), tenga en cuenta que las restricciones de igualdad del Primal hacen que las variables del dual están en el conjunto de reales:
Las restricciones 4, 5, 7, 8 del dual son insaturadas, por lo tanto, las variables 4, 5, 7, 8 del primario son cero. Por tanto, debemos resolver el siguiente sistema:
Este sistema se puede resolver de manera muy simple sin Excel y la respuesta es el vector (0, 1, 0, 0, 0, 1, 0, 0, 1, 1) y Z = 22. Hay una fuerte dualidad, por lo que es una solución óptima. Al representar los arcos utilizados por el flujo de energía en rojo, se obtiene el siguiente gráfico de difusión:
Ejercicio 5
Una isla de energía (red local aislada de la red global) tiene dos fuentes de energía y tres aldeas de consumidores. La planta 1 produce 550 MWh y la planta 2 produce 350 MWh. La aldea 1 requiere 400 MWh, la aldea 2 requiere 300 MWh y la aldea 3 requiere 200 MWh. Por cada MWh que pasa por una línea de red, el coste en euros es el que se muestra en el siguiente gráfico:
Existe una solución si la cantidad disponible es mayor o igual a la cantidad solicitada
- Expresar el problema de minimizar el costo del tránsito de energía de los productores a los consumidores, explicar la función objetivo y las limitaciones
- Expresar el problema de maximizar el beneficio del tránsito energético (punto de vista del administrador de la red).
- Resuelva uno de los problemas y encuentre una solución para el otro utilizando huecos complementarios.
Hay 900 cantidades disponibles y tantas solicitudes, por lo que hay una posible solución. Las variables son:
- para cada línea, X representa la cantidad que pasa por la línea.
La función objetivo es la siguiente:
- Minimizar el costo total de los recursos que pasan por todas las líneas.
Las restricciones son las siguientes:
- restricciones de stock (menor o igual)
- restricciones de demanda (mayores o iguales).
El programa lineal es el siguiente:
Al igual que el ejercicio anterior, resolveremos el primal y el dual en la misma hoja de Excel:
La solución del dual da para el vector solución (0, 2, 5, 6, 3) con la quinta y sexta restricciones insaturadas. De esto se deduce que la primera restricción de la primaria no está saturada (por lo tanto, con una variable de variación distinta de cero) y que la quinta y sexta variables básicas son cero. Por tanto, debemos resolver el siguiente sistema:
Es posible encontrar una solución sin Excel, dará el vector base (50, 300, 200, 350, 0, 0) con Z=3700. Por fuerte dualidad es una solución óptima.
