1. What is Linear Programming?
Dear student, welcome to Unit 4! In this unit, we learn about Linear Programming (sometimes called Linear Optimisation). This is one of the most practical topics in mathematics because it helps us make the best possible decision given limited resources.
Think about a farmer who has limited land, water, and money. The farmer wants to decide how much of each crop to plant to maximize profit. Or think about a factory that wants to minimize cost while meeting production targets. These are real-world problems that linear programming solves!
Have you ever had to make a choice with limited resources? Maybe you had 500 Birr and had to decide what to buy. That is the basic idea behind linear programming!
2. Key Components of a Linear Programming Problem
Every linear programming problem has three main parts. Let’s understand each one carefully.
2.1 Decision Variables
These are the unknowns we want to find. They represent the quantities we need to decide. We usually call them \( x \), \( y \), \( x_1 \), \( x_2 \), etc.
For example, if a farmer decides how many hectares of wheat (\( x \)) and how many hectares of barley (\( y \)) to plant, then \( x \) and \( y \) are the decision variables.
2.2 Objective Function
This is the mathematical expression we want to maximize (like profit) or minimize (like cost). It is always a linear expression in the decision variables.
2.3 Constraints
These are the restrictions or limitations on the decision variables. They come from the limited resources available (land, labour, money, time, etc.). Constraints are written as linear inequalities (or sometimes equations).
2.4 Non-Negativity Conditions
These are always required because negative values of decision variables usually have no real meaning.
So every LP problem has: Decision Variables + Objective Function + Constraints + Non-negativity conditions. Can you identify these four parts in any word problem? Let’s practice!
3. Formulating a Linear Programming Problem from a Word Problem
This is the most important skill — converting a real-life situation into mathematical form. Let’s learn it step by step.
Worked Example 1: A factory produces two types of products: Product A and Product B. Each unit of Product A gives a profit of 30 Birr and each unit of Product B gives a profit of 40 Birr. The factory has a maximum of 240 labour hours available. Product A requires 4 hours of labour per unit and Product B requires 6 hours. The factory can produce at most 40 units of Product A and at most 30 units of Product B. Formulate the LP problem.
Step 1: Identify Decision Variables
Let \( x \) = number of units of Product A produced
Let \( y \) = number of units of Product B produced
Step 2: Write the Objective Function
Profit from A = 30 Birr per unit, Profit from B = 40 Birr per unit
Step 3: Write the Constraints
Labour: \( 4x + 6y \leq 240 \) (total labour cannot exceed 240 hours)
Product A limit: \( x \leq 40 \)
Product B limit: \( y \leq 30 \)
Step 4: Write Non-negativity Conditions
Worked Example 2: A farmer has 100 hectares of land. He wants to plant wheat (\( x \) hectares) and maize (\( y \) hectares). Wheat requires 2 labourers per hectare and maize requires 3 labourers per hectare. He has at most 210 labourers available. The profit per hectare is 5000 Birr for wheat and 4000 Birr for maize. Formulate the LP problem.
Step 1: Decision variables: \( x \) = hectares of wheat, \( y \) = hectares of maize
Step 2: Objective: Maximize \( Z = 5000x + 4000y \)
Step 3: Constraints:
- Land: \( x + y \leq 100 \)
- Labour: \( 2x + 3y \leq 210 \)
Step 4: Non-negativity: \( x \geq 0, \; y \geq 0 \)
- “Maximize profit” → objective function to maximize
- “Minimize cost” → objective function to minimize
- “At least”, “minimum”, “no less than” → ≥ constraint
- “Exactly”, “must be” → = constraint
A bakery makes two types of cakes: chocolate cake and fruit cake. Each chocolate cake requires 200g of flour and 100g of sugar. Each fruit cake requires 150g of flour and 150g of sugar. The bakery has 6000g of flour and 4000g of sugar available. The profit on a chocolate cake is 50 Birr and on a fruit cake is 40 Birr. Formulate the LP problem.
Step 1: Let \( x \) = number of chocolate cakes, \( y \) = number of fruit cakes
Step 2: Maximize \( Z = 50x + 40y \)
Step 3: Constraints:
Step 4: \( x \geq 0, \; y \geq 0 \)
We can simplify by dividing:
4. Graphing Linear Inequalities
Before we can solve an LP problem graphically, we need to know how to graph linear inequalities. This is a crucial skill!
4.1 Steps to Graph a Linear Inequality
- Replace the inequality sign with = to get the boundary line.
- Find two points on the boundary line (set \( x = 0 \) to find y-intercept, set \( y = 0 \) to find x-intercept).
- Draw the boundary line. If the inequality is ≤ or ≥, draw a solid line. If it is < or >, draw a dashed line.
- Choose a test point (usually the origin \( (0,0) \)) and substitute it into the inequality.
- Shade the correct side. If the test point satisfies the inequality, shade that side. If not, shade the other side.
Worked Example 3: Graph the inequality \( 2x + 3y \leq 12 \).
Step 1: Boundary line: \( 2x + 3y = 12 \)
Step 2: Find intercepts:
When \( x = 0 \): \( 3y = 12 \), so \( y = 4 \). Point: \( (0, 4) \)
When \( y = 0 \): \( 2x = 12 \), so \( x = 6 \). Point: \( (6, 0) \)
Step 3: Draw a solid line through \( (0, 4) \) and \( (6, 0) \) (because ≤ means solid).
Step 4: Test point \( (0, 0) \): \( 2(0) + 3(0) = 0 \leq 12 \). TRUE!
Step 5: Shade the side containing \( (0, 0) \) — the region below the line.
Worked Example 4: Graph \( x + y \geq 5 \).
Boundary: \( x + y = 5 \). Intercepts: \( (0, 5) \) and \( (5, 0) \). Solid line.
Test \( (0, 0) \): \( 0 + 0 = 0 \geq 5 \). FALSE!
Shade the side away from the origin — the region above the line.
Worked Example 5: Graph \( x \leq 4 \).
This is a vertical line at \( x = 4 \). Solid line. Test \( (0, 0) \): \( 0 \leq 4 \). TRUE.
Shade the region to the left of the line.
Graph the inequality \( 3x + 2y \leq 18 \) with \( x \geq 0 \) and \( y \geq 0 \). Identify the intercepts of the boundary line.
Boundary: \( 3x + 2y = 18 \)
\( x \)-intercept (\( y = 0 \)): \( 3x = 18 \), so \( x = 6 \). Point: \( (6, 0) \)
\( y \)-intercept (\( x = 0 \)): \( 2y = 18 \), so \( y = 9 \). Point: \( (0, 9) \)
Test \( (0, 0) \): \( 0 \leq 18 \). TRUE — shade below the line.
Combined with \( x \geq 0 \) (right of y-axis) and \( y \geq 0 \) (above x-axis), the feasible region is a triangle with vertices at \( (0, 0) \), \( (6, 0) \), and \( (0, 9) \).
5. Feasible Region
The feasible region (also called the solution region or constraint region) is the area on the graph where ALL constraints are satisfied simultaneously. It is the intersection of all the shaded regions from individual constraints.
- It is always a convex polygon (could be bounded or unbounded)
- Every point inside (and on the boundary of) the feasible region satisfies ALL constraints
- The optimal solution (maximum or minimum) is always found at a corner point (vertex) of the feasible region
Why corner points? Think of it this way: if you are inside the region, you can always move in a direction that improves your objective until you hit a boundary, and eventually a corner!
Worked Example 6: Find the feasible region for:
Constraint 1: \( 2x + y = 8 \). Intercepts: \( (4, 0) \) and \( (0, 8) \). Test \( (0,0) \): TRUE. Shade below.
Constraint 2: \( x + y = 6 \). Intercepts: \( (6, 0) \) and \( (0, 6) \). Test \( (0,0) \): TRUE. Shade below.
Constraint 3 & 4: First quadrant only (\( x \geq 0, y \geq 0 \)).
Feasible region: The intersection of all shaded regions.
Now let’s find the corner points (vertices) of the feasible region:
- Origin: \( (0, 0) \) — intersection of \( x = 0 \) and \( y = 0 \)
- x-intercept of constraint 2: \( (6, 0) \) — where \( x + y = 6 \) meets \( y = 0 \)
- y-intercept of constraint 1: \( (0, 6) \) — where \( 2x + y = 8 \) meets \( x = 0 \)… Wait, \( y = 8 \), but constraint 2 says \( y \leq 6 \). So the binding constraint is \( (0, 6) \).
- Intersection of the two lines: Solve simultaneously:
\[ 2x + y = 8 \] \[ x + y = 6 \]Subtract: \( x = 2 \). Then \( y = 4 \). Point: \( (2, 4) \).
- Intersection of two constraint boundary lines — solve the system of equations
- Intersection of a constraint with the x-axis (\( y = 0 \)) or y-axis (\( x = 0 \))
- Always verify that each corner point satisfies ALL constraints!
Find the corner points of the feasible region defined by:
Corner Point 1: \( (0, 0) \) — origin
Corner Point 2: Where \( 3x + y = 15 \) meets \( y = 0 \): \( (5, 0) \)
Corner Point 3: Where \( x + 2y = 10 \) meets \( x = 0 \): \( (0, 5) \)
Corner Point 4: Intersection of \( x + 2y = 10 \) and \( 3x + y = 15 \):
Point: \( (4, 3) \). Verify: \( 4 + 6 = 10 \leq 10 \) ✓, \( 12 + 3 = 15 \leq 15 \) ✓
6. Solving LP Problems Graphically — The Corner Point Method
Now we put everything together! The Corner Point Method is the standard graphical method for solving LP problems with two variables.
6.1 Steps of the Corner Point Method
- Formulate the LP problem (objective function + constraints)
- Graph all the constraints and identify the feasible region
- Find all corner points (vertices) of the feasible region
- Evaluate the objective function at each corner point
- Identify the optimal solution — the corner point that gives the maximum (or minimum) value of Z
Worked Example 7: Solve the LP problem graphically:
Solution:
We already found the feasible region and corner points in Example 6:
Corner points: \( (0, 0) \), \( (6, 0) \), \( (2, 4) \), \( (0, 6) \)
Now evaluate \( Z = 5x + 3y \) at each corner point:
| Corner Point | \( Z = 5x + 3y \) | Value |
|---|---|---|
| \( (0, 0) \) | \( 5(0) + 3(0) \) | \( 0 \) |
| \( (6, 0) \) | \( 5(6) + 3(0) \) | \( 30 \) |
| \( (2, 4) \) | \( 5(2) + 3(4) \) | \( 10 + 12 = 22 \) |
| \( (0, 6) \) | \( 5(0) + 3(6) \) | \( 18 \) |
This means: To maximize profit, the factory should produce 6 units of product A and 0 units of product B, giving a maximum profit of 30 Birr.
Worked Example 8: Solve graphically:
Solution: From Practice Question 3, corner points are: \( (0, 0) \), \( (5, 0) \), \( (4, 3) \), \( (0, 5) \)
| Corner Point | \( Z = 3x + 5y \) | Value |
|---|---|---|
| \( (0, 0) \) | \( 0 \) | \( 0 \) |
| \( (5, 0) \) | \( 15 + 0 \) | \( 15 \) |
| \( (4, 3) \) | \( 12 + 15 \) | \( 27 \) |
| \( (0, 5) \) | \( 0 + 25 \) | \( 25 \) |
Notice how the optimal solution depends on the coefficients in the objective function. In Example 7, the answer was \( (6, 0) \), but here with different coefficients, the answer is \( (4, 3) \). Always evaluate ALL corner points!
7. Minimization Problems
Sometimes we want to minimize (reduce) something — like cost. The method is the same: find corner points and evaluate, but this time we look for the smallest value of the objective function.
Worked Example 9: A diet problem: A person needs at least 20 units of vitamin A and 30 units of vitamin B daily. Food I provides 2 units of vitamin A and 3 units of vitamin B per kg, and costs 60 Birr per kg. Food II provides 4 units of vitamin A and 2 units of vitamin B per kg, and costs 80 Birr per kg. Minimize the cost.
Formulation:
Let \( x \) = kg of Food I, \( y \) = kg of Food II
Minimize \( C = 60x + 80y \)
Subject to:
Graphing:
Constraint 1: \( 2x + 4y = 20 \), simplify: \( x + 2y = 10 \). Intercepts: \( (10, 0) \) and \( (0, 5) \). Test \( (0,0) \): \( 0 \geq 10 \) FALSE. Shade away from origin.
Constraint 2: \( 3x + 2y = 30 \). Intercepts: \( (10, 0) \) and \( (0, 15) \). Test \( (0,0) \): \( 0 \geq 30 \) FALSE. Shade away from origin.
Corner points:
- Intersection of \( x + 2y = 10 \) and \( 3x + 2y = 30 \): Subtract: \( 2x = 20 \), so \( x = 10 \), \( y = 0 \). Point: \( (10, 0) \)
- Intersection of \( x + 2y = 10 \) and \( x = 0 \): \( (0, 5) \)
- Intersection of \( 3x + 2y = 30 \) and \( y = 0 \): \( (10, 0) \) — same as above
- Intersection of \( 3x + 2y = 30 \) and \( x = 0 \): \( (0, 15) \)
Corner points: \( (10, 0) \), \( (0, 5) \), \( (0, 15) \)
Wait — we need to check: is \( (0, 5) \) valid? Check constraint 2: \( 3(0) + 2(5) = 10 \geq 30 \)? NO! \( 10 \not\geq 30 \). So \( (0, 5) \) is NOT in the feasible region!
The actual corner points are: \( (10, 0) \), \( (0, 15) \), and the intersection of the two lines \( (10, 0) \).
Let me re-examine: the intersection of \( x + 2y = 10 \) and \( 3x + 2y = 30 \) gives \( x = 10, y = 0 \). And we also need where each line meets the axes in the feasible region. The region is unbounded, but the corner points are: \( (10, 0) \) and \( (0, 15) \).
| Corner Point | \( C = 60x + 80y \) | Value |
|---|---|---|
| \( (10, 0) \) | \( 600 + 0 \) | \( 600 \) |
| \( (0, 15) \) | \( 0 + 1200 \) | \( 1200 \) |
A company produces two products P and Q. Each unit of P requires 3 hours of machine time and 2 hours of labour. Each unit of Q requires 2 hours of machine time and 4 hours of labour. The company has at most 120 hours of machine time and 100 hours of labour available. The profit per unit is 40 Birr for P and 30 Birr for Q. Formulate and solve the LP problem graphically.
Formulation:
Let \( x \) = units of P, \( y \) = units of Q
Corner Points:
- \( (0, 0) \)
- \( (40, 0) \): where \( 3x + 2y = 120 \) meets \( y = 0 \)
- \( (0, 25) \): where \( 2x + 4y = 100 \) meets \( x = 0 \)
- Intersection of \( 3x + 2y = 120 \) and \( 2x + 4y = 100 \):
Subtract (ii) from (i): \( 2x = 70 \), so \( x = 35 \). From (ii): \( 35 + 2y = 50 \), \( y = 7.5 \). Point: \( (35, 7.5) \)
Evaluation:
| Corner Point | \( Z = 40x + 30y \) | Value |
|---|---|---|
| \( (0, 0) \) | \( 0 \) | \( 0 \) |
| \( (40, 0) \) | \( 1600 \) | \( 1600 \) |
| \( (35, 7.5) \) | \( 1400 + 225 \) | \( 1625 \) |
| \( (0, 25) \) | \( 0 + 750 \) | \( 750 \) |
Produce 35 units of P and 7.5 units of Q for maximum profit of 1625 Birr.
8. Special Cases in Linear Programming
8.1 Multiple Optimal Solutions
Sometimes the objective function has the same value at two (or more) corner points. In this case, every point on the line segment connecting those corner points is also optimal.
Worked Example 10: Maximize \( Z = 2x + 4y \) subject to \( x + 2y \leq 8 \), \( x \leq 4 \), \( x \geq 0, y \geq 0 \).
Corner points: \( (0, 0) \), \( (4, 0) \), \( (4, 2) \), \( (0, 4) \)
| Corner Point | \( Z = 2x + 4y \) |
|---|---|
| \( (0, 0) \) | \( 0 \) |
| \( (4, 0) \) | \( 8 \) |
| \( (4, 2) \) | \( 8 + 8 = 16 \) |
| \( (0, 4) \) | \( 0 + 16 = 16 \) |
Both \( (4, 2) \) and \( (0, 4) \) give \( Z = 16 \). This means there are multiple optimal solutions. Every point on the line segment from \( (0, 4) \) to \( (4, 2) \) gives \( Z = 16 \).
8.2 Unbounded Feasible Region
If the feasible region extends to infinity, we call it unbounded. For maximization with an unbounded region, the maximum might be infinite (no finite solution). For minimization with positive coefficients, the minimum usually still exists at a corner point.
8.3 Infeasible Problem
If the constraints contradict each other, there is no feasible region. This means the problem has no solution.
Example: \( x \leq 3 \) and \( x \geq 5 \) cannot both be true. No feasible region exists.
8.4 Redundant Constraint
A constraint that does not affect the feasible region is called redundant. It is “extra” — removing it doesn’t change the feasible region or the optimal solution.
Maximize \( Z = 6x + 3y \) subject to:
Identify if any constraint is redundant, find all corner points, and solve.
Checking for redundancy: The feasible region is determined by all constraints. Let’s find corner points first and check.
Potential corner points:
- \( (0, 0) \)
- \( (3, 0) \): where \( x = 3 \) meets \( y = 0 \). Check: \( 2(3) + 0 = 6 \leq 8 \) ✓, \( 3 + 0 = 3 \leq 5 \) ✓
- \( (0, 5) \): where \( x + y = 5 \) meets \( x = 0 \). Check: \( 0 + 5 = 5 \leq 8 \) ✓, \( 0 \leq 3 \) ✓
- Intersection of \( 2x + y = 8 \) and \( x + y = 5 \): Subtract gives \( x = 3 \), \( y = 2 \). Point: \( (3, 2) \). Check: \( 3 \leq 3 \) ✓
- Intersection of \( 2x + y = 8 \) and \( x = 3 \): \( y = 2 \). Same point \( (3, 2) \)!
- Intersection of \( x + y = 5 \) and \( x = 3 \): \( y = 2 \). Same point \( (3, 2) \)!
All three lines pass through \( (3, 2) \)! The constraint \( x \leq 3 \) passes through this point, but does it cut off any part of the region? Let’s check: without \( x \leq 3 \), the corner points would include the intersection of \( 2x + y = 8 \) with \( y = 0 \), which is \( (4, 0) \). But \( (4, 0) \) satisfies \( x + y = 4 \leq 5 \), so it would be a corner point without the constraint \( x \leq 3 \).
So \( x \leq 3 \) is NOT redundant — it removes the point \( (4, 0) \) from the feasible region.
Corner points: \( (0, 0) \), \( (3, 0) \), \( (3, 2) \), \( (0, 5) \)
| Corner Point | \( Z = 6x + 3y \) |
|---|---|
| \( (0, 0) \) | \( 0 \) |
| \( (3, 0) \) | \( 18 \) |
| \( (3, 2) \) | \( 18 + 6 = 24 \) |
| \( (0, 5) \) | \( 0 + 15 = 15 \) |
9. Key Exam Notes — Summary
- Formulation is the first and most important step — read the problem carefully, identify variables, objective, and constraints.
- Look for keywords: “at most” → ≤, “at least” → ≥, “exactly” → =.
- Always include non-negativity conditions: \( x \geq 0, \; y \geq 0 \).
- Graphing inequalities: Find intercepts, draw boundary line, test origin, shade correctly.
- The feasible region is the intersection of ALL constraint regions.
- Corner points are found at intersections of boundary lines and with axes.
- Evaluate the objective function at EVERY corner point to find the optimum.
- For maximization, pick the largest Z value; for minimization, pick the smallest.
- If two corner points give the same optimal Z, there are multiple optimal solutions (the objective line is parallel to a boundary).
- Always verify that each corner point satisfies ALL constraints.
- In exams, show your graph, label corner points, and display the evaluation table clearly.
A furniture maker produces tables and chairs. Each table requires 5 m² of wood and 2 hours of labour. Each chair requires 2 m² of wood and 3 hours of labour. The maker has 100 m² of wood and 60 hours of labour. The profit per table is 300 Birr and per chair is 200 Birr.
(a) Formulate the LP problem.
(b) Find all corner points of the feasible region.
(c) How many tables and chairs should be produced for maximum profit? What is the maximum profit?
(a) Formulation:
Let \( x \) = number of tables, \( y \) = number of chairs
(b) Corner Points:
- \( (0, 0) \)
- \( (20, 0) \): \( 5x = 100 \), \( x = 20 \). Check: \( 40 \leq 60 \) ✓
- \( (0, 20) \): \( 3y = 60 \), \( y = 20 \). Check: \( 40 \leq 100 \) ✓
- Intersection of \( 5x + 2y = 100 \) and \( 2x + 3y = 60 \):
Multiply (i) by 3: \( 15x + 6y = 300 \). Multiply (ii) by 2: \( 4x + 6y = 120 \).
Subtract: \( 11x = 180 \), so \( x = \frac{180}{11} \approx 16.36 \)
Point: \( \left(\frac{180}{11}, \frac{100}{11}\right) \)
(c) Evaluation:
| Corner Point | \( Z = 300x + 200y \) |
|---|---|
| \( (0, 0) \) | \( 0 \) |
| \( (20, 0) \) | \( 6000 \) |
| \(\left(\frac{180}{11}, \frac{100}{11}\right)\) | \( 300 \times \frac{180}{11} + 200 \times \frac{100}{11} = \frac{54000 + 20000}{11} = \frac{74000}{11} \approx 6727.27 \) |
| \( (0, 20) \) | \( 4000 \) |
In practice, the maker would produce 16 tables and 9 chairs (nearest whole numbers) for a profit of \( 300(16) + 200(9) = 4800 + 1800 = 6600 \) Birr.
Quick Revision Notes — Linear Programming
1. Important Definitions
- Linear Programming (LP): A method to find the optimal value (max or min) of a linear objective function subject to linear constraints.
- Decision Variables: The unknown quantities to be determined (e.g., \( x, y \)). They represent what we are deciding.
- Objective Function: The linear expression to be maximized or minimized (e.g., \( Z = 5x + 3y \)).
- Constraints: Linear inequalities or equations that restrict the values of decision variables (e.g., \( 2x + 3y \leq 12 \)).
- Feasible Region: The set of all points that satisfy ALL constraints simultaneously. Always a convex polygon.
- Corner Point (Vertex): A point where two boundary lines of the feasible region intersect.
- Optimal Solution: The feasible point(s) that give the best value of the objective function. Always at a corner point.
- Bounded Region: A feasible region that is closed and finite (surrounded by boundaries).
- Unbounded Region: A feasible region that extends infinitely in at least one direction.
- Redundant Constraint: A constraint that does not affect the feasible region (removing it changes nothing).
2. Key Formulas and Relationships
General LP Problem Structure:
Corner Point Method:
where \( P_1, P_2, \ldots, P_n \) are the corner points of the feasible region.
3. Finding Intercepts (Quick Reference)
| Line Equation | x-intercept (set \( y=0 \)) | y-intercept (set \( x=0 \)) |
|---|---|---|
| \( ax + by = c \) | \(\left(\frac{c}{a}, 0\right)\) | \(\left(0, \frac{c}{b}\right)\) |
| \( x = k \) | \((k, 0)\) | No y-intercept (vertical line) |
| \( y = k \) | No x-intercept (horizontal line) | \((0, k)\) |
4. Inequality Keywords Guide
| Keyword in Problem | Symbol |
|---|---|
| At most, not exceed, maximum, no more than, up to | \( \leq \) |
| At least, minimum, no less than, not below | \( \geq \) |
| Exactly, must equal, required | \( = \) |
| More than, greater than | \( > \) |
| Less than, fewer than | \( < \) |
5. Graphing Rules Summary
- ≤ or ≥: Draw solid boundary line (points on the line are included)
- < or >: Draw dashed boundary line (points on the line are excluded)
- Test point method: Use \( (0, 0) \) as test point (if it is not on a boundary line). If it satisfies the inequality, shade the side containing \( (0, 0) \). Otherwise, shade the opposite side.
- ≥ constraints: Usually shade away from origin
- ≤ constraints: Usually shade toward origin
- Non-negativity: Restricts the feasible region to the first quadrant
6. Step-by-Step Solution Process
7. Common Mistakes to Avoid
- Wrong inequality direction: “At most 100” means ≤ 100, NOT ≥ 100. Read carefully!
- Forgetting non-negativity: Always write \( x \geq 0, \; y \geq 0 \). Without these, the feasible region extends to negative values.
- Wrong intercepts: For \( 2x + 3y = 12 \), x-intercept is 6 (not 12). Divide correctly!
- Shading the wrong side: Always test a point (especially for ≥ constraints where the origin is NOT in the shaded region).
- Missing a corner point: Make sure you find ALL corner points — intersection of every pair of boundary lines, plus intersections with axes.
- Not verifying corner points: A calculated intersection might not satisfy all constraints. Always check!
- Not evaluating all corner points: The optimal might not be at the “obvious” corner. Evaluate Z at EVERY corner point.
- Confusing max and min: Read the problem — are you maximizing profit or minimizing cost?
- Arithmetic errors in solving simultaneous equations: Double-check your algebra when finding intersections.
- Mixing up the axes: x is always horizontal, y is always vertical.
8. Quick Examples
Q: What are the corner points of: \( x + y \leq 4 \), \( x \leq 3 \), \( y \leq 3 \), \( x \geq 0, y \geq 0 \)?
A: \( (0, 0) \), \( (3, 0) \), \( (3, 1) \) [intersection of \( x=3 \) and \( x+y=4 \)], \( (1, 3) \) [intersection of \( y=3 \) and \( x+y=4 \)], \( (0, 3) \)
Q: Maximize \( Z = x + y \) with corner points \( (0,0) \), \( (4,0) \), \( (2,3) \), \( (0,5) \).
A: \( Z(0,0)=0 \), \( Z(4,0)=4 \), \( Z(2,3)=5 \), \( Z(0,5)=5 \). Maximum = 5 at \( (2,3) \) and \( (0,5) \). Multiple optimal solutions!
Q: Is \( (2, 3) \) feasible for \( 2x + y \leq 8 \), \( x + 2y \leq 10 \)?
A: \( 2(2) + 3 = 7 \leq 8 \) ✓. \( 2 + 6 = 8 \leq 10 \) ✓. Yes, it is feasible.
Challenge Exam Questions — Linear Programming
These questions are designed to test your deep understanding. Try each one fully before checking the answer!
Section A: Multiple Choice Questions
The feasible region of an LP problem with two variables is always a:
A) Circle B) Convex polygon C) Parabola D) Triangle only
Answer: B) Convex polygon
The feasible region is always a convex polygon (which could be a triangle, quadrilateral, pentagon, etc., depending on the number of constraints). It is never a circle or parabola because those come from non-linear equations.
In the LP problem “Minimize \( C = 3x + 5y \)”, the optimal solution is found at the corner point where \( C \) is:
A) Largest B) Smallest C) Zero D) Equal to \( x + y \)
Answer: B) Smallest
“Minimize” means we want the smallest possible value. We evaluate C at all corner points and pick the smallest one.
The constraint “at least 15 units of protein” in a diet problem is written as:
A) \( x + y \leq 15 \) B) \( x + y \geq 15 \) C) \( x + y = 15 \) D) \( x + y < 15 \)
Answer: B) \( x + y \geq 15 \)
“At least” means “no less than”, which translates to ≥.
If the objective function line is parallel to a boundary of the feasible region, the LP problem has:
A) No solution B) Unique optimal solution C) Multiple optimal solutions D) Unbounded solution
Answer: C) Multiple optimal solutions
When the objective line is parallel to a boundary edge, the entire edge gives the same optimal value, resulting in infinitely many optimal solutions along that edge.
The point \( (3, 5) \) satisfies \( 2x + y \leq 11 \) because:
A) \( 6 + 5 = 11 \leq 11 \) B) \( 6 + 5 = 11 < 11 \) C) \( 2 + 5 = 7 \leq 11 \) D) \( 2(3) + 5 = 11 \geq 11 \)
Answer: A) \( 6 + 5 = 11 \leq 11 \)
Substituting: \( 2(3) + 5 = 6 + 5 = 11 \). Since \( 11 \leq 11 \) is true, the point satisfies the constraint. Points on the boundary (where equality holds) are included when the symbol is ≤.
Section B: Fill in the Blanks
In a maximization problem, the optimal value of Z is the ________ value among all corner point evaluations.
Answer: Largest (or Maximum)
The x-intercept of the line \( 4x + 3y = 24 \) is ________
Answer: \( (6, 0) \)
A constraint that does not affect the feasible region is called a ________ constraint.
Answer: Redundant
In the inequality \( 3x + 5y \geq 15 \), the test point \( (0, 0) \) gives \( 0 \geq 15 \) which is ________, so we shade the side ________ the origin.
Answer: False; away from
Since the origin does NOT satisfy the inequality, the correct shaded region is on the opposite side of the boundary line from the origin.
The non-negativity conditions in an LP problem with variables \( x \) and \( y \) are written as ________ and ________
Answer: \( x \geq 0 \) and \( y \geq 0 \)
Section C: Short Answer Questions
Explain why decision variables in LP must be non-negative.
Decision variables represent real-world quantities like number of products, hectares of land, hours of labour, kg of food, etc. These quantities cannot be negative in reality — you cannot produce −5 tables or use −10 hectares of land. Therefore, we must always include \( x \geq 0 \) and \( y \geq 0 \) as constraints.
Is the point \( (4, 1) \) in the feasible region defined by \( x + y \leq 4 \), \( 2x + y \leq 9 \), \( x \geq 0, y \geq 0 \)? Show your work.
Check each constraint:
Since the point fails the first constraint (\( 5 \not\leq 4 \)), it is NOT in the feasible region.
What does it mean if an LP problem has no feasible region? Give an example.
If an LP problem has no feasible region, it means the constraints are contradictory — no point satisfies ALL constraints simultaneously. The problem is called infeasible.
Example: Maximize \( Z = x + y \) subject to \( x \leq 3 \), \( x \geq 5 \), \( x \geq 0, y \geq 0 \). Since \( x \) cannot be both ≤ 3 and ≥ 5, no feasible region exists.
Find the intersection point of the lines \( 3x + 2y = 18 \) and \( x – y = 1 \).
From the second equation: \( x = y + 1 \).
Substitute into the first:
Intersection point: \( (4, 3) \)
Section D: Step-by-Step Calculation Questions
A student wants to maximize study effectiveness. She can study Mathematics (\( x \) hours) and Physics (\( y \) hours). She has at most 10 hours total. Mathematics problems require 2 hours per unit of effectiveness and Physics requires 1 hour per unit. She needs at least 3 units of effectiveness in each subject. Her total effectiveness is \( Z = x + 2y \).
(a) Formulate the LP problem.
(b) Find the feasible region and its corner points.
(c) Find the optimal solution.
(a) Formulation:
(b) Corner Points:
- Intersection of \( x = 3 \) and \( y = 3 \): \( (3, 3) \). Check: \( 6 \leq 10 \) ✓
- Intersection of \( x = 3 \) and \( x + y = 10 \): \( y = 7 \). Point: \( (3, 7) \)
- Intersection of \( y = 3 \) and \( x + y = 10 \): \( x = 7 \). Point: \( (7, 3) \)
Corner points: \( (3, 3) \), \( (3, 7) \), \( (7, 3) \)
(c) Evaluation:
| Corner Point | \( Z = x + 2y \) |
|---|---|
| \( (3, 3) \) | \( 3 + 6 = 9 \) |
| \( (3, 7) \) | \( 3 + 14 = 17 \) |
| \( (7, 3) \) | \( 7 + 6 = 13 \) |
She should study 3 hours of Math and 7 hours of Physics.
Minimize \( C = 4x + 6y \) subject to:
Corner Points:
- Intersection of \( x + 2y = 8 \) and \( 3x + 2y = 12 \): Subtract: \( 2x = 4 \), \( x = 2 \), \( y = 3 \). Point: \( (2, 3) \). Check both: ✓
- Intersection of \( x + 2y = 8 \) and \( x = 0 \): \( (0, 4) \). Check: \( 0 + 8 = 8 \geq 12 \)? NO! Not feasible for second constraint.
- Intersection of \( 3x + 2y = 12 \) and \( x = 0 \): \( (0, 6) \). Check: \( 0 + 12 = 12 \geq 8 \) ✓
- Intersection of \( 3x + 2y = 12 \) and \( y = 0 \): \( (4, 0) \). Check: \( 4 + 0 = 4 \geq 8 \)? NO! Not feasible.
- Intersection of \( x + 2y = 8 \) and \( y = 0 \): \( (8, 0) \). Check: \( 24 + 0 = 24 \geq 12 \) ✓
Actual corner points: \( (2, 3) \), \( (0, 6) \), \( (8, 0) \)
| Corner Point | \( C = 4x + 6y \) |
|---|---|
| \( (2, 3) \) | \( 8 + 18 = 26 \) |
| \( (0, 6) \) | \( 0 + 36 = 36 \) |
| \( (8, 0) \) | \( 32 + 0 = 32 \) |
A toy company makes two types of toys: Type A and Type B. Type A requires 2 units of wood and 1 unit of paint. Type B requires 1 unit of wood and 2 units of paint. The company has 200 units of wood and 200 units of paint. Type A sells for 50 Birr and Type B for 60 Birr. The company must produce at least 20 units of each type. Find the number of each type to maximize revenue.
Formulation: Let \( x \) = Type A, \( y \) = Type B
Corner Points:
- \( (20, 20) \): Check: \( 40 + 20 = 60 \leq 200 \) ✓, \( 20 + 40 = 60 \leq 200 \) ✓
- Intersection of \( x = 20 \) and \( 2x + y = 200 \): \( y = 160 \). Point: \( (20, 160) \). Check: \( 20 + 320 = 340 \leq 200 \)? NO! Not feasible.
- Intersection of \( x = 20 \) and \( x + 2y = 200 \): \( 2y = 180 \), \( y = 90 \). Point: \( (20, 90) \). Check: \( 40 + 90 = 130 \leq 200 \) ✓
- Intersection of \( y = 20 \) and \( 2x + y = 200 \): \( 2x = 180 \), \( x = 90 \). Point: \( (90, 20) \). Check: \( 90 + 40 = 130 \leq 200 \) ✓
- Intersection of \( y = 20 \) and \( x + 2y = 200 \): \( x = 160 \). Point: \( (160, 20) \). Check: \( 320 + 20 = 340 \leq 200 \)? NO! Not feasible.
- Intersection of \( 2x + y = 200 \) and \( x + 2y = 200 \): Multiply 2nd by 2: \( 2x + 4y = 400 \). Subtract: \( 3y = 200 \), \( y = \frac{200}{3} \approx 66.67 \), \( x = 200 – \frac{400}{3} = \frac{200}{3} \approx 66.67 \). Point: \( \left(\frac{200}{3}, \frac{200}{3}\right) \). Check: both ≥ 20 ✓
Corner points: \( (20, 20) \), \( (20, 90) \), \( \left(\frac{200}{3}, \frac{200}{3}\right) \), \( (90, 20) \)
| Corner Point | \( Z = 50x + 60y \) |
|---|---|
| \( (20, 20) \) | \( 1000 + 1200 = 2200 \) |
| \( (20, 90) \) | \( 1000 + 5400 = 6400 \) |
| \(\left(\frac{200}{3}, \frac{200}{3}\right)\) | \( 50 \times \frac{200}{3} + 60 \times \frac{200}{3} = \frac{10000 + 12000}{3} = \frac{22000}{3} \approx 7333.33 \) |
| \( (90, 20) \) | \( 4500 + 1200 = 5700 \) |
Produce approximately 67 units of each type for maximum revenue of about 7333 Birr.
Maximize \( Z = 4x + 6y \) subject to \( x + y \leq 5 \), \( x + 2y \leq 8 \), \( x \geq 0, y \geq 0 \).
Show that this problem has multiple optimal solutions.
Corner Points:
- \( (0, 0) \)
- \( (5, 0) \): where \( x + y = 5 \) meets \( y = 0 \)
- \( (0, 4) \): where \( x + 2y = 8 \) meets \( x = 0 \)
- Intersection of \( x + y = 5 \) and \( x + 2y = 8 \): Subtract: \( y = 3 \), \( x = 2 \). Point: \( (2, 3) \)
| Corner Point | \( Z = 4x + 6y \) |
|---|---|
| \( (0, 0) \) | \( 0 \) |
| \( (5, 0) \) | \( 20 \) |
| \( (2, 3) \) | \( 8 + 18 = 26 \) |
| \( (0, 4) \) | \( 0 + 24 = 24 \) |
Maximum \( Z = 26 \) at \( (2, 3) \). This appears unique. Let me check…
Actually, \( (2, 3) \) gives 26 and this is the unique maximum. Let me reconsider: the objective is \( Z = 4x + 6y \), or \( 2x + 3y = \frac{Z}{2} \). The constraint \( x + 2y = 8 \) is NOT parallel to \( 2x + 3y \). So actually there is a unique solution here.
However, if the objective were \( Z = 2x + 4y \) (which is \( 2(x + 2y) \)), it WOULD be parallel to \( x + 2y = 8 \), giving multiple optimal solutions along that edge. The key is to check if the objective line is parallel to any boundary.
For multiple optimal solutions, the objective function must be a scalar multiple of a constraint boundary. Here \( 4x + 6y \) is NOT a multiple of \( x + 2y = 8 \) or \( x + y = 5 \), so the solution is actually unique at \( (2, 3) \).
A manufacturer produces two products. Product I requires 3 kg of raw material and Product II requires 5 kg. The manufacturer has 150 kg of raw material. The production time per unit is 4 hours for Product I and 2 hours for Product II, with 80 hours available. The profit per unit is 30 Birr for Product I and 20 Birr for Product II.
(a) Formulate the LP problem.
(b) Determine if the constraint \( x + y \leq 30 \) is redundant (someone suggested adding it as a “production limit”).
(c) Solve the LP problem.
(a) Formulation: Let \( x \) = Product I, \( y \) = Product II
(b) Checking redundancy of \( x + y \leq 30 \):
Without the extra constraint, corner points are:
- \( (0, 0) \)
- \( (20, 0) \): where \( 4x + 2y = 80 \) meets \( y = 0 \). Check: \( 60 \leq 150 \) ✓
- \( (0, 30) \): where \( 3x + 5y = 150 \) meets \( x = 0 \). Check: \( 60 \leq 80 \) ✓
- Intersection: \( 4x + 2y = 80 \) → \( 2x + y = 40 \). \( 3x + 5y = 150 \). From first: \( y = 40 – 2x \). Substitute: \( 3x + 5(40 – 2x) = 150 \), \( 3x + 200 – 10x = 150 \), \( -7x = -50 \), \( x = \frac{50}{7} \approx 7.14 \), \( y = 40 – \frac{100}{7} = \frac{180}{7} \approx 25.71 \). Check: \( x + y = \frac{230}{7} \approx 32.86 > 30 \). NOT feasible with the extra constraint!
Since the corner point \( \left(\frac{50}{7}, \frac{180}{7}\right) \) does NOT satisfy \( x + y \leq 30 \), the constraint is NOT redundant — it would change the feasible region and the optimal solution.
(c) Without the extra constraint:
| Corner Point | \( Z = 30x + 20y \) |
|---|---|
| \( (0, 0) \) | \( 0 \) |
| \( (20, 0) \) | \( 600 \) |
| \(\left(\frac{50}{7}, \frac{180}{7}\right)\) | \( 30 \times \frac{50}{7} + 20 \times \frac{180}{7} = \frac{1500 + 3600}{7} = \frac{5100}{7} \approx 728.57 \) |
| \( (0, 30) \) | \( 600 \) |
A hospital needs to plan a weekly menu. Two food types are available: Food X and Food Y. Each unit of Food X costs 40 Birr and provides 3 units of vitamin A and 4 units of vitamin B. Each unit of Food Y costs 50 Birr and provides 6 units of vitamin A and 3 units of vitamin B. The weekly requirements are at least 36 units of vitamin A and at least 24 units of vitamin B.
(a) Formulate as a minimization problem.
(b) Solve graphically and find the minimum cost.
(a) Formulation: Let \( x \) = units of Food X, \( y \) = units of Food Y
Simplify: \( x + 2y \geq 12 \) (dividing first constraint by 3)
(b) Corner Points:
- Intersection of \( x + 2y = 12 \) and \( 4x + 3y = 24 \): From first, \( x = 12 – 2y \). Substitute: \( 4(12 – 2y) + 3y = 24 \), \( 48 – 8y + 3y = 24 \), \( -5y = -24 \), \( y = 4.8 \), \( x = 12 – 9.6 = 2.4 \). Point: \( (2.4, 4.8) \). Verify both: ✓
- \( x + 2y = 12 \) meets \( x = 0 \): \( (0, 6) \). Check: \( 0 + 18 = 18 \geq 24 \)? NO! Not feasible.
- \( x + 2y = 12 \) meets \( y = 0 \): \( (12, 0) \). Check: \( 48 + 0 = 48 \geq 24 \) ✓
- \( 4x + 3y = 24 \) meets \( x = 0 \): \( (0, 8) \). Check: \( 0 + 16 = 16 \geq 12 \) ✓
- \( 4x + 3y = 24 \) meets \( y = 0 \): \( (6, 0) \). Check: \( 6 + 0 = 6 \geq 12 \)? NO! Not feasible.
Corner points: \( (2.4, 4.8) \), \( (12, 0) \), \( (0, 8) \)
| Corner Point | \( C = 40x + 50y \) |
|---|---|
| \( (2.4, 4.8) \) | \( 96 + 240 = 336 \) |
| \( (12, 0) \) | \( 480 + 0 = 480 \) |
| \( (0, 8) \) | \( 0 + 400 = 400 \) |
Show that the following LP problem has no solution (is infeasible):
The first constraint \( x + y \leq 3 \) requires \( x + y \) to be at most 3.
The second constraint \( x + y \geq 5 \) requires \( x + y \) to be at least 5.
These two constraints are contradictory — no value of \( x + y \) can be simultaneously ≤ 3 and ≥ 5.
On the graph: the first constraint shades a region below the line \( x + y = 3 \), while the second shades a region above the line \( x + y = 5 \). These two regions do not overlap. Therefore, no feasible region exists and the problem has no solution.
A transport company has two depots, A and B, with 80 and 60 trucks respectively. Three customers need 40, 50, and 50 trucks. The cost (in Birr) per truck from each depot to each customer is given below:
| Depot/Customer | Customer 1 | Customer 2 | Customer 3 |
|---|---|---|---|
| A | 4 | 3 | 5 |
| B | 2 | 7 | 6 |
Note: This is actually a transportation problem (a special type of LP). Write the LP formulation using 6 decision variables.
Decision Variables:
Let \( x_{ij} \) = number of trucks sent from Depot \( i \) to Customer \( j \)
So: \( x_{11}, x_{12}, x_{13}, x_{21}, x_{22}, x_{23} \)
Objective Function:
Supply Constraints:
Demand Constraints:
Non-negativity: \( x_{ij} \geq 0 \) for all \( i, j \)
Note: Transportation problems like this are typically solved using special methods (like Vogel’s Approximation or MODI method) rather than the graphical method, because they have more than 2 variables. The graphical method only works for 2-variable LP problems.