8 min readConcept sheet1-mark MCQ; the setting-up step of 3, 4 and 5-mark LPP questions

What linear programming is

Linear programming finds the best value (maximum or minimum) of a linear expression when the variables obey linear constraints and cannot be negative.

Linear programming problem (LPP)Finding the optimal (maximum or minimum) value of a linear function of several variables, subject to linear inequalities and non-negative variables

Decision variablesx and y, the quantities to be decided, such as the number of shirts and kurtas to make

Non-negative restrictionsx ≥ 0, y ≥ 0, because a count of real things cannot be negative

General two-variable formMaximise or minimise Z = ax + by, subject to linear constraints and x ≥ 0, y ≥ 0

Why linear programming

Every business and home works with limited resources: money, time, space and labour. Linear programming answers questions like 'how many of each item should we make to earn the most?' or 'which mix of foods costs the least yet meets our needs?'. The word linear means every expression has only first powers of the variables: no x², xy or 1/x. The word programming here means planning, not computer coding.

How to write (formulate) an LPP

1
Read the problem and name the decision variables: 'Let x = ..., y = ...'.
2
Write the objective function Z = ax + by for the profit or the cost.
3
Write one constraint for each limited resource or requirement (≤ for 'at most', ≥ for 'at least').
4
Add the non-negative restrictions x ≥ 0, y ≥ 0.
5★
Write it all together: Maximise (or Minimise) Z = ... subject to ....

★ key step

Example 1: a tailor's weekly plan

Problem

A tailor in Tiruppur makes shirts and kurtas. A shirt needs 2 hours of cutting and 1 hour of stitching. A kurta needs 1 hour of cutting and 2 hours of stitching. Each week she has at most 12 hours for cutting and 12 hours for stitching. She earns ₹ 40 on a shirt and ₹ 60 on a kurta (example rates). Formulate an LPP to maximise her earnings.

Working

Let x = number of shirts and y = number of kurtas.
Objective: Z = 40x + 60y, to be maximised.
Cutting: 2x + y ≤ 12
Stitching: x + 2y ≤ 12
Non-negative: x ≥ 0, y ≥ 0

Answer

Maximise Z = 40x + 60y subject to 2x + y ≤ 12, x + 2y ≤ 12, x ≥ 0, y ≥ 0.

Example 2: a hostel mess

Problem

A hostel mess mixes two foods P and Q. One kg of P gives 2 units of vitamin A and 1 unit of vitamin B. One kg of Q gives 1 unit of vitamin A and 2 units of vitamin B. The mix must give at least 8 units of A and 10 units of B. P costs ₹ 50 per kg and Q costs ₹ 70 per kg (example prices). Formulate an LPP to keep the cost lowest.

Working

Let x kg of P and y kg of Q be used.
Objective: Z = 50x + 70y, to be minimised.
Vitamin A: 2x + y ≥ 8
Vitamin B: x + 2y ≥ 10
Non-negative: x ≥ 0, y ≥ 0

Answer

Minimise Z = 50x + 70y subject to 2x + y ≥ 8, x + 2y ≥ 10, x ≥ 0, y ≥ 0.

Where linear programming is used

Manufacturing: how many of each product to make for the highest profit.
Diet planning: the cheapest mix of foods that meets nutrient needs.
Transport: the cheapest way to send goods from godowns to shops.
Farming: how much land to give each crop.

In real life

A hostel mess planning the cheapest mix of dal and rice that still gives enough protein and energy is solving a linear programming problem.

Exam angle

1 marks: “In an LPP, what are the conditions x ≥ 0, y ≥ 0 called?” Non-negative restrictions (non-negativity constraints).

1 marks: “Which of these can be the objective function of an LPP: Z = 3x + 4y, Z = x² + y, Z = xy, Z = 3/x + y?” Only Z = 3x + 4y, because it is linear in x and y.

2 marks: “A farmer has 10 hectares to grow ragi and groundnut. Ragi needs 2 workers per hectare and groundnut needs 3; 24 workers are available. Profit per hectare is ₹ 6000 for ragi and ₹ 8000 for groundnut (example rates). Formulate the LPP to maximise profit.” Let x ha of ragi and y ha of groundnut. Maximise Z = 6000x + 8000y subject to x + y ≤ 10, 2x + 3y ≤ 24, x ≥ 0, y ≥ 0.

Remember it

V-O-C-N: Variables, Objective, Constraints, Non-negative: the four parts of every LPP.