--- title: "Two-phase simplex method max:Z=3x₁−x₂" subject: "Mathematics III" chapter: 5 key: "semester_3/mathematics_iii:two-phase-simplex-method-max-z" source: https://www.bctengineer.com/q/semester_3/mathematics_iii/two-phase-simplex-method-max-z site: BCT Engineering --- # Two-phase simplex method max:Z=3x₁−x₂ Mathematics III · Chapter 5: Linear Programming - Asked in: 2079 Bhadra, 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/two-phase-simplex-method-max-z - Whole chapter: https://www.bctengineer.com/md/semester_3/mathematics_iii/chapter-5 ## Question Solve the linear programming problem by the simplex method using the two phase method: Maximize Z = 3x₁ − x₂ subject to 2x₁ + x₂ ≥ 2, x₁ + 3x₂ ≤ 2, x₂ ≤ 4; x₁, x₂ ≥ 0. ## Short answer Applying the two-phase simplex method, Phase I eliminates the artificial variable, and Phase II yields the optimal solution: x1 = 2, x2 = 0, maximum Z = 6. ## Answer **Idea of the two-phase method.** Phase I removes the artificial variables by maximising −(sum of artificial variables) (the same as minimising their sum). If the optimum is 0, a basic feasible solution of the original problem has been found. Phase II then optimises the real objective function starting from that solution. **Step 1: Standard form.** - 2x₁ + x₂ ≥ 2: subtract surplus variable s₁ and add artificial variable A₁. - x₁ + 3x₂ ≤ 2: add slack variable s₂. - x₂ ≤ 4: add slack variable s₃. ```text 2x₁ + x₂ − s₁ + A₁ = 2 x₁ + 3x₂ + s₂ = 2 x₂ + s₃ = 4 ``` **Phase I.** Maximize Z′ = −A₁ (cost 0 for all other variables). Starting basis: A₁, s₂, s₃. **Table 1** ```text Cj 0 0 0 -1 0 0 Basis CB x₁ x₂ s₁ A₁ s₂ s₃ b Ratio --------------------------------------- A₁ -1 2 1 -1 1 0 0 2 1 s₂ 0 1 3 0 0 1 0 2 2 s₃ 0 0 1 0 0 0 1 4 - --------------------------------------- Zj -2 -1 1 -1 0 0 -2 Cj-Zj 2 1 -1 0 0 0 Entering: x₁ Leaving: A₁ Pivot = 2 ``` **Table 2** ```text Cj 0 0 0 0 0 Basis CB x₁ x₂ s₁ s₂ s₃ b -------------------------------- x₁ 0 1 1/2 -1/2 0 0 1 s₂ 0 0 5/2 1/2 1 0 1 s₃ 0 0 1 0 0 1 4 -------------------------------- Zj 0 0 0 0 0 0 Cj-Zj 0 0 0 0 0 ``` In the last table of Phase I, Max Z′ = 0 and A₁ is no longer in the basis, so the original problem is feasible. Delete the A₁ column and go to Phase II. **Phase II.** Restore the original objective: Maximize Z = 3x₁ − x₂ + 0s₁ + 0s₂ + 0s₃, starting with the final basis of Phase I (x₁, s₂, s₃). **Table 1** ```text Cj 3 -1 0 0 0 Basis CB x₁ x₂ s₁ s₂ s₃ b Ratio --------------------------------------- x₁ 3 1 1/2 -1/2 0 0 1 - s₂ 0 0 5/2 1/2 1 0 1 2 s₃ 0 0 1 0 0 1 4 - --------------------------------------- Zj 3 3/2 -3/2 0 0 3 Cj-Zj 0 -5/2 3/2 0 0 Entering: s₁ Leaving: s₂ Pivot = 1/2 ``` **Table 2** ```text Cj 3 -1 0 0 0 Basis CB x₁ x₂ s₁ s₂ s₃ b ------------------------------ x₁ 3 1 3 0 1 0 2 s₁ 0 0 5 1 2 0 2 s₃ 0 0 1 0 0 1 4 ------------------------------ Zj 3 9 0 3 0 6 Cj-Zj 0 -10 0 -3 0 ``` All Cj − Zj ≤ 0, so the solution is optimal. **Answer:** x₁ = 2, x₂ = 0, Maximum Z = 6. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does Phase I of the two-phase method optimise? A. The original objective Z = 3x1 - x2 B. Maximise -(sum of artificial variables) C. Minimise the slack variables D. Maximise the sum of the artificial variables Answer: B. Phase I maximises Z' = -A1 (equivalently minimises the sum of artificials) to find a feasible start. (Key point: Phase I objective) 2. What does Max Z' = 0 at the end of Phase I tell us? A. The problem is unbounded B. The original problem has no solution C. The original problem has a basic feasible solution, with artificials out of the basis D. The optimal value of Z is 0 Answer: C. Zero total artificial value means all artificials can be removed, so a basic feasible solution exists for the original problem. (Key point: Meaning of Phase I result) 3. How does Phase II begin? A. Use the final Phase I basis with the artificial column deleted and the original objective restored B. Start again from the slack basis with the artificial column kept C. Use -M costs on the artificial variable D. Use the Phase I objective with new constraints Answer: A. Phase II restores Cj = 3, -1, 0, 0, 0 and starts from the Phase I final basis (x1, s2, s3). (Key point: Starting Phase II) 4. What is the optimal solution? A. x1 = 1, x2 = 0, Z = 3 B. x1 = 0, x2 = 2/3, Z = -2/3 C. x1 = 2, x2 = 0, Z = 6 D. x1 = 2, x2 = 4, Z = 2 Answer: C. In Phase II Table 2, all Cj - Zj <= 0, with x1 = 2 and x2 = 0 giving Z = 6. (Key point: Final result) ## Close variants set in other exams - [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× - [Simplex method max:P=15x+10y](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Asimplex-method-max-p-15x-10y) — Mathematics III, chapter 5, asked 17× - [Simplex method max:Z=15x₁+10x₂](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Asimplex-method-max-z-15x-10x) — Mathematics III, chapter 5, asked 15× - [Big-M method max:F=2x₁+x₂](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Abig-m-method-max-f-2x) — Mathematics III, chapter 5, asked 17× - [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× - [Simplex method max:Z=4x+3y](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Asimplex-method-max-z-4x-3y) — Mathematics III, chapter 5, asked 17× - [Simplex method max:P=20x₂−5x₁](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Asimplex-method-max-p-20x-5x) — Mathematics III, chapter 5, asked 17× - [Big-M method max:Z=2x₁+x₂](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Abig-m-method-max-z-2x) — Mathematics III, chapter 5, asked 17× - [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× ## Related in Mathematics III - [Simplex method max:Z=3x₁+5x₂](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Asimplex-method-max-z-3x-5x) — Mathematics III, chapter 5 - [Simplex method max:P=−x₁+2x₂](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Asimplex-method-max-p-x-2x) — Mathematics III, chapter 5, asked 8× - [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× - [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× - [Difference eq x(k+2)-3x(k+1)+2x(k)=4^k](https://www.bctengineer.com/question.md?key=semester_4%2Fapplied_mathematics%3Adifference-eq-forced-4k) — Applied Mathematics, chapter 2