LP Flashcards
What is the Weak Duality Theorem?
For Primal objective function transpose(c) * x and Dual objective function transpose(b) * y, transpose(c) * x <= transpose(b) * y.
e.g., for any feasible y, the Dual obj function transpose(b) * y UPPER BOUNDS the Primal obj function transpose(c) * x.
What does it mean when we find a feasible x (from Primal) and feasible y (from Dual) such that transpose(c) * x == transpose(b) * y?
It means x and y are both optima! (of their respective problems)
If the Primal is unbounded, then what is the Dual?
Infeasible
If the Dual is unbounded, then what is the Primal?
Infeasible
Is the relationship between Primal and Dual regarding feasibility and boundedness biconditional (iff)?
No
What is the standard form of a linear programming problem?
maximize transpose(c) * x given the following constraints:
Ax <= b
x >= 0
How do we check whether an LP is feasible or not?
Given an LP in a standard form…
maximize transpose(c) * x
Ax <= b
x >= 0
We add a new, unrestricted variable z to the Ax <= b constraint:
Ax + z <= b
This is always satisfiable with a negative enough z. But if there is a z >= 0 that satisfies the equation, then the original LP is feasible!
So we create a new LP:
max z
Ax + z <= b
x >= 0
And check if the solution z >= 0!
How do we check whether an LP is unbounded?
- Check whether Primal is feasible
- Check whether Dual is INfeasible
If both true, then the Primal is unbounded.
Why?
Weak Duality tells us that if Dual is infeasible than the Primal is infeasible or unbounded. We verified Dual is infeasible, then ruled out the Primal being infeasible, so Primal must be unbounded.
If Dual is infeasible, then the what is the Primal?
Primal is either infeasible or unbounded
What is the Strong Duality Theorem?
The Primal LP is feasible and bounded iff the Dual LP is feasible and bounded.
Can be reformulated as:
The Primal LP as optimum x_star iff the Dual LP has optimum y_star AND transpose(c) * x_star = transpose(b) * y_star
