Re: [Help-glpk] sensitivity analysis

[Andrew Makhorin]

> 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?

Because you maximize. See the glpk reference manual, Chapter 4 "Advanced
API Routines", Section 4.1 "Background" for details how reduced costs
(i.e. Lagrange multipliers) are computed.


> 
> 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? 

This corresponds to sensitivity analysis of objective coefficients, not
to analysis of active bounds.  Please read more carefully Subsection 3.4
"Post-optimal analysis routines" in the glpk reference manual.

[...]

PS: If you include glpk output in your e-mail, please use a fixed-pitch
font/formatting.