The linear problem is : minimize (cost) with optimal value = 100 $ . The cost is always >=0 in my program. Also, a constraint in my program that has the form x <= 0, has a dual value of 500 $. This means that if the constraint becomes x <= 1, then the objective will become 400 $, correct? But how can this be possible, since the objective functions cannot be negative? However, when I run the linear program with x <= 1 (and all else same), my objective is 20. We would expect however to be 400 since this is what the dual value of that constraint indicated. Is there an explanation on this weird behaviour ? asked 08 Aug '14, 12:07 spyimp 
Is the variable x at its bound in both solutions? The reduced cost is a rate (change in objective per unit change in variable) and only valid as long as the current basis remains optimal. If x is basic in the new solution (indeed, if any basis change occurred), all you can really say easily is that the new objective value will be less than or equal to the old one. answered 08 Aug '14, 13:38 Matthew Salt... ♦ Mathew thanks. I write it more precisely. minimize f(x,y,z), where f(x,y,z)>=0 cost function, with optimal value $100. One of the constraints says forces x to be zero ie x=0 . The dual value of this constraint is (minus)$500, which means that if the 0 becomes 1 , then the objective function optimal value (ie $100) will increase by (minus)$500. Also the reduced cost of x is 0. So I rerun the same program with the only change being that the constraint is x=1 instead of x=0. And although I would expect the optimal value to be 100500 = $400, it turns out to be $20. Ofcourse, the objective is >=0, so it could not turn out to be $400. Then, how was it possible for the dual of x=0 to be $500, knowing that the objective cannot become negative? I thought that the dual of a constraint shows the change in the objective for a marginal change in the righthandside of the constraint. The problem is solved optimally ie no infeasibilities there.
(10 Aug '14, 12:57)
spyimp
1
The dual value doesn't say that increasing x by one decreases the objective by 500. It says that as you start increasing x, the rate at which the objective falls is 500 per unit change in x. That rate is valid only for changes in x that don't change the optimal basis. The distance that you can move x at that rate without changing the basis might be very small (might even be zero in case of degeneracy). If the basis changes, the multiplier on the constraint you are moving can change. At some point, the bound on x might even become slack, in which case, the multiplier would become zero.
(10 Aug '14, 20:07)
Matthew Salt... ♦
Thank you. I write all the information. LinearAllContinuous problem: min f(w,y,z)=cw+dy+ez, where c,d,e constants, and w,y,z decision variables and f(w,y,z) ≥ 0. One constraint says x=0, where 'x' is one decision variable that is not part of the objective function. At the optimum: f(w,y,z)=100, and dual value of constraint 'x=0' is 500. Also the reduced cost of 'x' is zero. Observations:
I resolved the exact same problem with one change only. The constraint 'x=0' becomes 'x=1'. At the optimum I get f= 20, and reduced cost of x is zero. The dual value of the constraint 'x=1' is 30 ie it changed. Observations:
(11 Aug '14, 17:04)
spyimp
1
1. x=0 doesn't necessarily imply that x is nonbasic. The fact that the RC is 0 actually suggests otherwise, but the possibility of degeneracy and multiple optima means one can't tell for sure without getting a list of basic variables. 2.5. No, it's much more complicated than that. First, RC only indicates the rate of objective change as you start to move x. It tells you nothing about how far you can move x while sustaining that rate of objective change. There's more, but the comment is too short for a full explanation. 6. x=1 doesn't imply that x is basic. You've changed the bounds on x.
(11 Aug '14, 18:26)
Matthew Salt... ♦
Is it the case that your variables are all nonnegative and the x=0 and x=1 constraints are explicit constraints in the model? In that case, you can think of the x=a constraint as two inequality constraints, x >= a and x >= a. That might help you see how the usefulness of the multiplier is limited. (In fact, try formulating your problem this way and see what multipliers you get.) Also, you need to understand degeneracy, which is certainly an issue here. You have three variables (x and two slacks) at least two of which are zero and at least two of which are basic.
(11 Aug '14, 18:43)
Matthew Salt... ♦
