Dualidad y análisis de sensibilidad

"El dual te muestra el mismo problema desde el otro lado del mostrador."

Qué vas a aprender en este capítulo

Una vez que tenés el óptimo, surge la pregunta interesante: ¿qué pasa si los datos cambian? En la práctica, los $c_j$ (precios), $b_i$ (recursos) y $a_{ij}$ (coeficientes técnicos) son estimaciones. El modelo no sirve si su solución se cae con un cambio mínimo.

La dualidad y el análisis de sensibilidad responden:

¿Cuánto vale cada recurso? (precio sombra).
¿Cuánto puede cambiar un coeficiente sin que la solución cambie?
¿Conviene comprar más recurso $i$ ? ¿Hasta qué precio?
¿Vale la pena producir un nuevo producto? (costo reducido).

Estas son las preguntas que tu cliente realmente te va a hacer. Si solo le entregás "produzcan 40 pupusas de queso", no le servís de mucho. Si le explicás "y si compran 1 kg más de queso ganan $X extra", le diste valor real.

3.1 El problema dual

💡 Intuición

Volvé a la pupusería. Vos tenés recursos (masa, queso, chicharrón) y querés convertirlos en ingresos. Un comprador externo te ofrece: "te compro todos tus recursos a tal precio cada uno; vendele a mí en vez de hacer pupusas".

¿Te conviene? Si los precios que te ofrece igualan o superan lo que vos ganarías produciendo, sí. Si no, mejor producís.

El problema dual plantea exactamente eso: "encontrar los precios mínimos a los que un comprador querría adquirir todos los recursos, respetando que ningún producto deje al productor con pérdida".

El teorema fuerte de dualidad dice algo asombroso: el óptimo del primal = óptimo del dual. Mismo número, dos interpretaciones.

Esa equivalencia es la base de los precios sombra (cuánto vale cada recurso adicional) y del análisis económico de la solución.

📐 Fundamento

Reglas para construir el dual (asumiendo primal en forma de maximización con $\leq$ ):

Primal (max)	Dual (min)
$n$ variables	$n$ restricciones
$m$ restricciones	$m$ variables
Coeficientes $c_j$ del objetivo	RHS del dual
RHS $b_i$	Coeficientes objetivo del dual
Matriz $A$	Matriz $A^T$ (transpuesta)
Variable $\geq 0$	Restricción $\geq$
Restricción $\leq$	Variable $\geq 0$
Restricción $=$	Variable libre

Ejemplo de transformación:

Primal:

\max Z = 0.50 x_1 + 0.65 x_2

x_1 + x_2 \leq 100,\; 30 x_1 + 20 x_2 \leq 2000,\; x_2 \leq 50,\; x_j \geq 0

Dual: una variable $y_i$ por cada restricción primal:

\min W = 100 y_1 + 2000 y_2 + 50 y_3

\text{s.a.} \quad y_1 + 30 y_2 \geq 0.50 \quad (\text{producto } x_1)

y_1 + 20 y_2 + y_3 \geq 0.65 \quad (\text{producto } x_2)

y_1, y_2, y_3 \geq 0

Lectura: "¿cuál es el costo mínimo de los recursos (mortar de masa $\cdot$ 100 + ...) que iguale o supere el ingreso por unidad de cada producto?"

Teoremas clave

Dualidad débil: para todo $x$ primal factible y $y$ dual factible: $c^T x \leq b^T y$ .
Dualidad fuerte: si el primal tiene óptimo finito, $c^T x^$ = b^T y^* $c^{T} x^{*} = b^{T} y^{*}$ *.
Holgura complementaria: en óptimo, para cada par $(x_j, j\text{-ésima restricción dual})$ :
- O $x_j^* > 0$ y la restricción dual $j$ está activa.
- O $x_j^* = 0$ y la restricción dual puede tener holgura.
(Y simétricamente para $(y_i, i\text{-ésima restricción primal})$ .)

3.2 Precios sombra

📐 Fundamento

Precio sombra $y_i^*$ = valor de la variable dual $i$ en óptimo = incremento marginal del objetivo Z por aumentar $b_i$ en una unidad (dentro de un rango).

y_i^* = \frac{\partial Z^*}{\partial b_i}

Interpretación:

$y_i^* > 0$ : la restricción $i$ está activa (saturada). El recurso es escaso. Conseguir más unidades vale $y_i^*$ por unidad.
$y_i^* = 0$ : la restricción tiene holgura ( $s_i > 0$ ). El recurso sobra. Conseguir más no aporta — no pagués por él.

Aplicación práctica: ¿conviene comprar más queso?

Si el precio sombra del queso es $y_2^* = 0.02$ $/g, conseguir 1 kg más vale$ 20 adicionales en ingresos. Si te lo venden a $15/kg, gastalo, te quedan$ 5 de ganancia adicional. Si te lo cobran $25/kg, no.

Esa lógica simple es la base de toda decisión "cuánto pagar por X" en operaciones e inversión.

3.3 Costo reducido

📐 Fundamento

Costo reducido $\bar c_j$ = penalización por usar la variable $x_j$ si no está en la solución óptima.

\bar c_j = c_j - \sum_i a_{ij} y_i^*

Interpretación:

Si $\bar c_j > 0$ y $x_j^* = 0$ : la variable no entra porque su contribución al objetivo es menor que el "costo" de los recursos que consumiría (medido en precios sombra). Para que entrara, $c_j$ debería subir al menos $\bar c_j$ unidades.
Si $\bar c_j = 0$ : el cambio es marginal — entre y no afecta $Z$ .

Aplicación práctica: ¿conviene introducir un nuevo producto?

Pupusería evalúa lanzar pupusa loca ($0.80/unidad, usa 60 g masa, 25 g queso, 15 g chicharrón).

Costo reducido: $\bar c_{loca} = 0.80 - (60 \cdot y_1^* + 25 \cdot y_2^* + 15 \cdot y_3^*)$ .

Si $y^* = (0.10, 0.02, 0.01)$ (precios sombra del óptimo actual):

$\bar c_{loca} = 0.80 - (6 + 0.50 + 0.15) = -5.85$ .

Negativo en problema de maximización = entra ya. Conviene introducir el producto.

(Para minimización, las desigualdades se invierten.)

3.4 Análisis de sensibilidad (post-óptimo)

📐 Fundamento

Después de obtener el óptimo, querés saber cuánto pueden cambiar los datos sin invalidar tu solución.

Cambios en $c_j$ (coeficientes objetivo)

Hay un rango $[c_j^-, c_j^+]$ dentro del cual la misma base sigue siendo óptima (mismas variables en la solución; sus valores pueden ajustarse).

Si $c_j$ sale del rango: otra variable entrará. Tenés que re-optimizar (Simplex desde la base actual; normalmente toma 1-2 pivotes).

Excel Solver y PuLP reportan estos rangos en el reporte de sensibilidad.

Cambios en $b_i$ (lados derechos)

Hay un rango dentro del cual el conjunto de restricciones activas no cambia. Dentro del rango:

\Delta Z = y_i^* \cdot \Delta b_i

Lineal en $\Delta b_i$ . Fuera del rango: el cambio deja de ser lineal — otra restricción se vuelve activa y el precio sombra cambia.

Añadir restricción nueva

Chequeás si el óptimo actual la satisface:

Si sí: sigue siendo óptimo.
Si no: tenés que re-optimizar (Dual Simplex es eficiente acá).

Añadir variable nueva

Calculás su costo reducido. Si entra ( $\bar c_j$ con signo correcto), re-optimizás.

3.5 Reporte de sensibilidad en software

🛠️ Aplicado

Excel Solver

Cuando resuelve, ofrece 3 reportes: Answer, Sensitivity, Limits. El Sensitivity Report te muestra:

Variable Cells: valor óptimo, costo reducido, rango de $c_j$ .
Constraints: valor en óptimo, precio sombra, rango de $b_i$ .

Python — PuLP

# Después de m.solve():
for v in m.variables():
    print(f"{v.name} = {v.varValue}, reduced cost = {v.dj}")

for c in m.constraints.values():
    print(f"{c.name}: slack = {c.slack}, shadow price = {c.pi}")

v.dj = costo reducido. c.pi = precio sombra (variable dual asociada).

Python — scipy

res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')
print("Marginals (precios sombra):", res.ineqlin.marginals)
print("Costos reducidos:", res.upper.marginals + res.lower.marginals)

(scipy 1.10+. Versiones anteriores no reportan duales bien.)

📝 Ejemplo trabajado — análisis completo de la pupusería

Resolvemos:

\max Z = 0.50 x_1 + 0.65 x_2

x_1 + x_2 \leq 100,\; 30 x_1 + 20 x_2 \leq 2000,\; x_2 \leq 50,\; x_1 \geq 30,\; x_j \geq 0

Óptimo (calculado en cap. 2 con la corrección): $x_1 = 30$ , $x_2 = 50$ , $Z = 47.50$ .

Activas: $x_1 \geq 30$ y $x_2 \leq 50$ . Holgura: masa = $100 - 80 = 20$ ; queso = $2000 - 30 \cdot 30 - 20 \cdot 50 = 100$ .

Precios sombra (típicos en este óptimo):

Masa: $y_1^* = 0$ (sobra → no vale más). ✓
Queso: $y_2^* = 0$ (sobra → no vale más). ✓
Chicharrón: $y_3^* = 0.65$ (saturada — cada g más vale $0.0325 en ingresos).
Contrato $x_1 \geq 30$ : $y_4^* = -0.15$ (activa — relajar el mínimo a 29 ganarías $0.15).

Interpretación de negocio:

Conseguir más masa o queso: no vale. Sobran.
Conseguir más chicharrón: conviene hasta el precio sombra.
Renegociar el contrato con la cooperativa para bajar a 25 pupusas mínimo: ganarías $0.75 extra/día. Probablemente no vale la pena la negociación.

Lección: los precios sombra te dan agenda de acciones. Es muy raro que el cliente quiera "el plan óptimo"; lo que quiere es saber qué hacer para que el óptimo mejore.

3.6 Errores comunes

⚠️ Trampa común

Interpretar precio sombra fuera de su rango de validez. "El precio sombra del chicharrón es $0.0325/g, así que comprar 10 kg más me daría$ 325 extra." Falso: el precio sombra es marginal, válido dentro de un rango. Más allá del rango, otra restricción se vuelve activa y el precio sombra cambia (suele bajar).

Tip: siempre reportá precio sombra junto con el rango de validez. Si el rango es chico, la información es local; si es grande, podés extrapolar más.

⚠️ Trampa común

Confundir holgura con precio sombra. Restricción no activa tiene precio sombra cero, aunque tenga holgura grande. Suena contradictorio ("¡sobra mucho recurso!") pero correcto: si sobra, una unidad más no aporta nada al óptimo. El recurso solo "vale" si la restricción está saturada.

Tip: memorizá: holgura > 0 ⇔ precio sombra = 0.

⚠️ Trampa común

Confiar en el sensibilidad como predicción robusta. Sensibilidad asume que cambian uno o dos parámetros a la vez. Si muchos cambian simultáneamente, la solución puede saltar a otra base de manera no obvia.

Tip: para escenarios complejos, usá simulación de Monte Carlo: muestreas parámetros desde sus distribuciones, resolvés muchas veces, mirás la distribución de las soluciones. La sensibilidad analítica es un vista local; Monte Carlo da una vista global.

3.7 Resumen visual

Primal (max)                Dual (min)
─────────────               ─────────────
n variables                 m variables
m restricciones (≤)         n restricciones (≥)
c (objetivo)        ↔       b (objetivo)
b (RHS)             ↔       c (RHS)
A                   ↔       Aᵀ

         ↓                  ↓
      Óptimo Z*  =  Óptimo W*    ← dualidad fuerte


Para cada restricción primal i:
  - holgura sᵢ > 0  ⟹  precio sombra yᵢ* = 0
  - holgura sᵢ = 0  ⟹  precio sombra yᵢ* puede ser > 0

Para cada variable primal j:
  - xⱼ* > 0  ⟹  costo reducido c̄ⱼ = 0
  - xⱼ* = 0  ⟹  costo reducido c̄ⱼ ≥ 0

3.8 Ejercicios

Construí el dual de:

\min Z = 4x_1 + 5x_2,\; 2x_1 + x_2 \geq 6,\; x_1 + 3x_2 \geq 9,\; x_j \geq 0

En el ejemplo de la pupusería, calculá el costo reducido de una "pupusa de espinaca" hipotética ($0.55, 50 g masa, 25 g queso, 0 g chicharrón). ¿Conviene introducirla?
Resolvé la pupusería original con PuLP y reportá precios sombra y rangos de validez. Generá una recomendación de 1 página para el dueño.
Verificá empíricamente la dualidad fuerte: resolvé un problema PL y su dual; mostrá que ambos óptimos son iguales.
Si subís $b_2$ (queso) de 2000 a 2500, ¿cuánto cambia $Z$ ? (Asumí que el rango lo permite.)
Construí un caso donde un precio sombra es negativo. ¿Qué significa?

3.9 Para profundizar

Bertsimas & Tsitsiklis, Introduction to Linear Optimization, cap. 4-5.
Williams, Model Building in Mathematical Programming — joya práctica con casos reales.
Anderson, Sweeney & Williams, An Introduction to Management Science — orientado a admin/negocios.
Siguiente capítulo: Programación entera y problemas de redes.

3.10 Mini-proyecto integrador

🏗️ Avance del proyecto — Análisis dual

Continuación.

Entregables (cap. 3):

Calculá precios sombra de tu solución.
Calculá costos reducidos de cualquier variable no usada.
Identificá rango de validez de cada precio sombra.
Generá una recomendación de 1 página para el "cliente" con:
- Solución óptima propuesta.
- Cuáles restricciones son críticas (saturadas).
- Cuáles recursos comprar más, hasta qué precio.
- Cuál parámetro monitorear (el de rango más estrecho).

Criterio: un gerente no técnico puede leerlo y tomar 3 decisiones concretas.

Definiciones nuevas: problema dual, dualidad débil, dualidad fuerte, teorema de holgura complementaria, precio sombra (variable dual), costo reducido, análisis de sensibilidad, rango de validez, base óptima, restricción activa, restricción no activa.

← Anterior Programación lineal y método Simplex Siguiente → Programación entera y problemas de redes

Reportar error en este capítulo · Patrocinar este libro

Dualidad y análisis de sensibilidad

Qué vas a aprender en este capítulo

3.1 El problema dual

Teoremas clave

3.2 Precios sombra

3.3 Costo reducido

3.4 Análisis de sensibilidad (post-óptimo)

Cambios en cjc_jcj​ (coeficientes objetivo)

Cambios en bib_ibi​ (lados derechos)

Añadir restricción nueva

Añadir variable nueva

3.5 Reporte de sensibilidad en software

Excel Solver

Python — PuLP

Python — scipy

3.6 Errores comunes

3.7 Resumen visual

3.8 Ejercicios

3.9 Para profundizar

3.10 Mini-proyecto integrador

Cambios en $c_j$ (coeficientes objetivo)

Cambios en $b_i$ (lados derechos)