Hi everybody,
I have some misunderstand about GLPK's sensitivity analysis. I read several times the GLPK documentation but some details no more clear for me.
Let investigate the following problem:
max
9x1+20x2+45x3
subject to
2x1+5x2+15x3<=5000
4x1+6x2+8x3<=20000
end
I get the following output:
Status: OPTIMAL
Objective: obj = 22500 (MAXimum)
No. Row name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 r.7 NU 5000 5000 4.5
2 r.8 B 10000 20000
No. Column name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 x1 B 2500 0
2 x2 NL 0 0 -2.5
3 x3 NL 0 0 -22.5
The marginal column is the value of dual variable (as I understood). The value is OK, but why it is negative?
Becuse the dual constraint is >=? So, simply: the dual slack variables for nonnegative primal structural variables are always negatve?
Let us see the sensitivity report
Problem:
Objective: obj = 22500 (MAXimum)
No. Row name St Activity Slack Lower bound Activity Obj coef Obj value at Limiting
Marginal Upper bound range range break point variable
------ ------------ -- ------------- ------------- ------------- ------------- ------------- ------------- ------------
1 r.7 NU 5000.00000 . -Inf . -4.50000 . x1
4.50000 5000.00000 10000.00000 +Inf 45000.00000 r.8
2 r.8 BS 10000.00000 10000.00000 -Inf 6000.00000 -.62500 16250.00000 x2
. 20000.00000 10000.00000 +Inf +Inf
GLPK 4.55 - SENSITIVITY ANALYSIS REPORT Page 2
Problem:
Objective: obj = 22500 (MAXimum)
No. Column name St Activity Obj coef Lower bound Activity Obj coef Obj value at Limiting
Marginal Upper bound range range break point variable
------ ------------ -- ------------- ------------- ------------- ------------- ------------- ------------- ------------
1 x1 BS 2500.00000 9.00000 . -Inf 8.00000 20000.00000 x2
. +Inf 2500.00000 +Inf +Inf
2 x2 NL . 20.00000 . -2500.00000 -Inf 28750.00000 r.8
-2.50000 +Inf 1000.00000 22.50000 20000.00000 x1
3 x3 NL . 45.00000 . -454.54545 -Inf 32727.27273 r.8
-22.50000 +Inf 333.33333 67.50000 15000.00000 x1
End of report
The glpk documentation says:
The sensitivity analysis of active bounds is performed only for rows, which are active constraints, and only for non-basic columns, because inactive constraints and basic columns have no active bounds.
OK, it is quite logical. But, the second constraint (r.8) is not active constraint, we have 10000 slack. According to the previous sentence, the sensitivity analysis would not be performed. But what does 6000;10000 Activity range means? According to my understanding the RHS of 4x1+6x2+8x3<=20000 can be increased to infinity and can be decreased to 10000.
The previous version of sensitivity analysis is (the bounds section only) contains theese number:
Constraint Bounds Analysis
No. Row name St Value Max increase Max decrease
------ ------------ -- ------------- ------------- -------------
1 r.7 NU
UPPER 5000 5000 5000
2 r.8 B
UPPER 20000 infinity 10000
Let see x variables. Change a bit the model:
max
9x1+20x2+45x3
subject to
2x1+5x2+15x3<=5000
4x1+6x2+8x3<=7000
end
The sensitivity analysis is:
Problem:
Objective: obj = 20625 (MAXimum)
No. Row name St Activity Slack Lower bound Activity Obj coef Obj value at Limiting
Marginal Upper bound range range break point variable
------ ------------ -- ------------- ------------- ------------- ------------- ------------- ------------- ------------
1 r.7 NU 5000.00000 . -Inf 3500.00000 -3.25000 15750.00000 x2
3.25000 5000.00000 5833.33333 +Inf 23333.33333 x1
2 r.8 NU 7000.00000 . -Inf 6000.00000 -.62500 20000.00000 x1
.62500 7000.00000 10000.00000 +Inf 22500.00000 x2
GLPK 4.55 - SENSITIVITY ANALYSIS REPORT Page 2
Problem:
Objective: obj = 20625 (MAXimum)
No. Column name St Activity Obj coef Lower bound Activity Obj coef Obj value at Limiting
Marginal Upper bound range range break point variable
------ ------------ -- ------------- ------------- ------------- ------------- ------------- ------------- ------------
1 x1 BS 625.00000 9.00000 . -Inf 8.00000 20000.00000 r.8
. +Inf 1477.27273 10.40000 21500.00000 x3
2 x2 BS 750.00000 20.00000 . -Inf 18.40909 19431.81818 x3
. +Inf 1000.00000 22.50000 22500.00000 r.8
3 x3 NL . 45.00000 . -100.00000 -Inf 21500.00000 x1
-8.75000 +Inf 136.36364 53.75000 19431.81818 x2
End of report
What is Activity range for x variables? How can the RHS of xi>=0 costraint can be changed to remain the basis the same? Is it the Variable Bounds Analysis in the previous version? But what are the differences?
Variable Bounds Analysis
No. Column name St Value Max increase Max decrease
------ ------------ -- ------------- ------------- -------------
1 x1 B
LOWER 0 625 infinity
2 x2 B
LOWER 0 750 infinity
3 x3 NL
LOWER 0 136.364 100
Thank a lot, if you can help me!
Kolos