--- title: "Duality LPP min:Z=8x₁+9x₂" subject: "Mathematics III" chapter: 5 key: "semester_3/mathematics_iii:duality-lpp-min-z-8x-9x" source: https://www.bctengineer.com/q/semester_3/mathematics_iii/duality-lpp-min-z-8x-9x site: BCT Engineering --- # Duality LPP min:Z=8x₁+9x₂ Mathematics III · Chapter 5: Linear Programming - Asked in: 2082 Shrawan, 2+8 marks - 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-8x-9x - Whole chapter: https://www.bctengineer.com/md/semester_3/mathematics_iii/chapter-5 ## Question Define duality of a linear programming problem. Using the duality, solve the linear programming problem: Minimize Z = 8x₁ + 9x₂ subject to x₁ + 3x₂ ≥ 4, 2x₁ + x₂ ≥ 5, x₁, x₂ ≥ 0 by the simplex method. ## Short answer Dual: Maximize W=4y₁+5y₂ s.t. y₁+2y₂≤8, 3y₁+y₂≤9. Simplex yields y₁=2, y₂=3, W=23. Primal from final Cj-Zj: x₁=11/5, x₂=3/5, Min Z=23. ## Answer **Duality.** Every linear programming problem (the primal) has an associated problem (the dual) built from the same data: the rows of one are the columns of the other. For a minimisation primal with ≥ constraints, the dual is a maximisation with ≤ constraints; each primal constraint gives one dual variable and each primal variable gives one dual constraint. The duality theorem states that if one problem has an optimal solution, so has the other, and their optimal objective values are equal. The primal solution can be read from the Cj − Zj row of the final dual table. **Step 1: Write the dual.** For the primal (minimisation, all constraints ≥), the dual is: ```text Primal: Minimize Z = 8x₁ + 9x₂ subject to x₁ + 3x₂ ≥ 4 2x₁ + x₂ ≥ 5 x₁, x₂ ≥ 0 Dual: Maximize W = 4y₁ + 5y₂ subject to y₁ + 2y₂ ≤ 8 3y₁ + y₂ ≤ 9 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 = 4y₁ + 5y₂ subject to y₁ + 2y₂ + s₁ = 8 3y₁ + y₂ + s₂ = 9 ``` **Step 3: Simplex tables for the dual** **Table 1** ```text Cj 4 5 0 0 Basis CB y₁ y₂ s₁ s₂ b Ratio -------------------------------- s₁ 0 1 2 1 0 8 4 s₂ 0 3 1 0 1 9 9 -------------------------------- Zj 0 0 0 0 0 Cj-Zj 4 5 0 0 Entering: y₂ Leaving: s₁ Pivot = 2 ``` **Table 2** ```text Cj 4 5 0 0 Basis CB y₁ y₂ s₁ s₂ b Ratio ------------------------------------ y₂ 5 1/2 1 1/2 0 4 8 s₂ 0 5/2 0 -1/2 1 5 2 ------------------------------------ Zj 5/2 5 5/2 0 20 Cj-Zj 3/2 0 -5/2 0 Entering: y₁ Leaving: s₂ Pivot = 5/2 ``` **Table 3** ```text Cj 4 5 0 0 Basis CB y₁ y₂ s₁ s₂ b -------------------------------- y₂ 5 0 1 3/5 -1/5 3 y₁ 4 1 0 -1/5 2/5 2 -------------------------------- Zj 4 5 11/5 3/5 23 Cj-Zj 0 0 -11/5 -3/5 ``` **Step 4: Read the answer.** All Cj − Zj ≤ 0, so the dual is solved: y₁ = 2, y₂ = 3, Max W = 23. 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₁ = 11/5 (under s₁), x₂ = 3/5 (under s₂). Check: Z = 8(11/5) + 9(3/5) = 23. **Answer:** x₁ = 11/5, x₂ = 3/5, Minimum Z = 23. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is duality in LP? A. Adding slack variables B. Changing max to min only C. Solving the LP twice D. Every LP has an associated dual built from the same data, with equal optimal values Answer: D. Rows of one problem are the columns of the other. (Key point: Definition) 2. How do variables and constraints correspond? A. Constraints are unchanged B. Each primal constraint gives a dual variable; each primal variable gives a dual constraint C. Each primal variable gives a dual variable D. The number of dual variables equals primal variables Answer: B. Two constraints give y1, y2. (Key point: Variable/constraint link) 3. What is the dual optimum? A. y1 = 3, y2 = 2, W = 23 B. y1 = 2, y2 = 3, W = 5 C. y1 = 2, y2 = 3, W = 23 D. y1 = 4, y2 = 5, W = 41 Answer: C. 4(2) + 5(3) = 23. (Key point: Dual solution) 4. What are x1 and x2? A. 3/5 and 11/5 B. 2 and 3 C. 11/5 and 3/5 D. 4 and 5 Answer: C. From Cj - Zj under s1, s2; Z = 23. (Key point: Primal solution) ## Close variants set in other exams - [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=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× - [Simplex method max:Z=10x₁+x₂+2x₃](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Asimplex-method-max-z-10x-x) — Mathematics III, chapter 5, asked 18× ## Related in Mathematics III - [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× - [Duality LPP min:Z=20x+50y](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Aduality-lpp-min-z-20x-50y) — Mathematics III, chapter 5 - [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=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× - [Linear programming problem](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Alinear-programming-problem) — Mathematics III, chapter 5 - [Simplex method max:Z=3x₁+5x₂](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Asimplex-method-max-z-3x-5x-two) — Mathematics III, chapter 5, asked 17×