Simplex Algorithm

12.3.1 Simplex Algorithm - Slack Variables & Initial Tableau

Introduction

The Simplex algorithm is a systematic method for solving linear programming problems. It is commonly used for maximising or minimising an objective function subject to constraints. This note focuses on the initial steps of the algorithm:

Introducing slack variables to convert inequalities into equations.
Setting up the initial tableau for maximisation or minimisation problems.

Key Concepts

Slack Variables

Slack variables are added to constraints of the form $\leq$ to convert them into equations. For example:

x + y \leq 6 \quad \Rightarrow \quad x + y + s_1 = 6, \quad s_1 \geq 0

where $s_1$ is the slack variable representing unused capacity.

Initial Simplex Tableau

The problem is represented in tabular form, with rows for the constraints and columns for the variables:

Decision variables ( $x_1, x_2, \dots$ )
Slack variables ( $s_1, s_2, \dots$ )
Objective function ( $Z$ ) Each row represents a constraint, and the last row represents the negative of the objective function.

Setting Up the Initial Tableau

Problem Structure

1. Maximisation Problem:

Maximise $Z = c_1x_1 + c_2x_2 + \dots + c_nx_n$

Subject to:

a_{11}x_1 + a_{12}x_2 + \dots + s_1 = b_1

a_{21}x_1 + a_{22}x_2 + \dots + s_2 = b_2

x_1, x_2, \dots, s_1, s_2 \geq 0

2. Initial Tableau:

The tableau has:

Columns for $x_1, x_2, \dots$ , slack variables ( $s_1, s_2, \dots$ ), and $Z$

Rows for each constraint and the objective function.

Worked Examples

infoNote

Example 1: Maximising an Objective Function

Problem

Maximise:

Z = 3x_1 + 2x_2

Subject to:

$x_1 + x_2 \leq 4$
$2x_1 + x_2 \leq 6$
$x_1, x_2 \geq 0$

Step 1: Add Slack Variables

Convert each inequality into an equation:

x_1 + x_2 + s_1 = 4

2x_1 + x_2 + s_2 = 6

where $s_1, s_2 \geq 0$

Step 2: Set Up the Initial Tableau

\begin{array}{c|ccccc|c} \text{Basic Variable} & x_1 & x_2 & s_1 & s_2 & Z & \text{RHS} \\ \hline s_1 & 1 & 1 & 1 & 0 & 0 & 4 \\ s_2 & 2 & 1 & 0 & 1 & 0 & 6 \\ \hline Z & -3 & -2 & 0 & 0 & 1 & 0 \\ \end{array}

Basic Variable: Indicates which variable is currently in the solution (initially slack variables).
RHS: Right-hand side of the equations.
The $Z$ -row represents the negative of the objective function.

Step 3: Interpret the Tableau

The current solution is $x_1 = 0, x_2 = 0, s_1 = 4, s_2 = 6$ , giving $Z = 0$

$Z$ -row negative values $(-3, -2)$ indicate potential for improvement.

infoNote

Example 2: Minimising an Objective Function

Problem

Minimise:

Z = 4x_1 + 3x_2

Subject to:

$x_1 + 2x_2 \leq 8$
$2x_1 + x_2 \leq 10$
$x_1, x_2 \geq 0$

Step 1: Add Slack Variables

x_1 + 2x_2 + s_1 = 8

2x_1 + x_2 + s_2 = 10

where $s_1, s_2 \geq 0$

Step 2: Set Up the Initial Tableau

\begin{array}{c|ccccc|c} \text{Basic Variable} & x_1 & x_2 & s_1 & s_2 & Z & \text{RHS} \\ \hline s_1 & 1 & 2 & 1 & 0 & 0 & 8 \\ s_2 & 2 & 1 & 0 & 1 & 0 & 10 \\ \hline Z & 4 & 3 & 0 & 0 & 1 & 0 \\ \end{array}

Note Summary

infoNote

Common Mistakes

Forgetting slack variables: Omitting slack variables results in incorrect equations.
Incorrect objective function: Failing to convert the objective function to a negative form for the tableau.
Mixing maximisation and minimization methods: Ensure the tableau reflects the correct goal.
Arithmetic errors: Mistakes in setting up coefficients for constraints.
Misinterpreting the tableau: Confusion about the role of the row and RHS values.

infoNote

Key Formulas

Slack Variable for $\leq$ Constraints:

a_1x_1 + a_2x_2 \leq b \quad \Rightarrow \quad a_1x_1 + a_2x_2 + s = b, \quad s \geq 0

Initial Objective Function Row:

Z = c_1x_1 + c_2x_2 \quad \Rightarrow \quad Z - c_1x_1 - c_2x_2 = 0

Initial Tableau: Set up rows for constraints and the $Z$ -row, using slack variables for each $\leq$ constraint.

Simplex Algorithm - Slack Variables & Initial Tableau (Edexcel A-Level Further Mathematics): Revision Notes

12.3.1 Simplex Algorithm - Slack Variables & Initial Tableau

Introduction

Key Concepts

Slack Variables

Initial Simplex Tableau

Setting Up the Initial Tableau

Problem Structure

1. Maximisation Problem:

2. Initial Tableau:

Worked Examples

Example 1: Maximising an Objective Function

Example 2: Minimising an Objective Function

Note Summary

Common Mistakes

Key Formulas

Explore Edexcel A-Level Further Mathematics Model Answers by Topics

Linear Programming (LP) problems

Graphical Solution of LP problems

Explore Edexcel A-Level Further Mathematics Quizzes by Topics

Linear Programming (LP) problems

Graphical Solution of LP problems