Dual Problem: Linear Programming
Solving the dual problem.
Maximize z = 40w 1 + 50w 2
2w 1 + 3w 2 ≤ 3 4w 1 + 2w 2 ≤ 3
w 1 , w 2 ≥ 0
After adding slack variables, we have
Maximize z = 40w 1 + 50w 2 + 0x 3 + 0x 4
2w 1 + 3w 2 + x 3 = 3 4w 1 + 2w2 + x 4 = 3 w 1 , w 2 , x 3 , x 4 ≥ 0
Where x 3 and x 4 are slack variables.
Initial basic feasible solution
w 1 = 0, w 2 = 0, z = 0 x 3 = 3, x 4 = 3
Table 1: Simplex Method
On small screens, scroll horizontally to view full calculation
Use Horizontal Scrollbar to View Full Table Calculation
The optimal solution is: w 1 = 3/8, w 2 = 3/4 z = 40 X 3/8 + 50 X 3/4= 105/2.
In case of primal problem , you noted that the values of z j -c j under the surplus variables x 3 and x 4 were 3/8 and 3/4. In case of dual problem , these values are the optimal values of dual variables w 1 and w 2 .
The optimal values of the dual variables are often called shadow prices.
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.
Share this article with your friends
Operations Research Simplified Back Next
Goal programming Linear programming Transportation Problem Assignment Problem