7.1 Linear Programming Model
Linear programming is a mathematical technique used to manage and distribute limited resources—such as money, materials, and manpower—in the most efficient way to maximise profits or minimise costs.
Learning Objectives
- Identify decision variables, objective functions, and constraints from given real-life situations.
- Formulate mathematical models using linear inequalities and equations in two variables.
- Represent linear inequalities graphically using appropriate solid or dotted boundary lines.
- Identify and shade feasible regions that satisfy a system of linear constraints.
- Optimise an objective function \(k = ax + by\) to find maximum or minimum values using the graphical line method or vertex substitution.
Summary of Boundary Lines and Shaded Regions in Linear Programming
Distinguish solid and dotted lines, and determine the correct side to shade based on the sign of coefficient \(b\).
Line Type Rules
Use a solid line for \(\le\) or \(\ge\).
Use a dotted line for \(<\) or \(>\).
Shading Guide
For \(ax + by = c\):
If \(b > 0\), \(\ge\) is above and \(\le\) is below.
If \(b < 0\), the directions reverse.
| Inequality | Boundary line | Shaded region when \(b > 0\) | Shaded region when \(b < 0\) |
|---|---|---|---|
| \(ax + by \ge c\) | Solid | Above the line | Below the line |
| \(ax + by > c\) | Dotted | Above the line | Below the line |
| \(ax + by \le c\) | Solid | Below the line | Above the line |
| \(ax + by < c\) | Dotted | Below the line | Above the line |
Short Explanation
Model real-world problems, graph constraints, and optimise the objective function.
1. Decision Variables
Variables, usually \(x\) and \(y\), that represent the decisions to be made.
2. Objective Function
A linear expression written as \(k = ax + by\) that needs to be maximised or minimised.
3. Constraints
Restrictions or limitations expressed as linear equations or linear inequalities using symbols such as \(=\), \(\le\), \(<\), \(\ge\), and \(>\).
4. Feasible Region
The common area on a Cartesian graph where all given constraints are simultaneously satisfied.
Steps to Formulate a Linear Programming Model
Assign \(x\) and \(y\) to the two quantities being measured.
Translate written conditions into mathematical symbols.
Write the objective function \(k = ax + by\).
List all constraints as linear inequalities or equations.
Objective function in two variables
\(k = ax + by\)Maximise profit or minimise cost within the feasible region.
Try to Answer First
Answer in your mind, then press "Check Answer".
A tailor sews \(x\) shirts and \(y\) trousers. The total number of garments sewn is at most 60, and the number of trousers must be at least twice the number of shirts. Write two linear inequalities representing these conditions.
For the inequality \(4x - 2y \ge 8\), state whether the boundary line is solid or dotted, and whether the shaded region lies above or below the line \(4x - 2y = 8\).
The shaded region of a linear programming problem has vertices at \((10, 10)\), \((10, 50)\), and \((40, 20)\). Find the maximum value of the objective function \(k = 2x + 3y\).
At \((10, 10)\): \(k = 2(10) + 3(10) = 20 + 30 = 50\)
At \((10, 50)\): \(k = 2(10) + 3(50) = 20 + 150 = 170\)
At \((40, 20)\): \(k = 2(40) + 3(20) = 80 + 60 = 140\)
The maximum value of \(k\) is 170 at vertex \((10, 50)\).
Common Mistakes
- Drawing a solid line instead of a dotted line for strict inequalities (\(<\) or \(>\)).
- Assuming that \(\ge\) always means shading above the line, forgetting that if the coefficient of \(y\) is negative (\(b < 0\)), the shaded region actually lies below the line.
- Confusing common English constraints: writing \(x > 50\) for "at least 50" instead of \(x \ge 50\), or writing \(x < 50\) for "at most 50" instead of \(x \le 50\).
- Selecting arbitrary, awkward values of \(k\) when drawing the objective reference line \(ax + by = k\), rather than using the common multiple of \(a\) and \(b\).
Concept Misunderstandings
The optimal point of an objective function can occur in the middle of the shaded region.
In linear programming, the maximum or minimum value always occurs at one of the boundary vertices of the feasible region.
Test points can be chosen directly on the boundary line.
A test point must strictly lie off the boundary line, such as the origin \((0,0)\) when the line does not pass through it.
Summary
- A linear programming model comprises decision variables (\(x, y\)), an objective function (\(k = ax + by\)), and linear constraints.
- Boundary lines are solid for \(\le\) or \(\ge\), and dotted for \(<\) or \(>\).
- The feasible region represents the common solution set satisfying all constraints simultaneously.
- The optimum (maximum or minimum) value of an objective function is found at the vertices of the feasible region.
Short Activity
Objective: Identify constraints, boundary lines, objective functions and key terms in linear programming.
A. Objective Quiz
1 Which inequality represents the statement: "The number of units of car N (\(y\)) produced is not more than three times the number of units of car M (\(x\)) produced"?
2 When graphing the inequality \(x - 2y \ge -4\), why does the shaded region lie below the boundary line \(x - 2y = -4\)?
B. Fill in the Blanks
3 When representing a linear inequality graphically, a ________ line is used if the inequality involves the symbols \(\le\) or \(\ge\).
4 In linear programming, an objective function in two variables is generally written in the form \(k =\) ________.
C. Matching / Drag and Drop
Drag each term to the correct meaning. On a phone, tap a term first, then tap the matching box.
