- Foundation
- About 16 min
- 5 practice questions
Parts of a linear programming problem and formulation
Name the decision variables, objective function, constraints and non-negativity conditions of a linear programming problem, and turn manufacturing, diet and investment word problems into mathematical form.
If something looks wrong, please tell us.
A linear programming problem (LPP) is a word problem translated into a precise mathematical form. Most marks in this topic are lost not in the solving but in the translating: a ≤ written as ≥, two numbers swapped, a forgotten condition. This lesson names the parts of an LPP and gives a step-by-step routine for writing one from a story.
The four parts of an LPP
- Decision variables: the quantities you control, such as x = number of tables made and y = number of chairs made.
- Objective function: the quantity to be made as large as possible (profit) or as small as possible (cost), written Z = px + qy.
- Constraints: linear inequalities that express the limited resources or the minimum requirements, such as 3x + y ≤ 30.
- Non-negativity conditions: x ≥ 0 and y ≥ 0, because the quantities cannot be negative.
The word linear matters. Every expression must be a constant times x plus a constant times y (plus a constant). Terms such as x², xy or 1/x are not allowed.
A routine for formulating
- Read the whole problem and decide what is being chosen. Name the variables with their units.
- Write the objective: profit per unit times quantity, added up.
- Put the data in a table: one row per resource or requirement, one column per variable, plus the limit.
- Turn each row of the table into one inequality. "At most", "not more than" and "available" give ≤; "at least" and "not less than" give ≥.
- Add x ≥ 0 and y ≥ 0.
Worked example 1: a carpenter's workshop
A carpenter makes tables and chairs. A table needs 3 hours of carpentry and 1 hour of polishing and earns a profit of ₹500. A chair needs 1 hour of carpentry and 2 hours of polishing and earns ₹300. Each week 30 hours of carpentry and 20 hours of polishing are available. Formulate the problem of maximising profit.
| Resource | Table (x) | Chair (y) | Available |
|---|---|---|---|
| Carpentry hours | 3 | 1 | 30 |
| Polishing hours | 1 | 2 | 20 |
| Profit (₹) | 500 | 300 |
Let x = number of tables and y = number of chairs made in a week. Maximise Z = 500x + 300y subject to 3x + y ≤ 30 (carpentry), x + 2y ≤ 20 (polishing), x ≥ 0, y ≥ 0. Read each constraint along a row of the table, never down a column.
Worked example 2: a diet problem
A diet is made from two foods P and Q sold in packets. A packet of P contains 3 units of vitamin A and 1 unit of iron and costs ₹40. A packet of Q contains 1 unit of vitamin A and 2 units of iron and costs ₹30. The diet needs at least 9 units of vitamin A and at least 8 units of iron. Let x and y be the numbers of packets of P and Q. Minimise Z = 40x + 30y subject to 3x + y ≥ 9 (vitamin A), x + 2y ≥ 8 (iron), x ≥ 0, y ≥ 0. Requirements give ≥ constraints and the objective is a cost to be minimised: this is the typical shape of a diet problem.
Worked example 3: an investment allocation
Suppose a person has up to ₹50,000 to put into two schemes, A paying an illustrative 8% a year and B paying 10% a year. At least ₹10,000 must go into A, and not more than ₹30,000 into B. Measure money in thousands of rupees: x in A and y in B. Maximise Z = 0.08x + 0.10y (yearly return in thousands) subject to x + y ≤ 50, x ≥ 10, y ≤ 30, x ≥ 0, y ≥ 0. Here x ≥ 10 already implies x ≥ 0, which is harmless to keep. Choosing a convenient unit (thousands) keeps the numbers small.
An LPP: maximise or minimise Z = px + qy subject to linear constraints and x ≥ 0, y ≥ 0. "At most" gives ≤, "at least" gives ≥, and each constraint is read along one row of the data table.
Key takeaways: define the variables first, with units. Build a data table and read each constraint along a row. Translate the words carefully, including comparisons such as "at least twice", and check a translated constraint by trying a pair of numbers. Never forget the non-negativity conditions.
Check your understanding
-
1. In the problem "Maximise Z = 5x + 4y subject to x + y ≤ 10, x ≥ 0, y ≥ 0", what is Z = 5x + 4y called?
- A constraint
- The objective function
- The feasible region
- The non-negativity condition
Show answer
Answer: B. Z = 5x + 4y is the quantity to be made as large as possible, so it is the objective function. x + y ≤ 10 is a constraint, and x ≥ 0, y ≥ 0 are the non-negativity conditions.
-
2. A factory makes x bags and y belts. A bag needs 2 hours on a machine, a belt needs 1 hour, and the machine can run for at most 40 hours. Which constraint is correct?
- 2x + y ≤ 40
- x + 2y ≤ 40
- 2x + y ≥ 40
- x + y ≤ 40
Show answer
Answer: A. Machine time used = 2 hours × x bags + 1 hour × y belts = 2x + y. "At most 40" means ≤ 40. Putting 2 with y swaps the products, and ≥ would mean at least 40 hours.
-
3. Food A gives 4 units of protein per kg and food B gives 6 units per kg. A diet uses x kg of A and y kg of B and must give at least 24 units of protein. Which constraint is correct?
- 4x + 6y ≤ 24
- 6x + 4y ≥ 24
- 4x + 6y ≥ 24
- 4x + 6y = 24
Show answer
Answer: C. Protein = 4x + 6y. "At least 24" means ≥ 24. The diet may give more than 24 units, so an equation is too strict, and ≤ would put a ceiling on protein instead of a floor.
-
4. Which of these CANNOT be the objective function of a linear programming problem?
- Z = 3x + 2y
- Z = x − 4y
- Z = 7y
- Z = 3x + 2xy
Show answer
Answer: D. The objective must be linear: each term is a constant times x or a constant times y. The term 2xy multiplies the variables together, so Z = 3x + 2xy is not linear. A negative coefficient (x − 4y) or a missing variable (7y) is allowed.
-
5. A shop sells x pens and y notebooks. The number of notebooks must be at least twice the number of pens. Which constraint is correct?
- y ≥ 2x
- x ≥ 2y
- 2y ≥ x
- y ≤ 2x
Show answer
Answer: A. "Notebooks at least twice pens" means notebooks ≥ 2 × pens, so y ≥ 2x. Check with numbers: 1 pen and 2 notebooks should be allowed, and 2 ≥ 2 × 1 is true. The trap is writing x ≥ 2y by following the word order.
Sign in to keep track of the lessons you finish.