A furniture workshop in Kano makes tables and chairs. Carpentry hours are limited, so are finishing hours, a customer wants at least a few chairs, and the market will not take more than so many tables. With one scarce resource the answer is a ranking, as the last topic showed. With several, the best plan can be found only by solving all the limits at once.
Linear programming does that. It turns the business problem into a statement in algebra, draws it as a picture, and reads the best answer from the corner of the picture.
This topic explains how to define the variables, write the objective function and the constraints, draw the constraints on a graph, find the feasible region, and find the optimum by the corner point method, by the slope of the objective function, and by simultaneous equations. The simplex method is not examined at this level. It builds on the limiting factors topic. The next topic covers slack and shadow prices.
In 30 seconds
Linear programming (LP) finds the best outcome, such as maximum contribution or minimum cost, subject to several limits, when everything can be expressed as linear relationships.
Steps: (1) define the variables (x and y); (2) write the objective function (for example C = 50x + 40y); (3) write the constraints, with “≤” for a maximum limit and “≥” for a minimum, and the non-negativity constraints x, y ≥ 0; (4) plot each constraint as a line by finding where it crosses the axes; (5) shade the feasible region; (6) find the optimum, which lies at a corner of the feasible region, using the corner point method, the slope of the objective function or simultaneous equations.
Full marks come from correct inequalities, the corner values and a conclusion in business terms.
Formulating the problem
Linear programming is a mathematical method of finding the best outcome (maximum profit or contribution, or lowest cost) subject to a number of limiting factors, or constraints. A problem involves maximising or minimising a linear function (the objective function) subject to linear constraints. The overall approach is:
- Define the variables. One variable for each quantity to be decided: let x be the number of units of product 1 and y the number of units of product 2.
- Formulate the objective function. For maximum contribution, C = contribution per unit of x × x + contribution per unit of y × y.
- Formulate the constraints.
- Plot the constraints on a graph.
- Identify the feasible region.
- Find the optimum values of x and y.
Writing constraints
A separate constraint is needed for every item that limits the objective function. Each is a formula with a limit.
- A maximum limit is written as “less than or equal to” (≤). Maximum demand for product X of 5,000 units: x ≤ 5,000.
- A minimum limit is written as “greater than or equal to” (≥). A contract needs at least 2,000 units: x ≥ 2,000.
- Constraints with two variables. Each unit of x takes 2 hours and each unit of y takes 3 hours, with 18,000 hours available: 2x + 3y ≤ 18,000.
- Non-negativity. You cannot make a negative quantity: x ≥ 0 and y ≥ 0. These do not need to be plotted separately because the graph is drawn in the positive area.
Plotting a constraint
A constraint with two variables is a straight line on a graph with x on one axis and y on the other. Two points are enough. Set x to zero and find y; set y to zero and find x. For 3x + 2y = 600: if x = 0, y = 300; if y = 0, x = 200. Join (0, 300) and (200, 0).
Points on the origin side of the line (or on the line) satisfy a “≤” constraint; points beyond it need more of the resource than is available and are not feasible. A “≥” constraint is satisfied by points on the line and beyond it.
Solving: the three methods
The feasible region is the area on the graph where all constraints are met together. The best point lies on its outer edge, at a corner. There are three ways to find it.
- Corner point method. Find the x and y at every corner, using simultaneous equations where two constraint lines meet. Put each pair into the objective function. The corner with the highest value (for a maximum) is the optimum. It is the most reliable method.
- Slope of the objective function. Rearrange the objective function and each constraint into y = a + bx form and compare slopes. The slope of the objective function lies between the slopes of the two constraints that meet at the optimum corner. Alternatively, plot the objective line for any convenient value of C, then slide a ruler parallel to it away from the origin until it is about to leave the feasible region. The last corner touched is the optimum.
- Simultaneous equations. Having found which two constraints meet at the optimum, solve them: multiply one or both equations so a coefficient is the same, subtract, find one variable, and substitute back for the other.
For a minimisation, such as minimum cost, the best corner is the one with the lowest value, and the objective line is slid towards the origin.
Practical points
- Check every corner against all constraints: a corner found from two lines may be outside the region because a third constraint cuts it off.
- Some corners have fractional values. If whole units are needed, round down and check feasibility, and say so.
- State the answer in business terms: how many of each product, the resulting contribution, and which resources are fully used.
- Linear programming assumes that contribution per unit and the resource use per unit are constant, and that products can be made in any quantity. These simplifications should be noted when advising.
Layouts
- Variables: let x be …, let y be ….
- Objective: maximise C = ax + by.
- Constraints: resource per unit of x × x + resource per unit of y × y ≤ available; x ≤ maximum demand; x ≥ minimum; x, y ≥ 0.
- Intercepts: for px + qy = r, x = r ÷ p when y = 0; y = r ÷ q when x = 0.
- Corner table: corner, x, y, value of the objective function; choose the highest.
Money is in naira and answers are exact.
Worked examples
Example 1: formulate and solve. A company makes A and B each week. Contribution is ₦50 for A and ₦40 for B. Each A needs 3 labour hours and 2 machine hours; each B needs 2 labour hours and 4 machine hours. There are 600 labour hours and 640 machine hours. At least 40 units of A must be made, and no more than 130 of B can be sold. Required: the plan that maximises contribution.
- Variables. x = units of A; y = units of B.
- Objective. Maximise C = 50x + 40y.
- Constraints. Labour 3x + 2y ≤ 600. Machine 2x + 4y ≤ 640. x ≥ 40. y ≤ 130. x, y ≥ 0.
- Intercepts. Labour: (200, 0) and (0, 300). Machine: (320, 0) and (0, 160).
- Corners. (40, 0); (200, 0) where labour meets y = 0; (140, 90) where labour meets machine; (60, 130) where machine meets y = 130; (40, 130).
- The meeting of labour and machine.
3x + 2y = 600 (1)
2x + 4y = 640 (2).
Multiply (1) by 2: 6x + 4y = 1,200.
Subtract (2): 4x = 560, so x = 140.
Then 2y = 600 − 420, so y = 90.
Check in (2): 280 + 360 = 640. - Values of C.
(40, 0) = 2,000
(200, 0) = 10,000
(140, 90) = 7,000 + 3,600 = 10,600
(60, 130) = 3,000 + 5,200 = 8,200
(40, 130) = 2,000 + 5,200 = 7,200. - Slope check.
Objective slope = −50 ÷ 40 = −1.25.
Labour slope −1.5; machine slope −0.5.
The objective slope lies between them, so the optimum is where those two lines meet. - Answer. Make 140 A and 90 B, contribution ₦10,600.
Both labour (420 + 180 = 600) and machine (280 + 360 = 640) are fully used.
Example 2: writing constraints. A company makes tables (T) and chairs (C). A table needs 5 carpentry hours and a chair 2; 400 hours are available. At least 20 chairs must be made for a contract. No more than 60 tables can be sold. Total output must be at least 50 items. Required: the constraints and the intercepts of the carpentry line.
- Carpentry. 5T + 2C ≤ 400.
- Contract. C ≥ 20.
- Demand. T ≤ 60.
- Minimum total. T + C ≥ 50.
- Non-negativity. T, C ≥ 0.
- Carpentry intercepts.
T = 400 ÷ 5 = 80 when C = 0
C = 400 ÷ 2 = 200 when T = 0.
Expect variants: a minimisation problem, a constraint with a different form such as a ratio, a feasible region with fractional corners, and a request for the objective function line.
Common mistakes
- Wrong inequality direction. Maximum limits use ≤; minimum limits use ≥.
- Mixing up the coefficients. Each constraint uses resource per unit of x and of y.
- Not checking all corners. The optimum is the highest value among all feasible corners.
- Using a corner outside the region. Check it against every constraint.
- Slope errors. Compare the slopes with their signs.
- Leaving out the business conclusion. State the plan and contribution.
Quick revision
- Define variables; objective function; constraints (≤ maximum, ≥ minimum); x, y ≥ 0.
- Plot each line by setting x = 0 and y = 0. Feasible region satisfies all.
- Optimum at a corner: corner points, slope, or simultaneous equations.
- Simplex is not examined at this level.
How the marks are earned
- Formulate: a mark for the variables, the objective and each constraint.
- Solve: the intercepts, the corners and the values of the objective.
- Conclude: the plan, the contribution and which resources are fully used.
Practice questions
These are original questions, written in the style of the Skills examination. Work each one before you open the answer.
Recall check: multiple choice
Question 1. The function to be maximised or minimised in linear programming is the:
- Constraint
- Objective function
- Slack
- Intercept
Show the answer
B. For example total contribution.
Question 2. A maximum limit on a resource is written as:
- Greater than
- Equal to
- Greater than or equal to
- Less than or equal to
Show the answer
D. Use ≥ for a minimum.
Question 3. The constraints x, y ≥ 0 mean:
- A negative quantity cannot be made
- Both must equal zero
- Both are maximum limits
- Both must be above 100
Show the answer
A. They do not need to be plotted.
Question 4. The feasible region is:
- The area outside all lines
- The area with the highest cost
- The area that satisfies all the constraints
- The area on one axis
Show the answer
C. The optimum is on its edge.
Question 5. The optimum solution lies at:
- The origin
- A corner of the feasible region
- The middle of a line
- Outside the region
Show the answer
B. Test every corner.
Question 6. The constraint 3x + 2y = 600 crosses the axes at:
- x = 200 when y = 0, and y = 300 when x = 0
- x = 300 and y = 200
- x = 600 and y = 600
- x = 0 and y = 0
Show the answer
A. 600 ÷ 3 = 200 and 600 ÷ 2 = 300.
Question 7. The slope of the objective function 50x + 40y, written y = C/40 − 1.25x, is:
- 50
- 40
- +1.25
- −1.25
Show the answer
D. It lies between the slopes of the two constraints meeting at the optimum.
Question 8. Simultaneous equations are used to find:
- The selling price
- The fixed cost
- The coordinates of a corner where two constraints meet
- The tax
Show the answer
C. Solve the two lines together.
Question 9. A requirement to supply at least 2,000 units of X is written:
- x ≤ 2,000
- x = 0
- x ≥ 2,000
- x < 0
Show the answer
C. A minimum limit uses ≥.
Question 10. The simplex method is:
- Not examined at this level
- The only method allowed
- A costing method
- A pricing method
Show the answer
A. The graphical and simultaneous equation methods are examined.
Section B style: written questions
Question 11 (10 marks). (a) State the six steps in solving a two-variable linear programming problem. (6 marks) (b) Explain why the optimum lies at a corner of the feasible region. (4 marks)
Question 12 (15 marks). A company makes X and Y with contributions of ₦30 and ₦20. Each X needs 4 labour hours and each Y needs 2; 800 hours are available. Each X needs 1 machine hour and each Y 2; 500 hours are available. At least 20 X and 50 Y must be made.
(a) Formulate the problem. (5 marks) (b) Calculate the intercepts of the two resource constraints. (2 marks) (c) Calculate the corners of the feasible region. (4 marks) (d) Calculate the contribution at each corner and state the optimum. (4 marks)
Question 13 (20 marks). A company makes P and Q with contributions of ₦25 and ₦35. Each P needs 2 kg of material and 4 labour hours; each Q needs 3 kg and 2 hours. There are 1,200 kg of material and 1,400 labour hours. At least 100 P must be made.
(a) Formulate the problem. (6 marks) (b) Calculate the intercepts of the resource lines. (4 marks) (c) Solve by the corner point method. (8 marks) (d) State TWO assumptions of linear programming. (2 marks)
Model answers
Show the model answer to Question 11
(a) Define the variables (1); formulate the objective function (1); formulate the constraints (1); plot the constraints on a graph (1); identify the feasible region (1); find the values of x and y that give the optimum (1).
(b) The objective function is linear, so its value changes at a constant rate as x and y change (1). Moving the objective line away from the origin increases its value (1). The furthest point it can reach within the feasible region is a corner, because the region is bounded by straight lines (2).
Show the model answer to Question 12
(a)
- Let x.
units of X, y = units of Y (1). - Maximise C = 30x + 20y (1).
- Labour 4x + 2y ≤ 800 (1).
- Machine x + 2y ≤ 500 (1). x ≥ 20, y ≥ 50 (1).
(b) Labour: (200, 0) and (0, 400). Machine: (500, 0) and (0, 250) (2).
(c)
- Labour and machine meet.
subtract x + 2y = 500 from 4x + 2y = 800 to give 3x = 300, so x = 100, y = 200 (2). - Other corners.
(20, 50); (175, 50) where labour meets y = 50; (20, 240) where machine meets x = 20 (2).
(d)
- (20, 50) = 1,600
- (175, 50) = 5,250 + 1,000 = 6,250
- (100, 200) = 3,000 + 4,000 = 7,000
- (20, 240) = 600 + 4,800 = 5,400.
- Optimum: 100 X and 200 Y, contribution ₦7,000 (4).
Show the model answer to Question 13
(a)
- x = P, y = Q (1).
- Maximise C = 25x + 35y (1).
- Material 2x + 3y ≤ 1,200 (1).
- Labour 4x + 2y ≤ 1,400 (2). x ≥ 100, y ≥ 0 (1).
(b) Material: x = 600 when y = 0; y = 400 when x = 0. Labour: x = 350 when y = 0; y = 700 when x = 0 (4).
(c)
- Material and labour meet.
multiply the material equation by 2 to get 4x + 6y = 2,400 - subtract 4x + 2y = 1,400 to give 4y = 1,000, so y = 250, and x = (1,200 − 750) ÷ 2 = 225 (2).
- Corners.
(100, 0); (350, 0); (225, 250); (100, 333.33) where material meets x = 100 (2). - Values.
(100, 0) = 2,500 - (350, 0) = 8,750
- (225, 250) = 5,625 + 8,750 = 14,375
- (100, 333.33) = 2,500 + 11,666.67 = 14,166.67 (3).
- Optimum: 225 P and 250 Q, contribution ₦14,375 (1).
(d) Any two: contribution and resource use per unit are constant; products can be made in any quantity, including fractions; the constraints and objective are linear (1 each).
Pathfinder on Linear programming: formulation and graphical solution
These are the ICAN Pathfinder questions that test this topic. ICAN owns the questions and the suggested solutions, so we point you to them and do not copy them. Open your Pathfinder, attempt each question under exam conditions, then check your answer against the notes above.
LP formulation, simultaneous equations, shadow prices as overtime limits, single-product choice.
Revise first: Layouts
Machine utilisation and bottleneck; marginal analysis; throughput accounting mix; TA inventory valuation; scarce resources in budgets and LP.
Revise first: Layouts
LP objective and constraints, optimum plan, dual prices by one-unit change, slack, ways to overcome capacity limits.
Revise first: Layouts
LP concept and uses; cost-plus prices; optimal output; shadow prices (e: NPV/IRR outside course).
Revise first: Layouts
Source: ICAN Pathfinder, Performance Management. Diets covered: March/July Diet, 2020 to May Diet, 2026. All 13 diets in the Pathfinder are mapped.
Spotted a mistake? Tell us and we will check it.
