THE SIMPLEX ALGORITHM Decision 1, Cha

Note: it is not possible for these chapter summaries to cover all the possible ways examiners can assess the topic

Setting up the tableau

Q1) Set up the initial tableau for the following linear programme: Slack variables take up spare capacity

e.g. 𝑥 ≤ 7 is rewritten as 𝑥 + 𝑠 = 7
Maximise
𝑃 = 2𝑥 + 4𝑦 + 3𝑧
Basic variables are the ones which are
Subject to non-zero. They can be read off using the
12𝑥 + 4𝑦 + 5𝑧 ≤ 246 b.v. and value columns.
9𝑥 + 6𝑦 + 3𝑧 ≤ 153
5𝑥 + 2𝑦 − 2𝑧 ≤ 171 If 𝑃 = 𝑎𝑥 + 𝑏𝑦 rewrite as
𝑥, 𝑦, 𝑧 ≥ 0 𝑃 − 𝑎𝑥 − 𝑏𝑦 = 0
before entering into the tableau
Use 𝑟, s and 𝑡 for your slack variables.

b. v. 𝑥 𝑦 𝑧 𝑟 𝑠 𝑡 Value
Performing one iteration
The tableau below is the initial tableau for the linear programming problem in 𝑥, 𝑦 and 𝑧. Simplex summary
The objective is to maximise the profit, 𝑃.
• Most negative in 𝑃 → pivot column
b. v. 𝑥 𝑦 𝑧 𝑟 𝑠 𝑡 Value • Smallest +𝜃 → pivot row
• Use row operations to make pivot → 1
𝑟 12 4 5 1 0 0 246 • Switch pivot column heading to b.v. in
pivot row
𝑠 9 6 3 0 1 0 153 • Use row operations to make other
values in pivot column → 0
𝑡 5 2 −2 0 0 1 171 • Check for negatives in 𝑃 row
𝑃 −2 −4 −3 0 0 0 0
𝜽 is value column ÷ pivot column

The algorithm finishes when there are no

Taking the most negative number in the profit row to indicate the pivot column, perform one negative values in 𝑃 row
complete iteration of the simplex method, to obtain a new tableau.
Make your method clear by stating the row operations you use.

b. v. 𝑥 𝑦 𝑧 𝑟 𝑠 𝑡 Value Row operations

You can use the b.v. and value columns

to read off the current state
 Interpreting the final tableau
The final tableau for the linear programming problem is shown below.
Use the b.v. and value columns to
read off the optimal solution
b. v. 𝑥 𝑦 𝑧 𝑟 𝑠 𝑡 Value
1 2
𝑧 2 0 1 − 0 48
3 9
1 1 5
𝑦 1 0 − 0 1.5
2 6 18

𝑡 8 0 0 1 −1 1 264

1 4
𝑃 6 0 0 0 150
3 9

Explain how you can tell this is the final tableau.

State the final values of the objective function and each variable.

One of the constraints is not at capacity. Explain how it can be identified.

Two
-Stage Simplex
– setting up the tableau
Q2) Set up the initial tableau for the following linear programme: Change minimising problems into
maximising problems by setting 𝑄 = −𝑃
Minimise
𝑃 = 2𝑥 − 4𝑦 + 𝑧 You will need to negate any final values of 𝑄
at the end!
Subject to
𝑦 + 2𝑧 ≤ 24
2𝑥 − 𝑦 − 𝑧 ≥ 10 Surplus variables remove spare capacity
𝑥+𝑦+𝑧≥6 Artificial variables are always added on
𝑥, 𝑦, 𝑧 ≥ 0
e.g. 𝑥 ≥ 7 is rewritten as 𝑥 − 𝑠 + 𝑎 = 7

For the first-stage, we add in an 𝐼 row where

𝑰 = −(𝒂𝟏 + 𝒂𝟐 + 𝒂𝟑 )

Convert 𝐼 so it is not in terms of 𝑎

Artificial variables always start as b.v.

b. v. 𝑥 𝑦 𝑧 𝑠1 𝑠2 𝑠3 𝑎1 𝑎2 Value
Two
-Stage Simplex
– formulate the programme from the tableau
Q3) A maximisation linear programming problem in 𝑥, 𝑦 and 𝑧 is to be solved using the two-stage You are expected to be able to formulate
simplex method. linear programmes from tableaux

The initial tableau is shown below.

Formulate the linear programme, stating the objective and listing the constraints as inequalities.

b. v. 𝑥 𝑦 𝑧 𝑠1 𝑠2 𝑠3 𝑎1 Value
𝑠1 1 1 1 1 0 0 0 39
𝑠2 −3 2 2 0 1 0 0 0
𝑎1 1 0 1 0 0 −1 1 28
𝑃 0 −1 −1 0 0 0 0 0
𝐼 −1 0 −1 0 0 1 0 −28
 Two
-Stage Simplex
– performing an iteration, interpreting the tableau after the
By finding the pivot using the 𝑥 column, perform the first iteration of the first stage of the two-stage Same as before…
simplex method. Show the row operations used. • Most negative → pivot column
• Smallest +𝜃 → pivot row
• Use row operations to make pivot → 1
b. v. 𝑥 𝑦 𝑧 𝑠1 𝑠2 𝑠3 𝑎1 Value • Switch pivot column heading to b.v. in
pivot row
𝑠1 1 1 1 1 0 0 0 39 • Use row operations to make other values
in pivot column → 0
𝑠2 −3 2 2 0 1 0 0 0
• Check for negatives in 𝐼 row
𝑎1 1 0 1 0 0 −1 1 28
If 𝐼 = 0 there is a feasible solution.
𝑃 0 −1 −1 0 0 0 0 0
Remove 𝐼 row and 𝑎 columns, then proceed
𝐼 −1 0 −1 0 0 1 0 −28 as normal for the second-stage

If 𝐼 ≠ 0 there is no feasible solution.

b. v. 𝑥 𝑦 𝑧 𝑠1 𝑠2 𝑠3 𝑎1 Value Row operations

Hence, determine whether there is a feasible solution to the linear programme.

 The Big
-M Method
– setting up the tableau
Q4) Set up the initial tableau for solving the following linear Big-M Method
programming problem using the Big-M method
• Rewrite all constraints with slack,
surplus and artificial variables
Maximise
𝑃 = 3𝑥 − 4𝑦 + 2𝑧 • Modify objective function by subtracting
Subject to 𝑀 multiplied by the sum of the artificial
2𝑥 + 𝑦 + 3𝑧 ≤ 20 variables (𝑀 is a very large number)
2𝑥 − 𝑦 + 𝑧 ≥ 15 𝑃 = 𝑎𝑥 + 𝑏𝑦 + 𝑐𝑧 − 𝑀(𝑎1 + 𝑎2 + 𝑎3 )
𝑥 + 𝑦 ≥ 12
• Convert 𝑃 so it is not in terms of 𝑎
𝑥, 𝑦, 𝑧 ≥ 0
Artificial variables always start as b.v.

b. v. 𝑥 𝑦 𝑧 𝑠1 𝑠2 𝑠3 𝑎1 𝑎2 Value
 The Big
-M Method
– performing an iteration
The first iteration is performed, giving the tableau below.
State the column that contains the pivot value for the first iteration.
You must give a reason for your answer.

b. v. 𝑥 𝑦 𝑧 𝑠1 𝑠2 𝑠3 𝑎1 𝑎2 Value
𝑠1 0 2 2 1 1 0 −1 0 5
𝑥 1 −0.5 0.5 0 −0.5 0 0.5 0 7.5
𝑎2 0 1.5 −0.5 0 0.5 −1 −0.5 1 4.5
𝑃 0 2.5 − 1.5𝑀 0.5𝑀 − 0.5 0 −0.5𝑀 − 1.5 𝑀 1.5𝑀 + 1.5 0 −4.5𝑀 + 22.5

Complete the second iteration of the Big-M method for the tableau below, filling in all blank boxes. Indicate which pivot value used.

b. v. 𝑥 𝑦 𝑧 𝑠1 𝑠2 𝑠3 𝑎1 𝑎2 Value
0 1 1 0.5 0.5 0 −0.5 5 2.5
1 0 1 0.25 −0.25 0 0.25 0 8.75
0 0 −2 −0.75 −0.25 −1 0.25 1
𝑃 0 0 0.75𝑀 − 1.25 𝑀 0.75𝑀 + 2.75 0 −0.75𝑀 + 16.25
The Big
-M Method
– interpreting the final tableau
Using the tableau formed after the second iteration, decide whether:
Stop when all of 𝑃 is non-negative.

i) A further iteration is required If any of the basic variables are

ii) The linear programme has been solved, stating the solution if so artificial, there is no feasible solution.
iii) The linear programme is unfeasible, giving a reason for your answer
Otherwise, there is a feasible solution.