Este tutorial ofrece varios ejercicios corregidos sobre el programa dual y el algoritmo de desviación complementario. 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 para la solución (0, 2, 0, 3) y para la función objetivo 15. Las soluciones del primario y el dual son iguales, hay una fuerte dualidad, por lo tanto, es una solución óptima.
Ejercicio 1
Resuelva el siguiente programa lineal usando el dual (resolución gráfica + simplex y desviaciones 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 está ubicado en el punto (6/5, 7/5) con la 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.
Por tanto, debemos 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 se trata del óptimo global del programa lineal.
Ejercicio 2
Considere el siguiente programa lineal:
Calcule la solución óptima por resolución gráfica. La función objetivo dispone de nuevo coeficiente (3, 5), para 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 modelo matemático resulta ser falso, y después de verificar el vector b de las restricciones es (950, 550, 1575, 6900). Con el dual, compruebe 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 primario es cero, por lo que las restricciones del dual están saturadas
- la primera restricción del primario 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 tanto, las variables básicas del dual son cero.
No es necesario resolver el dual porque las variables básicas 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 una solución, por lo que la solución propuesta no se encuentra en un extremo del dominio de la definición. Por tanto, no puede ser el óptimo del programa lineal.
Ejercicio 4
Al inyectar una cantidad de electricidad a la red, esta energía se difunde a través de las líneas que ofrecen la menor resistencia. Es posible conocer las líneas que tomará este flujo de energía mediante 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:
- tratamos de minimizar el costo total, es decir la suma de los porcentajes de uso de las líneas multiplicada 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).
- Resuelve un problema y encuentra una solución para el otro usando las desviaciones complementarias.
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:
Como en el ejercicio anterior, resolveremos el primario 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, esto dará el vector base (50, 300, 200, 350, 0, 0) con Z = 3700. Por una fuerte dualidad, esta es una solución óptima.
ES 
FR 
EN