1 Análisis de sensibilidad en Programación Lin-
eal con Julia/JuMP
1.1 Modelo base
Consideremos el siguiente PL de maximización:
max Z = 5xA + 6xB
s.a. 2xA + 4xB ≤ b1 (= 40),
3xA + 2xB ≤ b2 (= 30),
xA , xB ≥ 0.
Su implementación en Julia con JuMP y GLPK es:
using JuMP, GLPK
model = Model([Link])
@variable(model, xA >= 0)
@variable(model, xB >= 0)
@objective(model, Max, 5xA + 6xB)
@constraint(model, c1, 2xA + 4xB <= 40) # b1
@constraint(model, c2, 3xA + 2xB <= 30) # b2
optimize!(model)
println("xA=", value(xA), " xB=", value(xB),
" Z=", objective_value(model))
# Sensibilidad directamente desde el solver:
println("shadow_price c1=", shadow_price(c1))
println("shadow_price c2=", shadow_price(c2))
println("reduced_cost xA=", reduced_cost(xA))
println("reduced_cost xB=", reduced_cost(xB))
Para esta instancia, la solución óptima es xA = 5, xB = 7.5 y Z = 70. El
solver reporta shadow_price(c1) = 1 y shadow_price(c2) = 1, con reduced_cost(xA) =
0 y reduced_cost(xB) = 0.
1.2 Precios sombra (shadow prices)
Idea intuitiva. El precio sombra de una restricción responde: “si aumento en
1 unidad el lado derecho (RHS) de esta restricción, cuántas unidades aumenta
el óptimo Z?” Esto es válido mientras no cambie la base óptima (es decir,
mientras el punto óptimo permanezca en la misma esquina).
Definición formal. Sea el PL en forma max{c⊤ x : Ax ≤ b, x ≥ 0} y sea
y ∗ ≥ 0 una solución dual óptima del problema dual
min{b⊤ y : A⊤ y ≥ c, y ≥ 0}.
1
Entonces, en el óptimo y dentro del rango de validez de la base, un pequeño
cambio db produce un cambio en Z dado por
dZ = y ∗ ⊤ db.
Por lo tanto, cada componente yi∗ es el precio sombra de la restricción i.
Cálculo en el ejemplo. El dual del modelo base es:
2y1 + 3y2 ≥ 5,
min 40y1 + 30y2 s.a. 4y1 + 2y2 ≥ 6,
y1 , y2 ≥ 0.
En el óptimo se activan ambas desigualdades: 2y1 +3y2 = 5, 4y1 +2y2 = 6, cuya
solución es y1∗ = 1, y2∗ = 1. Así, el precio sombra de c1 y c2 vale 1: aumentar b1
o b2 en una unidad eleva Z en 1 (mientras no cambie la base).
1.3 Costos reducidos (reduced costs)
Idea intuitiva. El costo reducido de una variable indica si conviene “activar”
una variable que está en cero. En una maximización estándar con Ax ≤ b y
x ≥ 0, el costo reducido de xj mide la mejora neta marginal del objetivo al
intentar introducir xj desde cero, respetando la factibilidad dual.
Definición formal. Con y ∗ dual óptimo, el costo reducido de xj es
rj = cj − a⊤ ∗
j y ,
donde aj es la columna j de A. En el óptimo:
(
rj = 0 si xj > 0 (o degenerado con xj = 0),
rj ≤ 0 si xj = 0.
Para el ejemplo, con y ∗ = (1, 1): rxA = 5−(2·1+3·1) = 0, rxB = 6−(4·1+2·1) =
0.
Ejemplo con tercera variable. Agreguemos xC con beneficio bajo y con-
sumo de recursos:
max Z = 5xA + 6xB + 2xC ,
2xA + 4xB + 1xC ≤ 40, 3xA + 2xB + 2xC ≤ 30.
Su costo reducido (con y ∗ = (1, 1)) es rxC = 2 − (1 + 2) = −1 < 0, luego xC
permanece en 0. Si aumentamos su coeficiente a 3, entonces rxC = 3−(1+2) = 0:
queda en el límite (puede seguir xC = 0 pero con rxC = 0, caso degenerado).
Para cierto aumento mayor, la base cambiará y xC podrá entrar con xC > 0.
Implementación en Julia:
2
m = Model([Link])
@variable(m, xA >= 0); @variable(m, xB >= 0); @variable(m, xC >= 0)
@objective(m, Max, 5xA + 6xB + 2xC) # prueba con 2 y luego con 3
@constraint(m, 2xA + 4xB + 1xC <= 40)
@constraint(m, 3xA + 2xB + 2xC <= 30)
optimize!(m)
println(("xA=",value(xA), " xB=",value(xB), " xC=",value(xC),
" Z=", objective_value(m)))
println(("rc_xA=", reduced_cost(xA),
" rc_xB=", reduced_cost(xB),
" rc_xC=", reduced_cost(xC)))
1.4 Rangos de los coeficientes del objetivo que preservan
la base
En el óptimo actual, las dos restricciones son activas y el punto óptimo es la
intersección. Para que esa misma esquina siga siendo óptima, la pendiente de la
recta de nivel del objetivo debe quedar entre las pendientes de las rectas activas.
Las pendientes de las restricciones activas son:
b1 − 2xA 2 b2 − 3xA 3
c1 : xB = ⇒ pendiente − = − 12 , c2 : xB = ⇒ pendiente − .
4 4 2 2
La pendiente del objetivo es −cA /cB . Exigir − 32 ≤ − ccB
A
≤ − 21 equivale a
2
cA ≤ cB ≤ 2 cA
3
(si cB > 0). Con cA = 5, cB = 6, se cumple 3.3 ≤ 6 ≤ 10, por lo que la base no
cambia.
1.5 Rangos de los RHS (b1 , b2 ) que preservan la base
Si la esquina óptima es la intersección (ambas activas), entonces
2b − b1
xA = 2
,
2 4 xA b1 4
= ⇒
3 2 xB b2 xB = 3b1 − 2b2 .
8
Para preservar la base se requiere xA ≥ 0 y xB ≥ 0, lo que induce
2
b2 ≤ b 1 ≤ 2 b 2
3
(más no negatividad). En este rango, los precios sombra valen 1, por lo que un
incremento unitario en b1 o b2 aumenta Z en 1 mientras la base no cambie.
3
1.6 Resumen práctico
• Precio sombra (dual): en JuMP se obtiene con shadow_price(c) y
mide ∂Z/∂bi mientras no cambie la base.
• Costo reducido: reduced_cost(xj ) = cj −a⊤ j y . En el óptimo, si xj = 0
∗
entonces rj ≤ 0; si xj > 0, rj = 0 (o = 0 con xj = 0 por degeneración).
2 2
• Rangos que preservan la base: cA ≤ cB ≤ 2cA , b2 ≤ b1 ≤ 2b2 .
3 3
