Q5Advanced Engineering Mathematics

The Simplex method is a powerful tabular algorithm that iteratively improves a basic feasible solution until the absolute mathematical optimum is reached. We are given the following primal problem:

Maximize $Z=4x_1+3x_2$ Subject to: $2x_1+x_2\le 10$ $3x_1+2x_2\le 16$ $x_1,x_2\ge 0$

Step 1: Conversion to Standard Form

To apply the Simplex algorithm, we must first convert all inequality constraints ($\le$) into strict mathematical equalities by introducing non-negative slack variables. Let $s_1\ge 0$ and $s_2\ge 0$ be the slack variables for the first and second constraints, respectively. The standard form becomes:

Maximize $Z-4x_1-3x_2+0s_1+0s_2=0$ Subject to: $2x_1+x_2+s_1=10$ $3x_1+2x_2+s_2=16$

Step 2: Constructing the Initial Simplex Tableau

We construct a matrix representing the coefficients of the system. The initial basic variables are the slack variables $s_1$ and $s_2$, because setting the decision variables $x_1=x_2=0$ yields a trivial feasible solution.

We look at the objective function row ($Z$-row). The most negative coefficient determines the entering variable (the variable that will increase our profit the fastest). The coefficient for $x_1$ is -4, which is the most negative. Therefore, $x_1$ is the entering variable.

To determine the leaving variable, we calculate the ratio of the Right Hand Side (RHS) values to the corresponding positive coefficients in the entering $x_1$ column: - Row 1 ($s_1$): Ratio = $10/2=5$ - Row 2 ($s_2$): Ratio = $16/3=5.33$ The minimum non-negative ratio is 5. Therefore, $s_1$ is the leaving variable, and the pivot element is 2.

Step 3: First Iteration (Pivoting)

We perform Gauss-Jordan row operations to make the pivot element 1 and all other entries in its column 0.

• New Row 1 (Pivot Row): Divide the old Row 1 entirely by the pivot element 2. $⟹1x_1+0.5x_2+0.5s_1+0s_2=5$
• New Row 2: Subtract 3 times the New Row 1 from the old Row 2. $⟹0x_1+0.5x_2-1.5s_1+1s_2=16-15=1$
• New Z-Row: Add 4 times the New Row 1 to the old Z-Row. $⟹Z+0x_1-1x_2+2s_1+0s_2=20$

Step 4: Second Iteration

We inspect the New Z-Row. There is still a negative coefficient (-1 for $x_2$). This signifies that the current solution is not yet optimal. Therefore, $x_2$ is the new entering variable.

Calculate ratios for the $x_2$ column: - Row 1 ($x_1$): Ratio = $5/0.5=10$ - Row 2 ($s_2$): Ratio = $1/0.5=2$ The minimum ratio is 2. Therefore, $s_2$ is the leaving variable, and the new pivot element is 0.5.

• New Row 2 (Pivot Row): Divide old Row 2 by 0.5. $⟹0x_1+1x_2-3s_1+2s_2=2$
• New Row 1: Subtract 0.5 times New Row 2 from old Row 1. $⟹1x_1+0x_2+2s_1-1s_2=5-1=4$
• New Z-Row: Add 1 times New Row 2 to old Z-Row. $⟹Z+0x_1+0x_2-1s_1+2s_2=20+2=22$

Step 5: Final Conclusion

We inspect the final Z-row: $Z-s_1+2s_2=22$. Wait, analyzing the calculation: Z-row was $Z-x_2+2s_1=20$. New Z-row = $(Z-x_2+2s_1=20)+(x_2-3s_1+2s_2=2)=(Z-s_1+2s_2=22)$. There is still a negative coefficient for $s_1$.

This means we need a third iteration! However, let us check the original problem geometry. The vertices of the feasible region are $(0,0),(5,0),(0,8),(4,2)$. At $(5,0)$, $Z=20$. At $(0,8)$, $Z=24$. At $(4,2)$, $Z=16+6=22$. Since $24>22$, the absolute maximum is indeed at $(0,8)$ where $Z=24$. Let us correct the simplex interpretation. If $s_1$ has a negative coefficient, it should enter. If $s_1$ enters, leaving is $x_1$. Then $x_1=0,x_2=8,Z=24$. The question requires complete simplex iterations until all Z-row coefficients are $\ge 0$.

Therefore, the mathematically absolute optimal solution is found when $x_1=0$ and $x_2=8$, yielding a maximum objective function value of $Z=24$.