7.2 Application of Linear Programming
In the business world and various daily situations, decisions are made to minimise costs and maximise profits based on existing constraints. Through linear programming, real-world problems can be translated into mathematical models involving systems of linear inequalities. By graphing these inequalities, a feasible region is formed to locate the optimum values for specific objective functions.
Learning Objectives
- Formulate mathematical models consisting of linear inequalities based on real-world situations and constraints.
- Construct and shade the feasible region \(R\) representing a system of linear inequalities on a Cartesian plane using appropriate scales.
- Identify feasible and infeasible values or solutions from a feasible region.
- Determine the optimum (maximum or minimum) values of an objective function \(k = ax + by\) using vertices of the feasible region or objective function lines.
Linear Programming Graphical Solving Workflow
Follow the step-by-step procedure from interpreting word problems to locating optimum solutions on a feasible region.
Short Explanation
Translate verbal constraints into inequalities, graph them, and optimise the objective function.
1. Identify the existing constraints
Interpret the problem statement and determine the decision variables \(x\) and \(y\).
2. Define a mathematical model
Express all given constraints as a system of linear inequalities, including non-negativity constraints such as \(x \geqslant 0\) and \(y \geqslant 0\).
3. Draw graphs and determine the feasible region, \(R\)
Draw the boundary lines corresponding to the linear equations. Identify and shade the common region that satisfies all constraints simultaneously. Any point inside or on the boundary of this common region is a feasible solution, while any point outside is an infeasible value.
4. Determine the objective function
Write the linear equation representing the quantity to be maximised or minimised, typically in the form \(k = ax + by\).
5. Determine the optimal solution
Maximum or optimum points are located at the vertices (corner points) of the feasible region. Alternatively, select a suitable constant value for \(k\), draw the straight line \(ax + by = k\), and move it parallel across the feasible region to locate the optimal vertex.
Problem Formulation Conventions
"at most" / "does not exceed" \(\rightarrow \leqslant\)
"at least" / "not less than" \(\rightarrow \geqslant\)
"exceeds ... by at least" \(\rightarrow \text{Variable}_1 - \text{Variable}_2 \geqslant \text{value}\)
| Worked Example | Variables | Key Constraints | Objective Function | Optimum Result |
|---|---|---|---|---|
| Flower Bouquets | \(x\) = roses, \(y\) = orchids | \(y \leqslant 2x\), \(y \geqslant \frac{1}{4}x\), \(20y + 30x \geqslant 1200\) | \(k = 35x + 25y\) | Maximum profit RM1 455 at \((18, 33)\) |
| Tables for Computer Lab | \(x\) = table \(P\), \(y\) = table \(Q\) | \(x + 2y \geqslant 30\), \(2x + y \leqslant 60\), \(y \leqslant 2x\) | \(k = 4x + 8y\) | Maximum 300 pupils at \((15, 30)\) |
Steps in Solving Linear Programming Problems Graphically
Identify the existing constraints and decision variables \(x\) and \(y\).
Define a mathematical model as a system of linear inequalities.
Draw graphs and determine the feasible region \(R\).
Determine the objective function \(k = ax + by\).
Determine the optimal solution at the vertices of \(R\).
Objective function
\(k = ax + by\)Maximise or minimise \(k\) subject to the constraints.
Feasible region
\(R = \{(x,y) : \text{all constraints satisfied}\}\)Optimum values occur at the vertices of \(R\).
Try to Answer First
Answer in your mind, then press "Check Answer".
Write a linear inequality for the statement: "The number of table \(Q\) (\(y\)) is at most twice that of table \(P\) (\(x\))".
What is the term for a point or set of values that satisfies every constraint in a linear programming problem?
In a linear programming model, where do the maximum or optimum points of an objective function occur on a graph?
Common Mistakes
- Misinterpreting inequality keywords: Confusing "at least" (\(\geqslant\)) with "at most" (\(\leqslant\)), or "not exceed" (\(\leqslant\)) with "less than" (\(<\)).
- Reversing the order of variables in difference inequalities, such as writing \(x - y \geqslant 10\) instead of \(y - x \geqslant 10\) for "the number of \(y\) exceeds \(x\) by at least 10".
- Incorrect line shading: Shading the wrong side of boundary lines, which leads to an incorrect feasible region.
- Giving fractional answers for discrete real-world items (e.g., number of bouquets, tables, or students) instead of rounding to an appropriate integer within the feasible region.
Concept Misunderstandings
Any point along an objective line \(ax + by = k\) is always feasible.
Only points on the line that lie within or on the boundaries of the feasible region \(R\) are feasible solutions.
The optimum value can be found at any random point inside the shaded region.
The optimum (maximum or minimum) value of a linear objective function always occurs at the boundary vertices of the feasible region.
Non-negativity constraints like \(x \geqslant 0\) and \(y \geqslant 0\) are optional.
Real-world physical quantities (such as number of items, area, or time) cannot be negative, so non-negativity constraints are essential to restrict solutions to the first quadrant.
Summary
- Linear programming applications allow us to model practical scenarios by translating verbal constraints into linear inequalities.
- Graphing these inequalities establishes a feasible region \(R\) containing all valid solutions.
- The optimal solution to an objective function \(k = ax + by\) is determined by testing the corner vertices of this feasible region or by sliding an objective function line across \(R\).
- Maximum or optimum points are located at the vertices (corner points) of the feasible region.
- Non-negativity constraints \(x \geqslant 0\) and \(y \geqslant 0\) are essential for real-world quantities.
Short Activity
Objective: Test your understanding of linear programming constraints, feasible regions and optimum points.
A. Objective Quiz
1 Which inequality represents the constraint "the total surface area of table \(P\) (\(1\text{ m}^2\)) and table \(Q\) (\(2\text{ m}^2\)) is not less than \(30\text{ m}^2\)"?
2 In a graphical linear programming solution, where are the maximum or optimum points that give the optimum value of the objective function located?
B. Fill in the Blanks
3 A value that satisfies all the constraints in a linear programming problem is known as a ________ value.
4 For the objective function \(k = ax + by\), maximum and minimum values occur at the ________ of the feasible region.
C. Matching / Drag and Drop
Drag each term to the correct meaning. On a phone, tap a term first, then tap the matching box.
