Let's solve each problem using the **two-phase simplex method** step by step. --- ## Problem (a): **Maximize** \( 3x_1 + x_2 \) **Subject to:** \( x_1 - x_2 \leq -1 \) \( -x_1 - x_2 \leq -3 \) \( 2x_1 + x_2 \leq 4 \) \( x_1, x_2 \geq 0 \) --- ### **Step 1: Convert to Standard Form** First, convert all constraints to equalities with slack/surplus and artificial variables as needed. #### First constraint: \( x_1 - x_2 \leq -1 \) Rewrite as: \( x_1 - x_2 + s_1 = -1 \), \( s_1 \geq 0 \) But the right side is negative. Multiply both sides by -1: \( -x_1 + x_2 - s_1 = 1 \) To bring to standard form, we need the right side to be positive. So, \( -x_1 + x_2 - s_1 + a_1 = 1 \), where \( a_1 \) is artificial variable. #### Second constraint: \( -x_1 - x_2 \leq -3 \) Again, right side is negative. Multiply both sides by -1: \( x_1 + x_2 + s_2 = 3 \) #### Third constraint: \( 2x_1 + x_2 \leq 4 \) \( 2x_1 + x_2 + s_3 = 4 \) Variables: \( x_1, x_2, s_1, s_2, s_3, a_1 \geq 0 \) --- ### **Standard Form Table** | Constraint | Equation | |---------------------------|--------------------------------| | (1) | \(-x_1 + x_2 - s_1 + a_1 = 1\) | | (2) | \(x_1 + x_2 + s_2 = 3\) | | (3) | \(2x_1 + x_2 + s_3 = 4\) | Objective: Maximize \( 3x_1 + x_2 \) --- ### **Step 2: Phase I Objective Function** Minimize sum of artificial variables: \( W = a_1 \) (since only one artificial variable) --- ### **Step 3: Initial Simplex Tableau (Phase I)** Variables: \( x_1, x_2, s_1, s_2, s_3, a_1 \) Write the tableau: | Basis | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | \(a_1\) | RHS | |-------|--------|--------|--------|--------|--------|--------|------| | a1 | -1 | 1 | -1 | 0 | 0 | 1 | 1 | | s2 | 1 | 1 | 0 | 1 | 0 | 0 | 3 | | s3 | 2 | 1 | 0 | 0 | 1 | 0 | 4 | | W | 1 | -1 | 1 | 0 | 0 | 0 | -1 | How did we get the W row? Phase I objective: \( W = a_1 \) Since \( a_1 = 1 + x_1 - x_2 + s_1 \), subtract row 1 from W row. --- #### **Phase I: Find Basic Feasible Solution** Currently, the basis is \( [a_1, s_2, s_3] \). Let's try to remove \( a_1 \) from the basis. Look at row 1 (a1): the coefficient of \( x_2 \) is 1 (positive), so we can try to bring \( x_2 \) into the basis. Compute the ratio test for \( x_2 \): - Row 1: coefficient of \( x_2 \) is 1, RHS = 1 ⇒ \( 1/1 = 1 \) - Row 2: coefficient of \( x_2 \) is 1, RHS = 3 ⇒ \( 3/1 = 3 \) - Row 3: coefficient of \( x_2 \) is 1, RHS = 4 ⇒ \( 4/1 = 4 \) Minimum positive ratio is 1 (row 1). So pivot on \( x_2 \) in row 1. --- #### **Pivot: Introduce \( x_2 \) into Basis, Remove \( a_1 \)** Row 1: \( -x_1 + x_2 - s_1 + a_1 = 1 \) - Solve for \( x_2 \): \( x_2 = 1 + x_1 + s_1 - a_1 \) Update the tableau (row operations): - New row 1 (x2): \( x_2 = 1 + x_1 + s_1 - a_1 \) - Substitute into other rows. **Row 2:** \( x_1 + x_2 + s_2 = 3 \) Substitute \( x_2 \): \( x_1 + [1 + x_1 + s_1 - a_1 ] + s_2 = 3 \) \( x_1 + 1 + x_1 + s_1 - a_1 + s_2 = 3 \) \( 2x_1 + s_1 + s_2 - a_1 = 2 \) **Row 3:** \( 2x_1 + x_2 + s_3 = 4 \) \( 2x_1 + [1 + x_1 + s_1 - a_1 ] + s_3 = 4 \) \( 2x_1 + 1 + x_1 + s_1 - a_1 + s_3 = 4 \) \( 3x_1 + s_1 + s_3 - a_1 = 3 \) **W row:** Previous W row: \( W = a_1 \) But after pivot, W row will be updated. Substitute \( a_1 = x_2 - 1 - x_1 - s_1 \) into W row: \( W = x_2 - 1 - x_1 - s_1 \) So W row coefficients: \( x_1: -1 \), \( x_2: 1 \), \( s_1: -1 \), \( a_1: 0 \), RHS: -1 --- So the new tableau is: | Basis | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | \(a_1\) | RHS | |-------|--------|--------|--------|--------|--------|--------|------| | x2 | 1 | 1 | 1 | 0 | 0 | -1 | 1 | | s2 | 2 | 0 | 1 | 1 | 0 | -1 | 2 | | s3 | 3 | 0 | 1 | 0 | 1 | -1 | 3 | | W | -1 | 1 | -1 | 0 | 0 | 0 | -1 | But notice, in row 1, \( x_2 = 1 + x_1 + s_1 - a_1 \), so the tableau should reflect \( x_2 \) in the basis (column for \( x_2 \) should be 1 in row 1, and 0 in others). But let's just continue with the variables for now. Now, is there any artificial variable in the basis? No. We can proceed to Phase II. --- ### **Step 4: Phase II (Original Objective Function)** Now, the basis is \( x_2, s_2, s_3 \). Express the original objective function in terms of the current non-basic variables (i.e., set all artificial variables to zero, as they are out of the basis). Recall: Original objective: \( Z = 3x_1 + x_2 \) We need to write the coefficients for the current basis. Let's set up the tableau for Phase II: **Objective function coefficients:** \( x_1: 3 \), \( x_2: 1 \), other variables: 0 Our current basic variables: \( x_2, s_2, s_3 \) From the last tableau, the only nonzero coefficients in the objective row are for \( x_1 \) and \( x_2 \). Set up the tableau: | Basis | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | RHS | |-------|--------|--------|--------|--------|--------|------| | x2 | 1 | 1 | 1 | 0 | 0 | 1 | | s2 | 2 | 0 | 1 | 1 | 0 | 2 | | s3 | 3 | 0 | 1 | 0 | 1 | 3 | | Z | 3 | 1 | 0 | 0 | 0 | 0 | Now, to proceed with the simplex method, subtract the appropriate multiples of the basic variable rows from the objective row (Z-row) to make the coefficients of the basic variables zero in the Z-row. - For \( x_2 \) (row 1): coefficient in Z-row is 1. Subtract 1 × row 1 from Z-row. New Z-row: \( [3, 1, 0, 0, 0 | 0] - 1 \times [1, 1, 1, 0, 0 | 1] = [2, 0, -1, 0, 0 | -1] \) So, new Z-row: \( x_1: 2 \), \( x_2: 0 \), \( s_1: -1 \), \( s_2: 0 \), \( s_3: 0 \), RHS: -1 --- ### **Step 5: Continue Simplex Iterations** Now, check if any non-basic variable has a positive coefficient in the Z-row. - \( x_1 \): 2 > 0 So, \( x_1 \) enters the basis. Look at the minimum ratio test: - Row 1 (x2): coefficient of \( x_1 \) is 1, RHS = 1 ⇒ \( 1/1 = 1 \) - Row 2 (s2): coefficient of \( x_1 \) is 2, RHS = 2 ⇒ \( 2/2 = 1 \) - Row 3 (s3): coefficient of \( x_1 \) is 3, RHS = 3 ⇒ \( 3/3 = 1 \) All ratios are 1. Let's select row 1 for the pivot (arbitrary among ties). Pivot on \( x_1 \) in row 1. --- #### **Pivot: \( x_1 \) enters, \( x_2 \) leaves** Row 1: \( x_2 = 1 + x_1 + s_1 \) Swap \( x_1 \) into basis: - \( x_1 = x_2 - 1 - s_1 \) Substitute into other rows. **Row 2 (s2):** \( 2x_1 + s_1 + s_2 = 2 \) Substitute \( x_1 = x_2 - 1 - s_1 \): \( 2(x_2 - 1 - s_1) + s_1 + s_2 = 2 \) \( 2x_2 - 2 - 2s_1 + s_1 + s_2 = 2 \) \( 2x_2 - 2 - s_1 + s_2 = 2 \) \( 2x_2 - s_1 + s_2 = 4 \) **Row 3 (s3):** \( 3x_1 + s_1 + s_3 = 3 \) \( 3(x_2 - 1 - s_1) + s_1 + s_3 = 3 \) \( 3x_2 - 3 - 3s_1 + s_1 + s_3 = 3 \) \( 3x_2 - 3 - 2s_1 + s_3 = 3 \) \( 3