Dual Problem: Linear Programming
Solving the dual problem.
Example: Duality
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
IMAGES
VIDEO
COMMENTS
Linear programming is used daily in the real world to optimize the allocation of resources or activities to generate the most benefit or profit. Linear programming can take multiple factors into account into the thousands and is used extens...
Advantages of linear programming include that it can be used to analyze all different areas of life, it is a good solution for complex problems, it allows for better solution, it unifies disparate areas and it is flexible.
Real world uses for linear functions include solving problems and finding unknowns in engineering, economics and finances. A linear function describes a gradual rate of change, either positive or negative. When drawn, it presents a straight...
Thus, a greater-than-or-equal-to constraint in a minimization problem has an associated nonnegative dual variable. The primal and dual problems that we have
If either the primal or dual problem has a solution then the other also has a solution and their optimum values are equal. 3. If any of the two problems has an
If we transform the dual linear program into an equivalent minimization problem, and take its.
Make sure you watch part 1 and 2 before part 3. In this video, we go over another example on how to write the dual programming of a LP.
Linear Program Duality Example. 25K views · 6 ... Primal to Dual conversion | Duality in LPP | linear programming problem | Method-1| Lecture.16.
There is always a corresponding. Linear Programming Problem (LPP) associated to every LPP, which is called as dual problem of the original. LPP(Primal Problem).
This video tutorial provides a basic concept of Duality in LPP and explains the Duality in Linear Programming with the help of plenty of
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
Worked examples · Write down the dual problem of the following: min 4 x 1 − 2 x 2 s.t. x 1 + 2 x 2 ≥ 3 3 x 1 − 4 x 2 = 0 x 2 ≥ 0. · Write down the dual
LP Duality Theorem: Consider the linear programming problem: maximize cT x.
solved like in sec 4.1. • LPP: Linear Programming Problem, one of these “find the optimal value of a linear function subject to linear constraints” problems.