--- title: "Linear programming problem" subject: "Mathematics III" chapter: 5 key: "semester_3/mathematics_iii:linear-programming-problem" source: https://www.bctengineer.com/q/semester_3/mathematics_iii/linear-programming-problem site: BCT Engineering --- # Linear programming problem Mathematics III · Chapter 5: Linear Programming - Asked in: 2070 Chaitra, 10 marks - Video: [Linear Programming (Optimization) 2 Examples Minimize & Maximize](https://www.youtube.com/watch?v=Y7e7DCsDUMY) — Mario's Math Tutoring - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_3/mathematics_iii/linear-programming-problem - Whole chapter: https://www.bctengineer.com/md/semester_3/mathematics_iii/chapter-5 ## Question Minimize z = 8x₁ + 9x₂ subject to x₁ + 3x₂ ≥ 4, 2x₁ + x₂ ≥ 5 with x₁, x₂ ≥ 0. ## Short answer The dual is solved by simplex, yielding y₁ = 2, y₂ = 3 and Max W = 23. Hence primal minimum Z = 23 at x₁ = 11/5, x₂ = 3/5. ## Answer **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. For Minimize Z = 8x1 + 9x2 with x1 + 3x2 >= 4 and 2x1 + x2 >= 5, what is the dual? A. Maximize W = 8y1 + 9y2 subject to y1 + 3y2 <= 4, 2y1 + y2 <= 5 B. Minimize W = 4y1 + 5y2 subject to y1 + 2y2 >= 8, 3y1 + y2 >= 9 C. Maximize W = 4y1 + 5y2 subject to y1 + 3y2 <= 8, 2y1 + y2 <= 9 D. Maximize W = 4y1 + 5y2 subject to y1 + 2y2 <= 8, 3y1 + y2 <= 9 Answer: D. The right sides 4, 5 become the dual costs; costs 8, 9 become right sides; the coefficient matrix is transposed. (Key point: Writing the dual) 2. In the dual's Table 1 (Cj - Zj = 4, 5; ratios 8/2 = 4 and 9/1 = 9), which enters and leaves? A. y2 enters, s1 leaves, pivot 2 B. y1 enters, s2 leaves, pivot 3 C. y2 enters, s2 leaves, pivot 1 D. y1 enters, s1 leaves, pivot 1 Answer: A. y2 has the largest Cj - Zj (5); the smaller ratio 4 is in the s1 row, so s1 leaves and the pivot is 2. (Key point: First pivot) 3. When the dual's final table has all Cj - Zj <= 0, what are the dual solution values? A. y1 = 3, y2 = 2, Max W = 23 B. y1 = 2, y2 = 3, Max W = 23 C. y1 = 11/5, y2 = 3/5, Max W = 23 D. y1 = 2, y2 = 3, Max W = 20 Answer: B. The final table has y1 = 2 and y2 = 3, so W = 4(2) + 5(3) = 23. (Key point: Optimal dual solution) 4. How are the primal variables x1, x2 read from the final dual table? A. From the b column, as x1 = 2, x2 = 3 B. As the Zj values under y1 and y2 C. As the numbers (without sign) in the Cj - Zj row under the slack columns s1, s2: x1 = 11/5, x2 = 3/5 D. By swapping the dual values: x1 = 3, x2 = 2 Answer: C. The primal solution appears (without sign) in the Cj - Zj row under the slack columns, giving Min Z = 8(11/5) + 9(3/5) = 23. (Key point: Reading primal from dual table) ## 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× - [Big-M method max:P=2x₁+x₂+3x₃](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Abig-m-method-max-p-2x) — Mathematics III, chapter 5, asked 17× - [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× - [Graphical method max:z=2x₁+3x₂](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Agraphical-method-max-z-2x-3x) — Mathematics III, chapter 5, asked 12× ## Related in other subjects - [Difference eq x(k+2)+2x(k+1)+3x(k)=0](https://www.bctengineer.com/question.md?key=semester_4%2Fapplied_mathematics%3Adifference-eq-2x1-3x-x0-0-x1-2) — Applied Mathematics, chapter 2, asked 5× - [Difference equation x(k+2)+3x(k+1)+2x(k)=0](https://www.bctengineer.com/question.md?key=semester_6%2Fdigital_control_system%3Adifference-equation-x0-0-x1-1) — Digital Control System, chapter 2, asked 5× - [Difference eq x(k+2)+3x(k+1)+2x(k)=0](https://www.bctengineer.com/question.md?key=semester_4%2Fapplied_mathematics%3Adifference-eq-3x1-2x-x0-0-x1-1) — Applied Mathematics, chapter 2, asked 3× - [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×