Let's solve the problem **step-by-step using the big-M method**. --- ### **Step 1: Write the problem in standard form** Given: \[ \text{min } z = -3x_1 + x_2 + x_3 \] Subject to: \[ \begin{align*} x_1 - 2x_2 + x_3 &\leq 11 \\ -4x_1 + x_2 + 2x_3 &\geq 3 \\ -2x_1 + x_3 &= 1 \\ x_1, x_2, x_3 &\geq 0 \end{align*} \] --- ### **Step 2: Convert inequalities to equalities** #### 1st Constraint (\(\leq\)): Add a **slack variable** \(s_1 \geq 0\): \[ x_1 - 2x_2 + x_3 + s_1 = 11 \] #### 2nd Constraint (\(\geq\)): Subtract a **surplus variable** \(s_2 \geq 0\) and **add an artificial variable** \(a_1 \geq 0\): \[ -4x_1 + x_2 + 2x_3 - s_2 + a_1 = 3 \] #### 3rd Constraint (equality): Add an **artificial variable** \(a_2 \geq 0\): \[ -2x_1 + x_3 + a_2 = 1 \] --- ### **Step 3: Write the full standard form** Objective function (with big-M penalty for artificial variables): \[ \text{min } z = -3x_1 + x_2 + x_3 + M(a_1 + a_2) \] Subject to: \[ \begin{align*} x_1 - 2x_2 + x_3 + s_1 &= 11 \\ -4x_1 + x_2 + 2x_3 - s_2 + a_1 &= 3 \\ -2x_1 + x_3 + a_2 &= 1 \\ x_1, x_2, x_3, s_1, s_2, a_1, a_2 &\geq 0 \end{align*} \] --- ### **Step 4: Set up the initial simplex tableau** Let’s order variables as: \(x_1, x_2, x_3, s_1, s_2, a_1, a_2\) | Basic | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | \(a_1\) | \(a_2\) | RHS | |-------|--------|--------|--------|--------|--------|--------|--------|-----| | \(s_1\) | 1 | -2 | 1 | 1 | 0 | 0 | 0 | 11 | | \(a_1\) | -4 | 1 | 2 | 0 | -1 | 1 | 0 | 3 | | \(a_2\) | -2 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | | **z** | -3 | 1 | 1 | 0 | 0 | M | M | 0 | --- ### **Step 5: Adjust objective function row for artificial variables** For each artificial variable in the basis, subtract M times its row from the objective row: **For \(a_1\) and \(a_2\):** - Subtract \(M\) × (row of \(a_1\)) and \(M\) × (row of \(a_2\)) from \(z\)-row: \[ z' = -3x_1 + x_2 + x_3 + M(a_1 + a_2) - M(-4x_1 + x_2 + 2x_3 - s_2 + a_1) - M(-2x_1 + x_3 + a_2) \] Expand and collect like terms: \[ = -3x_1 + x_2 + x_3 + M a_1 + M a_2 + 4M x_1 - M x_2 - 2M x_3 + M s_2 - M a_1 + 2M x_1 - M x_3 - M a_2 \] \[ = (-3 + 4M + 2M)x_1 + (1 - M)x_2 + (1 - 2M - M)x_3 + M s_2 \] \[ = (6M - 3)x_1 + (1 - M)x_2 + (1 - 3M)x_3 + M s_2 \] Artificial variables' coefficients become 0. So the new \(z\)-row is: | | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | \(a_1\) | \(a_2\) | RHS | |-----|-------|-------|-------|-------|-------|-------|-------|-----| | **z** | \(6M-3\) | \(1-M\) | \(1-3M\) | 0 | \(M\) | 0 | 0 | \(-3M-1M\) = \(-4M\) (from the constants on the right: \(3M+1M\) but with a minus sign) | --- ### **Step 6: Start simplex iterations** You now proceed with the simplex method, using the tableau above: - **Entering variable**: Choose the variable with most negative coefficient in the \(z\)-row. - **Leaving variable**: Use minimum positive ratio test (RHS/column entry). - **Pivot**: Update tableau. Continue until all coefficients in the \(z\)-row for non-basic variables are non-negative (for minimization). --- ### **Summary of Steps** 1. **Convert each constraint to equality** (add slack, surplus, artificial as needed). 2. **Set up the initial simplex tableau** with artificial variables in the basis. 3. **Write the penalized objective function** (Big-M method). 4. **Adjust the objective function row** in the tableau for artificial variables. 5. **Apply simplex iterations** (pivot until optimality). --- **If you need help with the simplex iterations (pivot steps), let me know and I'll walk you through them!**