Duality

Question 1

what is normal form?

Answer 1

Just a nice form that help us in the dual primal connection

Question 2

Give matrix notation for the primal and the dual problem when everything is in normal form

Answer 2

PRIMAL

max z = c^(T)x

s.t. Ax<=b
x>=0

DUAL

min w = b^(T)v

s.t. A^(T)v >= c
v >= 0

Question 3

Elaborate on the 6 cases

Answer 3

1) A variable in normal form in the primal, gives a constraint in normal form in the dual

2) A constraint in normal form in the primal, gives a variable in normal form in the dual

3) A variable defined as xj <= 0 in the primal, gives a constraint in the dual that has reverse of normal form type

4) A constraint in the primal that is reverse of normal form, gives a variable in the dual defined as vi <= 0

5) A free variable in the primal gives an equality constraint in the dual

6) An equality constraint in the primal gives a free variable in the dual

Question 4

Elaborate on weak duality

Answer 4

if x and v are feasible solutions to their own problems, then the following result apply for max problems:

cx <= bv

If the problem is a min problem, the weak duality line is flipped:

cx >= bv

What does this mean?
It means that the dual solution, as long as it is feasible, is always an optimistic bound to the primal solution.

Question 5

What follows from the weak duality theorem?

Answer 5

If we have feasible solutions v and x, and we have that cx = bv, then x and v are optimal solutions to their own problems.

the resonign for this is that the dual is always an optimistic solution. They are optimistic solution to each other. If they are equal, they must represent the optimal.

Question 6

What is strong duality?

Answer 6

If one of the problems has a bounded optimal solution, so must the other. And the two objective function values are equal at the optimum:

cx = bv

Question 7

What is the dual theorem?

Answer 7

Assume that xb = B^(-1)b is an optimal solution to P. Then v = cb B^(-1) is an optimal solution to D, and z star == w star.

Question 8

Recall what happens if a constraint is not active

Answer 8

Its corresponding shadow price is 0

Question 9

elaborate on what we can use the constraints binding vs shadow price value for

Answer 9

Complementary slackness.

The relationship between a primal constraint “i” and a dual variable “vi” is given by the complementary slackness constraint:

vi (bi - ∑aij xj) = 0

this say that either the dual variable is 0, or the constraint is binding. Both can be zero as well.

The same relationship apply to dual constraints and primal variables:

xj (∑aij vi - cj) = 0