Edexcel IAL - Decision Mathematics 1- 5.1 Formulating Linear Programming Problems- Study notes  - New syllabus

Formulation of Problems as Linear Programs

Linear programming is a mathematical technique used to optimise (maximise or minimise) a quantity subject to a set of linear constraints.

The first and most important step is the correct formulation of the real-world problem as a linear program.

Decision Variables

Decision variables represent the unknown quantities to be determined.

They are usually defined as:

• Let \( \mathrm{x} \) = number of units of product A
• Let \( \mathrm{y} \) = number of units of product B

All decision variables must satisfy non-negativity conditions:

\( \mathrm{x \geq 0,\; y \geq 0} \)

Objective Function

The objective function is the quantity to be maximised or minimised.

It is always a linear function of the decision variables.

Typical examples:

• Maximise profit
• Minimise cost or time

Example objective function:

Maximise \( \mathrm{Z = 5x + 3y} \)

Constraints

Constraints represent the limitations or restrictions of the problem.  

They arise from limited resources such as:

• Time
• Labour
• Materials

Each constraint must be a linear inequality or equation.

Example constraints:

\( \mathrm{2x + y \leq 20} \)

\( \mathrm{x + 3y \leq 30} \)

Assumptions of Linear Programming

When formulating a linear program, the following assumptions are made:

• Proportionality: contributions are directly proportional to variable values
• Additivity: total contribution is the sum of individual contributions
• Divisibility: variables may take fractional values
• Certainty: all coefficients are known and constant

Steps in Formulating a Linear Programming Problem

1. Define the decision variables clearly
2. Write down the objective function
3. Identify all constraints from the problem statement
4. Express constraints as linear inequalities
5. Include non-negativity conditions

Standard Mathematical Form

A linear programming problem is typically written as:

Maximise or Minimise \( \mathrm{Z = ax + by} \)

Subject to:

\( \mathrm{c_1x + d_1y \leq k_1} \)

\( \mathrm{c_2x + d_2y \leq k_2} \)

\( \mathrm{x \geq 0,\; y \geq 0} \)

Key Examination Point

• Always define variables explicitly
• Check that all constraints are linear
• Include non-negativity conditions
• State clearly whether the objective is maximisation or minimisation