LP: casos especiales (ejercicios - soluciones)

Casos particulares

Este tutorial ofrece ejercicios corregidos sobre casos particulares (degeneración, M mayúscula, símplex en dos etapas).

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.

Corrección

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

que da por resolución de gráficos :

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

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

Tienes que resolver el símplex de dos fases para eliminar variables artificiales:

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

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:

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

Entrenarse

Ejercicio 1

Un minorista de electricidad prometió a sus clientes que al menos 25% de su electricidad provendrían de fuentes renovables. Ha calculado que para el próximo año tendrá un mercado de un máximo de 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 pueden aportar estos tres productores. ¿A qué productores y en qué cantidad debe este revendedor comprar su electricidad para obtener el mayor beneficio posible? Resuelve el problema lineal con el método de la gran M usando Excel.

Corrección

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

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

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

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

Y termina con la siguiente tabla:

Ejercicio 2

Resuelva el siguiente programa lineal (por Excel):

Corrección

Notamos sobre todo que hay más variables que restricciones, por lo que es necesario resolver el programa lineal pasando por el simplex y el desviaciones adicionales. El doble bajo forma canónica entonces el estándar es el siguiente:

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

Lo que resulta en:

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

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.

Valida tus habilidades

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:

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.

Corrección

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:

Lo que da como forma estándar:

Comencemos resolviendo la gran M:

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

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