--- title: "Duality LPP min:C=16x₁+45x₂" subject: "Mathematics III" chapter: 5 key: "semester_3/mathematics_iii:duality-lpp-min-c-16x-45x" source: https://www.bctengineer.com/q/semester_3/mathematics_iii/duality-lpp-min-c-16x-45x site: BCT Engineering --- # Duality LPP min:C=16x₁+45x₂ Mathematics III · Chapter 5: Linear Programming - Asked in: 2070 Asar, 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-c-16x-45x - Whole chapter: https://www.bctengineer.com/md/semester_3/mathematics_iii/chapter-5 ## Question Find the dual of the following linear programming problem and solve it by the simplex method: Minimize C = 16x₁ + 45x₂ subject to 2x₁ + 5x₂ ≥ 50, x₁ + 3x₂ ≥ 27, x₁, x₂ ≥ 0. ## Short answer The dual is Maximize W=50y1+27y2 subject to 2y1+y2≤16, 5y1+3y2≤45, y1,y2≥0. Solve by simplex: initial table, enter y1, then y2. Optimal dual: y1=3, y2=10, W=420. Primal solution x1=15, x2=4 gives Min C=420. ## Answer **Step 1: Write the dual.** For the primal (minimisation, all constraints ≥), the dual is: ```text Primal: Minimize C = 16x₁ + 45x₂ subject to 2x₁ + 5x₂ ≥ 50 x₁ + 3x₂ ≥ 27 x₁, x₂ ≥ 0 Dual: Maximize W = 50y₁ + 27y₂ subject to 2y₁ + y₂ ≤ 16 5y₁ + 3y₂ ≤ 45 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 = 50y₁ + 27y₂ subject to 2y₁ + y₂ + s₁ = 16 5y₁ + 3y₂ + s₂ = 45 ``` **Step 3: Simplex tables for the dual** **Table 1** ```text Cj 50 27 0 0 Basis CB y₁ y₂ s₁ s₂ b Ratio --------------------------------- s₁ 0 2 1 1 0 16 8 s₂ 0 5 3 0 1 45 9 --------------------------------- Zj 0 0 0 0 0 Cj-Zj 50 27 0 0 Entering: y₁ Leaving: s₁ Pivot = 2 ``` **Table 2** ```text Cj 50 27 0 0 Basis CB y₁ y₂ s₁ s₂ b Ratio ------------------------------------- y₁ 50 1 1/2 1/2 0 8 16 s₂ 0 0 1/2 -5/2 1 5 10 ------------------------------------- Zj 50 25 25 0 400 Cj-Zj 0 2 -25 0 Entering: y₂ Leaving: s₂ Pivot = 1/2 ``` **Table 3** ```text Cj 50 27 0 0 Basis CB y₁ y₂ s₁ s₂ b ----------------------------- y₁ 50 1 0 3 -1 3 y₂ 27 0 1 -5 2 10 ----------------------------- Zj 50 27 15 4 420 Cj-Zj 0 0 -15 -4 ``` **Step 4: Read the answer.** All Cj − Zj ≤ 0, so the dual is solved: y₁ = 3, y₂ = 10, Max W = 420. By the duality theorem, Min C = Max W. The values of the primal variables are the numbers (without sign) in the Cj − Zj row under the slack columns: x₁ = 15 (under s₁), x₂ = 4 (under s₂). Check: C = 16(15) + 45(4) = 420. **Answer:** x₁ = 15, x₂ = 4, Minimum C = 420. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is the dual of Minimize C = 16x1 + 45x2 with 2x1 + 5x2 >= 50 and x1 + 3x2 >= 27? A. Maximize W = 16y1 + 45y2 subject to 2y1 + 5y2 <= 50, y1 + 3y2 <= 27 B. Maximize W = 50y1 + 27y2 subject to 2y1 + y2 <= 16, 5y1 + 3y2 <= 45 C. Maximize W = 50y1 + 27y2 subject to 2y1 + 5y2 <= 16, y1 + 3y2 <= 45 D. Minimize W = 50y1 + 27y2 subject to 2y1 + y2 >= 16, 5y1 + 3y2 >= 45 Answer: B. Right sides become dual costs, costs become right sides, and the coefficient matrix is transposed with <= constraints. (Key point: Dual formation) 2. In Table 1 (Cj - Zj = 50, 27; ratios 16/2 = 8 and 45/5 = 9), which variable leaves? A. s2, with pivot 5 B. s1, with pivot 2 C. s2, with pivot 3 D. s1, with pivot 1 Answer: B. y1 enters (largest Cj - Zj = 50); smallest ratio is 8 in the s1 row, so s1 leaves and the pivot is 2. (Key point: Pivot selection) 3. What is the optimal dual solution? A. y1 = 3, y2 = 10, Max W = 420 B. y1 = 10, y2 = 3, Max W = 420 C. y1 = 8, y2 = 5, Max W = 535 D. y1 = 15, y2 = 4, Max W = 420 Answer: A. The final table gives y1 = 3 and y2 = 10, so W = 50(3) + 27(10) = 150 + 270 = 420. (Key point: Dual optimum) 4. The final Cj - Zj row under s1 and s2 is -15 and -4. What is the primal solution and Min C? A. x1 = 4, x2 = 15, Min C = 420 B. x1 = 3, x2 = 10, Min C = 420 C. x1 = -15, x2 = -4, Min C = 420 D. x1 = 15, x2 = 4, Min C = 420 Answer: D. Primal values are the unsigned entries under the slack columns: x1 = 15, x2 = 4, and C = 16(15) + 45(4) = 420 = Max W. (Key point: Primal from final dual table) ## Related in Mathematics III - [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: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: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× - [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× ## Related in other subjects - [Convergence of 2x+3x²/8+4x³/27+...](https://www.bctengineer.com/question.md?key=semester_2%2Fmathematics%3Aconvergence-2x-3x2-8-4x3) — Mathematics, chapter 6, asked 3×