# Operations Research/The Simplex Method

We can solve two variables${\displaystyle (x_{2},s_{2})}$ LP models easily using the graphical method outlined in the previous section but what should we do in case of three variable problems, i.e. when our company makes three products we have to make decisions about. What about four or five variable problems? This is where the simplex method comes in. It is an iterative method which by repeated use gives us the solution to any n variable LP model.

## Standard form of a LP modelEdit

Let us define an LP model as being in standard form if it satisfies the following two conditions:

• All the constraints with the exception of the non-negativity restrictions are equations with non-negative right hand side.
• All the variables are non-negative.

For example,

Maximize ${\displaystyle z=5x_{1}+4x_{2}}$
subject to,
${\displaystyle 6x_{1}+4x_{2}+s_{1}=24}$ ,
${\displaystyle x_{1}+2x_{2}+s_{2}=6}$ ,
${\displaystyle x_{2}-x_{1}+s_{3}=1}$ ,
${\displaystyle x_{2}+s_{4}=2}$ ,
${\displaystyle x_{1},x_{2},s_{1},s_{2},s_{3},s_{4}\geq 0}$

is an LP model in standard form. Note that the usual ${\displaystyle \leq }$  signs have been equivalently replaced by both ${\displaystyle s_{n}}$  variables (s as in slack) and the ${\displaystyle =}$  sign.

How do we convert a given model into a standard model while retaining its sense? This is done as follows:

• If there is a constraint of the type ${\displaystyle 6x_{1}+4x_{2}\leq 24}$  then the right hand side usually represents some limit on the resource (for example the amount of the raw material available) and the left hand side the usage of that resource (i.e. how much raw material is actually used) and so their difference represents the slack or unused amount of the resource. So to convert into an equality we must add a variable representing the slack amount on the left hand side. This variable is known as the slack variable and is obviously also non-negative. If we represent it by ${\displaystyle s_{1}}$  our constraint is converted into the equation ${\displaystyle 6x_{1}+4x_{2}+s_{1}=24}$ . A similar thing is done in case of a constraint of the type ${\displaystyle 6x_{1}+4x_{2}\geq 24}$ . Here the left hand side has a surplus or extra amount then the right hand side and so a non-negative surplus variable say ${\displaystyle s_{2}}$  must be subtracted to get the equation ${\displaystyle 6x_{1}+4x_{2}-s_{2}=24}$ .
• If the given variable ${\displaystyle x_{i}}$  is given to be non-positive then its negative ${\displaystyle y_{i}=-x_{i}}$  is obviously non-negative and can be substituted in the problem. The real problem comes in the case when the variable is allowed to take on any sign. Then it is called an unrestricted variable. This is overcome by using the substitution ${\displaystyle x_{i}=x_{i}^{-}-x_{i}^{+}}$  where ${\displaystyle x_{i}^{-},x_{i}^{+}}$  are both non-negative. Intuitively if the variable ${\displaystyle x_{i}}$  is positive then ${\displaystyle x_{i}^{-}}$  is positive and ${\displaystyle x_{i}^{+}}$  is zero, while if the variable ${\displaystyle x_{i}}$  is negative then ${\displaystyle x_{i}^{-}}$  is zero and ${\displaystyle x_{i}^{+}}$  is positive. If ${\displaystyle x_{i}}$  is zero then obviously ${\displaystyle x_{i}^{-},x_{i}^{+}}$  are both zero.

A point to note is that the objective function in the original LP model and the standard model is the same.

## Algebraic solution of a LPEdit

Let us now try to analyze a LP model algebraically. A solution of the standard LP model will be a solution for the original model (since the slack and surplus variables once removed would make the equations regain their old imbalance) and due to a similar reasoning a solution for the original model will also correspond to a solution for the standard model. Since the objective function is the same for both models so an optimal solution for the standard model will be optimal for the original model as well. Therefore we need to bother only about the standard model.

Now what are the candidates for the optimal solution? They are the solutions of the equality constraints. All we need to do is to find out the solutions and check which of those give the optimal value when put in the objective function. Now usually in the LP model the number of constraints, say m, is outnumbered by the number of variables, say n, and so there are infinitely many solutions to the system of constraints. We can't possibly examine the complete set of infinite solutions. However due to a mathematical result our work is shortened. The result is that if out of the n variables, n-m variables are put to zero, and then if the constraint system can be solved then the solution will correspond to a corner point in the n-space. Such a solution is called a basic solution (Initial Solution). If in addition to being basic it happens to be feasible to the original problem, then it is called a basic feasible solution (often abbreviated as BFS). Since the optimal solution is obtained on a corner point (as we observed graphically) so all we need to do is to examine all the basic feasible solutions (which are at most ${\displaystyle {n \choose m}}$  in number, reflective of the number of ways n-m variables can be chosen among the total n to be zero) and then decide which one gives the maximum value for the objective function.

Let us consider an example:

Consider the following LP model:

Maximize z = ${\displaystyle 2x_{1}+3x_{2}}$

subject to,

${\displaystyle 2x_{1}+x_{2}\leq 4}$ ,

${\displaystyle x_{1}+2x_{2}\leq 5}$ ,

${\displaystyle x_{1},x_{2}\geq 0}$ .

We first convert it into standard form:

Maximize z = ${\displaystyle 2x_{1}+3x_{2}}$

subject to,

${\displaystyle 2x_{1}+x_{2}+s_{1}=4}$ ,

${\displaystyle x_{1}+2x_{2}+s_{2}=5}$ ,

${\displaystyle x_{1},x_{2},s_{1},s_{2}\geq 0}$ .

The constraint system has m=2 constraints and n=4 variables. Thus we need to set 4-2=2 variables equal to zero to get a basic solution. For example putting ${\displaystyle x_{1}=0}$  and ${\displaystyle x_{2}=0}$  we get a solution ${\displaystyle s_{1}=4}$  and ${\displaystyle s_{2}=5}$ . This is also clearly feasible and so is a basic feasible solution. The variables being put to zero, that are ${\displaystyle x_{1},x_{2}}$  are called nonbasic variables and ${\displaystyle s_{1},s_{2}}$  are called basic variables. The objective value (the value that is obtained by putting the solution in the objective function) that these solutions (both basic and non basic) give on substitution in the objective function is zero.

The following table summarizes all the basic solutions to the problem:

Nonbasic variables Basic variables Basic solution Feasible Objective value
${\displaystyle (x_{1},x_{2})}$  ${\displaystyle (s_{1},s_{2})}$  (4,5) Yes 0
${\displaystyle (x_{1},s_{1})}$  ${\displaystyle (x_{2},s_{2})}$  (4,-3) No -
${\displaystyle (x_{1},s_{2})}$  ${\displaystyle (x_{2},s_{1})}$  (2.5,1.5) Yes 7.5
${\displaystyle (x_{2},s_{1})}$  ${\displaystyle (x_{1},s_{2})}$  (2,3) Yes 4
${\displaystyle (x_{2},s_{2})}$  ${\displaystyle (x_{1},s_{1})}$  (5,-6) No -
${\displaystyle (s_{1},s_{2})}$  ${\displaystyle (x_{1},x_{2})}$  (1,2) Yes 8

Note that we have not bothered to calculate the objective value for infeasible solutions. The optimal solution is the one which yields the highest objective value i.e. ${\displaystyle x_{1}=1,x_{2}=2}$ . Hence we have solved the LP model algebraically.

This procedure of solving LP models works for any number of variables but is very difficult to employ when there are a large number of constraints and variables. For example, for m = 10 and n = 20 it is necessary to solve ${\displaystyle {20 \choose 10}=184756}$  sets of equations, which is clearly a staggering task. With the simplex method, you need only solve a few of these sets of equations, concentrating on those which give improving objective values.

## The Simplex methodEdit

The method in a nutshell is this. You start with a basic feasible solution of an LP in standard form (usually the one where all the slack variables are equal to the corresponding right hand sides and all other variables are zero) and replace one basic variable with one which is currently non-basic to get a new basic solution (since n-m variables remain zero). This is done in a fashion which ensures that the new basic solution is feasible and its objective value is at least as much as that of the previous BFS. This is repeated until it is clear that the current BFS can't be improved for a better objective value. In this way the optimal solution is achieved.

It is clear that one factor is crucial to the method: which variable should replace which. The variable which is replaced is called the leaving variable and the variable which replaces it is known as the entering variable. The design of the simplex method is such so that the process of choosing these two variables allows two things to happen. Firstly, the new objective value is an improvement(or at least equals) on the current one and secondly the new solution is feasible.

Let us now explain the method through an example. Consider our old chemical company problem in standard form:

Maximize z = ${\displaystyle 5x_{1}+4x_{2}}$

subject to,

${\displaystyle 6x_{1}+4x_{2}+s_{1}=24}$ ,

${\displaystyle x_{1}+2x_{2}+s_{2}=6}$ ,

${\displaystyle x_{2}-x_{1}+s_{3}=1}$ ,

${\displaystyle x_{2}+s_{4}=2}$ ,

${\displaystyle x_{1},x_{2},s_{1},s_{2},s_{3},s_{4}\geq 0}$ .

Now an immediate BFS is obtained by putting all the ${\displaystyle x_{i}}$  equal to zero. (Clearly the solution thus obtained will be feasible to the original problem as the right hand sides are all non-negative which is precisely our solution.) If we consider our objective function z = ${\displaystyle 5x_{1}+4x_{2}}$  then it is evident that an increase in ${\displaystyle x_{1}}$  or ${\displaystyle x_{2}}$  will increase our objective value. (Note that currently both are zero being non-basic). A unit increase in ${\displaystyle x_{1}}$  will give a 5-fold increase in the objective value while a unit increase in ${\displaystyle x_{2}}$  will give a 4-fold increase. It is logical that we elect to make the entering variable ${\displaystyle x_{1}}$  in the next iteration.

In the tabular form of the simplex method the objective function is usually represented as ${\displaystyle z-5x_{1}-4x_{2}=0}$ . Also the table contains the system of constraints along with the BFS that is obtained. Only the coefficients are written as is usual when handling linear systems.

Basic z ${\displaystyle x_{1}}$  ${\displaystyle x_{2}}$  ${\displaystyle s_{1}}$  ${\displaystyle s_{2}}$  ${\displaystyle s_{3}}$  ${\displaystyle s_{4}}$  BFS
z 1 -5 -4 0 0 0 0 0
${\displaystyle s_{1}}$  0 6 4 1 0 0 0 24
${\displaystyle s_{2}}$  0 1 2 0 1 0 0 6
${\displaystyle s_{3}}$  0 -1 1 0 0 1 0 1
${\displaystyle s_{4}}$  0 0 1 0 0 0 1 2

Now for the next iteration we have to decide the entering and the leaving variables. The entering variable is ${\displaystyle x_{1}}$  as we discussed. In fact, due to our realignment of the objective function, the most negative value in the z-row of the simplex table will always be the entering variable for the next iteration. This is known as the optimality condition. What about the leaving variable? We have to account for the fact that our next basic solution is feasible. So our leaving variable must be chosen with this thought in mind.

To decide the leaving variable we apply what is sometimes called as the feasibility condition. That is as follows: we compute the quotient of the solution coordinates (that are 24, 6, 1 and 2) with the constraint coefficients of the entering variable ${\displaystyle x_{1}}$  (that are 6, 1, -1 and 0). The following ratios are obtained: 24/6 = 4, 6/1 = 6, 1/-1 = -1 and 2/0 = undefined. Ignoring the negative and the undefined ratio we now proceed to select the minimum of the other two ratios which is 4, obtained from dividing 24(the value of ${\displaystyle s_{1}}$ ) by 6. Since the minimum involved the division by ${\displaystyle s_{1}}$ 's current value we take the leaving variable as ${\displaystyle s_{1}}$ .

What is the justification behind this procedure? It is this. The minimum ratios actually represent the intercepts made by the constraints on the ${\displaystyle x_{1}}$  axis. To see this look at the following graph:

Since currently all ${\displaystyle x_{i}}$  are 0 we are considering the BFS corresponding to the origin. Now, in the next iteration according to the simplex method we should get a new BFS i.e move to a new corner point on the graph. We can induce an increase in the value of only one variable at a time by making it an entering variable, and since ${\displaystyle x_{1}}$  is our entering variable our plan is to increase the value of ${\displaystyle x_{1}}$ . From the graph we can see that the value of ${\displaystyle x_{1}}$  must be increased to 4 at the point (4,0), which is the smallest non-negative intercept with the ${\displaystyle x_{1}}$  axis. An increase beyond that point is infeasible. Also at (4,0) the slack variable ${\displaystyle s_{1}}$  assumes a zero value as the first constraint is satisfied as an equality there and so ${\displaystyle s_{1}}$  becomes the leaving variable.

Now the problem is to determine the new solution. Although any procedure of solving a linear system can be applied at this stage, usually Gauss Jordan elimination is applied. It is based on a result in linear algebra that the elementary row transformations on a system [A|b] to [H|c] do not alter the solutions of the system. According to it the columns corresponding to the basic-variables in the table are given the shape of an identity matrix. (Readers familiar with linear algebra will recognize that it means that the matrix formed with the basis variable columns is transformed into reduced row echelon form.) The solution can then be simply read off from the right most solution column (as n-m of the variables are put to zero and the rest including z have coefficient 1 in one constraint each). Since z is also a variable it's row is treated as one among the constraints comprising the linear system.

The entering variable column is called the pivot column and the leaving variable row is called the pivot row. The intersection of the pivot column and the leaving variable column is called the pivot element. In our example the second row (of ${\displaystyle s_{1}}$ ) is the pivot row and the second column(of ${\displaystyle x_{1}}$ ) is the pivot column.

The computations needed to produce the new basic solution are:

• Replace the leaving variable in the 'Basic' column with the entering variable.
• New pivot row = Current pivot row ÷ Pivot element

For other rows, including the z row:

• New row = Current row - (Its pivot column coefficient)×(New pivot row)

In our case the computations proceed as follows:

• Replace ${\displaystyle s_{1}}$  in the 'Basic' column with ${\displaystyle x_{1}}$
• New pivot ${\displaystyle x_{1}}$  row = Current ${\displaystyle s_{1}}$  row ÷ 6 = ${\displaystyle {\begin{pmatrix}0&1&{\frac {2}{3}}&{\frac {1}{6}}&0&0&0&4\end{pmatrix}}}$
• New z row = Current z row - (-5)×New ${\displaystyle x_{1}}$  row = ${\displaystyle {\begin{pmatrix}1&0&{\frac {-2}{3}}&{\frac {5}{6}}&0&0&0&20\end{pmatrix}}}$
• New ${\displaystyle s_{2}}$  row = Current ${\displaystyle s_{2}}$  row - (1)×New ${\displaystyle x_{1}}$  row = ${\displaystyle {\begin{pmatrix}0&0&{\frac {4}{3}}&{\frac {-1}{6}}&1&0&0&2\end{pmatrix}}}$
• New ${\displaystyle s_{3}}$  row = Current ${\displaystyle s_{3}}$  row - (-1)×New ${\displaystyle x_{1}}$  row = ${\displaystyle {\begin{pmatrix}0&0&{\frac {5}{3}}&{\frac {1}{6}}&0&1&0&5\end{pmatrix}}}$
• New ${\displaystyle s_{4}}$  row = Current ${\displaystyle s_{4}}$  row - (0)×New ${\displaystyle x_{1}}$  row = ${\displaystyle {\begin{pmatrix}0&0&1&0&0&0&1&2\end{pmatrix}}}$

Thus our new table is:

Basic z ${\displaystyle x_{1}}$  ${\displaystyle x_{2}}$  ${\displaystyle s_{1}}$  ${\displaystyle s_{2}}$  ${\displaystyle s_{3}}$  ${\displaystyle s_{4}}$  BFS
z 1 0 ${\displaystyle {\frac {-2}{3}}}$  ${\displaystyle {\frac {5}{6}}}$  0 0 0 20
${\displaystyle x_{1}}$  0 1 ${\displaystyle {\frac {2}{3}}}$  ${\displaystyle {\frac {1}{6}}}$  0 0 0 4
${\displaystyle s_{2}}$  0 0 ${\displaystyle {\frac {4}{3}}}$  ${\displaystyle {\frac {-1}{6}}}$  1 0 0 2
${\displaystyle s_{3}}$  0 0 ${\displaystyle {\frac {5}{3}}}$  ${\displaystyle {\frac {1}{6}}}$  0 1 0 5
${\displaystyle s_{4}}$  0 0 1 0 0 0 1 2

The optimality condition now shows that ${\displaystyle x_{2}}$  is the entering variable. The feasiblity condition produces the ratios: 4/(2/3) = 6, 2/(4/3) = 1.5, 5/(5/3) = 3 and 2/1 = 2 of which the minimum is 1.5 produced by dividing the coefficient in the ${\displaystyle s_{2}}$  row (i.e. the row in which the basic variable ${\displaystyle s_{2}}$  has coefficient 1). So ${\displaystyle s_{2}}$  becomes the leaving variable. The Gauss Jordan elimination process is applied again to get the following table:

Basic z ${\displaystyle x_{1}}$  ${\displaystyle x_{2}}$  ${\displaystyle s_{1}}$  ${\displaystyle s_{2}}$  ${\displaystyle s_{3}}$  ${\displaystyle s_{4}}$  BFS
z 1 0 0 ${\displaystyle {\frac {3}{4}}}$  ${\displaystyle {\frac {1}{2}}}$  0 0 21
${\displaystyle x_{1}}$  0 1 0 ${\displaystyle {\frac {1}{4}}}$  ${\displaystyle {\frac {-1}{2}}}$  0 0 3
${\displaystyle x_{2}}$  0 0 1 ${\displaystyle {\frac {-1}{8}}}$  ${\displaystyle {\frac {3}{4}}}$  0 0 ${\displaystyle {\frac {3}{2}}}$
${\displaystyle s_{3}}$  0 0 0 ${\displaystyle {\frac {3}{8}}}$  ${\displaystyle {\frac {-5}{4}}}$  1 0 ${\displaystyle {\frac {5}{2}}}$
${\displaystyle s_{4}}$  0 0 0 ${\displaystyle {\frac {1}{8}}}$  ${\displaystyle {\frac {-3}{4}}}$  0 1 ${\displaystyle {\frac {1}{2}}}$

Based on the optimality condition none of the z-row coefficients associated with the non-basic variables ${\displaystyle s_{1}}$  and ${\displaystyle s_{2}}$  are negative. Hence the last table is optimal. The optimal solution can thus be read off as ${\displaystyle x_{1}=3,x_{2}={\frac {3}{2}},s_{3}={\frac {5}{2}}}$  and ${\displaystyle s_{4}={\frac {1}{2}}}$  and the optimal value as z = 21. Obviously the variables ${\displaystyle s_{1}}$  and ${\displaystyle s_{2}}$  are zero. Our original problem involving only ${\displaystyle x_{1}}$  and ${\displaystyle x_{2}}$  also clearly has the same solution (just disregard the slacks).

We have dealt with a maximization problem. If the minimization case, since min z = max (-z) (if z is a linear function, which it is) so we can either convert the problem into a maximization one or reverse the optimality condition. Instead of selecting the entering variable as the one with the most negative coefficient in the z row we can select the one with the most positive coefficient. The rest of the steps are the same.

Online tool to solve problems via Simplex method

## Exercise Problem:Edit

1. A company involved in the assembly and distribution of printers is concerned with two types – laser and inkjet. Assembly of each laser printer takes two hours, while each inkjet printer takes one hour to assemble, and the staff can provide a total of 40 person-hours of assembly time per day. In addition, warehouse space must be available for the assembly and distribution of the printers, 1 square meter for each laser printer and 3 square meters for each inkjet printer; the company has a total of 45 square meters of storage space available for assembled printers each day. Laser printers can be sold for a profit of €30 per unit and inkjet printers earn a profit of €25 each, but the market in which the company is operating can absorb a maximum of 12 laser printers per day. (There is no such limitation on the market for inkjet printers). Formulate this as a linear programming problem and determine, using the simplex method, the number of each type of printer the company should assemble and distribute in order to maximize daily profit.

Maximize ${\displaystyle z=30x_{1}+25x_{2}}$

subject to,

${\displaystyle 2x_{1}+x_{2}\leq 40}$ ,

${\displaystyle x_{1}+3x_{2}\geq 45}$ ,

${\displaystyle x_{1}\leq 12,x_{1},x_{2}\geq 0}$

Solution using PHPSimplex (see link for solution step by step): the optimal solution value is ${\displaystyle z}$  = 635 with ${\displaystyle x_{1}}$  = 12 and ${\displaystyle x_{2}}$  = 11

## Artificial Starting SolutionEdit

In the previous problem we had a convenient initial basic feasible solution to apply the simplex method which comprised of the slack variables. If the problem however includes surplus variables the solution obtained by putting all the ${\displaystyle x_{i}}$  zero will be basic but not feasible (Why?). In that case instead of arbitrarily searching for an initial basic feasible solution, variables known as artificial variables are used. They play the role of slacks in the first iteration and being external to the problem are disposed of (by being driven to zero) at a later iteration. We will discuss a method known as the two-phase method which is usually used to handle artificial variable problems.

Let us consider the following problem:

Minimize z = ${\displaystyle 4x_{1}+x_{2}}$

subject to,

${\displaystyle 3x_{1}+x_{2}=3}$ ,

${\displaystyle 4x_{1}+3x_{2}\geq 6}$ ,

${\displaystyle x_{1}+2x_{2}\leq 4}$ ,

${\displaystyle x_{1},x_{2}\geq 0}$ .

Now after converting the problem into standard form we have:

Minimize z = ${\displaystyle 4x_{1}+x_{2}}$

subject to,

${\displaystyle 3x_{1}+x_{2}=3}$ ,

${\displaystyle 4x_{1}+3x_{2}-Sx_{3}=6}$ ,

${\displaystyle x_{1}+2x_{2}+sx_{6}=4}$ ,

${\displaystyle x_{1},x_{2},Sx_{3},sx_{6}\geq 0}$ .

Now the first and second constraints do not have any slack variable associated with them. This means that we don't have a convenient initial basic feasible solution available with us. Thus we must introduce artificial variables ${\displaystyle Rx_{4},Rx_{5}}$  in the problem to get an initial BFS.

${\displaystyle 3x_{1}+x_{2}+Rx_{4}=3}$ ,

${\displaystyle 4x_{1}+3x_{2}-Sx_{3}+Rx_{5}=6}$ ,

${\displaystyle x_{1}+2x_{2}+sx_{6}=4}$ .

What exactly is the two-phase method? As the name suggests, it consists of two phases: In the first phase we start with an initial basic feasible solution (obtained using the slack and the artificial variables equal to the right hand side and other variables equal to zero) and work to eliminate the artificial variables. To do this we must minimize the sum of the artificial variables. So we change our objective function to Minimize ${\displaystyle z=Rx_{4}+Rx_{5}}$ . Hence our problem becomes:

Minimize ${\displaystyle z=Rx_{4}+Rx_{5}}$

subject to,

${\displaystyle 3x_{1}+x_{2}+Rx_{4}=3}$ ,

${\displaystyle 4x_{1}+3x_{2}-Sx_{3}+Rx_{5}=6}$ ,

${\displaystyle x_{1}+2x_{2}+sx_{6}=4}$ .

${\displaystyle x_{1},x_{2},Sx_{3},sx_{6},Rx_{4},Rx_{5}\geq 0}$ .

Our initial BFS is of course obtained by putting all the original variables and the surplus variable equal to zero. A problem though crops up at this point. The z row in the simplex method is given by ${\displaystyle z-Rx_{4}-Rx_{5}=0}$  and so the whole system in matrix form is:

${\displaystyle {\begin{pmatrix}1&0&0&0&-1&-1&0\\0&3&1&0&1&0&0\\0&4&3&-1&0&1&0\\0&1&2&0&0&0&1\end{pmatrix}}{\begin{pmatrix}z\\x_{1}\\x_{2}\\Sx_{3}\\Rx_{4}\\Rx_{5}\\sx_{6}\end{pmatrix}}={\begin{pmatrix}0\\3\\6\\4\end{pmatrix}}}$

Clearly if we put the surplus and the original variables to zero the solution to the system will not be the convenient right hand side because the first row has non zero coefficients of ${\displaystyle Rx_{4}}$  and ${\displaystyle Rx_{5}}$  in it. To be more precise write the above system in the following form: ${\displaystyle {\Bigg \{}z{\begin{pmatrix}1\\0\\0\\0\end{pmatrix}}+x_{1}{\begin{pmatrix}0\\3\\4\\1\end{pmatrix}}+x_{2}{\begin{pmatrix}0\\1\\3\\2\end{pmatrix}}+Sx_{3}{\begin{pmatrix}0\\0\\-1\\0\end{pmatrix}}+Rx_{4}{\begin{pmatrix}-1\\1\\0\\0\end{pmatrix}}+Rx_{5}{\begin{pmatrix}-1\\0\\1\\0\end{pmatrix}}+sx_{6}{\begin{pmatrix}0\\0\\0\\1\end{pmatrix}}{\Bigg \}}{\begin{pmatrix}z\\x_{1}\\x_{2}\\Sx_{3}\\Rx_{4}\\Rx_{5}\\sx_{6}\end{pmatrix}}={\begin{pmatrix}0\\3\\6\\4\end{pmatrix}}}$ .

Now putting the variables ${\displaystyle x_{1},x_{2},Sx_{3}}$  to be zero our solution changes to:

${\displaystyle {\Bigg \{}z{\begin{pmatrix}1\\0\\0\\0\end{pmatrix}}+Rx_{4}{\begin{pmatrix}-1\\1\\0\\0\end{pmatrix}}+Rx_{5}{\begin{pmatrix}-1\\0\\1\\0\end{pmatrix}}+sx_{6}{\begin{pmatrix}0\\0\\0\\1\end{pmatrix}}{\Bigg \}}{\begin{pmatrix}z\\Rx_{4}\\Rx_{5}\\sx_{6}\end{pmatrix}}={\begin{pmatrix}0\\3\\6\\4\end{pmatrix}}}$ .

or in the form:

${\displaystyle {\begin{pmatrix}1&-1&-1&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}}{\begin{pmatrix}z\\Rx_{4}\\Rx_{5}\\sx_{6}\end{pmatrix}}={\begin{pmatrix}0\\3\\6\\4\end{pmatrix}}}$

Now this is not in reduced row echelon form and therefore the right hand side does not directly provide the basic feasible solution. In the simplex table the last column should contain the solution. Therefore before we can start the simplex method some modification is necessary in the first row so that the system gets the reduced row echelon form. The obvious required elementary transformation is:

New z row = Old z row (i.e. ${\displaystyle z-Rx_{4}-Rx_{5}=0}$ ) + (1×${\displaystyle Rx_{4}}$  row + 1×${\displaystyle Rx_{5}}$ )

Now the first equation becomes ${\displaystyle z+7x_{1}+4x_{2}-Sx_{3}=9}$  and on putting the requisite variables to zero we find that the right hand side provides a convenient initial BFS.

Basic ${\displaystyle x_{1}}$  ${\displaystyle x_{2}}$  ${\displaystyle Sx_{3}}$  ${\displaystyle Rx_{4}}$  ${\displaystyle Rx_{5}}$  ${\displaystyle sx_{6}}$  BFS
z 7 4 -1 0 0 0 9
${\displaystyle Rx_{4}}$  3 1 0 1 0 0 3
${\displaystyle Rx_{5}}$  4 3 -1 0 1 0 6
${\displaystyle sx_{6}}$  1 2 0 0 0 1 4

Note that we have not bothered to write the column of z in the above table. This is because the nature of the elementary row transformations is such that the z column will always be of the form ${\displaystyle (1,0,\cdots 0)^{T}}$  and so that column can be assumed in every iteration.

The simplex method is now applied to get the solution ${\displaystyle z=0,x_{1}=0.6,x_{2}=1.2,sx_{6}=1}$ . The final table obtained will be:

Basic ${\displaystyle x_{1}}$  ${\displaystyle x_{2}}$  ${\displaystyle Sx_{3}}$  ${\displaystyle Rx_{4}}$  ${\displaystyle Rx_{5}}$  ${\displaystyle sx_{6}}$  BFS
z 0 0 0 -1 -1 0 0
${\displaystyle x_{1}}$  1 0 ${\displaystyle {\frac {1}{5}}}$  ${\displaystyle {\frac {3}{5}}}$  ${\displaystyle {\frac {-1}{5}}}$  0 ${\displaystyle {\frac {3}{5}}}$
${\displaystyle x_{2}}$  0 1 ${\displaystyle {\frac {-3}{5}}}$  ${\displaystyle {\frac {-4}{5}}}$  ${\displaystyle {\frac {3}{5}}}$  0 ${\displaystyle {\frac {6}{5}}}$
${\displaystyle sx_{6}}$  0 0 1 1 -1 1 1

Since the artificial variables are zero so we have reached the end of phase 1. If the value of objective function at the end of stage one is not zero, it means that the artificial variables can not be eliminated, meaning the problem is infeasible.

Phase 2 involves using the basic feasible solution currently available as a starting basic feasible solution for the original problem. The objective function is therefore changed and the z-row is made to reflect that. Since the artificial variables have completed their mission of providing us with an initial BFS they should never be made the entering variables now. In fact, they can be totally eliminated from the problem. So our original problem can now be restated as:

Minimize z = ${\displaystyle 4x_{1}+x_{2}}$

subject to,

${\displaystyle x_{1}+{\frac {1}{5}}Sx_{3}={\frac {3}{5}}}$ ,

${\displaystyle x_{2}-{\frac {3}{5}}Sx_{3}={\frac {6}{5}}}$ ,

${\displaystyle Sx_{3}+sx_{6}=1}$ ,

${\displaystyle x_{1},x_{2},Sx_{3},sx_{6}\geq 0}$ .

The table can now be written as:

Basic ${\displaystyle x_{1}}$  ${\displaystyle x_{2}}$  ${\displaystyle Sx_{3}}$  ${\displaystyle sx_{6}}$  BFS
z -4 -1 0 0 0
${\displaystyle x_{1}}$  1 0 ${\displaystyle {\frac {1}{5}}}$  0 ${\displaystyle {\frac {3}{5}}}$
${\displaystyle x_{2}}$  0 1 ${\displaystyle {\frac {-3}{5}}}$  0 ${\displaystyle {\frac {6}{5}}}$
${\displaystyle sx_{6}}$  0 0 1 1 1

A similar problem which cropped up in the begining of phase 1 is now evident. Since the basic variables ${\displaystyle x_{1}}$  and ${\displaystyle x_{2}}$  have nonzero coefficients in the z-row, the system is not in reduced row echelon form. So we must first apply an elementary row transformation to make these coefficients zero. The evident row transformation is:

New z row = Old z row + (4×${\displaystyle x_{1}}$  row + 1×${\displaystyle x_{2}}$ )

The table thus becomes:

Basic ${\displaystyle x_{1}}$  ${\displaystyle x_{2}}$  ${\displaystyle Sx_{3}}$  ${\displaystyle sx_{6}}$  BFS
z 0 0 ${\displaystyle {\frac {1}{5}}}$  0 ${\displaystyle {\frac {18}{5}}}$
${\displaystyle x_{1}}$  1 0 ${\displaystyle {\frac {1}{5}}}$  0 ${\displaystyle {\frac {3}{5}}}$
${\displaystyle x_{2}}$  0 1 ${\displaystyle {\frac {-3}{5}}}$  0 ${\displaystyle {\frac {6}{5}}}$
${\displaystyle Sx_{3}}$  0 0 1 1 1

Now the simplex method can be applied. The final solution is: ${\displaystyle z=3.4,x_{1}=0.4,x_{2}=1.8,Sx_{3}=1}$ .

All the tables of the problem are listed below: