# Linear Programming Problem: Simplex Method Solution ## Problem Statement **Maximize:** \[ 3x_1 + 2x_2 + 5x_3 \] **Subject to:** \[ \begin{cases} 2x_1 + 3x_2 + 2x_3 \leq 5 \\ x_1 + 2x_2 + 3x_3 \leq 4 \\ x_1, x_2, x_3 \geq \end{cases} \] --- ## Step 1: Standard Form Introduce slack variables \( s_1 \) and \( s_2 \): \[ \begin{align*} 2x_1 + 3x_2 + 2x_3 + s_1 &= 5 \\ x_1 + 2x_2 + 3x_3 + s_2 &= 4 \\ x_1, x_2, x_3, s_1, s_2 &\geq \end{align*} \] Objective function: \[ Z = 3x_1 + 2x_2 + 5x_3 \] Or in standard form to minimize: \[ -Z + 3x_1 + 2x_2 + 5x_3 = \] --- ## Step 2: Initial Simplex Tableau | Basic Var | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | RHS | |-----------|-------|-------|-------|-------|-------|-----| | \(s_1\) | 2 | 3 | 2 | 1 | | 5 | | \(s_2\) | 1 | 2 | 3 | | 1 | 4 | | **Z** | -3 | -2 | -5 | | | | --- ## Step 3: Identify Entering and Leaving Variables - Most negative in Z-row: **-5** (column \(x_3\)), so \(x_3\) enters. ### Ratios to determine leaving variable: - Row 1: \( \frac{5}{2} = 2.5 \) - Row 2: \( \frac{4}{3} \approx 1.33 \) (smallest, so \(s_2\) leaves) **Pivot on Row 2, Column \(x_3\)** --- ## Step 4: Pivot Operation ### Make pivot (row 2, col 3) a 1: Divide Row 2 by 3: - \(x_1 + 2x_2 + 3x_3 + s_2 = 4\) - \(x_1/3 + 2x_2/3 + x_3 + s_2/3 = 4/3\) | Basic Var | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | RHS | |-----------|-------|-------|-------|-------|-------|------| | \(s_1\) | 2 | 3 | 2 | 1 | | 5 | | \(x_3\) | 1/3 | 2/3 | 1 | | 1/3 | 4/3 | | **Z** | -3 | -2 | -5 | | | | ### Zero out the \(x_3\) column in other rows #### Row 1: \(s_1 - 2 \times\) new Row 2 - \(2 - 2 \times (1/3) = 2 - 2/3 = 4/3\) - \(3 - 2 \times (2/3) = 3 - 4/3 = 5/3\) - \(2 - 2 \times 1 = \) - \(1 - 2 \times = 1\) - \( - 2 \times (1/3) = -2/3\) - \(5 - 2 \times (4/3) = 5 - 8/3 = 7/3\) #### Z Row: \(Z + 5 \times\) new Row 2 - \(-3 + 5 \times (1/3) = -3 + 5/3 = -4/3\) - \(-2 + 5 \times (2/3) = -2 + 10/3 = 4/3\) - \(-5 + 5 \times 1 = \) - \( + 5 \times = \) - \( + 5 \times (1/3) = 5/3\) - \( + 5 \times (4/3) = 20/3\) New tableau: | Basic Var | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | RHS | |-----------|-------|-------|-------|-------|-------|------| | \(s_1\) | 4/3 | 5/3 | | 1 | -2/3 | 7/3 | | \(x_3\) | 1/3 | 2/3 | 1 | | 1/3 | 4/3 | | **Z** | -4/3 | 4/3 | | | 5/3 | 20/3 | --- ## Step 5: Next Iteration - Most negative in Z-row: \(-4/3\) (column \(x_1\)), so \(x_1\) enters. ### Ratios: - Row 1: \( (7/3) / (4/3) = 7/4 = 1.75 \) - Row 2: \( (4/3) / (1/3) = 4 \) So, \(s_1\) leaves. **Pivot on Row 1, Column \(x_1\)** --- ## Step 6: Pivot Operation Divide Row 1 by \(4/3\): - \(1, (5/3)/(4/3) = 5/4, , (1)/(4/3) = 3/4, (-2/3)/(4/3) = -2/4 = -1/2, (7/3)/(4/3) = 7/4\) | Basic Var | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | RHS | |-----------|-------|-------|-------|-------|-------|------| | \(x_1\) | 1 | 5/4 | | 3/4 | -1/2 | 7/4 | | \(x_3\) | 1/3 | 2/3 | 1 | | 1/3 | 4/3 | | **Z** | -4/3 | 4/3 | | | 5/3 | 20/3 | Now, zero out \(x_1\) in other rows. ### Row 2: \(x_3 - (1/3) \times\) Row 1 - \(1/3 - (1/3) \times 1 = \) - \(2/3 - (1/3) \times (5/4) = 2/3 - 5/12 = (8/12 - 5/12) = 3/12 = 1/4\) - \(1 - (1/3) \times = 1\) - \( - (1/3) \times (3/4) = -1/4\) - \(1/3 - (1/3) \times (-1/2) = 1/3 + 1/6 = (2/6 + 1/6) = 1/2\) - \(4/3 - (1/3) \times (7/4) = 4/3 - 7/12 = (16/12 - 7/12) = 9/12 = 3/4\) ### Z Row: \(Z + (4/3) \times\) Row 1 - \(-4/3 + (4/3) \times 1 = \) - \(4/3 + (4/3) \times (5/4) = 4/3 + 5/3 = 9/3 = 3\) - \( + (4/3) \times = \) - \( + (4/3) \times (3/4) = 1\) - \(5/3 + (4/3) \times (-1/2) = 5/3 - 2/3 = 1\) - \(20/3 + (4/3) \times (7/4) = 20/3 + 7/3 = 27/3 = 9\) New tableau: | Basic Var | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | RHS | |-----------|-------|-------|-------|-------|-------|------| | \(x_1\) | 1 | 5/4 | | 3/4 | -1/2 | 7/4 | | \(x_3\) | | 1/4 | 1 | -1/4 | 1/2 | 3/4 | | **Z** | | 3 | | 1 | 1 | 9 | --- ## Step 7: Check Optimality All Z-row coefficients for variables are now non-negative. **Optimal solution found.** --- ## Step 8: Read Solution - \(x_1 = 7/4\) - \(x_2 = \) (not a basic variable) - \(x_3 = 3/4\) - Maximum \(Z = 9\) --- ## **Final Summary** - **Optimal Solution:** \(x_1 = 1.75\), \(x_2 = \), \(x_3 = .75\) - **Maximum Value:** \(Z = 9\) **Interpretation:** To maximize the objective function \(3x_1 + 2x_2 + 5x_3\) under the given constraints, use \(x_1 = 1.75\), \(x_2 = \), and \(x_3 = .75\). This yields a maximum value of \(Z = 9\).

# Correct Simplex Tableau for Linear Programming ## Problem Overview ### Objective Function Maximize: \[ Z = 3x_1 + 2x_2 + 5x_3 \] ### Subject to Constraints \[ \begin{cases} 2x_1 + 3x_2 + 2x_3 \leq 5 \\ x_1 + 2x_2 + 3x_3 \leq 4 \\ x_1, x_2, x_3 \geq 0 \end{cases} \] ## Step 1: Standard Form Introduce slack variables \( s_1 \) and \( s_2 \): \[ \begin{align*} 2x_1 + 3x_2 + 2x_3 + s_1 &= 5 \\ x_1 + 2x_2 + 3x_3 + s_2 &= 4 \\ x_1, x_2, x_3, s_1, s_2 &\geq 0 \end{align*} \] ### Objective Function in Standard Form \[ -Z + 3x_1 + 2x_2 + 5x_3 = 0 \] ## Step 2: Initial Simplex Tableau | Basic Var | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | RHS | |-----------|---------|---------|---------|---------|---------|-----| | \(s_1\) | 2 | 3 | 2 | 1 | 0 | 5 | | \(s_2\) | 1 | 2 | 3 | 0 | 1 | 4 | | **Z** | -3 | -2 | -5 | 0 | 0 | 0 | ## Step 3: Identify Entering and Leaving Variables - **Entering Variable:** \(x_3\) (most negative in Z-row: -5) - **Leaving Variable:** \(s_2\) (smallest ratio in the table) ### Ratios: - Row 1: \( \frac{5}{2} = 2.5 \) - Row 2: \( \frac{4}{3} \approx 1.33 \) ## Step 4: Pivot Operation ### Make Pivot (Row 2, Column \(x_3\)) a 1 Divide Row 2 by 3: | Basic Var | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | RHS | |-----------|---------|---------|---------|---------|---------|------| | \(s_1\) | 2 | 3 | 2 | 1 | 0 | 5 | | \(x_3\) | \(1/3\) | \(2/3\) | 1 | 0 | \(1/3\) | \(4/3\) | | **Z** | -3 | -2 | -5 | 0 | 0 | 0 | ### Zero Out \(x_3\) Column in Other Rows #### Row 1: Update - New Row 1: \(Row 1 - 2 \times Row 2\) | Basic Var | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | RHS | |-----------|---------|---------|---------|---------|---------|------| | \(s_1\) | \(4/3\) | \(5/3\) | 0 | 1 | -2/3 | \(7/3\) | | \(x_3\) | \(1/3\) | \(2/3\) | 1 | 0 | \(1/3\) | \(4/3\) | | **Z** | -4/3 | \(4/3\) | 0 | 0 | \(5/3\) | \(20/3\) | ## Step 5: Next Iteration - **Entering Variable:** \(x_1\) (most negative in Z-row: -4/3) - **Leaving Variable:** \(s_1\) ### Ratios: - Row 1: \( \frac{7/3}{4/3} = \frac{7}{4} = 1.75 \) - Row 2: \( \frac{4/3}{1/3} = 4 \) ### Pivot Operation Divide Row 1 by \(4/3\): | Basic Var | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | RHS | |-----------|---------|---------|---------|---------|---------|-----| | \(x_1\) | 1 | \(5/4\) | 0 | \(3/4\) | -1/2 | \(7/4\) | | \(x_3\) | \(1/3\) | \(2/3\) | 1 | 0 | \(1/3\) | \(4/3\) | | **Z** | -4/3 | \(4/3\) | 0 | 0 | \(5/3\) | \(20/3\) | ### Zero Out \(x_1\) in Other Rows #### Update Row 2: - New Row 2: \(Row 2 - (1/3) \times Row 1\) | Basic Var | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | RHS | |-----------|---------|---------|---------|---------|---------|-----| | \(x_1\) | 1 | \(5/4\) | 0 | \(3/4\) | -1/2 | \(7/4\) | | \(x_3\) | 0 | \(1/4\) | 1 | -1/4 | \(1/2\) | \(3/4\) | | **Z** | 0 | 3 | 0 | 1 | 1 | 9 | ## Step 6: Check Optimality All coefficients in Z-row are non-negative. The optimal solution is found. ## Final Summary - **Optimal Solution:** \(x_1 = 1.75\), \(x_2 = 0\), \(x_3 = 0.75\) - **Maximum Value:** \(Z = 9\) **Interpretation:** To maximize the objective function \(3x_1 + 2x_2 + 5x_3\) under the given constraints, set \(x_1 = 1.75\) and \(x_3 = 0.75\). This yields a maximum value of \(Z = 9\).

# Summary of Each Step in the Simplex Method ## Step 1: Standard Form Introduce slack variables \(s_1\) and \(s_2\) to convert inequalities into equalities. Rewrite the objective function to reflect maximization while including slack variables. ## Step 2: Initial Simplex Tableau Construct the initial tableau, representing the coefficients of the variables and slack variables, along with the right-hand side (RHS) values from the constraints. This sets the stage for the simplex iterations. ## Step 3: Identify Entering and Leaving Variables Determine which variable enters the basis (most negative coefficient in the Z-row) and which slack variable leaves (smallest ratio of RHS to the pivot column). Here, \(x_3\) enters and \(s_2\) leaves. ## Step 4: Pivot Operation Perform the pivot operation to convert the pivot element to 1 and zero out the rest of the pivot column. Update the tableau accordingly, reflecting changes from the pivot operation. ## Step 5: Next Iteration Reassess the tableau to identify the next entering and leaving variables. In this case, \(x_1\) enters and \(s_1\) leaves, necessitating another pivot operation to refine the solution. ## Step 6: Check Optimality After performing the necessary updates, check the Z-row for non-negative coefficients. All coefficients being non-negative indicates that an optimal solution has been reached. ## Final Summary The optimal solution occurs at \(x_1 = 1.75\), \(x_2 = 0\), and \(x_3 = 0.75\), yielding a maximum value of \(Z = 9\). This solution satisfies all constraints and maximizes the objective function effectively.