L3 - Duality and Sensitivity Analysis Flashcards
Who created the Duality theory?
John von Neumann (Princeton IAS)
- There are two mirror problems in optimisation: a manager trying to maximise profit subject to some constraints and accountant or comptroller is trying to minimise resources to get to the same profit
What is the objective function for the controller?
The constraints are now written ATy >= c where c is the amount of profit each of the goods are going to generate
What is the primal problem?
- This will give me how much i need to produce
What is the Duel problem?
- It mirrors the primal
- A is transposed and c/b and x/y are swapped
- You are now minimising
Doing the Duel or Primal optimisation will still get you the same optimal profit.
- Will tell me how much each of the input resources are worth to me
How do you do a minimisation optimisation in MATLAB?
- Write all the variables as negative
What is the shadow price?
- it is the solution of the duel optimisation
- shadow price shows how much each resource is worth to you ( same as the value of lamda in a lagrangian optimisation?)
What is the weak duality Theorem?
gap between primal and dual so not at the optimal solution
by(bar) -cx(bar) >= 0
What is the strong duality theorem?
- The profit of the Dual is the same as the Primal
What is the meaning of the weak duality theorem?
- You are at a nonoptimal point where the primal is not producing the maximum profits and costs are too high according to the duel
- so in weak form duality, there is always a gap and only in strong form does the gap disappear when the primal meets the duel (both of them are optimal and will lead to the optimal solution)
What is complementary slackness?
•If we take the second of the equalities in 5.7, we note that for every constraint it must hold the following:
- • yjwj = 0
- This gives rise to the following three possibilities
- y ≠ 0 but wj = 0
- wj = 0 and yj = 0 –> when a constant is at the optimal but not binding
- degeneracy –> (ΔP/Δbj) = 0
- wj ≠ 0 but yj = 0
- •Thus, if a constraint is not binding, wj is different from zero, and the shadow price must be zero. –> there is no shadow price
- means that we consider buying more of a resource
- •If a constraint is binding, then the shadow price can be null or not.
- •What does this mean in terms of resource management?
- It means that we do not need to spend money to buy resources that we have not completely exploited given the optimal plan.
- •Thus, if a constraint is not binding, wj is different from zero, and the shadow price must be zero. –> there is no shadow price
How can the shadow price be interpreted?
What do we mean by a binding constraint with respect to the geometric feasible region?
- A binding constraint will indicate which vertex we are on
How do you mathematically tell if a constraint is binding or not?
A * X* = the absorption function at X* –> this is the left-hand side of the constraint and shows how many resources we need to reach the optimal solution
- Ax* = b
- w = bT - Ax* = 0
- If this equation is actually w > 0 we are not actually exhausting the resources
- We have three values that characterise our resources
- bj shows how much we
- yj (corresponding shadow price) –> shows how much that resources costs
- wj –> how much of the resources we have left (have - consumption)
What is an important thing to remember when resources change?
- If you have more resources, unless you change the optimal plan, you are not going to exploit them
- ΔP = shadow price * Δresources???
- As shadow prices show how much the resource is worth to me?
- Although after a certain point the shadow price = 0 (as we go past the optima point) –> or gets smaller as you tend towards the optimal point
Lotsa Pasta example of resource increase?
- Given that the shadow price is 40 —> a trader offers you 2 pounds of wheat germ for 60 EUR do you accept
- Yes because profit generated by the increase is 40*2 = 80 as this is greater than 60 we would generate a profit of 20
- What if he offered it at 90EUR
- No cause then we would make a loss of ten
