3.5.2. Optimization

For reference, here is the tableau we obtained at the end of the initialization phase:

\[\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}\]

It represents an LP that is equivalent to our original LP and whose basic solution is feasible (because all entries in the leftmost column of the first four rows are non-negative). Its BFS is not necessarily optimal because \(x_3\) and \(y_2\) have positive coefficients in the objective function.

First let us try to move \(x_3\) into the basis. \(x_3\) has positive coefficients in the second, third, and fourth constraints. The corresponding upper bounds imposed on \(x_3\) by these constraints are

\[\frac{1}{5/4} = \frac{4}{5} \qquad \frac{9}{7/2} = \frac{18}{7} \qquad \frac{7}{1/4} = 28.\]

The tightest of these upper bounds is \(\frac{4}{5}\). Thus, if we want to bring \(x_3\) into the basis, the second basic variable, \(x_2\), needs to leave the basis. Again, we start by rearranging the tableau:

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

To ensure that \(x_3\) has coefficient \(1\) in the second constraint and coefficient \(0\) everywhere else, we multiply the second constraint with \(\frac{4}{5}\) and then subtract the result from the other constraints and from the objective function, multiplied with \(-\frac{1}{2}\), \(\frac{7}{2}\), \(\frac{1}{4}\), and \(4\), respectively:

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

Next let's move \(y_1\) into the basis because its objective function coefficient is \(\frac{2}{5} > 0\). \(y_1\) has positive coefficients in the first, third, and fourth constraints. The corresponding upper bounds on the value of \(y_1\) imposed by these constraints are

\[\frac{7/5}{1/5} = 7 \qquad \frac{31/5}{8/5} = \frac{31}{8} \qquad \frac{34/5}{2/5} = 17,\]

of which \(\frac{31}{8}\) is the tightest. Thus, \(y_3\) needs to leave the basis:

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

Next we divide the third constraint by \(\frac{8}{5}\) and subtract the result from the other constraints and from the objective function, multiplied with \(\frac{1}{5}\), \(-\frac{3}{5}\), \(\frac{2}{5}\), and \(\frac{2}{5}\), respectively:

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

We still have a non-basic variable with positive coefficient in the objective function left: \(y_2\). \(y_2\) has positive coefficients in the second and fourth constraints. The upper bounds on the value of \(y_2\) imposed by these constraints are

\[\frac{25/8}{1/8} = 25 \qquad \frac{21/4}{1/4} = 21,\]

of which \(21\) is the tighter one. Thus, \(y_4\) needs to leave the basis if \(y_2\) enters the basis:

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

Next we multiply the fourth constraint with \(4\) and subtract the result from the other constraints and from the objective function, multiplied with \(-\frac{3}{8}\), \(\frac{1}{8}\), \(-\frac{1}{8}\), and \(\frac{1}{4}\), respectively:

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

Finally, all non-basic variables have non-positive coefficients in the objective function. Thus, the current basic solution,

\[\begin{aligned} x_1 &= \frac{17}{2} & y_1 &= \frac{13}{2}\\ x_2 &= 0 & y_2 &= 21\\ x_3 &= \frac{1}{2} & y_3 &= 0\\ & & y_4 &= 0, \end{aligned}\]

is an optimal solution with objective function value \(9\). At least, this is what we claim.

Considering our original LP (3.3),

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

we can verify that \((x_1, x_2, x_3) = \bigl(\frac{17}{2}, 0, \frac{1}{2}\bigr)\) is a feasible solution because

\[\begin{aligned} x_1, x_2, x_3 &\ge 0\\ x_1 + 2x_2 + 2x_3 = \frac{17}{2} + 1 = \frac{19}{2} &\ge 3\\
3x_1 + 2x_2 + x_3 = \frac{51}{2} + \frac{1}{2} = 26 &\ge 5\\ x_1 + 3x_3 = \frac{17}{2} + \frac{3}{2} = 10 &\le 10\\ x_1 + x_2 + x_3 = \frac{17}{2} + \frac{1}{2} = 9 &\le 9. \end{aligned}\]

\(y_1, y_2, y_3, y_4\) were merely slack variables we introduced to convert the LP into standard form. The objective function value of this solution is indeed \(x_1 - 2x_2 + x_3 = \frac{17}{2} + \frac{1}{2} = 9\).

At this point, we lack the tools to prove that this is an optimal solution. We develop LP duality in the next chapter and will use it in Section 4.2 to verify that this solution is indeed optimal.