<?xml version="1.0" encoding="UTF-8"?>
<quiz>
  <question type="description">
    <name>
      <text>7.2.8 (Example of simplex method)</text>
    </name>
    <questiontext format="html">
      <text><![CDATA[<h3>Example</h3>
<p>Find the maximum of the optimisation function \(z = 3x+4y\) subject to the constraints 
\[ 
\begin{align*} 
&amp;x+3y \leq 30 
\\ 
&amp;2x+y \leq 20 
\\ 
&amp; x \geq 0 
\\ 
&amp;y \geq 0 
\end{align*}. 
\]
</p>
<h3>Solution</h3>

<p>We can see here that we have four constraints, so it becomes inefficient to solve this optimisation problem using the graphical method we saw in the previous section. Therefore we use the simplex algorithm.</p>
<ol>
<li>The first step towards using the simplex algorithm is to convert the structural constraints into equalities by adding <em>slack variables</em>. Notice that the lhs of the first two inequalities is less than or equal to the rhs, therefore there are non-negative integers \(s_1,s_2\) that can be added to the lhs which produces the equations
 \[ 
\begin{align*} 
&amp;x+3y +s_1= 30 
\\
&amp;2x+y +s_2 = 20 
\\ 
&amp; x \geq 0 
\\ 
&amp;y \geq 0, 
\end{align*} 
\] 
\(s_1,s_2\) are the <em>slack variables</em>. Notice that they will always be non-negative so it is a sign we made an error if we ever see them be negative.</li>
<li>The next step is to re-write the optimisation equation so that it has the same format as the constraints. That is, write 
\[ 
z = 3x+4y \implies -3x-4y + z = 0. 
\]
</li>
<li>We can now enter the coefficients of each of these equations into a table called the <strong>simplex tableau</strong>. This is done as follows:
<br/>
<img style="display: block; margin-left: auto; margin-right: auto;" src="@@PLUGINFILE@@/Simplex%20tableau.png" alt="diagram showing the simplex tableau" width="328" height="148" />
<br/>
This is the initial simplex tableau, every entry in the bottom row to the left of the vertical line is called an <b>indicator</b>.
</li>
<li>Once we have set up the initial simplex tableau the simplex method consists of checking for optimality and then, if the current solution is not optimal, improving the current solution. We do this improvement by a process called <b>pivoting</b>. We firstly must find the <b>pivot element</b>. The column of the pivot element is the column containing the lowest negative value on the bottom row (for us this is the \(-4\) column). Next the <i>pivot row</i> is the row corresponding to the smallest non negative quotient of the \(b\) (i.e. the final) column over the pivot column. In our case we have 
\[
\frac{30}{3}=10 \qquad \mbox{and} \qquad \frac{20}{1} = 20.
\]
Hence the top row is the pivot row, and the <b>pivot element</b> is \(3\).
</li>
<li>Pivoting means to then set the <i>pivot element</i> equal to \(1\) and all other elements in that column equal to zero. When pivoting is done, and we set the nonbasic variables to zero, we obtain a solution called a basic feasible solution to the linear programming problem. In order to pivot we perform any of the following operations:
<ol type ="a">
<li>Swapping two rows.</li>
<li>Multiplying a row by a nonzero number.</li>
<li>Adding a multiple of of one row to another row.</li>
</ol>
In this case we perform the following steps:
<ol>
<li>Replace row 1 with \(\frac{1}{3}\) times row 1</i>
<li>Replace row 3 with four times row 1 plus row 3.</li>
<li>Replace row 2 with row 2 minus row 1.</li>
</ol>
This process gives us: 
\[
\begin{align*}
\begin{bmatrix}
1 & 3 & 1 & 0 & 0 & 30
\\
2 & 1 & 0 & 1 & 0 & 20
\\
-3 & -4 & 0 & 0 & 1 & 0
\end{bmatrix} &= \begin{bmatrix}
\frac{1}{3} & 1 & \frac{1}{3} & 0 & 0 & 10
\\
2 & 1 & 0 & 1 & 0 & 20
\\
-3 & -4 & 0 & 0 & 1 & 0
\end{bmatrix}
\\
&= \begin{bmatrix}
\frac{1}{3} & 1 & \frac{1}{3} & 0 & 0 & 10
\\
2 & 1 & 0 & 1 & 0 & 20
\\
-\frac{5}{3} & 0 & \frac{4}{3} & 0 & 1 & 40
\end{bmatrix} 
\\
&= \begin{bmatrix}
\frac{1}{3} & 1 & \frac{1}{3} & 0 & 0 & 10
\\
\frac{5}{3} & 0 & -\frac{1}{3} & 1 & 0 & 10
\\
-\frac{5}{3} & 0 & \frac{4}{3} & 0 & 1 & 40
\end{bmatrix}
\end{align*}.
\]
</li>
<li>We can see that there is still a negative indicator \(-\frac{5}{3}\) so we repeat steps 4. and 5. until we have no negative indicators. Repeating the pivot process, the pivot column is column 1 and calculating the ratios we have 
\[
\frac{10}{\frac{1}{3}}=30 \qquad \mbox{and} \qquad \frac{10}{\frac{5}{3}}=6,
\]
So the pivot row is the second row and the pivot element is \(\frac{5}{3}\). So we perform the pivot by performing the operations: 
<ol type="a">
<li>Replace row 3 with row 3 plus row 2.</i>
<li>Replace row 2 with \(\frac{3}{5}\) times row 2.</li>
<li>Replace row 1 with row 1 minus \(\frac{1}{3}\) times row 2.</li>
</ol>
This gives 
\[
\begin{align*}
\begin{bmatrix}
\frac{1}{3} & 1 & \frac{1}{3} & 0 & 0 & 10
\\
\frac{5}{3} & 0 & -\frac{1}{3} & 1 & 0 & 10
\\
-\frac{5}{3} & 0 & \frac{4}{3} & 0 & 1 & 40
\end{bmatrix} &= \begin{bmatrix}
\frac{1}{3} & 1 & \frac{1}{3} & 0 & 0 & 10
\\
\frac{5}{3} & 0 & -\frac{1}{3} & 1 & 0 & 10
\\
0 & 0 & 1 & 1 & 1 & 50
\end{bmatrix}
\\
&= \begin{bmatrix}
\frac{1}{3} & 1 & \frac{1}{3} & 0 & 0 & 10
\\
1 & 0 & -\frac{1}{5} & \frac{3}{5} & 0 & 6
\\
0 & 0 & 1 & 1 & 1 & 50
\end{bmatrix} 
\\
&= \begin{bmatrix}
0 & 1 & \frac{2}{5} & -\frac{1}{5} & 0 & 8
\\
1 & 0 & -\frac{1}{5} & \frac{3}{5} & 0 & 6
\\
0 & 0 & 1 & 1 & 1 & 50
\end{bmatrix} 

\end{align*}
\]
</li>
</ol>
<p>We now notice that there are no negative indicators so we can read off the solution from the final column of the simplex tableau. So the solution is that \(z = 3x+4y\) reaches its maximum value of \(50\) subject to the given constraints when \(x = 6\) and \(y = 8\).</p>
<br/>
<p>Clearly, this is a complicated process to do by hand, however for larger systems, we would input this algorithm in a computer for systems with potentially even greater numbers of variables and constraints. Note that because a linear programming problem in standard form asks us to maximise the optimisation function, an improved solution means a larger value of \(z\). Notice that \(x,y\) are free variables in the sense that we can set them to any values. Finally, notice that the simplex tableau takes the form of an array called a <i>matrix</i> we will discuss this in more detail in the next section. In general matrices allow us to tackle a wider variety of systems of equations.</p>]]></text>
<file name="Simplex tableau.png" path="/" encoding="base64">[encoded data, 36596 characters]</file>
    </questiontext>
    <generalfeedback format="html">
      <text/>
    </generalfeedback>
    <defaultgrade>0</defaultgrade>
    <penalty>0</penalty>
    <hidden>0</hidden>
    <idnumber/>
  </question>
</quiz>
