Duality Flashcards
What is the Duality Theorem in Linear Programming?
The Duality Theorem states that every linear programming problem (primal) has a corresponding dual problem, and both have the same optimal value if they are feasible.
How is the dual of a linear programming problem formed?
To form the dual problem, transform the primal’s constraints into the dual’s objective function, and vice versa, using transposition of the coefficient matrix and transforming the inequalities.
What is the economic interpretation of duality?
In the dual problem, variables can be interpreted as shadow prices, representing the worth per unit of resources, which are the constraints in the primal problem.
What does Farkas’ Lemma state in the context of linear programming?
Farkas’ Lemma states that a linear system has a solution if and only if a certain associated inequality does not hold for any nonnegative multipliers, which helps in proving the feasibility and boundedness in the context of duality.
What is the significance of the proof of the duality theorem using the Simplex method?
It provides a foundational understanding that if the primal is feasible and bounded, the dual is also feasible and bounded, and they share the same optimal solution value.
How does the physical interpretation of duality help understand its principles?
By considering the primal variables as coordinates in space affected by forces (like gravity), the dual variables can be seen as forces ensuring the primal solution is at equilibrium, thus achieving the optimal solution.
What is a shadow price in the context of duality?
A shadow price is the change in the objective function value per unit increase in a right-hand side value of a constraint, indicating the worth of loosening that constraint by one unit.
How do changes in objective function coefficients affect the dual?
Changes in the primal’s objective function coefficients reflect directly on the constraints of the dual problem, influencing the feasibility and optimality of the dual solution.
What is the proof technique using Farkas’ Lemma for the duality theorem?
The proof using Farkas’ Lemma typically involves showing that if a certain system related to the primal has no solution, then a corresponding dual system must have a solution, hence proving duality.
How are reduced costs interpreted in the context of duality?
Reduced costs represent the opportunity cost of not engaging a unit more of an activity in the optimal solution, essentially the cost of consuming one more unit of resource than allowed by the constraint.
