08_Duality

Question 1

What are the 4 Duality Properties?

Answer 1

• Weak duality property
• Strong Duality Property
• Unboundness Property
• Complementary Slackness

Question 2

Strong duality

Answer 2

for the optimal solution of the primal and dual problem:
v=z

Question 3

Weak Duality Property

Answer 3

• for a feasible but not optimal solution of the the primal problem as well as the dual problem
• v > z holds

Question 4

Unboundness Property

How to detect unboundeness

Answer 4

for an unbounded primal problem we have a feasible dual problem

Question 5

Complementary slackness

Answer 5

-if decision variable is in the basis of the optimal solution of the primal problem the slack variable of the associated constrained of the **optimal solution of the dual **= 0

• if decision variable is NBV of the optimal solution of the primal problem, **slack variable of optimal solution of dual is in the basis **

Question 6

Why can it be beneficial to use the dual simplex method?

Answer 6

• # of iterations conducted until an optimal solution is found is about 1.5 to 2 times the # of constraints of the LP
• # variables of a problem equals # of constraints of its dual
• objective function values of the optimal solution of the primal and the dual problem are equal (strong duality property)
• generally more efficient to solve the dual problem with the Simplex Algorithm if it holds: **# of variables is smaller than # of constraints in the primal **