What is duality?
Duality is a linear programming (LP) concept which states that it is possible to interpret every LP problem using two distinct methods, but they will have similar solutions. That means any LP problem can be mentioned in another equivalent form based on identical data.
Dual and primal problems
When a new linear programming problem is derived from another one, the new problem that is derived is called a dual linear programming problem. The original problem is known as the primal linear programming problem.
Construction of a dual linear programming problem
To construct a dual from a primal or primal from a dual, the following rules should be considered:
- The dual variable corresponds to every constraint in the primal and vice-versa. So, in the primal for every m constraint and n variables, there will be a dual for m variables and n constraints.
- In the primal problem, the right-hand side constants b1, b2, …, bm will become the coefficients of dual variables y1, y2, …, ym in the dual function Zy. The coefficients c1, c2, …, cn of the primal variables x1, x2, … xn in the objective function will be converted to the right-hand side constants in the dual problem.
- There will be less than or equal to (≤) constraints in the maximization primal problem and the minimization dual problem, there will be greater than or equal to (≥) constraints and vice-versa. That means the inequality sign is changed in all constraints unless the conditions are non-negative.
- The coefficient variables matrix in the dual constraints is the transpose of the coefficient variables matrix in constraints of the primal and vice versa.
- When the objective function of a primal requires maximization, then the dual’s objective function should be minimized. Similarly, when the objective function of a primal is required minimization, then the objective function of the dual should be maximized.
- If the ith primal constraint is equal to type, the dual’s ith variable will be unrestricted in sign and vice versa.
The above-mentioned duality rules and the primal-dual relationship can be remembered easily using the table below:
Constraint in minimization problem is | Associated variable in maximization problem is |
>= | >= 0 |
<= | <=0 |
= | Unrestricted |
Variable in minimization problem is | Corresponding constraint in maximization problem is |
>=0 | <= |
<=0 | >= |
Unrestricted | = |
Consider the following primal linear programming problem to understand the above rules in a better manner.
Subject to constraints
After applying the rules mentioned above, dual of the problem mentioned above will be:
Subject to constraints
Dual linear programming example
Construct a dual for the problem mentioned below.
Subject to constraints:
Solution: Here, the constraints m will be 3, and variables n will be 3.
Consequently, there will be dual variables m = 3 and constraints n = 3.
The primal variables coefficients will be:
c1 = 1, c2 = -1, c3 = 3 will be the right-hand side of the dual.
Also, the constants on the right-hand side, will be the coefficients of the dual objective function. So,
b1 = 10, b2 = 2, b3 = 6
The dual objective function contains a minimization objective function having constraints of ≥ type.
Let y1, y2, y3 be dual variables corresponding to the primal constraints. Therefore, the dual will be:
Maximize Zy = 10y1 - 2y2 + 6y3
Subject to constraints:
Properties of duality
Some of the properties of duality are as follows:
- The dual LP of a dual is primal.
- If a primal or dual LP has a solution, the other will also have a solution. Their optimum values will be equivalent.
- If the dual or primal consists of an infeasible solution, the value of the objective function of the other problem will be unbounded.
- The objective function value for any primal’s feasible solution is never greater than the objective function value of any feasible solution of the dual.
- If the primal or dual LP problem has an unbounded solution, the solution to the other problem is infeasible.
- If the primal LP contains a feasible solution, but the dual does not, the primal will not have a finite optimal solution and vice versa.
Advantages of duality
The benefits of using duality in linear programming are as mentioned below:
- Duality prevents the addition of artificial variables. Consequently, it helps in solving the problem quickly.
- Duality helps to determine the changes in parameters of an LP problem.
- Duality allows solving an LP problem using the simplex method when the initial solution of the LP problem is infeasible.
- This approach is beneficial to solve dual of a primal having fewer number constraints because the number of constraints equals the number of iterations needed to find the problem’s solution.
Uses of duality
Duality has several uses in real life. These include:
- It is used in proving graph-related theorems like Konig’s theorem.
- The minimax theorem for zero-sum games is proved using the duality theorem.
- If a problem does not yield any primal solution, it can be checked with a dual.
- Managers use it to make economic interpretations and identify shadow prices.
- It is used in parallel and series circuit concepts in physics.
Context and Applications
The duality concept is a concept of data structure and algorithms. The topic is included in several computer science courses such as:
- Bachelors of Science in Computer Science
- Bachelors of Science in Information Technology
- Masters of Science in Computer Science
- Masters of Science in Information Technology
Practice Problems
Q1. In linear programming, what is a dual of a dual called?
- Primal
- Dual
- Objective function
- Constraint
Answer: Option a
Explanation: According to one of the duality properties, the dual of dual linear programming problem is primal.
Q2. In a linear programming problem, the new problem derived from an LP is known as?
- Primal
- Dual
- Variable
- Constraint
Answer: Option b
Explanation: The new LP derived from the original LP is known as dual linear programming.
Q3. Duality is used for proving which of the following theorems?
- Queen’s theorem
- Kaizen’s theorem
- Simplex theorem
- Minimax theorem
Answer: Option d
Explanation: Duality is used to prove the minimax theorem for zero-sum games.
Q4. Which of the following statements are true?
- If the objective function of a primal needs to be maximized, the objective function of the dual needs to be minimized.
- If the objective function of a primal needs to be maximized, the objective function of the dual needs to be maximized.
- If the objective function of a primal needs to be minimized, the objective function of the dual needs to be minimized.
- None of these
Answer: Option a
Explanation: According to the duality rules, if the objective function of a primal needs to be maximized, the objective function of the dual should be minimized.
Q5. Which of the following is an application of duality?
- For break-even analysis
- For economic interpretations
- For reducing redundancy
- All of the above
Answer: Option b
Explanation: One of the real-world applications of duality is that it is used for economic interpretations.
Common Mistakes
Students should not forget that if the objective function of the primal needs to be minimized, the objective function of the dual will have to be maximized and vice versa while constructing a dual.
Related Concepts
- Weak duality
- Strong duality
- Maximization in linear programming
- Minimization in linear programming
Want more help with your computer science homework?
*Response times may vary by subject and question complexity. Median response time is 34 minutes for paid subscribers and may be longer for promotional offers.
Search. Solve. Succeed!
Study smarter access to millions of step-by step textbook solutions, our Q&A library, and AI powered Math Solver. Plus, you get 30 questions to ask an expert each month.
Search. Solve. Succeed!
Study smarter access to millions of step-by step textbook solutions, our Q&A library, and AI powered Math Solver. Plus, you get 30 questions to ask an expert each month.