Big-M Method

What is the Big-M method?

The Big-M method is an adaption of the simplex algorithm
- It is an alternative to the two-stage simplex method
The Big-M method can be used to
- solve problems involving constraints that contain ≥
- solve minimisation (as well as maximisation) linear programming problems
The Big-M method has the advantage of not requiring two stages
- Each tableau requires just one objective row
The big-M method has the disadvantage that some of the algebra can get awkward to track and follow
$M$ is an arbitrarily large positive number
- This is so expressions such as $1 - M$ are definitely negative and $M - 12$ will definitely be positive
- $M$ is never actually assigned a value, nor would it need to be calculated

How do I rewrite the constraints and objective function for the Big-M method?

STEP 1
Use slack, surplus and artificial variables to convert the constraints of a linear programming problem into equations

STEP 2
Rearrange each constraint containing an artificial variable such that the artificial variable is the subject

STEP 3
Subtract $M A$ from the objective function, where
- $A$ is the sum of the artificial variables ( $a_{1} + a_{2} + . . .$ )
- $M$ is an arbitrarily large, positive number

Worked example

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

Maximise

$P = 3 x + 2 y$

subject to

$\begin{array}{rcl} x - y & \leq & 4 \\ x + 2 y & \leq & 16 \\ 2 x + 3 y & \geq & 18 \\ 2 x - y & \geq & 0 \\ x, y & \geq & 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 \leq 4$ requires a slack variable

$x - y + s_{1} = 4$

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

$x + 2 y + s_{2} = 16$

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

$2 x + 3 y - s_{3} + a_{1} = 18$

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

$2 x - y - s_{4} + a_{2} = 2$

( $s_{1}, s_{2}, s_{3}, s_{4}, a_{1}, a_{2} \geq 0$ )

STEP 2
Rearrange each constraint containing an artificial variable

$\begin{array}{rcl} a_{1} & = & 18 - 2 x - 3 y + s_{3} \\ a_{2} & = & 2 - 2 x + y + s_{4} \end{array}$

STEP 3
Subtract $M A$ from $P$ (find $A$ first)

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

and so

$\begin{array}{rcl} P & = & 3 x + 2 y - A M \\ P & = & 3 x + 2 y - M (20 - 4 x - 2 y + s_{3} + s_{4}) \end{array}$

$P - (4 M + 3) x - (2 M + 2) y + M s_{3} + M s_{4} = - 20 M$

How do I apply the Big-M method?

Once the constraints and objective function and rewritten the initial tableau for the Big-M method can be produced
- (Some of) the entries in the objective line will be algebraic - in terms of $M$
Apply the simplex algorithm as usual to solve the problem
- A tableau is optimal when there are no negative entries in the objective row
  - Big-M makes negative entries easy to spot!
- The row operations for the objective row are a little harder as they involve adding or subtracting algebraic terms that are in terms of $M$
- As previously, use apostrophes to indicate 'old rows' in the row operations column

Examiner Tip

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

Worked example

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 + 2 y + s_{2} & = & 16 \\ 2 x + 3 y - s_{3} + a_{1} & = & 18 \\ 2 x - y - s_{4} + a_{2} & = & 2 \end{array}$

$P - (4 M + 3) x - (2 M + 2) y + M s_{3} + M s_{4} = - 20 M$

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

b.v.	$x$	$y$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	$a_{1}$	$a_{2}$	Value
$s_{1}$	1	-1	1	0	0	0	0	0	4
$s_{2}$	1	2	0	1	0	0	0	0	16
$a_{1}$	2	3	0	0	-1	0	1	0	18
$a_{2}$	2	-1	0	0	0	-1	0	1	2
$P$	$- (4 M + 3)$	$- (2 M + 2)$	0	0	$M$	$M$	0	0	$- 20 M$

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
$- (4 M + 3)$ is the most negative

C1 is the pivot column; the $θ$ -values are

$\begin{array}{rcl} θ_{1} & = & 4 \div 1 = 4 \\ θ_{2} & = & 16 \div 1 = 16 \\ θ_{3} & = & 18 \div 2 = 9 \\ θ_{4} & = & 2 \div 2 = 1 \end{array}$

$θ_{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

b.v.	$x$	$y$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	$a_{1}$	$a_{2}$	Value	Row Op.
$s_{1}$	0	-0.5	1	0	0	0.5	0	-0.5	3	$' R 1' - R 4$
$s_{2}$	0	2.5	0	1	0	0.5	0	-0.5	15	$' R 2' - R 4$
$a_{1}$	0	4	0	0	-1	1	1	-1	16	$' R 3' - 2 R 4$
$x$	1	-0.5	0	0	0	-0.5	0	0.5	1	$0.5' R 4'$
$P$	0	$- (4 M + 3.5)$	0	0	$M$	$- (M + 1.5)$	0	$2 M + 1.5$	$3 - 16 M$	$' R 5' + (4 M + 3) R 4$

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

C2 is the pivot column; the $θ$ -values are

$\begin{array}{rcl} θ_{1} & = & 3 \div (- 0.5) = - 6 \\ θ_{2} & = & 15 \div 2.5 = 6 \\ θ_{3} & = & 16 \div 4 = 4 \\ θ_{4} & = & 1 \div (- 0.5) = - 2 \end{array}$

$θ_{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

b.v.	$x$	$y$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	$a_{1}$	$a_{2}$	Value	Row Op.
$s_{1}$	0	0	1	0	-0.125	0.625	0.125	-0.625	5	'R1' + 0.5R3
$s_{2}$	0	0	0	1	0.625	-0.125	-0.625	0.125	5	'R2' - 2.5R3
$y$	0	1	0	0	-0.25	0.25	0.25	-0.25	4	0.25'R3'
$x$	1	0	0	0	-0.125	-0.375	0.125	0.375	3	'R4' + 0.5R3
$P$	0	0	0	0	-0.875	-0.625	$M + 0.875$	$M + 0.625$	17	$' R 5' + (4 M + 3.5) R 3$

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 $θ$ -values are

$\begin{array}{rcl} θ_{1} & = & 5 \div (- 0.125) = - 40 \\ θ_{2} & = & 5 \div 0.625 = 8 \\ θ_{3} & = & 4 \div (- 0.25) = - 16 \\ θ_{4} & = & 3 \div (- 0.125) = - 24 \end{array}$

$θ_{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

b.v.	$x$	$y$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	$a_{1}$	$a_{2}$	Value	Row Op.
$s_{1}$	0	0	1	0.2	0	0.6	0	-0.6	6	$' R 1' + 0.125 R 2$
$s_{3}$	0	0	0	1.6	1	-0.2	-1	0.2	8	$1.6' R 2'$
$y$	0	1	0	0.4	0	0.2	0	-0.2	6	$' R 3' + 0.25 R 2$
$x$	1	0	0	0.2	0	-0.4	0	0.4	4	$' R 4' + 0.125 R 2$
$P$	0	0	0	1.4	0	-0.8	$M$	$M + 0.8$	24	$' R 5' + 0.875 R 2$

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 $θ$ -values are

$\begin{array}{rcl} θ_{1} & = & 6 \div 0.6 = 10 \\ θ_{2} & = & 8 \div (- 0.2) = - 40 \\ θ_{3} & = & 6 \div 0.2 = 30 \\ θ_{4} & = & 4 \div (- 0.4) = - 10 \end{array}$

$θ_{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

b.v.	$x$	$y$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	$a_{1}$	$a_{2}$	Value	Row Op.
$s_{4}$	0	0	5/3	1/3	0	1	0	-1	10	$\frac{5}{3}' R 1'$
$s_{3}$	0	0	1/3	5/3	1	0	-1	0	10	$' R 2' + 0.2 R 1$
$y$	0	1	-1/3	1/3	0	0	0	0	4	$' R 3' - 0.2 R 1$
$x$	1	0	2/3	1/3	0	0	0	0	8	$' R 4' + 0.4 R 1$
$P$	0	0	4/3	5/3	0	0	$M$	$M$	32	$' R 5' + 0.8 R 1$

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

$P = 3 x + 2 y$ is maximised when $x = 8$ and $y = 4$ at $P = 32$

$s_{3} = 10, s_{4} = 10 s_{1} = s_{2} = a_{1} = a_{2} = 0$

How do I use the Big-M method for minimisation problems?

To use the Big-M method for minimising the objective function
- Introduce a new objective function, $Q$ , say, such that
  $Q = - P$
- After finding $P$ in the required form for tableau entry, write $Q$ in the same way
- Use $Q$ as the objective row in the simplex algorithm
Maximising $Q$ is the same as minimising $P$
Make sure to interpret the final tableau correctly in light of this adaption!
- i.e. $P_{m i n} = - Q_{m a x}$

How do I know when the Big-M method is complete or optimal?

A Big-M method tableau provides an optimal solution when there are no negative entries in the objective row
- Remember that is an (arbitrarily) large positive number
  - For example, $M - 7$ will be positive, $7 - M$ would be negative
Questions may ask for an interpretation of a tableau after any iteration of the Big-M method

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

Revision Note

What is the Big-M method?

How do I rewrite the constraints and objective function for the Big-M method?

How do I apply the Big-M method?

How do I use the Big-M method for minimisation problems?

How do I know when the Big-M method is complete or optimal?

You've read 0 of your 5 free revision notes this week

Sign up now. It’s free!

Join the 100,000+ Students that ❤️ Save My Exams

Algorithms & Graph Theory

Algorithms

General Algorithms

Sorting Algorithms

Bin Packing Algorithms

Graphs

Graph Theory

Eulerian & semi-Eulerian Graphs

Planarity Algorithm

Algorithms on Graphs

Minimum Spanning Trees

Networks & Matrices

Kruskal's Algorithm

Prim's Algorithm

Comparing MST Algorithms

Shortest Path Algorithms

Dijkstra's Algorithm

Floyd's Algorithm

Comparing Dijkstra's & Floyd's Algorithms

The Route Inspection Algorithm

Route Inspection

Route Inspection & Repeated Routes

The Travelling Salesman Problem

The Travelling Salesman Problem

Upper & Lower Bounds for the Travelling Salesman Problem

Solving the Travelling Salesman Problem

Critical Path Analysis

Critical Path Analysis

Activity Networks & Precedence Tables

Dummy Activities

Critical Path Analysis

Gantt (Cascade) Charts

Resource Histograms

Resource Levelling

Scheduling Activities

Linear programming

Linear Programming (LP) problems

Formulating a Linear Programming Problem

Graphical Solution of LP problems

Solving a Linear Programming Problem Graphically

Simplex Algorithm

Simplex Algorithm - Slack Variables & Initial Tableau

Two-stage Simplex Method

Big-M Method

Author: Paul