Welcome to Linear Programming (D1 Decision Maths)!
Hello there! Linear Programming might sound complicated, but it is one of the most practical and visual topics in Decision Mathematics. Essentially, it’s a powerful tool used in business, manufacturing, and logistics to find the best possible outcome (maximum profit or minimum cost) when you are faced with limited resources.
In this chapter, we will learn how to turn a real-world problem into a set of mathematical inequalities and then solve it using graphical methods. Don't worry if this seems tricky at first; we will break down the steps clearly!
Part 1: Formulating the Problem
The first and most critical step in Linear Programming is translating the situation into mathematical terms. Every LP problem has three main components:
1. The Decision Variables
These are the items you need to decide how much of to produce, buy, or use. Since we are solving this graphically, we will usually have two variables, \(x\) and \(y\).
- Let \(x\) represent the quantity of the first item (e.g., the number of Type A chairs).
- Let \(y\) represent the quantity of the second item (e.g., the number of Type B chairs).
Quick Requirement: Since you cannot produce a negative amount of anything, you must always include the non-negativity constraints: \(x \ge 0\) and \(y \ge 0\).
2. The Objective Function (The Goal)
This is the mathematical expression that represents the quantity you want to maximize (like profit, P) or minimize (like cost, C). It is always a linear function of \(x\) and \(y\).
Example: If Type A chairs yield a profit of £50 and Type B chairs yield £80, the objective function (P, for Profit) would be:
\[ P = 50x + 80y \]
Goal: We want to find the values of \(x\) and \(y\) that make P as large (or small) as possible.
3. The Constraints (The Rules)
These are the limitations imposed by the resources (time, materials, budget, etc.). Constraints are always expressed as linear inequalities.
Example: If making Type A chairs requires 2 hours of labour and Type B requires 4 hours, and you only have 100 hours total labour available:
\[ 2x + 4y \le 100 \]
Understanding Inequality Signs:
- \(\le\) (Less than or equal to): Used for resources that are limited (e.g., maximum capacity, total time available).
- \(\ge\) (Greater than or equal to): Used for minimum requirements (e.g., must produce at least 10 units, minimum nutritional intake).
Key Takeaway (Part 1): Formulation involves defining variables (\(x, y\)), setting the goal (the objective function), and writing the rules (the constraints) as inequalities. Don't forget \(x \ge 0\) and \(y \ge 0\)!
Part 2: Solving Graphically
Once formulated, we use a graph to find the set of points that satisfy all constraints simultaneously. This area is called the Feasible Region.
1. Plotting the Constraints (Drawing the Boundary Lines)
To plot an inequality (e.g., \(2x + 4y \le 100\)), first treat it as an equality (\(2x + 4y = 100\)).
Step-by-Step Drawing:
- Find the intercepts:
- Set \(x=0\) to find the y-intercept. (If \(x=0\), \(4y=100\), so \(y=25\). Point: (0, 25))
- Set \(y=0\) to find the x-intercept. (If \(y=0\), \(2x=100\), so \(x=50\). Point: (50, 0))
- Plot these two points on your axes.
- Draw a straight line connecting them.
Note on Line Types: Since all our inequalities include "or equal to" (\(\le\) or \(\ge\)), we use a solid line. If you had a strict inequality (like \(x + y < 10\)), you would use a dashed line, but this is less common in D1 exams.
2. Identifying the Feasible Region (R)
The feasible region (R) is the area where ALL constraints are met. We use a test point to determine which side of the line is the 'wanted' region.
The Shading Convention (Crucial!)
In Edexcel Decision Maths, the standard convention is to shade the UNWANTED region. This leaves the feasible region (R) clear and unshaded.
How to test and shade:
- Choose a test point, usually \((0, 0)\), unless the line passes through the origin.
- Substitute \((0, 0)\) into the inequality.
- If the test point satisfies the inequality (it’s TRUE), then \((0, 0)\) is in the WANTED region. Shade the side AWAY from \((0, 0)\).
- If the test point does NOT satisfy the inequality (it’s FALSE), then \((0, 0)\) is in the UNWANTED region. Shade the side CONTAINING \((0, 0)\).
- Repeat this for all constraints, including \(x \ge 0\) (shade left of the y-axis) and \(y \ge 0\) (shade below the x-axis).
The resulting clear area is the Feasible Region (R).
3. Finding the Optimal Solution
A key concept in LP is that the optimal solution (max profit or min cost) will always lie on one of the vertices (corner points) of the feasible region R.
We have two main methods to find the optimal point:
Method A: The Objective Function Line (Ruler Method)
This is often the quickest visual method.
Step 1: Determine the Gradient. Look at your objective function, e.g., \(P = 50x + 80y\). Choose an arbitrary constant value for P (call it K) to get the equation of the objective line: \(50x + 80y = K\).
To find the gradient \(m\): \[ 80y = -50x + K \] \[ y = -\frac{50}{80}x + \frac{K}{80} \] \[ m = -\frac{5}{8} \]
Step 2: Draw the Line. Draw this line somewhere within or near the feasible region R. It is often easiest to choose a K value that gives easy intercepts (e.g., if K=400, \(50x+80y=400\), intercepts are (8, 5)).
Step 3: Slide the Line. Using a ruler parallel to this objective line (maintaining the gradient \(-\frac{5}{8}\)), slide it across the feasible region R.
- For Maximisation: Slide the line outwards from the origin until it hits the very last point of the feasible region R.
- For Minimisation: Slide the line inwards towards the origin until it hits the very last point of the feasible region R nearest the origin (often this is just \((0, 0)\) if that is feasible).
Step 4: Find the Coordinates. The coordinates \((x, y)\) of this optimal corner point are the solution.
Method B: Vertex Testing (Corner Point Substitution)
This method is purely algebraic and is useful for confirming the result found graphically.
Step 1: Find all Vertices. Systematically identify the coordinates of every corner point of the feasible region R. If a vertex is formed by the intersection of two constraint lines, you must solve those two simultaneous equations to find the exact coordinates.
Step 2: Test the Objective Function. Substitute the \((x, y)\) coordinates of each vertex into the objective function (P or C).
Step 3: Compare Results. The vertex that yields the highest value is the maximum solution; the vertex that yields the lowest value is the minimum solution.
Example: Finding an Exact Vertex
Suppose the optimal point is the intersection of two lines:
Constraint 1: \(x + 2y = 12\) (1)
Constraint 2: \(3x + y = 16\) (2)
We solve simultaneously:
Multiply (2) by 2: \(6x + 2y = 32\) (3)
Subtract (1) from (3): \((6x - x) + (2y - 2y) = 32 - 12\)
\[ 5x = 20 \implies x = 4 \]
Substitute \(x=4\) into (2): \(3(4) + y = 16 \implies 12 + y = 16 \implies y = 4\)
The vertex is \((4, 4)\).
Key Takeaway (Part 2): Plot boundary lines, shade the unwanted region to find R, and then use either the sliding objective line or vertex testing to find the coordinates that maximise or minimise your objective function.
Part 3: Special Considerations and Final Answers
1. Dealing with Integer Constraints
In many real-world problems (e.g., you can't build 3.4 cars or hire 5.7 people), the variables \(x\) and \(y\) must be integers (whole numbers).
If your optimal solution found in Section 2 is a non-integer point (e.g., \((4.5, 6.2)\)), you cannot simply round up or round down, as this new point might lie outside the feasible region R!
The Integer Solution Method:
- Identify the optimal vertex, \(V_{opt}\) (e.g., \((4.5, 6.2)\)).
- Locate the integer points nearest to \(V_{opt}\) that are still within the feasible region R. (This usually means testing the four integer points surrounding the optimal vertex: (4, 6), (5, 6), (4, 7), (5, 7), etc., and only keeping those within R).
- Test these few feasible integer points by substituting them into the objective function P.
- The integer point that gives the highest (for maximization) or lowest (for minimization) value is your final answer.
Common Mistake: Never assume rounding will work! Always check that the rounded point is inside the feasible region R and test its value.
2. Parallel Optimal Lines
Sometimes, the objective function line has the exact same gradient as one of the constraint boundary lines.
In this case, the optimal solution is not a single point, but any point along that entire edge of the feasible region R.
Example: If the maximum profit occurs on the segment of the line between vertices A and B, you state that the maximum profit occurs at A, B, and any point on the line segment AB.
3. Answering the Question Fully
Your final answer must not only state the maximum/minimum value but also the specific values of the decision variables that achieve it.
Example: Maximise \(P = 50x + 80y\). Optimal vertex found at \((4, 4)\).
Final Answer Format:
- The maximum profit is achieved when \(x = 4\) units of Product A are produced and \(y = 4\) units of Product B are produced.
- The maximum profit is \(P = 50(4) + 80(4) = 200 + 320 = 520\).
Quick Review: Linear Programming Checklist
- Formulation: Define \(x\) and \(y\), write the objective function (P or C), and list all constraints (inequalities).
- Graphing: Draw boundary lines accurately (use intercepts).
- Feasible Region (R): Shade the UNWANTED region. Label the feasible region R.
- Optimal Point: Use the ruler method (objective line gradient) OR test all vertices by solving simultaneous equations.
- Integer Solutions: If required, test surrounding feasible integer points.
- Conclusion: State \(x\), \(y\), and the resulting maximum/minimum value clearly.
Did you know? Linear Programming was developed during World War II by the military to help optimize resource allocation for war efforts, demonstrating its incredible power in logistics!