Q5Advanced Engineering Mathematics

The standard Simplex method is a highly efficient algorithm for solving Linear Programming Problems (LPPs). However, it fundamentally requires an Initial Basic Feasible Solution (IBFS) to begin its iterative search. When an LPP has constraints of the type "less than or equal to" ($\le$), we introduce positive slack variables, which conveniently form an identity matrix and serve as the IBFS. However, when constraints are of the type "greater than or equal to" ($\ge$) or strictly "equal to" ($=$), we must subtract surplus variables. These surplus variables have a coefficient of -1, so they cannot form the required identity matrix. To force an IBFS, we introduce "Artificial Variables". The Two-Phase Method is a mathematically rigorous algorithm designed to systematically handle and eventually eliminate these artificial variables.

1. Standardizing the Given Problem

Consider the given problem: Maximize $Z=5x_1+8x_2$ Subject to: $3x_1+2x_2\ge 3$ $x_1+4x_2\ge 4$ $x_1+x_2\le 5$ $x_1,x_2\ge 0$

We convert these inequalities into strict equations. For the first two ($\ge$) constraints, we subtract non-negative surplus variables ($s_1,s_2$). For the third ($\le$) constraint, we add a non-negative slack variable ($s_3$).

$3x_1+2x_2-s_1=3$ $x_1+4x_2-s_2=4$ $x_1+x_2+s_3=5$

Because $s_1$ and $s_2$ have negative coefficients, they cannot serve as initial basic variables (setting $x_1=x_2=0$ would make $s_1=-3$ and $s_2=-4$, violating the non-negativity constraint). Therefore, we must add artificial variables $A_1\ge 0$ and $A_2\ge 0$ to the first two equations to create a valid starting basis.

$3x_1+2x_2-s_1+A_1=3$ $x_1+4x_2-s_2+A_2=4$ $x_1+x_2+s_3=5$

Our Initial Basic Feasible Solution is now $A_1=3,A_2=4,s_3=5$.

2. Phase I: Elimination of Artificial Variables

The primary, sole objective of Phase I is to forcefully drive the artificial variables out of the basis. We do this by completely ignoring the original objective function and creating a new, temporary objective function that heavily penalizes the existence of artificial variables. We seek to minimize the sum of the artificial variables.

Phase I Objective: Minimize $W=A_1+A_2$ (or Maximize $Z^{\ast }=-A_1-A_2$).

We construct a Simplex tableau using this new objective function $Z^{\ast }$. We then perform standard Simplex iterations (pivot operations). The goal is to make the value of $Z^{\ast }$ exactly equal to zero. If the optimal value of Phase I is $Z^{\ast }=0$, it mathematically proves that all artificial variables have been driven to zero, meaning they have left the basis. The resulting solution is a basic feasible solution to the original problem without artificial variables. (Note: If Phase I ends and $Z^{\ast }<0$, it mathematically proves that the original problem has no feasible solution).

3. Phase II: Optimization of the Original Objective

Once Phase I successfully concludes with $Z^{\ast }=0$, we immediately transition to Phase II. The procedure is as follows:

• Discard the temporary objective function $Z^{\ast }$.
• Physically delete the columns corresponding to the artificial variables ($A_1$ and $A_2$) from the final Simplex tableau of Phase I, as they are no longer needed.
• Restore the original objective function: Maximize $Z=5x_1+8x_2$.
• Recalculate the objective row ($Z$-row or ${\Delta }_j$ row) using the original coefficients.
• Resume standard Simplex iterations. Continue pivoting until all values in the objective row indicate optimality (for maximization, all ${\Delta }_j\ge 0$).

This two-phase approach guarantees that the algorithm first finds a mathematically valid starting point in the multi-dimensional feasible region, and then seamlessly navigates along the edges of that region to find the absolute optimal vertex.