LP: Brecha dual y complementaria (ejercicios - soluciones)

Brecha dual y complementaria

Este DT ofrece varios ejercicios corregidos sobre el programa dual y el algoritmo de desviación complementaria. Los ejercicios van seguidos de correcciones.

Tutorial

Vamos a tomarlo programa lineal Próximo :

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

Resuelve el programa lineal.

Corrección

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:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

Y aquí está su representación gráfica, con un mínimo en (1,1) y para la función objetivo 15.

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

Mirémoslos desviaciones adicionales para encontrar una solución del primal.

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

Entrenarse

Ejercicio 1

Resuelve el siguiente programa lineal usando el doble (resolución de gráficos + símplex y desviaciones adicionales):

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

Corrección

El programa lineal está bajo forma canónica, podemos por lo tanto calcular el dual sin cambiar la forma del programa. El dual es el siguiente:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

con resolución gráfica:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

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 símplex, la forma estándar agrega un variable de holgura para cada restricción del programa lineal. La tabla final es:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

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:

ejercicios corregidos de brechas complementarias de forma dual de programación 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.

Corrección

los campo de definición es el siguiente:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

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:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

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:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

Pruebe la optimización de la solución (250, 500, 1500) utilizando las desviaciones duales y complementarias.

los modelo matematico resulta ser falso, y después de verificar el vector de restricción b es (950, 550, 1575, 6900). Utilizando el dual, comprueba si la solución es admisible y si es la solución óptima.

Lo mismo ocurre con el vector (1000, 500, 1500, 9750).

Corrección

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:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

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.

Valida tus habilidades

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.

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

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 :

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

Corrección

El programa lineal que representa el problema de camino más corto es el siguiente:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

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:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

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:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

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:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

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:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

Existe una solución si la cantidad disponible es mayor o igual a la cantidad solicitada

  1. 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
  2. Expresar el problema de maximizar el beneficio del tránsito energético (punto de vista del administrador de la red).
  3. Resuelve un problema y encuentra una solución para el otro usando las desviaciones complementarias.

Corrección

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:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

Como en el ejercicio anterior, resolveremos el primario y el dual en la misma hoja de Excel:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

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:

ejercicios corregidos de brechas complementarias de forma dual de programación lineal

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.

Compartir, repartir
es_ESES