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

casos especiales programación lineal forma primaria ejercicios corregidos

que da por resolución de gráficos :

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

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

Tienes que resolver el símplex de dos fases para eliminar 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).

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.

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

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:

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

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:

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 a la 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.

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:

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.

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:

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
es_ESES
A los bloggers de %d les gusta esto: