3 ejercicios corregidos para casos especiales en LP

Ejercicios corregidos para casos especiales (Big M) en programación lineal

Este tutorial ofrece ejercicios corregidos en casos particulares (degeneración, M grande, simplex de dos fases).

casos particulares

Tutorial

Un corredor necesita, para sus clientes, 108 MWh de electricidad para la ciudad 1 y 96 MWh de electricidad para la ciudad 2. Sin embargo, las leyes de Kirchhoff no permiten que un distribuidor apunte a una sola ciudad para el tránsito de energía. Dos distribuidores atienden estas ciudades: el distribuidor A puede enviar 12 MWh a la ciudad 1 y 8 MWh a la ciudad 2 por lote comprado; El distribuidor B puede enviar 9 MWh a la ciudad 1 y 12 MWh a la ciudad 2 por lote comprado. Todos los lotes tienen el mismo precio. ¿Cuántos lotes debe comprar el corredor para satisfacer la demanda de energía de las dos ciudades? Resuelva por el método gráfico y por el simplex.

El programa lineal es el siguiente: X1 para el primer lote y X2 para el segundo lote

casos especiales programación lineal forma primaria ejercicios corregidos

Lo que da por resolución gráfica:

ejercicios corregidos de forma primal de programacion lineal

El gradiente es (-1, -1) porque es un mínimo (min f (x) = - max -f (x)). En el campo de la definición en verde, el punto C es el único extremo que es un óptimo global. Resolver el sistema anterior en forma de igualdad da las coordenadas (6, 4) con Z = 10.

Para la resolución del simplex es necesario sobre todo reducir a la forma estándar.

programación lineal símplex de dos fases método degenerado de la gran M

Es necesario resolver el simplex en dos fases para eliminar las variables artificiales:

programación lineal símplex de dos fases método degenerado de la gran M

Y el resultado de la primera fase. Notamos que Z = 0, por lo que hay una solución al problema:

programación lineal símplex de dos fases método degenerado de la gran M

Para la segunda fase, la fila Z se vuelve a calcular después de eliminar las columnas de variables artificiales. Para hacer esto, tomamos los buenos coeficientes de la función objetivo (-1, -1, 0, 0):

- (0) + (-1 * 6) + (-1 * 4) = -10 para la columna b (P0)
- (- 1) + (-1 * 1) + (-1 * 0) = 0 para la columna P1
- (- 1) + (-1 * 0) + (-1 * 1) = 0 para la columna P2
- (0) + (-1 * -1 / 6) + (-1 * 1/9) = 1/18 para la columna P3
- (0) + (-1 * 1/8) + (-1 * -1 / 6) = 1/24 para la columna P4

Lo que da el siguiente simplex:

programación lineal símplex de dos fases método degenerado de la gran M

Todos los coeficientes excepto la columna b son positivos, por lo tanto, el simplex ya tiene la solución óptima que es Z = 10 con el vector (6, 4, 0, 0).

Ejercicio 1

Un revendedor de electricidad prometió a sus clientes que al menos 25% de su electricidad sería de origen renovable. Calculó que para el próximo año tendrá un mercado de como máximo 18 TWh. También ha preseleccionado a tres proveedores a los que comprará su electricidad al por mayor. Aquí están las cantidades (en TWh), la tarifa de electricidad renovable y el margen generado (en miles de euros / TWh) que estos tres productores pueden aportar. ¿De qué productores y en qué cantidad este revendedor debe comprar su electricidad para obtener el mejor beneficio posible? Resuelva el problema lineal con el método M grande usando Excel.

programación lineal símplex de dos fases método degenerado de la gran M

Después del formato estándar, el problema es el siguiente, hay más restricciones que variables, por lo que podemos resolver el primario:

programación lineal símplex de dos fases método degenerado de la gran M

El problema se resuelve en dos fases porque hay una variable artificial. Aquí está la tabla de la primera fase:

programación lineal símplex de dos fases método degenerado de la gran M

Y la solución de la primera fase, notamos que Z = 0 por lo que hay una solución al problema:

programación lineal símplex de dos fases método degenerado de la gran M

Después de recalcular los coeficientes de Z, la segunda fase comienza con la siguiente tabla:

programación lineal símplex de dos fases método degenerado de la gran M

Y termina con la siguiente tabla:

programación lineal símplex de dos fases método degenerado de la gran M

Ejercicio 2

Resuelva el siguiente programa lineal (por Excel):

programación lineal símplex de dos fases método degenerado de la gran M

Se nota sobre todo que hay más variables que restricciones, por lo que es necesario resolver el programa lineal pasando por el simplex y las variaciones complementarias. El dual en forma canónica y luego estándar es el siguiente:

programación lineal símplex de dos fases método degenerado de la gran M

Por lo tanto, debemos resolver el problema de la M grande para eliminar las variables artificiales. El simplex a resolver es el siguiente:

programación lineal símplex de dos fases método degenerado de la gran M

Lo que resulta en:

programación lineal símplex de dos fases método degenerado de la gran M

Eliminando las variables artificiales y volviendo al programa dual tenemos la siguiente tabla:

programación lineal símplex de dos fases método degenerado de la gran M

La solución óptima tiene para el vector (3/7, 2/7) con Z = 65/7. Repasemos las diferencias complementarias para encontrar una solución al primario.

Las dos variables no son cero, por lo tanto, las restricciones de la primaria están saturadas. Las restricciones 2 y 3 del dual están insaturadas, por lo que la segunda y la tercera variable del primario son cero. Por tanto, debe resolverse el siguiente problema:

  • X1 + 5 X4 = 15
  • 2 X1 - 4 X4 = 10

El vector solución del primario es (55/7, 0, 0, 10/7) y Z = 65/7. Hay una fuerte dualidad, por lo que es una solución óptima de lo primordial.

Ejercicio 3

Cuando un eco-distrito produce más energía de la que consume, vende el excedente de energía al vecindario y a la red. Por lo tanto, el ecodistrito busca maximizar sus ganancias en base a ofertas del mercado local. Las ofertas del mercado son las siguientes:

Oferta n °123456
Lucro10815415
Energía (en kWh)51010517

El problema se formula de la siguiente manera: el eco-distrito busca obtener el máximo beneficio por una venta de energía de 25 kWh. El eco-distrito debe vender todo el excedente energético.

Para solucionar este problema, considere que cada oferta está representada por una variable (en porcentaje de aceptación de la oferta) que estará entre 0 y 1.

El problema se formula de la siguiente manera:

programación lineal símplex de dos fases método degenerado de la gran M

Lo que da como forma estándar:

programación lineal símplex de dos fases método degenerado de la gran M

Comencemos resolviendo la gran M:

programación lineal símplex de dos fases método degenerado de la gran M

Después de resolver la M grande y volver a la forma estándar:

programación lineal símplex de dos fases método degenerado de la gran M

Observamos que el valor Z para la variable 1, 2, 3, 4, 5 está en cero, por lo que hay un número infinito de soluciones. La solución obtenida aquí es Z = 166/5 con el vector (1, 9/10, 1, 0, 1, 0).

Compartir, repartir