1. Sensitivity analysis in PuLP
Well done on getting this far. Our final topic is sensitivity analysis in PulP where we will look at more flexible constraints.
2. Sensitivity analysis in linear programming
Solutions can and will change when problem specifications change.
Sensitivity analysis changes one parameter in a model and answers how much the output or outcome changes.
In linear programming it answers how much the value of the objective changes at the optimum.
We'll discuss three approaches for sensitivity analysis in linear programming.
Changing a variable coefficient in the objective.
Changing a variable coefficient in the constraint.
Changing the constant term in a constraint.
In all cases, we may solve the original and the changed model, where the relevant coefficient is increased by 1, and evaluate the differences.
Let's look at how to do this with PuLP.
3. Definitions
Before solving, some definitions are in order.
A satisfied constraint at the optimum is active or binding if it holds with equality. If it holds with strict inequality it is called non active, non-binding, or slack.
Slack as a noun is the amount added to the left of the constraint to make it binding. Binding constraints have 0 slack.
Shadow price is the marginal increase in the value of the objective at the optimum when the right of a constraint changes.
4. The diet problem in PuLP
Let's consider a cost minimizing diet problem.
A farmer wishes to feed his pigs at minimum cost. He has two types of food available, corn and soybean.
The cost of corn is 11 cents per pound and the cost of soybean is 28 cents per pound. The recommended diet contains at least 17% protein and 2% fat. Corn contains 10% protein and 2.5% fat, while soybean contains 40% protein and 1% fat.
The objective is 0.11C, the unit cost of corn times C the quantity of corn plus 0.28S for soybean.
For the constraints, we require that the amount of protein, which is 10 per cent times C plus 40 per cent times S is more than 17 per cent of the total weight C + S and similarly for fat and we also require that the total quantity is at least 7 pounds.
Note that we won't need to rewrite this for PuLP, which is quite handy.
5. Slack and shadow price in PuLP
First we print the status by accessing the status of the model using the LpStatus function with the status attribute of the model. We do this to ensure a solution was found. The status is optimal.
model.constraints contains an ordered dictionary where key is the name of the constraint and value the constraint along with useful information. We'll want to iterate through the items of this dictionary with a for loop.
We'll also access the attributes for slack and shadow price, slack and pi, respectively.
When slack is zero, the shadow price is positive. This makes sense since slack zero means the constraint is binding.
If we relax the constraint, then the objective should increase.
On the other hand, when slack is non-zero the constraint is non-active. Shifting the constraint does not affect its slackness and as a result the solution and the objective remain unaffected as shown with shadow price equal to zero.
6. Let's practice!
Let's practice these concepts!