• 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

Terms used in linear programming
TermMeaningIn the tailor problem
Decision variablesThe unknown quantities to be decided; always non-negativex shirts, y kurtas
Objective functionThe linear function Z = ax + by to be maximised or minimisedZ = 100x + 180y
ConstraintsLinear inequalities or equations that the variables must satisfy2x + 3y ≤ 60, x + 2y ≤ 35
Non-negative restrictionsThe conditions x ≥ 0, y ≥ 0Cannot make a negative number of garments
Optimal valueThe maximum or minimum value of ZTo 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. 1. In a linear programming problem, the linear function that is to be maximised or minimised is called the

    1. constraint
    2. objective function
    3. feasible region
    4. 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. 2. Which of these cannot be the objective function of an LPP?

    1. Z = 3x + 5y
    2. Z = 0.5x − 2y
    3. Z = x² + y
    4. 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. 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

    1. 10x + 40y ≥ 400
    2. 40x + 10y ≤ 400
    3. x + y ≤ 400
    4. 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. 4. The non-negative restrictions in an LPP in x and y are

    1. x ≥ 0, y ≥ 0
    2. x > 0, y > 0
    3. x + y ≥ 0
    4. 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. 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.

    1. Both A and R are true, and R is the correct explanation of A
    2. Both A and R are true, but R is not the correct explanation of A
    3. A is true, but R is false
    4. 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.

Privacy · Terms · Refunds · Delivery