help-glpk
[Top][All Lists]

## [Help-glpk] sensitivity analysis

 From: kolos . agoston Subject: [Help-glpk] sensitivity analysis Date: Fri, 6 Mar 2015 14:45:17 +0100

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