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:

  1. 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.
  2. 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.
  3. 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.
  4. The coefficient variables matrix in the dual constraints is the transpose of the coefficient variables matrix in constraints of the primal and vice versa.
  5. 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.
  6. 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 isAssociated variable in maximization problem is
>=>= 0
<=<=0
=Unrestricted
Variable in minimization problem isCorresponding constraint in maximization problem is
>=0<=
<=0>=
Unrestricted=

Consider the following primal linear programming problem to understand the above rules in a better manner.

Maximize Zx = c1x1 + c2x2 +  + cnxn

Subject to constraints 

a11x1 + a12x2 +  + a1nxn  b1a21x1 + a22x2 +  + a2nxn  b2.......am1x1 + am2x2 +  + amnxn  bmAnd x1, x2,  , xn  0

After applying the rules mentioned above, dual of the problem mentioned above will be:

Minimize Zy = b1y1 + b2y2 +  + bmym

Subject to constraints 

a11y1 + a12y2 +  + a1mym  c1a21y1 + a22y2 +  + a2mym  cn.......a1ny1 + a1ny2 +  + amnym  cnAnd y1, y2,  , ym  0

Dual linear programming example

Construct a dual for the problem mentioned below.

Maximize Zx = x1 - x2 + 3x3

Subject to constraints:

x1 - x2 + x3  102x1 - x2 + x3  22x1 - 2x2 + 3x3  6

And x1, x2, x3  0

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:

y1 + 2y2 + 2y3   1y1 - y2 - 2y3  1y1 - y2 + 3y3  3And y1, y2, y3  0

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?

  1. Primal
  2. Dual
  3. Objective function
  4. 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?

  1. Primal
  2. Dual
  3. Variable
  4. 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?

  1. Queen’s theorem
  2. Kaizen’s theorem
  3. Simplex theorem
  4. 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?

  1. If the objective function of a primal needs to be maximized, the objective function of the dual needs to be minimized.
  2. If the objective function of a primal needs to be maximized, the objective function of the dual needs to be maximized.
  3. If the objective function of a primal needs to be minimized, the objective function of the dual needs to be minimized.
  4. 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?

  1. For break-even analysis
  2. For economic interpretations
  3. For reducing redundancy
  4. 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.

  • Weak duality
  • Strong duality
  • Maximization in linear programming
  • Minimization in linear programming

Want more help with your computer science homework?

We've got you covered with step-by-step solutions to millions of textbook problems, subject matter experts on standby 24/7 when you're stumped, and more.
Check out a sample computer science Q&A solution here!

*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.

Tagged in
EngineeringComputer Science

Algorithms

Linear Program

Duality

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.

Tagged in
EngineeringComputer Science

Algorithms

Linear Program

Duality