- Foundation
- About 15 min
- 5 practice questions
Optimisation problems and the language of linear programming
See how everyday choices under limits become optimisation problems, and learn the terms of a linear programming problem: decision variables, objective function, constraints and non-negativity restrictions.
If something looks wrong, please tell us.
A shopkeeper with limited money and shelf space, a factory with limited machine hours, a family planning meals within a budget: each wants the best result (most profit, least cost) while staying within limits. Problems that seek the maximum or minimum of some quantity under such limits are called optimisation problems. A very important class of them, in which every relation is linear, is called linear programming. In this chapter we solve such problems in two variables by the graphical method.
A motivating example
A tailor (the numbers are illustrative) makes shirts and kurtas. A shirt needs 2 m of cloth and 1 hour of work; a kurta needs 3 m of cloth and 2 hours. Each week the tailor has 60 m of cloth and 35 working hours. The profit is ₹100 on a shirt and ₹180 on a kurta. How many of each should be made to earn the greatest profit, assuming everything made is sold?
Try a few plans. Only shirts: the cloth allows 60 ÷ 2 = 30 and the hours allow 35, so at most 30 shirts, profit ₹3000. Only kurtas: the cloth allows 20 and the hours allow 17 (17.5 rounded down), profit 17 × 180 = ₹3060. 15 shirts and 10 kurtas: cloth 30 + 30 = 60 m, hours 15 + 20 = 35, both exactly used; profit 1500 + 1800 = ₹3300. Different plans give different profits, and guessing will not tell us whether ₹3300 is the best possible. We need a systematic method, and the first step is to state the problem mathematically.
Mathematical formulation
Let x be the number of shirts and y the number of kurtas. They cannot be negative: x ≥ 0, y ≥ 0. The cloth used, 2x + 3y metres, cannot exceed 60: 2x + 3y ≤ 60. The time used, x + 2y hours, cannot exceed 35: x + 2y ≤ 35. The profit is Z = 100x + 180y. So the problem is: Maximise Z = 100x + 180y subject to 2x + 3y ≤ 60, x + 2y ≤ 35, x ≥ 0, y ≥ 0.
The vocabulary
| Term | Meaning | In the tailor problem |
|---|---|---|
| Decision variables | The unknown quantities to be decided; always non-negative | x shirts, y kurtas |
| Objective function | The linear function Z = ax + by to be maximised or minimised | Z = 100x + 180y |
| Constraints | Linear inequalities or equations that the variables must satisfy | 2x + 3y ≤ 60, x + 2y ≤ 35 |
| Non-negative restrictions | The conditions x ≥ 0, y ≥ 0 | Cannot make a negative number of garments |
| Optimal value | The maximum or minimum value of Z | To be found |
A linear programming problem (LPP) is one that is concerned with finding the optimal value (maximum or minimum) of a linear function of several variables, called the objective function, subject to the conditions that the variables are non-negative and satisfy a set of linear inequalities, called linear constraints. The word linear means all the relations are linear (no x², xy, √x and so on); the word programming means planning a programme or course of action, not computer programming.
Parts of a linear programming problem
-
Decision variables
- x, y ≥ 0
- What we choose
-
Objective function
- Z = ax + by
- Maximise profit or minimise cost
-
Constraints
- Linear inequalities such as 2x + 3y ≤ 60
- Come from limited resources or requirements
An LPP: optimise a linear objective function Z = ax + by subject to linear constraints and x ≥ 0, y ≥ 0.
Worked examples
Worked example 1: is it an LPP?
(i) Maximise Z = 4x + 7y subject to x + y ≤ 10, 3x + y ≤ 18, x, y ≥ 0: an LPP; everything is linear. (ii) Minimise Z = x² + y subject to x + y ≥ 2, x, y ≥ 0: not an LPP, because the objective function contains x². (iii) Maximise Z = x + y subject to xy ≤ 6, x, y ≥ 0: not an LPP, because the constraint xy ≤ 6 is not linear.
Worked example 2: writing constraints from words
Translate: (a) 'pens cost ₹10 each, notebooks ₹40 each, and at most ₹400 can be spent' gives 10x + 40y ≤ 400, i.e. x + 4y ≤ 40; (b) 'at least 5 notebooks are needed' gives y ≥ 5; (c) 'the number of pens is at least twice the number of notebooks' gives x ≥ 2y. 'At most' means ≤ and 'at least' means ≥.
Key takeaways
- An optimisation problem seeks the best value of a quantity under limits.
- In an LPP, the objective function and all constraints are linear, and the variables are non-negative.
- Decision variables are the quantities you choose; constraints come from limited resources or minimum requirements.
- 'At most' becomes ≤; 'at least' becomes ≥.
- Trying plans by hand shows the need for a systematic method, developed in the next lessons.
Check your understanding
-
1. In a linear programming problem, the linear function that is to be maximised or minimised is called the
- constraint
- objective function
- feasible region
- decision variable
Show answer
Answer: B. The objective function Z = ax + by is the quantity, such as profit or cost, that we want to make as large or as small as possible.
-
2. Which of these cannot be the objective function of an LPP?
- Z = 3x + 5y
- Z = 0.5x − 2y
- Z = x² + y
- Z = 7x
Show answer
Answer: C. An objective function must be linear. Z = x² + y contains x², so it is not linear. Z = 7x is linear (the coefficient of y is 0).
-
3. Pens cost ₹10 each and notebooks ₹40 each, and at most ₹400 may be spent. With x pens and y notebooks, the constraint is
- 10x + 40y ≥ 400
- 40x + 10y ≤ 400
- x + y ≤ 400
- 10x + 40y ≤ 400
Show answer
Answer: D. The cost of x pens and y notebooks is 10x + 40y rupees, and 'at most ₹400' means this is ≤ 400.
-
4. The non-negative restrictions in an LPP in x and y are
- x ≥ 0, y ≥ 0
- x > 0, y > 0
- x + y ≥ 0
- x ≤ 0, y ≤ 0
Show answer
Answer: A. Decision variables represent quantities that cannot be negative, but they may be zero, so the restrictions are x ≥ 0 and y ≥ 0.
-
5. Assertion (A): 'Maximise Z = 3x + 4y subject to x + y ≤ 4, xy ≤ 3, x ≥ 0, y ≥ 0' is not a linear programming problem. Reason (R): In a linear programming problem the objective function and all the constraints must be linear.
- Both A and R are true, and R is the correct explanation of A
- Both A and R are true, but R is not the correct explanation of A
- A is true, but R is false
- A is false, but R is true
Show answer
Answer: A. The constraint xy ≤ 3 contains the product xy, which is not linear. By R this disqualifies the problem, so A is true and R explains it.
Sign in to keep track of the lessons you finish.