3.5.1. Initialization

For reference, here is the tableau representing the LP we want to solve:

\[\begin{array}{|r|rrrr|rrr|} \hline & y_1 & y_2 & y_3 & y_4 & x_1 & x_2 & x_3\\ \hline -3 & 1 & & & & -1 & -2 & -2\\ -5 & & 1 & & & -3 & -2 & -1\\ 10 & & & 1 & & 1 & & 3\\ 9 & & & & 1 & 1 & 1 & 1\\ \hline 0 & & & & & 1 & -2 & 1\\ \hline \end{array}\]

The basic solution of this LP \(P\) is not feasible because \(y_1 = -3\) and \(y_2 = -5\). Thus, we need to first convert it into an equivalent LP \(P^{(0)}\) whose basic solution is feasible. The outcome of this step could also be that we decide that the LP has no feasible solution at all.

To find this equivalent LP, we construct our auxiliary LP \(Q\), represented as the following tableau:

\[\begin{array}{|r|rrrr|rrrr|} \hline & y_1 & y_2 & y_3 & y_4 & x_1 & x_2 & x_3 & s \\ \hline -3 & 1 & & & & -1 & -2 & -2 & -1\\ -5 & & 1 & & & -3 & -2 & -1 & -1\\ 10 & & & 1 & & 1 & & 3 & -1\\ 9 & & & & 1 & 1 & 1 & 1 & -1\\ \hline 0 & & & & & & & & -1\\ \hline \end{array}\]

All we did here was to add the non-basic variable \(s\) to the LP, with coefficient \(-1\) in every constraint, and we changed the objective function to \(-s\). This represents the auxiliary LP

\[\begin{gathered} \text{Maximize } {-s}\\ \begin{array}{r@{\ }r@{\ }r@{\ }r>{{}}c<{{}}r>{{}}c<{{}}r>{{}}c<{{}}r>{{}}c<{{}}r>{{}}c<{{}}r} \text{s.t.}\ y_1 & & & & - & x_1 & - & 2x_2 & - & 2x_3 & - & s & = & -3\\ & y_2 & & & - & 3x_1 & - & 2x_2 & - & x_3 & - & s & = & -5\\ & & y_3 & & + & x_1 & & & + & 3x_3 & - & s & = & 10\\ & & & y_4 & + & x_1 & + & x_2 & + & x_3 & - & s & = & 9\\ &&&&&&&&&&& \llap{x_1, x_2, x_3, y_1, y_2, y_3, y_4, s} & \ge & 0\rlap{.} \end{array} \end{gathered}\]

We have \(\min \{b_1, b_2, b_3, b_4\} = b_2 = -5\). Thus, to obtain an equivalent LP \(Q^{(0)}\) whose basic solution is feasible, we perform a pivoting step that puts \(s\) into the basis and makes \(y_2\) leave the basis. First we reorder the columns of the tableau to reflect the new basis:

\[\begin{array}{|r|rrrr|rrrr|} \hline & y_1 & s & y_3 & y_4 & x_1 & x_2 & x_3 & y_2\\ \hline -3 & 1 & -1 & & & -1 & -2 & -2 & \\ -5 & & -1 & & & -3 & -2 & -1 & 1 \\ 10 & & -1 & 1 & & 1 & & 3 & \\ 9 & & -1 & & 1 & 1 & 1 & 1 & \\ \hline 0 & & -1 & & & & & & \\ \hline \end{array}\]

Next we need to ensure that \(s\) has coefficient \(1\) in the second constraint and coefficient \(0\) in all other constraints and in the objective function. This is where the tableau representation comes in handy because it is easy to see what we have to do to achieve this. Here, we need to multiply the second constraint by \(-1\), and then we need to add the result to every other row of the tableau because \(s\)'s coefficient is \(-1\) in every row of the tableau:

\[\begin{array}{|r|rrrr|rrrr|} \hline & y_1 & s & y_3 & y_4 & x_1 & x_2 & x_3 & y_2\\ \hline 2 & 1 & & & & 2 & & -1 & -1 \\ 5 & & 1 & & & 3 & 2 & 1 & -1 \\ 15 & & & 1 & & 4 & 2 & 4 & -1 \\ 14 & & & & 1 & 4 & 3 & 2 & -1 \\ \hline 5 & & & & & 3 & 2 & 1 & -1 \\ \hline \end{array}\]

This tableau represents the LP \(Q^{(0)}\)

\[\begin{gathered} \text{Maximize } 3x_1 + 2x_2 + x_3 - y_2 - 5\\ \begin{array}{r@{\ }r@{\ }r@{\ }r>{{}}c<{{}}r>{{}}c<{{}}r>{{}}c<{{}}r>{{}}c<{{}}r>{{}}c<{{}}r} \text{s.t.}\ y_1 & & & & + & 2x_1 & & & - & x_3 & - & y_2 & = & 2\\ & s & & & + & 3x_1 & + & 2x_2 & + & x_3 & - & y_2 & = & 5\\ & & y_3 & & + & 4x_1 & + & 2x_2 & + & 4x_3 & - & y_2 & = & 15\\ & & & y_4 & + & 4x_1 & + & 3x_2 & + & 2x_3 & - & y_2 & = & 14\\ &&&&&&&&&&& \llap{x_1, x_2, x_3, y_1, y_2, y_3, y_4, s} & \ge & 0\rlap{,} \end{array} \end{gathered}\]

which is equivalent to \(Q\), has the basis \((y_1, s, y_3, y_4)\) (represented by the basic columns of the tableau), and has the BFS \(y_1 = 2\), \(s = 5\), \(y_3 = 15\), \(y_4 = 14\), and \(x_1 = x_2 = x_3 = y_2 = 0\). The objective function value of this BFS is \(-5\) (the negation of the bottom-left entry of the tableau).

Now we pivot to find better solutions of this LP. We pick an arbitrary non-basic variable whose coefficient in the objective function is positive. \(x_1\) is a valid choice because its coefficient is \(3\). \(x_1\) is the non-basic variable that enters the basis in the pivoting operation we are about to perform. To choose the basic variable that leaves the basis, we need to find a constraint in which \(x_1\) has a positive coefficient \(a_{i,x_1}\) and which minimizes the value \(\frac{b_i}{a_{i,x_1}}\).¹ We have

\[\frac{b_1}{a_{1,x_1}} = \frac{2}{2} = 1 \qquad \frac{b_2}{a_{2,x_1}} = \frac{5}{3} \qquad \frac{b_3}{a_{3,x_1}} = \frac{15}{4} \qquad \frac{b_4}{a_{4,x_1}} = \frac{14}{4}.\]

The smallest of these values is \(\frac{b_1}{a_{1,x_1}} = 1\), so the first basic variable, \(y_1\), is the one that needs to leave the basis.

Having identified the pair of variables that need to enter and leave the basis, we now implement the pivoting step in the same way as we did above to obtain our initial LP \(Q^{(0)}\). We start by arranging the columns of the tableau to reflect the new basis:

\[\begin{array}{|r|rrrr|rrrr|} \hline & x_1 & s & y_3 & y_4 & y_1 & x_2 & x_3 & y_2\\ \hline 2 & 2 & & & & 1 & & -1 & -1 \\ 5 & 3 & 1 & & & & 2 & 1 & -1 \\ 15 & 4 & & 1 & & & 2 & 4 & -1 \\ 14 & 4 & & & 1 & & 3 & 2 & -1 \\ \hline 5 & 3 & & & & & 2 & 1 & -1 \\ \hline \end{array}\]

Next we divide the first row of the tableau by \(2\) and subtract the result multiplied by \(3\), \(4\), \(4\), and \(3\) from the remaining rows of the tableau to ensure that \(x_1\) has coefficient \(1\) in the first constraint and coefficient \(0\) everywhere else, including in the objective function:

\[\begin{array}{|r|rrrr|rrrr|} \hline & x_1 & s & y_3 & y_4 & y_1 & x_2 & x_3 & y_2 \\ \hline 1 & 1 & & & & \frac{1}{2} & & -\frac{1}{2} & -\frac{1}{2} \\ 2 & & 1 & & & -\frac{3}{2} & 2 & \frac{5}{2} & \frac{1}{2} \\ 11 & & & 1 & & -2 & 2 & 6 & 1 \\ 10 & & & & 1 & -2 & 3 & 4 & 1 \\ \hline 2 & & & & & -\frac{3}{2} & 2 & \frac{5}{2} & \frac{1}{2} \\ \hline \end{array}\]

Note that the BFS of this LP, \(x_1 = 1\), \(s = 2\), \(y_3 = 11\), \(y_4 = 10\), and \(y_1 = x_2 = x_3 = y_2 = 0\) has objective function value \(-2\), which is an improvement over the previous solution's objective function value, \(-5\).

Next let us try to bring \(x_2\) into the basis because its coefficient in the objective function is \(2\). \(x_2\) has coefficients \(2\), \(2\), and \(3\) in the second, third, and fourth constraints, respectively. The coefficient in the first constraint is \(0\), so only \(s\), \(y_3\), and \(y_4\) are valid candidates for basic variables that can leave the basis. Of the three values \(\frac{2}{2} = 1\), \(\frac{11}{2}\), and \(\frac{10}{3}\), \(1\) is the smallest. Thus, \(s\) is the basic variable that should leave the basis. Again, we start by rearranging the tableau to reflect the new basis:

\[\begin{array}{|r|rrrr|rrrr|} \hline & x_1 & x_2 & y_3 & y_4 & y_1 & s & x_3 & y_2 \\ \hline 1 & 1 & & & & \frac{1}{2} & & -\frac{1}{2} & -\frac{1}{2} \\ 2 & & 2 & & & -\frac{3}{2} & 1 & \frac{5}{2} & \frac{1}{2} \\ 11 & & 2 & 1 & & -2 & & 6 & 1 \\ 10 & & 3 & & 1 & -2 & & 4 & 1 \\ \hline 2 & & 2 & & & -\frac{3}{2} & & \frac{5}{2} & \frac{1}{2} \\ \hline \end{array}\]

To give \(x_2\) coefficient \(1\) in the second constraint and coefficient \(0\) everywhere else, we divide the second constraint by \(2\) and then subtract the result multiplied by \(2\), \(3\), and \(2\) from the third and fourth constraint and from the objective function, respectively:

\[\begin{array}{|r|rrrr|rrrr|} \hline & x_1 & x_2 & y_3 & y_4 & y_1 & s & x_3 & y_2 \\ \hline 1 & 1 & & & & \frac{1}{2} & & -\frac{1}{2} & -\frac{1}{2} \\ 1 & & 1 & & & -\frac{3}{4} & \frac{1}{2} & \frac{5}{4} & \frac{1}{4} \\ 9 & & & 1 & & -\frac{1}{2} & -1 & \frac{7}{2} & \frac{1}{2} \\ 7 & & & & 1 & \frac{1}{4} & -\frac{3}{2} & \frac{1}{4} & \frac{1}{4} \\ \hline 0 & & & & & & -1 & & \\ \hline \end{array}\]

Now all non-basic variables have non-positive coefficients in the objective function. Thus, the BFS of the current LP \(Q'\) is an optimal solution of the auxiliary LP \(Q\)! We are still in the initialization phase of the Simplex Algorithm.

Since this optimal solution has objective function value \(0\) (as stated in the bottom-left corner of the tableau), our original LP \(P\) is feasible. Thus, we can convert \(Q'\) into an LP \(P^{(0)}\) that is equivalent to \(P\) and has a BFS.

In this example, we do not need to remove \(s\) from the basis of \(Q'\) because it is not in the basis of \(Q'\). Thus, we start by removing the column corresponding to \(s\) from the tableau and restoring the original objective function of \(P\):

\[\begin{array}{|r|rrrr|rrr|} \hline & x_1 & x_2 & y_3 & y_4 & y_1 & x_3 & y_2 \\ \hline 1 & 1 & & & & \frac{1}{2} & -\frac{1}{2} & -\frac{1}{2} \\ 1 & & 1 & & & -\frac{3}{4} & \frac{5}{4} & \frac{1}{4} \\ 9 & & & 1 & & -\frac{1}{2} & \frac{7}{2} & \frac{1}{2} \\ 7 & & & & 1 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\ \hline 0 & 1 & -2 & & & & 1 & \\ \hline \end{array}\]

To turn \((x_1, x_2, y_3, y_4)\) into a proper basis, we need to ensure that \(x_1\) and \(x_2\) have coefficient \(0\) in the objective function, which we can achieve by subtracting the first row from the objective function row and adding the second row multiplied by \(2\) to the objective function row:

\[\begin{array}{|r|rrrr|rrr|} \hline & x_1 & x_2 & y_3 & y_4 & y_1 & x_3 & y_2 \\ \hline 1 & 1 & & & & \frac{1}{2} & -\frac{1}{2} & -\frac{1}{2} \\ 1 & & 1 & & & -\frac{3}{4} & \frac{5}{4} & \frac{1}{4} \\ 9 & & & 1 & & -\frac{1}{2} & \frac{7}{2} & \frac{1}{2} \\ 7 & & & & 1 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\ \hline 1 & & & & & -2 & 4 & 1 \\ \hline \end{array}\]

We now have an LP \(P^{(0)}\) that is equivalent to our original LP \(P\) and which has the BFS \(x_1 = 1\), \(x_2 = 1\), \(y_3 = 9\), \(y_4 = 7\), and \(y_1 = x_3 = y_2 = 0\). This is not necessarily an optimal solution yet because \(x_3\) and \(y_2\) both have positive coefficients in the objective function. So let us try to find an optimal solution, by continuing to pivot. We now enter the optimization phase of solving \(P\).