Big-M Method (Edexcel A Level Further Maths: Decision 1): Revision Note

The linear programming problem formulated below is to be solved using the Big-M method.

Maximise

$P=3x+2y$

subject to

$\begin{array}{rcl}x-y& \le & 4\\ x+2y& \le & 16\\ 2x+3y& \ge & 18\\ 2x-y& \ge & 2\\ x,y& \ge & 0\end{array}$

Rewrite the constraints and objective function such that the initial tableau for the Big-M method can be produced. (You do not need to produce the initial tableau.)

• STEP 1 $x-y\le 4$ requires a slack variable

$\mathit{x}\mathbf{-}\mathit{y}\mathbf{+}{\mathit{s}}_{\mathbf{1}}\mathbf{=}\mathbf{4}$

$x+2y\le 16$ requires a slack variable

$\mathit{x}\mathbf{+}\mathbf{2}\mathit{y}\mathbf{+}{\mathit{s}}_{\mathbf{2}}\mathbf{=}\mathbf{16}$

$2x+3y\ge 18$ requires a surplus and an artificial variable

$\mathbf{2}\mathit{x}\mathbf{+}\mathbf{3}\mathit{y}\mathbf{-}{\mathit{s}}_{\mathbf{3}}\mathbf{+}{\mathit{a}}_{\mathbf{1}}\mathbf{=}\mathbf{18}$

$2x-y\ge 2$ requires a surplus and an artificial variable

$\mathbf{2}\mathit{x}\mathbf{-}\mathit{y}\mathbf{-}{\mathit{s}}_{\mathbf{4}}\mathbf{+}{\mathit{a}}_{\mathbf{2}}\mathbf{=}\mathbf{2}$

($s_1,s_2,s_3,s_4,a_1,a_2\ge 0$)

• STEP 2 Rearrange each constraint containing an artificial variable

$\begin{array}{rcl}{a}_1& =& 18-2x-3y+s_3\\ a_2& =& 2-2x+y+s_4\end{array}$

• STEP 3 Subtract $MA$ from $P$ (find $A$ first)

$\begin{array}{rcl}A& =& 18-2x-3y+s_3+2-2x+y+s_4\\ A& =& 20-4x-2y+s_3+s_4\end{array}$

and so

$\begin{array}{rcl}P& =& 3x+2y-AM\\ P& =& 3x+2y-M\left(20-4x-2y+s_3+s_4\right)\end{array}$

$\mathit{P}\mathbf{-}\mathbf{(}\mathbf{4}\mathit{M}\mathbf{+}\mathbf{3}\mathbf{)}\mathit{x}\mathbf{-}\mathbf{(}\mathbf{2}\mathit{M}\mathbf{+}\mathbf{2}\mathbf{)}\mathit{y}\mathbf{+}\mathit{M}{\mathit{s}}_{\mathbf{3}}\mathbf{+}\mathit{M}{\mathit{s}}_{\mathbf{4}}\mathbf{=}\mathbf{-}\mathbf{20}\mathit{M}$

• If a question doesn't specify, it is a good idea to write down the values of all variables as the final answer

  • the decision variables, and any slack, surplus and artificial variables

  • only the basic variables take their values from the final tableau

  • non-basic variables always have the value zero 

• Remember to also state the objective function value, stating whether it is a maximum or minimum

A maximisation linear programming problem has been formulated so it is ready to be solved using the Big-M adaption of the simplex algorithm.

$\begin{array}{rcl}x-y+s_1& =& 4\\ x+2y+s_2& =& 16\\ 2x+3y-s_3+a_1& =& 18\\ 2x-y-s_4+a_2& =& 2\end{array}$

$P-\left(4M+3\right)x-\left(2M+2\right)y+M{s}_3+M{s}_4=-20M$

Form the initial tableau and apply the simplex algorithm to find the optimal solution to the problem.

The initial tableau is formed from the rearranged constraints and objective function

There is at least one negative entry in the objective line so the tableau is not yet optimal
Apply an iteration of the simplex algorithm $-\left(4M+3\right)$ is the most negative

C1 is the pivot column; the $\theta$-values are

$\begin{array}{rcl}{\theta }_1& =& 4÷1=4\\ {\theta }_2& =& 16÷1=16\\ {\theta }_3& =& 18÷2=9\\ {\theta }_4& =& 2÷2=1\end{array}$

${\theta }_4$ is the least positive so R4 is the pivot row
The pivot element is in cell R4C1

Pivot is 2

The pivot (R4C1) needs to be changed to 1 through a row operation
Every other entry in C1 should be changed to 0 through row operations

There is a negative entry in the objective row, so apply a second iteration $-\left(4M+3.5\right)$ is the most negative

C2 is the pivot column; the $\theta$-values are

$\begin{array}{rcl}{\theta }_1& =& 4÷\left(-0.5\right)=-8\\ {\theta }_2& =& 15÷2.5=6\\ {\theta }_3& =& 16÷4=4\\ {\theta }_4& =& 1÷\left(-0.5\right)=-2\end{array}$

${\theta }_3$ is the least positive so R3 is the pivot row The pivot element is in cell R3C2

Pivot is 4

Apply the appropriate row operations, starting with the pivot row, R3

There is a negative entry in the objective row, so apply a third iteration -0.875 is the most negative

C5 is the pivot column; the $\theta$-values are

$\begin{array}{rcl}{\theta }_1& =& 5÷\left(-0.125\right)=-40\\ {\theta }_2& =& 5÷0.625=8\\ {\theta }_3& =& 4÷\left(-0.25\right)=-16\\ {\theta }_4& =& 3÷\left(-0.125\right)=-24\end{array}$

${\theta }_2$ is the least positive so R2 is the pivot row
The pivot element is in cell R2C5

Pivot is 0.625

Apply the appropriate row operations, starting with the pivot row, R2

There is a negative entry in the objective row, so apply a fourth iteration -0.8 is the most negative

C6 is the pivot column; the $\theta$-values are

$\begin{array}{rcl}{\theta }_1& =& 6÷0.6=10\\ {\theta }_2& =& 8÷\left(-0.2\right)=-40\\ {\theta }_3& =& 6÷0.2=30\\ {\theta }_4& =& 4÷\left(-0.4\right)=-10\end{array}$

${\theta }_1$ is the least positive so R1 is the pivot row
The pivot element is in cell R1C6

Pivot is 0.6

Apply the appropriate row operations, starting with the pivot row, R1

There are no negative entries in the objective row so the tableau is optimal

$x,y,s_3,s_4$ are the basic variables and so their values are read from the table
$s_1,s_2,a_1,a_2$ are the non-basic variables and so their values are all zero

$\mathit{P}\mathbf{=}\mathbf{3}\mathit{x}\mathbf{+}\mathbf{2}\mathit{y}$ is maximised when $\mathit{x}\mathbf{=}\mathbf{8}$ and $\mathit{y}\mathbf{=}\mathbf{4}$ at $\mathit{P}\mathbf{=}\mathbf{32}$

$\begin{array}{l}{\mathit{s}}_{\mathbf{3}}\mathbf{=}\mathbf{10}\mathbf{,}{\mathit{s}}_{\mathbf{4}}\mathbf{=}\mathbf{10}\\ {\mathit{s}}_{\mathbf{1}}\mathbf{=}{\mathit{s}}_{\mathbf{2}}\mathbf{=}{\mathit{a}}_{\mathbf{1}}\mathbf{=}{\mathit{a}}_{\mathbf{2}}\mathbf{=}\mathbf{0}\end{array}$