Duality

Question 1

if minimising in the primal objective what does the dual solution give us?

Answer 1

the dual solution is the lower bound on the primal

Question 2

if minimising in the primal objective what does the primal solution give us for the dual?

Answer 2

the primal solution is the upper bound on the dual

Question 3

What is the weak duality theorem:

Answer 3

Weak duality states (if primal is minimising and dual is maximising) that p^Tb ≤ c^Tx

the dual is the lower bound for the optimal value of the primal, and the primal is the upper bound for the optimal value of the dual (if minimising)

Question 4

What does weak duality tell us:

Answer 4

• If the primal is unbounded the dual is infeasible
• If the dual is unbounded the primal is infeasible
• if the primal has a finite solution the dual has a finite solution and vice versa

Answer 5

A SF LP defines:
Primal: min cTx s.t. Ax = b, x ≥ 0
Dual: max pTb s.t. pTA ≤ cT

If x is feasible in the primal and p is feasible in the dual then we know that pTb ≤ cTx because we can replace b with Ax to give: pTAx ≤ cT.

Question 6

What is the strong duality theorem:

Answer 6

That if the primal has an optimal solution the dual optimal solution has one two and the values are equal:

P^Tb = C^Tx

Question 7

What can complementary slackness be used for?

Answer 7

• A proof for both weak and strong duality
• to show that a solution is optimal

Question 8

What is the complementary slackness condition:

Answer 8

if x and p are feasible solutions to the primal and dual, these are optimal if all these quantities = 0 for:
u = p(a^Tx - b)
v = x(c - p^Ta)

there is one of these quantities for each constraint

Question 9

What is u = p(a^Tx - b)

Answer 9

the left side minus the right side of the constraint in the primal multiplied by the value of the equivalent variable in the dual

Question 10

What is v = x(c - P^Ta)

Answer 10

multiply the variable in the primal by the right side minus the left side of the equivalent constraint in the dual

Question 11

How do we know if we’ve found an optimal solution for running simplex on the dual LP?

Answer 11

If all reduced costs are non-negative and all basic variables are also non-negative

Question 12

What does it mean if all the values in each row are non-negative for a dual LP?

Answer 12

That the dual is unbounded hence the primal is feasible

Question 13

Let x∗ be a basic feasible solution. Suppose that for every basis corre-
sponding to x∗, the associated basic solution to the dual is infeasible.
Then, the optimal cost must be strictly less than cT x∗.

Answer 13

The statement is true. Set up a simplex tableau for x∗. If x∗ were optimal, then using a terminating pivoting rule, we would eventually reach a tableau where the reduced costs are non-negative and the dual solution cTB B−1 is feasible. However, we are assuming that the dual solution is infeasible, so x∗ cannot be optimal

Question 14

The dual of the auxiliary primal problem considered in Phase I of the Two-Phase Simplex algorithm is always feasible

Answer 14

The statement is true. The modified problem is feasible and the optimal solution is bounded from below by 0, so there must be a finite optimum. By strong duality, the dual has to have the same finite optimum. In particular, it must be feasible.

Question 15

Let pi be the dual variable associated with the ith equality constraint in the primal. Removing the ith primal equality constraint is equivalent to introducing the additional constraint pi = 0 in the dual problem

Answer 15

The statement is true. The dual after eliminating the ith primal equality
constraint is equivalent to the original dual with pi = 0.

Question 16

If the unboundedness test of the primal Simplex algorithm is satisfied,
then the dual problem is infeasible.

Answer 16

The statement is true. In that case, the primal is unbounded, so the
dual must be infeasible by weak duality.