Dual Problem: Linear Programming
Solving the dual problem.
Example: Duality
Maximize z = 40w1 + 50w2
subject to
2w1 + 3w2 ≤
3
4w1 + 2w2 ≤ 3
w1, w2 ≥ 0
After adding slack variables, we have
Maximize z = 40w1 + 50w2 + 0x3 + 0x4
2w1 + 3w2 + x3 = 3
4w1 + 2w2 + x4 = 3
w1, w2, x3, x4 ≥
0
Where x3 and x4 are slack variables.
Initial basic feasible solution
w1= 0, w2 = 0, z = 0
x3 = 3, x4 = 3
Table 1: Simplex Method
| cj | 40 | 50 | 0 | 0 | ||
|---|---|---|---|---|---|---|
| cB | Basic variables B |
w1 | w2 | x3 | x4 | Solution values b (=XB) |
| 0 | x3 | 2 | 3 | 1 | 0 | 3 |
| 0 | x4 | 4 | 2 | 0 | 1 | 3 |
| zj-cj | -40 | -50 | 0 | 0 |
Table 2
| cj | 40 | 50 | 0 | 0 | ||
|---|---|---|---|---|---|---|
| cB | Basic variables B |
w1 | w2 | x3 | x4 | Solution values b (=XB) |
| 50 | w2 | 2/3 | 1 | 1/3 | 0 | 1 |
| 0 | x4 | 8/3 | 0 | -2/3 | 1 | 1 |
| zj-cj | -20/3 | 0 | 50/3 | 0 |
Table 3
| cj | 40 | 50 | 0 | 0 | ||
|---|---|---|---|---|---|---|
| cB | Basic variables B |
w1 | w2 | x3 | x4 | Solution values b (=XB) |
| 50 | w2 | 0 | 1 | 1/2 | -1/4 | 3/4 |
| 40 | w1 | 1 | 0 | -1/4 | 3/8 | 3/8 |
| zj-cj | 0 | 0 | 15 | 5/2 |
The optimal solution is:
w1 = 3/8, w2 = 3/4
z = 40 X 3/8 + 50 X 3/4= 105/2.
In case of primal problem, you noted that the values of zj-cj under the surplus variables x3 and x4 were 3/8 and 3/4. In case of dual problem, these values are the optimal values of dual variables w1 and w2.
Further, the values of the objective functions in both the problems are same (i.e., 105/2)
Important Primal-Dual Results
- If one problem has an unbounded optimal solution, then the other problem cannot have a feasible solution.
- Optimal solution of either problem gives complete information about the optimal solution of the other.
- If either the primal or dual problem has a finite optimal solution, then the other has also a finite optimal solution.
- The dual of a dual is primal.
