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 maximize or minimize.
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 = ax + 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:

ax + by = c

Solving a Linear Programming Problem Graphically Simplified Revision Notes for A-Level Edexcel Further Maths Decision Maths 1

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

500K+ Students Use These Powerful Tools to Master Solving a Linear Programming Problem Graphically For their A-Level Exams.

Other Revision Notes related to Solving a Linear Programming Problem Graphically you should explore