--- title: "Duality LPP min:Z=20x+50y" subject: "Mathematics III" chapter: 5 key: "semester_3/mathematics_iii:duality-lpp-min-z-20x-50y" source: https://www.bctengineer.com/q/semester_3/mathematics_iii/duality-lpp-min-z-20x-50y site: BCT Engineering --- # Duality LPP min:Z=20x+50y Mathematics III · Chapter 5: Linear Programming - Asked in: 2074 Asoj, 10 marks - Video: [Duality Problem 1,2 - Linear Programming Problems (LPP) - Engineering Mathematics - 4](https://www.youtube.com/watch?v=drU7dOa836M) — Ekeeda - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_3/mathematics_iii/duality-lpp-min-z-20x-50y - Whole chapter: https://www.bctengineer.com/md/semester_3/mathematics_iii/chapter-5 ## Question Solve the following LPP by the simplex method using duality: Minimize Z = 20x + 50y subject to 2x + 5y ≥ 12, 3x + 7y ≥ 17, x, y ≥ 0. ## Short answer Form the dual maximization problem and solve it by simplex; the dual optimum is y₁ = 10, y₂ = 0, Max W = 120. By duality the primal optimum is x = 6, y = 0, giving Min Z = 120. ## Answer **Step 1: Write the dual.** For the primal (minimisation, all constraints ≥), the dual is: ```text Primal: Minimize Z = 20x + 50y subject to 2x + 5y ≥ 12 3x + 7y ≥ 17 x, y ≥ 0 Dual: Maximize W = 12y₁ + 17y₂ subject to 2y₁ + 3y₂ ≤ 20 5y₁ + 7y₂ ≤ 50 y₁, y₂ ≥ 0 ``` Here y₁, y₂ are the dual variables, one for each primal constraint. **Step 2: Standard form of the dual.** Add slack variables s₁, s₂ (one per dual constraint). Since all right sides are positive, the slack variables give the starting basis. ```text Maximize W = 12y₁ + 17y₂ subject to 2y₁ + 3y₂ + s₁ = 20 5y₁ + 7y₂ + s₂ = 50 ``` **Step 3: Simplex tables for the dual** **Table 1** ```text Cj 12 17 0 0 Basis CB y₁ y₂ s₁ s₂ b Ratio --------------------------------- s₁ 0 2 3 1 0 20 20/3 s₂ 0 5 7 0 1 50 50/7 --------------------------------- Zj 0 0 0 0 0 Cj-Zj 12 17 0 0 Entering: y₂ Leaving: s₁ Pivot = 3 ``` **Table 2** ```text Cj 12 17 0 0 Basis CB y₁ y₂ s₁ s₂ b Ratio ----------------------------------------- y₂ 17 2/3 1 1/3 0 20/3 10 s₂ 0 1/3 0 -7/3 1 10/3 10 ----------------------------------------- Zj 34/3 17 17/3 0 340/3 Cj-Zj 2/3 0 -17/3 0 Entering: y₁ Leaving: y₂ Pivot = 2/3 ``` **Table 3** ```text Cj 12 17 0 0 Basis CB y₁ y₂ s₁ s₂ b -------------------------------- y₁ 12 1 3/2 1/2 0 10 s₂ 0 0 -1/2 -5/2 1 0 -------------------------------- Zj 12 18 6 0 120 Cj-Zj 0 -1 -6 0 ``` **Step 4: Read the answer.** All Cj − Zj ≤ 0, so the dual is solved: y₁ = 10, y₂ = 0, Max W = 120. By the duality theorem, Min Z = Max W. The values of the primal variables are the numbers (without sign) in the Cj − Zj row under the slack columns: x = 6 (under s₁), y = 0 (under s₂). Check: Z = 20(6) + 50(0) = 120. **Answer:** x = 6, y = 0, Minimum Z = 120. Note: in Table 2 the two ratios tied (10 and 10), so the next solution is degenerate (s₂ = 0 in Table 3). **Remark (alternative optimum).** The cost line 20x + 50y = 10(2x + 5y) is parallel to the first constraint 2x + 5y = 12. So the point (1, 2), which lies on that constraint and also satisfies 3x + 7y ≥ 17, gives the same Z = 20 + 100 = 120. Every point on the segment from (6, 0) to (1, 2) is optimal; the simplex method reports the corner (6, 0). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is the dual of the problem? A. Max W = 20y1 + 50y2 with 2y1 + 5y2 <= 12 and 3y1 + 7y2 <= 17 B. Max W = 12y1 + 17y2 with 2y1 + 3y2 <= 20 and 5y1 + 7y2 <= 50 C. Min W = 12y1 + 17y2 with 2y1 + 3y2 >= 20 D. Max W = 12y1 + 17y2 with 2y1 + 5y2 <= 20 Answer: B. Right-hand sides become objective coefficients, costs become right-hand sides, and the coefficient matrix is transposed. (Key point: Forming the dual) 2. How are x and y obtained from the final dual table? A. From the b column B. From the y1 and y2 columns of Zj C. From the Cj - Zj row under the slack columns (without sign) D. By setting them equal to y1 and y2 Answer: C. The Cj - Zj entries under s1 and s2 are -6 and 0, giving x = 6, y = 0. (Key point: Reading the primal solution) 3. What does the tie in the minimum-ratio test lead to? A. A basic variable equal to 0 in the next table (degeneracy) B. An infeasible solution C. An unbounded problem D. An extra artificial variable Answer: A. Both rows tie at 10, so after pivoting s2 stays basic with value 0, which is degeneracy. (Key point: Degeneracy) 4. Why does the problem have many optimal solutions? A. The dual is unbounded B. There is a tie in the ratios, which always gives alternatives C. The primal has no feasible region D. The cost line 20x + 50y is parallel to the constraint 2x + 5y = 12 Answer: D. The objective is 10 times the left side of constraint 1, so the cost line is parallel to it and every point on the segment from (6, 0) to (1, 2) gives Z = 120. (Key point: Alternative optimum) ## Related in Mathematics III - [Duality LPP min:Z=21x+50y](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Aduality-lpp-min-z-21x-50y) — Mathematics III, chapter 5, asked 6× - [Duality LPP min:Z=3x₁+2x₂](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Aduality-lpp-min-z-3x-2x) — Mathematics III, chapter 5, asked 3× - [Duality LPP min:Z=3x₁+2x₂](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Aduality-lpp-min-z-3x-2x-two) — Mathematics III, chapter 5, asked 3× - [Duality LPP min:Z=8x₁+9x₂](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Aduality-lpp-min-z-8x-9x) — Mathematics III, chapter 5, asked 4× - [Duality LPP min:C=16x₁+45x₂](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Aduality-lpp-min-c-16x-45x) — Mathematics III, chapter 5 - [Duality LPP min:Z=8x+9y](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Aduality-lpp-min-z-8x-9y) — Mathematics III, chapter 5, asked 6× ## Related in other subjects - [Gauss-Seidel: 20x+y-2z=17](https://www.bctengineer.com/question.md?key=semester_4%2Fnumerical_method%3Agauss-seidel-20x-y-2z) — Numerical Method, chapter 3