> 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. _______________________________________________ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk