--- title: "Duality LPP min:Z=3x₁+2x₂" subject: "Mathematics III" chapter: 5 key: "semester_3/mathematics_iii:duality-lpp-min-z-3x-2x-two" source: https://www.bctengineer.com/q/semester_3/mathematics_iii/duality-lpp-min-z-3x-2x-two site: BCT Engineering --- # Duality LPP min:Z=3x₁+2x₂ Mathematics III · Chapter 5: Linear Programming - Asked in: 2069 Asar, 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-3x-2x-two - Whole chapter: https://www.bctengineer.com/md/semester_3/mathematics_iii/chapter-5 ## Question Solve the linear programming problem by the simplex method constructing the duality: Minimize Z = 3x₁ + 2x₂ subject to 2x₁ + 4x₂ ≥ 10, 4x₁ + 2x₂ ≥ 10, x₂ ≥ 4 and x₁, x₂ ≥ 0. ## Short answer The dual is solved by simplex, yielding y₁ = 0, y₂ = 3/4, y₃ = 1/2 and Max W = 19/2. Hence primal minimum Z = 19/2 at x₁ = 1/2, x₂ = 4. ## Answer **Step 1: Write the dual.** For the primal (minimisation, all constraints ≥), the dual is: ```text Primal: Minimize Z = 3x₁ + 2x₂ subject to 2x₁ + 4x₂ ≥ 10 4x₁ + 2x₂ ≥ 10 x₂ ≥ 4 x₁, x₂ ≥ 0 Dual: Maximize W = 10y₁ + 10y₂ + 4y₃ subject to 2y₁ + 4y₂ ≤ 3 4y₁ + 2y₂ + y₃ ≤ 2 y₁, y₂, y₃ ≥ 0 ``` Here y₁, 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 = 10y₁ + 10y₂ + 4y₃ subject to 2y₁ + 4y₂ + s₁ = 3 4y₁ + 2y₂ + y₃ + s₂ = 2 ``` **Step 3: Simplex tables for the dual** **Table 1** ```text Cj 10 10 4 0 0 Basis CB y₁ y₂ y₃ s₁ s₂ b Ratio ----------------------------------- s₁ 0 2 4 0 1 0 3 3/2 s₂ 0 4 2 1 0 1 2 1/2 ----------------------------------- Zj 0 0 0 0 0 0 Cj-Zj 10 10 4 0 0 Entering: y₁ Leaving: s₂ Pivot = 4 ``` **Table 2** ```text Cj 10 10 4 0 0 Basis CB y₁ y₂ y₃ s₁ s₂ b Ratio ------------------------------------------ s₁ 0 0 3 -1/2 1 -1/2 2 2/3 y₁ 10 1 1/2 1/4 0 1/4 1/2 1 ------------------------------------------ Zj 10 5 5/2 0 5/2 5 Cj-Zj 0 5 3/2 0 -5/2 Entering: y₂ Leaving: s₁ Pivot = 3 ``` **Table 3** ```text Cj 10 10 4 0 0 Basis CB y₁ y₂ y₃ s₁ s₂ b Ratio -------------------------------------------- y₂ 10 0 1 -1/6 1/3 -1/6 2/3 - y₁ 10 1 0 1/3 -1/6 1/3 1/6 1/2 -------------------------------------------- Zj 10 10 5/3 5/3 5/3 25/3 Cj-Zj 0 0 7/3 -5/3 -5/3 Entering: y₃ Leaving: y₁ Pivot = 1/3 ``` **Table 4** ```text Cj 10 10 4 0 0 Basis CB y₁ y₂ y₃ s₁ s₂ b ----------------------------------- y₂ 10 1/2 1 0 1/4 0 3/4 y₃ 4 3 0 1 -1/2 1 1/2 ----------------------------------- Zj 17 10 4 1/2 4 19/2 Cj-Zj -7 0 0 -1/2 -4 ``` **Step 4: Read the answer.** All Cj − Zj ≤ 0, so the dual is solved: y₁ = 0, y₂ = 3/4, y₃ = 1/2, Max W = 19/2. 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₁ = 1/2 (under s₁), x₂ = 4 (under s₂). Check: Z = 3(1/2) + 2(4) = 19/2. **Answer:** x₁ = 1/2, x₂ = 4, Minimum Z = 19/2. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. The primal has three constraints (2x1+4x2>=10, 4x1+2x2>=10, x2>=4). What does the dual look like? A. Maximize W = 10y1 + 10y2 + 4y3 with 2 constraints: 2y1+4y2 <= 3 and 4y1+2y2+y3 <= 2 B. Maximize W = 3y1 + 2y2 with 3 constraints C. Minimize W = 10y1 + 10y2 + 4y3 with 2 constraints of >= type D. Maximize W = 10y1 + 10y2 + 4y3 with 3 constraints Answer: A. There is one dual variable per primal constraint (3) and one dual constraint per primal variable (2), with <= type and right sides 3 and 2. (Key point: Forming the dual) 2. In Table 1 (Cj - Zj = 10, 10, 4; ratios 3/2 and 2/4), which variable leaves when y1 enters? A. s2, because its ratio 1/2 is the smaller B. s1, because its ratio 3/2 is the larger C. s2, because it has the larger b value D. s1, because it appears first Answer: A. The leaving variable has the smallest non-negative ratio: 2/4 = 1/2 (row s2), so the pivot is 4. (Key point: First iteration) 3. After Table 3, Cj - Zj for y3 is +7/3. What must be done? A. Stop; the solution is optimal B. Stop; the problem is unbounded C. Let y3 enter and y1 leave (smallest ratio 1/2) to get Table 4 D. Add an artificial variable Answer: C. A positive Cj - Zj means the solution can still improve, so y3 enters; the ratio test selects y1 to leave. (Key point: Continuing until optimal) 4. In the final table Cj - Zj under s1 is -1/2 and under s2 is -4, and Max W = 19/2. What is the primal solution? A. x1 = 4, x2 = 1/2, Min Z = 19/2 B. x1 = 0, x2 = 3/4, Min Z = 19/2 C. x1 = 1/2, x2 = 4, Min Z = 19/2 D. x1 = 3/4, x2 = 1/2, Min Z = 19/2 Answer: C. Primal variables are the unsigned Cj - Zj entries under s1 and s2: x1 = 1/2, x2 = 4, and Z = 3(1/2) + 2(4) = 19/2 equals Max W. (Key point: Primal values from dual) ## 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) — 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× ## Related in Mathematics III - [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× - [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× - [Big-M method min:Z=4x₁+2x₂](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Abig-m-method-min-z-4x) — Mathematics III, chapter 5 - [Graphical method min:z=4x₁+3x₂+x₃](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Agraphical-method-min-z-4x-3x) — Mathematics III, chapter 5 ## 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×