Graphical Solution of LP problems Revision Notes for Edexcel A-Level Further Mathematics

12.2.1 Solving a Linear Programming Problem Graphically

Introduction

Linear programming problems with two variables can be solved graphically by plotting constraints and finding the optimal solution within the feasible region. Two key methods are used:

Objective Line Method: Using a line to represent the objective function and shifting it to find the optimal value.
Vertex Method: Evaluating the objective function at each vertex (corner point) of the feasible region. This note includes solving problems graphically and handling cases requiring integer solutions.

Key Steps in Graphical Solution

Define the Problem
Plot the Constraints
Identify the Feasible Region
Solve Using

1. Define the Problem

Identify decision variables $x$ and $y$ .
Write the objective function to maximise or minimise.
Write all constraints, including non-negativity conditions ( $x, y \geq 0$ ).

2. Plot the Constraints

Convert inequalities into equalities to plot boundary lines.
Determine which side of the line satisfies the inequality by testing a point (e.g., $(0, 0)$ ).

3. Identify the Feasible Region

The feasible region is the area where all constraints overlap. It is bound for most problems.

4. Solve Using:

Objective Line Method: Draw a line for the objective function, shift it parallelly within the feasible region, and identify the optimal point.
Vertex Method: Evaluate the objective function at each vertex of the feasible region.

Worked Examples

infoNote

Example 1: Maximise Profit

Problem

Maximise:

Z = 3x + 5y

Subject to:

$x + y \leq 6$
$2x + y \leq 8$
$x, y \geq 0$

Step 1: Plot the Constraints

$x + y = 6$ : A straight line passing through $(6,0)$ and $(0,6)$
$2x + y = 8$ : A straight line passing through $(4,0)$ and $(0,8)$
$x, y \geq 0$ : Constraints for the first quadrant.

Step 2: Identify the Feasible Region

The feasible region is bounded by the lines and lies in the first quadrant. It is a polygon defined by:

$(0, 0)$
$(4, 0)$
$(2, 4)$
$(0, 6)$

Step 3: Solve Using the Vertex Method

Evaluate $Z = 3x + 5y$ at each vertex:

Z(0, 0) = 3(0) + 5(0) = 0

Z(4, 0) = 3(4) + 5(0) = 12

Z(2, 4) = 3(2) + 5(4) = 6 + 20 = 26

Z(0, 6) = 3(0) + 5(6) = 30

Step 4: Identify the Optimal Solution

The maximum value of $Z = 30$ occurs at $(0, 6)$

infoNote

Example 2: Integer Solution Required

Problem

Maximise:

Z = 4x + 7y

Subject to:

$x + 2y \leq 10$
$3x + y \leq 12$
$x, y \geq 0$

Step 1: Plot the Constraints

$x + 2y = 10$ : Line passes through $(10, 0)$ and $(0, 5)$
$3x + y = 12$ : Line passes through $(4, 0)$ and $(0, 12)$

Step 2: Identify the Feasible Region

The feasible region is bounded by the lines and lies in the first quadrant. Vertices are:

$(0, 0)$
$(0, 5)$
$(2, 4)$
$(4, 0)$

Step 3: Check Integer Solutions

Vertices:

$Z(0, 0) = 4(0) + 7(0) = 0$
$Z(0, 5) = 4(0) + 7(5) = 35$
$Z(2, 4) = 4(2) + 7(4) = 8 + 28 = 36$
$Z(4, 0) = 4(4) + 7(0) = 16$

Step 4: Adjust for Integer Solutions

If only integer solutions are allowed, test lattice points within the feasible region, such as $(3, 3)$ or $(1, 4)$ :

$Z(3, 3) = 4(3) + 7(3) = 12 + 21 = 33$
$Z(1, 4) = 4(1) + 7(4) = 4 + 28 = 32$ Optimal integer solution: $(2, 4)$ with $Z = 36$

Note Summary

infoNote

Common Mistakes

Incorrect plotting: Misplacing lines or identifying the wrong feasible region.
Omitting non-negativity: Forgetting $x, y \geq 0$ , leading to incorrect solutions.
Failing to test all vertices: Missing the optimal point by not evaluating all feasible region vertices.
Overlooking integer constraints: When required, failing to check integer solutions.
Objective line misplacement: Drawing the objective line incorrectly during the objective line method.

infoNote

Key Formulas

Objective Function:

Z = axe + by

where $a$ and $b$ are coefficients.

Vertex Method: Evaluate $Z$ at each vertex of the feasible region.
Feasible Region: The intersection of all constraints, satisfying $x, y \geq 0$
Constraint Boundaries: Convert inequalities to equalities for plotting:

axe + by = c

Graphical Solution of LP problems (Edexcel A-Level Further Mathematics): Revision Notes

12.2.1 Solving a Linear Programming Problem Graphically

Introduction

Key Steps in Graphical Solution

1. Define the Problem

2. Plot the Constraints

3. Identify the Feasible Region

4. Solve Using:

Worked Examples

Example 1: Maximise Profit

Example 2: Integer Solution Required

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

Simplex Algorithm

Explore Edexcel A-Level Further Mathematics Quizzes by Topics

Linear Programming (LP) problems

Graphical Solution of LP problems

Simplex Algorithm

Explore Edexcel A-Level Further Mathematics Flashcards by Topics

Linear Programming (LP) problems

Graphical Solution of LP problems

Simplex Algorithm

Join 100,000+ A-Level students studying Revision Notes with us.