Formulating a Linear Programming Problem | Edexcel A Level Further Maths: Decision Maths 1 Revision Notes 2017

Introduction to Linear Programming

What is linear programming?

Linear programming, often abbreviated to LP, is a means of solving problems that
- involve working with a set of constraints
- require a quantity to be maximised or minimised
Typical uses of linear programming problems including finance and manufacturing
- For example, a furniture manufacturer may make a mixture of chairs and tables
  - they would want to minimise their costs (of raw materials, manufacturing time)
  - they would want to maximise their profit (chairs may make more profit than tables)
  - but would be restricted (constrained) by things such as build time and the amount of raw materials available

Decision Variables in Linear Programming

What are decision variables?

In a linear programming problem, decision variables are the quantities that can be varied
- $x, y, z$ are usually used as the decision variables
- A furniture manufacturer, it could be that they produce $x$ chairs and $y$ tables (per day/week)
Varying the decision variables will vary the quantity that is to be maximised or minimised
- 12 chairs and 3 tables may lead to a profit of £200, whilst 3 chairs and 12 tables may lead to a profit of £160
The values that the decision variable may take will depend upon the constraints
- A furniture manufacturer can't make endless chairs and tables to gain unlimited profit !

What is the objective function in a linear programming?

The objective function is the quantity in a linear programming problem that requires optimising
- The objective of a furniture manufacturer may be to maximise its profits
- they may also wish to minimise their costs
The objective function is the aim of a linear programming problem
- It is a function of the decision variables
- $P$ is usually used for maximising problems ( $P$ , profit)
- $C$ is usually used for minimising problems ( $C$ , costs)

Constraints & Inequalities in Linear Programming

What are constraints in linear programming?

The constraints in a linear programming problem are the restrictions the problem is contained within
- These restrictions are called constraints
  - Mathematically they are represented by inequalities involving the decision variables
- for a furniture manufacturer constraints could include glue drying time and the amount of paint/varnish available
Decision variables are usually zero or positive as they represent a 'number of things'
- the constraint $x, y \geq 0$ is usually included
- this is called the non-negativity constraint

How do I formulate a linear programming problem?

Formulating a linear programming problems involves
- defining the decision variables
- deducing the constraints as inequalities
- determining the objective function
- writing the problem out formally

STEP 1
Define the decision variables
- Read the question carefully to gather what quantities can be varied
- Typically these will be a 'number of things'

STEP 2
Write each constraint (given in words) as a mathematical inequality
- Where possible, inequalities should be simplified, e.g. $2 x + 4 y \leq 8$ simplifies to $x + 2 y \leq 4$
- Each inequality will be in terms of the decision variables

STEP 3
Determine the objective function
- This will be the quantity that is required to be maximised or minimised
- Typically this would be maximising profit or minimising costs

STEP 4
Formulate the linear programming problem by writing it in a formal manner
- This is of the form
  Maximise
  <objective function>
  subject to
  <constraints>
- Include the non-negativity constraint, e.g. $x, y \geq 0$

Examiner Tip

Whether specified or not, and where appropriate, always include the non-negativity constraint when writing formal linear programming problem
- $x, y \geq 0$

Worked example

A furniture manufacturer makes chairs and tables.

Due to the availability of quality timber, on any particular day the manufacturer cannot make more than a total of 10 chairs and tables.

A chair takes an hour to produce whilst a table takes 2 hours to produce. The manufacturer's factory can produce items for a maximum 18 hours per day.

The varnish on a chair takes 3 hours to dry whilst the varnish on a table takes 2 hours to dry. There are four drying zones within the factory, each able to provide 6 hours of drying time per day.

The manufacturer makes £30 profit on each chair it produces in a day, and £40 profit on each table. The manufacturer wants to maximise its daily profit.

Formulate the above as a linear programming problem, defining the decision variables, stating the objective function and listing the constraints.

STEP 1
Define the decision variables
The 'things' that can be varied here are the number of chairs and the number of tables that are made per day

Let $x$ be the number of chairs made by the furniture manufacturer per day
Let $y$ be the number of tables made by the furniture manufacturer per day

STEP 2
Write each constraint (given in words) as an inequality
The first constraint is the total amount of chairs and tables able to be made in a day

$x + y \leq 10$

The second constraint is the production time - chairs take one hour, tables take two with a maximum 18 hours available per day

$x + 2 y \leq 18$

The third constraint is the varnish drying time - 3 hours for a chair, 2 hours for a table.
The maximum drying time per day available is 4 x 6 = 24 hours

$3 x + 2 y \leq 24$

STEP 3
Determine the objective function
Profit is to be maximised

$P = 30 x + 40 y$

STEP 4
Formulate the linear programming problem by writing it in a formal manner, including the non-negativity constraint

Maximise

$P = 30 x + 40 y$

subject to

$\begin{array}{rcl} x + y & \leq & 10 \\ x + 2 y & \leq & 18 \\ 3 x + 2 y & \leq & 24 \\ x, y & \geq & 0 \end{array}$

Formulating a Linear Programming Problem (Edexcel A Level Further Maths: Decision Maths 1)

Revision Note