Fundamentos de Programación Lineal: Modelo Dual, Precios Sombra y Análisis de Sensibilidad

Conceptos Fundamentales de Programación Lineal

1. El Modelo Dual y el Teorema de las Holguras Complementarias

Pregunta: Explique para qué sirve el modelo dual y qué establece el teorema de las holguras complementarias.

Respuesta: El modelo dual permite calcular los precios sombra de las restricciones del problema primal.

Teorema de las Holguras Complementarias:

1. El producto entre el precio sombra de una restricción primal y su holgura debe ser siempre cero.
2. El producto entre una variable primal óptima y la holgura de la restricción dual correspondiente debe ser siempre cero.

2. Restricciones con Precio Sombra Nulo

Pregunta: En el óptimo de un Problema de Programación Lineal (PPL), explique qué tipo de restricción tiene precio sombra nulo siempre.

Respuesta: Toda restricción que en el óptimo tenga una holgura mayor que cero.

3. Fundamentación: Variable Básica Dual y Holgura Primal Nula

Pregunta: Fundamente la siguiente aseveración: Una variable básica del problema dual en el óptimo tiene asociada una holgura del primal nula.

Respuesta: La variable dual es el precio sombra de una restricción primal. Si esta variable es básica en el óptimo dual, la holgura de la restricción primal debe ser cero, según el Teorema de las Holguras Complementarias.

4. Condiciones para Aseveraciones en Programación Lineal

Indique las condiciones que deben cumplir las constantes literales: a1, a2, c1, c2 y b; para que las siguientes aseveraciones sean verdaderas:

1. La presente solución es óptima y existe una solución óptima alternativa que se obtiene haciendo entrar X1 a la base y haciendo salir X2 de ella.
2. La presente solución básica es factible pero la función objetivo puede ser mejorada reemplazando H1 por X3 como variable básica.
3. La presente solución básica es factible pero el problema de programación lineal es no acotado.

Respuestas a las condiciones:

1. c1 = 0, a1 > 0, c2 > 0, b y a2 = cualquier valor
2. c1 > 0, c2 > 0
3. c1 > 0, a1 = 0

Ejercicios de Programación Lineal

Problema 1: Optimización de Reparaciones

Cuentan con un grupo de 4 maestros que trabajan 40 horas a la semana. El capital de trabajo que disponen es de [valor no especificado].

Variables:

Sean: P, T y R = m² de reparaciones a abordar en el negocio.

Función Objetivo:

MAX Z = 2 P + 4 T + 6 R

Restricciones:

• R1) P ≥ [valor no especificado]
• R2) T ≥ [valor no especificado]
• R3) R ≥ [valor no especificado]
• R4) 0,2 P + T + 2,5 R ≥ [valor no especificado]
• R5) P + 2 T + 4 R ≥ [valor no especificado]
• R6) T/100 + R/100 = 3

Problema 2: Corridas de Producción con Tecnologías

Variables:

Sean: Tn y Ta = Corridas de producción con tecnología nueva y antigua.

Función Objetivo:

MAX Z = 103 Tn + 110 Ta

Restricciones:

• R1) 7 Tn + 10 Ta ≥ [valor no especificado]
• R2) 12 Tn + 8 Ta ≥ [valor no especificado]
• R3) 8 Tn + 10 Ta ≥ 900 (Tn/112,5 + Ta/90 = 1)
• R4) 6 Tn + 7 Ta ≥ 300 (Tn/50 + Ta/43 = 1)
• R5) 5 Tn + 4 Ta ≥ 800 (Tn/160 + Ta/200 = 1)
• R6) 5 Tn + 4 Ta ≥ [valor no especificado]

F.O. Referencia con Z = 22660 es: Tn/220 + Ta/206 = 1

Solución Óptima:

Óptimo máximo en la intersección de R1 y R2:

• 7 Tn + 10 Ta = 1400
• 12 Tn + 8 Ta = 2000

Resultados:

• Tn* = 137,5
• Ta* = 43,75
• Z* = 18975 US$

Análisis de Sensibilidad en Programación Lineal

a. Identificación de Restricciones Activas y Variables Básicas

Pregunta: Identifique las restricciones activas y las variables básicas de la solución óptima.

Respuesta:

• Restricciones Activas: R1 y R2
• Variables Básicas: X1, X2, H3, H4 y H5 (aquellas con reduced cost = 0)

b. Significado del "Reduced Cost"

Pregunta: Explique el significado del valor "reduced cost = 0,714286".

Respuesta:

1. Si se produce el producto 3, la Función Objetivo (F.O.) óptima empeora en 0,714286 por cada unidad de producto 3 que se fabrique.
2. Si la ganancia unitaria del producto 3 fuese 25,714286, se podría producir el producto 3 sin que varíe el valor óptimo de la F.O.

c. Significado y Rango de Validez del "Dual Price"

Pregunta: Explique el significado del valor "Dual Price = 1,142857" indicando su rango de validez.

Respuesta: Por cada hora máquina extra en el torno, la F.O. mejora en 1,142857. Por cada hora máquina menos, empeora en esa misma cantidad. Esto es válido en el rango de cantidad de horas máquina entre 347,88 y 666,6.

d. Significado de "Slack or Surplus"

Pregunta: Explique el significado del valor "slack or surplus = 20".

Respuesta: Indica que no se produce el producto 3.

e. Impacto de una Descomposición de Máquina en la F.O.

Pregunta: La máquina fresadora se ha descompuesto y su mantención correctiva tomará 40 horas. ¿Cómo afectará esto al valor óptimo de la F.O.?, ¿no cambia?, ¿cambia y a qué valor?

Respuesta: La F.O. empeorará en 30 * 5,142857 = 154,28.

Teoría del Modelo Dual

El Teorema Dual establece que el problema primal y su dual tienen el mismo valor óptimo de su función objetivo.

Principio de Holgura Complementaria 1: Si una restricción primal tiene un valor de holgura distinto a cero, su precio sombra es cero.

Holgura de una Restricción Dual

Principio de Holgura Complementaria 2: Cuando una variable primal básica óptima es distinta a cero, la holgura de la restricción dual, valorizada en el óptimo, debe ser necesariamente igual a cero.