2

I have the next LP problem

Maximize

1000 x1 + 500 x2 - 500 x5 - 250 x6 

Subject To

 c1: x1 + x2 - x3 - x4  = 0

 c2: - x3 + x5  = 0

 c3: - x4 + x6  = 0

With these Bounds

 0 <= x1 <= 10

 0 <= x2 <= 15

 0 <= x5 <= 15

 0 <= x6 <= 5

By solving this problem with Cplex dual algorithm I get an optimal solution of 6250. But checking the reduced costs of the variables I get the next results

Variable   value    reduced cost
1          10.0          500.0 
1           0.0         -0.0 
2          5.0          -0.0 
3          5.0          -0.0
4          5.0          -0.0 
5          5.0         250.0

Is it possible to have a positive reduced cost on a positive valued variable? Because the reduced cost value indicates how much the objective function coefficient on the corresponding variable must be improved before the value of the variable will be positive in the optimal solution, what does a positive reduced cost means on a postive valued variable?

Andrea Bustillos
  • 23
  • 3
  • What you see listed as reduced cost is really the dual value of the first upper bound constraint: if the upper bound becomes 11 instead of 10, the objective function will improve (increase in this case) by 500. When you have both upper and lower bounds and a non-zero reduced cost, that can be interpreted as the dual value of the active bound (if no bound is active, the reduced cost is of course zero). – Ioannis Aug 06 '17 at 10:13
  • Thank you for your answer, that makes a lot of sense. Because this is my first question, how do I give you narks for the right answer? – Andrea Bustillos Aug 07 '17 at 15:22
  • Glad that it helped. I am not sure if you can give marks on a comment, but it is not that important anyway. You can perhaps update/accept the answer below, as it is correct, and it revolves around the same argument. And, welcome to SO! – Ioannis Aug 07 '17 at 16:02
  • 1
    Ok, done and thank you so much! – Andrea Bustillos Aug 07 '17 at 17:58

1 Answers1

0

Variable 1 is listed twice in the solution?

Note that you need to distinguish between nonbasic at lower bound and nonbasic at upper bound. The reduced cost indicates how much the objective can change when the corresponding bound changes by one unit.

Note also that most textbooks focus on the special case x >= 0 while practical solvers support both lower and upper bounds: L <= x <= U.

Erwin Kalvelagen
  • 15,677
  • 2
  • 14
  • 39