In this video, we'll talk about weak duality, strong duality, and how to use duality to
solve the dual based on the optimal solution to the primal.
These are general primal and dual problems in the standard form.
The primal is a maximization problem.
The objective function is z.
The dual is a minimization problem.
The objective function is w. c and b switch places in the primal and dual.
The coefficient of the primal becomes the RHS of the dual.
The RHS of the primal becomes the coefficient of the dual.
The constraints are "less than or equal to" in primal, and they are "greater than or equal
to" in the dual.
The coefficient aij becomes aji.
With this in mind, now let's introduce the weak duality theorem.
Let x = [x1, …, xn] be any feasible solution to the primal problem.
Let u = [u1, …, um] be any feasible solution to the dual problem.
The weak duality theorem says that the z value for x in the primal is always less than or
equal to the w value for u in the dual.
Let's check an example.
This is the primal, and this is the dual.
For the primal, let's check this point (5, 2).
It is a feasible solution, because it satisfies all the constraints.
We plug these values into the objective function, and z=350.
For the dual, let's check this point (0, 10, 0).
It is a feasible solution, because it satisfies all the constraints.
We plug these values into the objective function, and w=400.
In this example, z is less than or equal to w.
You can also check other feasible solutions to the primal and dual.
They should all follow this rule.
Now let's introduce the strong duality lemma.
Let x = [x1, …, xn] be any feasible solution to the primal problem.
Let u = [u1, …, um] be any feasible solution to the dual problem.
The strong duality lemma says that if the z value for x in the primal is equal to the
w value for u in the dual, then x is the optimal solution to the primal and u is the optimal
solution to the dual.
Let's check this example again.
This is the primal problem, and this is the dual.
For the primal, the optimal solution is this point (3, 2.8).
We plug these values into the objective function, and z*=370.
For the dual, the optimal solution is this point (0, 10, 10).
We plug these values into the objective function, and w*=370.
In this example, z* is equal to w*.
You can also check the primal and dual of other LP examples.
They should all follow this rule.
Now let me explain the graphical meaning of the weak duality theorem and the strong duality
lemma.
Let's consider this vertical axis.
It increases from -∞ to +∞.
For the primal problem, we want to maximize z.
The initial BFS may give us a very small z1.
For example, it is located here.
After the first simplex iteration, we find a better BFS with a larger value z2 here.
After many iterations, we finally found the optimal solution, which gives us the max value
z* here.
We cannot go above this point.
For the dual problem, we want to minimize w.
The initial BFS might give us w1 that is very large, for example, it is located here.
After the first dual simplex iteration, we find a better BFS with a smaller value w2
here.
After many iterations, we finally found the optimal solution, which gives us the min value
w* here.
We cannot go below this point.
The strong duality lemma says z* must be equal to w*.
This is its graphical meaning.
So, based on this graphical explanation, we can also derive these two lemmas: If the primal
is unbounded, then z* is infinitely large, so is w*.
So the dual is infeasible.
If the dual is unbounded, then w* is infinitely small, so is z*.
So the primal is infeasible.
Based on the weak duality theorem and the strong duality lemma, we can derive this strong
duality theorem.
Suppose BV is an optimal basis for the primal.
Then we can use this formula, u=cBVB-1 to calculate the optimal solution to the dual.
Also, z*=w*.
cBV is the vector of the initial objective function coefficients for the optimal tableau’s
BVs.
B is the matrix whose jth column is the column for BVj in the constraints of the initial
canonical form.
Let's check this example.
It is a maximization problem with three inequality constraints.
We introduced three slack variables and write out the initial simplex tableau.
We also used the simplex method and found that this is the optimal tableau.
Now in the optimal tableau, the BVs are s1, x3, and x1.
The coefficients of these three BVs in the Initial objective function are 0, 20, and
60, respectively.
B is a matrix.
Its first column is the column for s1 in the constraints of the Initial canonical form.
Its second column is the column for x3 in the constraints, and its third column is the
column for x1 in the constraints.
Then we can use this formula, u=cBVB-1 to calculate the optimal solution to the dual.
Finally, we have u1, u2, and u3 are 0, 10, and 10, respectively.
Also, w*=z*=280.
There is actually another way to find the optimal dual solution quickly by reading the
optimal primal tableau.
If constraint i has a ≤ in the primal, then the optimal value of dual variable ui is equal
to the coefficient of slack variable si in row 0 of the optimal primal tableau.
If constraint i has a ≥ in the primal, then the optimal value of dual variable ui is equal
to -(coefficient of excess variable ei in row 0 of the optimal primal tableau.
If constraint i has a = in the primal, then the optimal value of dual variable ui is equal
to (coefficient of artificial variable ai in row 0 of the optimal primal tableau) - M.
Let's check this example.
This is the primal and this is the dual.
This is the optimal tableau for the primal.
Let's try to find the optimal solution by just observing this optimal primal tableau.
The first constraint has a ≤ in the primal, then the optimal value of dual variable u1
is equal to the coefficient of slack variable s1 in row 0 of the optimal primal tableau,
which is 51/23.
The second constraint has a ≥ in the primal, then the optimal value of dual variable u2
is equal to -(coefficient of excess variable e2 in row 0 of the optimal primal tableau),
which is -58/23.
The third constraint has a = in the primal, then the optimal value of dual variable u3
is equal to (coefficient of artificial variable a3 in row 0 of the optimal primal tableau)
- M, which is 9/23.
Also, w*=z*=565/23.
Okay, that's all about weak duality, strong duality, and how to use duality to solve the
dual based on the optimal solution to the primal.
Thanks for watching.