Linear Programming

In the first edition of my book “Taking Sound Business Decisions: From Rich Data to Better Solutions”, I explain on pages 14 and 15 what the shadow price and reduced cost of a linear programming model really mean. I write the following:

• A shadow price value is associated with each constraint of the model. It is the instantaneous change in the objective value of the optimal solution obtained by changing the right hand side constraint by one unit.
• A reduced cost value is associated with each variable of the model. It is the amount by which an objective function parameter would have to improve before it would be possible for a corresponding variable to assume a positive value in the optimal solution.

Then, I continue on page 15 with a sentence as follows:

“It should be intuitively clear that the reduced cost is equal to the shadow price of the non-negativity constraint of the variable”.

In the book, I suggest the reader to think about this statement, but some people asked me to explain this statement in more detail. I guess it is less intuitive than I initially thought. Below you find some explanation. I still think, however, that it’s best not to read this and think about it for a minute. It’s not that difficult.

Let’s take a look at the model (I call it here model 1) that I use in the book. I assume that the decision variables x1 and x2 are amounts for production of ... whatever.

Model 1.
minimise cost (C) = 10 x1 + 7 x2.
subject to the following constraints:
x1 + x2 >= 10
x1 >= 0
x2 >= 0

The optimal solution is equal to x1 = 0 and x2 = 10 with an objective of 70.

In the book I explain that the reduced cost for x1 is equal to 3. Indeed, x1 is too expensive compared to x2, and therefore x1 = 0. Therefore, the cost should be reduced from 10 to 7 (or lower, so by minimum a value of 3) to make the production of x1 attractive, hence, the value of 3 for the reduced cost.

Now let’s go back to the statement: “The reduced cost of a decision variable (i.e. value 3 for variable x1) is equal to the shadow price of the non-negativity constraint of the variable (i.e. x1 >= 0)”

The shadow price for the constraint x1 >= 0 can be defined as follows: If you increase the right hand side of that constraint (currently 0) by one unit (i.e. the constraint changes to x1 >= 1), what is the impact on the objective. Hence, the model changes into (notice the small difference):

Model 2.
minimise cost (C) = 10 x1 + 7 x2.
subject to the following constraints:
x1 + x2 >= 10
x1 >= 1
x2 >= 0

The optimal solution is now equal to x1 = 1 and x2 = 9 with an objective of 73. This is exactly 3 more than the previous solution, and hence, the shadow price of the constraint x1 >= 0 in model 1 is equal to 3. This value 3 is equal to the reduced cost of x1 in model 1, which illustrates my statement.


^{Click on the picture to download the book (free)}