Duality In Linear Programming
Introduction:
Most important finding in the development of Linear Programming Problems is the existence of duality in linear programming problems.
Duality:
- Linear programming problems exist in pairs.
- That is in linear programming problem, every maximization problem is associated with a minimization problem. Conversely, associated with every minimization problem is a maximization problem.
- Once we have a problem with its objective function as maximization, we can write by using duality relationship of linear programming problems, its minimization version.
- The original linear programming problem is known as primal problem, and the derived problem is known as dual problem. The concept of the dual problem is important for several reasons.
- Most important are (i) the variables of dual problem can convey important information to managers in terms of formulating their future plans and (ii) in some cases the dual problem can be instrumental in arriving at the optimal solution to the original problem in many fewer iterations, which reduces the labour of computation.
Example: The doctor advises a patient visited him that the patient is weak in his health due to shortage of two vitamins, i.e., vitamin X and vitamin Y. He advises him to take at least 40 units of vitamin X and 50 units of Vitamin Y every day. He also advises that these vitamins are available in two tonics A and B. Each unit of tonic A consists of 2 units of vitamin X and 3 units of vitamin Y. Each unit of tonic B consists of 4 units of vitamin X and 2 units of vitamin Y. Tonic A and B are available in the medical shop at a cost of Rs. 3 per unit of A and Rs. 2,50 per unit of B. The patient has to fulfill the need of vitamin by consuming A and B at a minimum cost.
Primal problem:
Minimize Z = 3a 2.5b. s.t.
2a 4b ≥ 40
3a 2b ≥ 50
Both a and b are ≥ 0.
Dual Problem: Maximize Z = 40x 50y s.t. 2x 3y ≤ 3 4x 2y ≤ 2.50 both x and y are ≥ 0.
Solution to Primal: (Minimization problem i.e., patient’s problem)
