--- title: "Duality LPP min:Z=8x+9y" subject: "Mathematics III" chapter: 5 key: "semester_3/mathematics_iii:duality-lpp-min-z-8x-9y" source: https://www.bctengineer.com/q/semester_3/mathematics_iii/duality-lpp-min-z-8x-9y site: BCT Engineering --- # Duality LPP min:Z=8x+9y Mathematics III · Chapter 5: Linear Programming - Asked in: 2082 Baishakh, 7 marks; 2081 Baishakh, 8 marks (asked 2 times) - 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-9y - Whole chapter: https://www.bctengineer.com/md/semester_3/mathematics_iii/chapter-5 ## Question Solve the following Linear Programming Problem by constructing the dual: Minimize Z = 8x + 9y subject to x + 3y ≥ 4, 2x + y ≥ 5 and x, y ≥ 0. ## Short answer Construct dual: Maximize W=4y₁+5y₂ subject to y₁+2y₂≤8, 3y₁+y₂≤9, y₁,y₂≥0. Solve by simplex: y₁=2, y₂=3, W=23. From final Cj-Zj row, primal x=11/5, y=3/5, Min Z=23. ## Answer **Step 1: Write the dual.** For the primal (minimisation, all constraints ≥), the dual is: ```text Primal: Minimize Z = 8x + 9y subject to x + 3y ≥ 4 2x + y ≥ 5 x, y ≥ 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₁), y = 3/5 (under s₂). Check: Z = 8(11/5) + 9(3/5) = 23. **Answer:** x = 11/5, y = 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 the dual of min 8x + 9y with x + 3y >= 4, 2x + y >= 5? A. Max 4y1 + 5y2 with y1 + 2y2 <= 8, 3y1 + y2 <= 9 B. Min 4y1 + 5y2 with y1 + 2y2 >= 8 C. Max 8y1 + 9y2 with y1 + 3y2 <= 4 D. Max 4y1 + 5y2 with y1 + 3y2 <= 8 Answer: A. Transpose the coefficient matrix and swap costs with RHS. (Key point: Dual) 2. What is the optimum of the dual? A. y1 = 3, y2 = 2, W = 23 B. y1 = 2, y2 = 3, W = 23 C. y1 = 8, y2 = 0, W = 32 D. y1 = 2, y2 = 3, W = 20 Answer: B. 4(2) + 5(3) = 23. (Key point: Dual solution) 3. What does the duality theorem say? A. Dual is always infeasible B. Optimal solutions are identical C. Optimal values of primal and dual are equal D. Primal is always larger Answer: C. Min Z = Max W = 23. (Key point: Duality theorem) 4. What are x and y? A. x = 4, y = 5 B. x = 3/5, y = 11/5 C. x = 2, y = 3 D. x = 11/5, y = 3/5 Answer: D. Read from Cj - Zj under slack columns; 8(11/5) + 9(3/5) = 23. (Key point: Primal values) ## Close variants set in other exams - [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× ## Related in Mathematics III - [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: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: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=20x+50y](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Aduality-lpp-min-z-20x-50y) — Mathematics III, chapter 5 - [Linear programming problem](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Alinear-programming-problem) — Mathematics III, chapter 5 ## Related in other subjects - [Solve y''+3y'+2y=e^(2x) sin x](https://www.bctengineer.com/question.md?key=semester_1%2Fmathematics_i%3Ade-d2-3d-2-e2x-sinx) — Mathematics I, chapter 4, asked 2×