In two-phase simplex method subtracted variable is called as

Given the following system :

\begin{align*} \text{minimise } z = &2x_1 &+ 3x_2 &+ 3x_3 &+ x_4 &- 2x_5& \\ \end{align*}

Subject to \begin{align*} & x_1 &+ 3x_2 & &+x_4 &+ x_5 &= 2 \\ & x_1 &+ 2x_2 & &- 3x_4 &+ x_5 &= 2 \\ - &x_1 &- 4x_2 & +x_3 & & &= 1 \\ \end{align*}

with $x_1, x_2, x_3, x_4, x_5 \geq 0$

There should be Phase I and then Phase II of the simplex method.

Q1 - how to explain why Phase I is required here

Q2 - how to know which rows should have artificial variables added

For question 1, the objective function can be written as

\begin{align*} -z + 2x_1 + 3x_2 + 3x_3 + x_4 - 2x_5 = 0\\ \end{align*}

The way that the system is initially set up has basic variables $x_3$ and non-basic variables $x_1,x_2,x_4,x_5 = 0$.

Meaning the objective function is

\begin{align*} -z + 3x_3 = 0\\ \end{align*}

\begin{align*} z = 3x_3 \end{align*}

Why is this an issue?

For Question 2 I'm not sure what to consider.

There are two standard methods for handling artificial variables within the simplex method:

The Big M method

The 2-Phase Method

Although they seem to be different, they are essentially identical. However, methodologically the 2-Phase method is much superior. We shall therefore focus on it.

The 2-Phase method is based on the following simple observation: Suppose that you have a linear programming problem in canonical form and you wish to generate a feasible solution (not necessarily optimal) such that a given variable, say x3, is equal to zero. Then, all you have to do is solve the linear programming problem obtained from the original problem by replacing the original objective function by x3 and setting opt=min.

If more than one variable is required to be equal to zero, then replace the original objective function by the sum of all the variables you want to set to zero.

Observe that because of the non-negativity constraint, the sum of any collection of variables cannot be negative. Hence the smallest possible feasible value of such a sum is zero. If the smallest feasible sum is strictly positive, then the implication is that it is impossible to set all the designated variables to zero.

Applying this simple idea to artificial variables we obtain the following recipe:

To set all the artificial variables to zero, solve a linear programming problem derived from the canonical form of the original problem by replacing the original objective function by the sum of all the artificial valriables and setting opt=min.
If the optimal value of the modified objective function is not equal to zero, then the problem (system of constraints) is not feasible.

To illustrate the modelling aspects of this approach let us re-examine the following little example:

x1 + 3x2 + 7x3 > = 25
-3x1 - 2x2 + 7x3 = - 5
2x1 + x2 + 4x3 < = 10
x2,x3 >= 0

Taking case of its violations of the standard form we obtain the following canonical form:

x1 - x2 + 3x3 + 7x4 - x5 + x6 = 25

3x1 - 3x2 + 2x3 - 7x4 + x7 = 5

2x1 - 2x2 + x3 + 4x4 + x8 = 10

xj>= 0 , j=1,...,8

There are two artificial variables, namey x6 and x7. Thus, Phase 1 of the 2-Phase method involves the following linear programming problem:

w* := min w := x6 + x7

x1 - x2 + 3x3 + 7x4 - x5 + x6 = 25

3x1 - 3x2 + 2x3 - 7x4 + x7 = 5

2x1 - 2x2 + x3 + 4x4 + x8 = 10

xj>= 0 , j=1,...,8

If we now incorporate the objective function in the constraint in the usual manner and place the new variable, namely w last, we obtain the following system:

x1 - x2 + 3x3 + 7x4 - x5 + x6 = 25

3x1 - 3x2 + 2x3 - 7x4 + x7 = 5

2x1 - 2x2 + x3 + 4x4 + x8 = 10

- x6 - x7 + w = 0

xj>= 0 , j=1,...,8, w>= 0

Note that this system is not in a canonical form because the columns of the artificial variables are not elementary columns. To obtain a canonical form we have to add the rows of the artificial variables to the last row. This yields:

x1 - x2 + 3x3 + 7x4 - x5 + x6 = 25

3x1 - 3x2 + 2x3 - 7x4 + x7 = 5

2x1 - 2x2 + x3 + 4x4 + x8 = 10

4x1 - 4x2 + 5x3 + - x5 + w = 30

xj>= 0 , j=1,...,8, w>= 0

This is then the system that will be used to initialise the simplex algorithm for Phase 1 of the 2-Phase method. Of course, the column of w will not appear in the tableau.

We can ditinguish between two cases as far as the end of Phase 1 is concerned, namely:

Case 1: w* > 0 : The optimal value of w is greater than zero.

Case 2: w* = 0 : The optimal value of w is equal to zero.

In Case 1 we conclude that the LP problem under consideration does not have a feasible solution whereas Case 2 implies that the constraints are feasible, hence the problem under consideration possesses a feasible solution.

The following final simplex tableau is an example of Case 1:

x1 x2 x3 x4 x5 x6 x7 w RHS

1 -1 2 7 -1 2 25

-3 1 -7 1 1 5

-2 -1 -4 -1 1 5

One artificial variable (x6) is in the basis and is not equal to zero. The problem does not have a feasible solution.

It should be noted that although Case 2 implies that all the artificial variables are equal to zero, this does not mean that they are all out of the basis.

So it is necessary to consider Case 1 in more detail, namey:

Case 2.1: All the artificial variables are non-basic.

Case 2.2: some of the artificial variables are in the basis

In Case 2.1 we proceed to Phase 2 of the 2-Phase method replacing the objecitve function of Phase 1 with the original objecitve function. This will typically violate the canonical form of the problem and thus pivot operations may have to be used to restore the canonical form.

The following is a typical example of Case 2.1

x1 x2 x3 x4 x5 x6 x7 w RHS

1 -1 2 7 2 25

-3 1 -7 1 1 1 5

-2 -1 -3 -1 1 0

The two artificial variables are not in the basis, hence w is equal to zero.

Case 2.2 represents a degenerate basis, namely a situation where one or more of the basic variables are equal to zero. Here is an example:

x1 x2 x3 x4 x5 x6 x7 w RHS

1 -1 2 7 -1 2 25

-3 1 -7 1 1 0

-2 -1 -4 -1 1 0

To take a degenerate artificial variable out of the basis we pivot on any non-artificial variable whose coefficient in the row of the artificial is not equal to zero and enter it into the basis.

Fore example, in the table above, we can replace x6 by either x2 or x3 or x4.

If the coefficients of all the non-artificial variables in that row are zeros, then the conclusion is that the constraint is redundant and thus can be ignored.

More to come soon .......