• 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

  1. Read the whole problem and decide what is being chosen. Name the variables with their units.
  2. Write the objective: profit per unit times quantity, added up.
  3. Put the data in a table: one row per resource or requirement, one column per variable, plus the limit.
  4. Turn each row of the table into one inequality. "At most", "not more than" and "available" give ≤; "at least" and "not less than" give ≥.
  5. 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.

ResourceTable (x)Chair (y)Available
Carpentry hours3130
Polishing hours1220
Profit (₹)500300

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. 1. In the problem "Maximise Z = 5x + 4y subject to x + y ≤ 10, x ≥ 0, y ≥ 0", what is Z = 5x + 4y called?

    1. A constraint
    2. The objective function
    3. The feasible region
    4. 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. 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?

    1. 2x + y ≤ 40
    2. x + 2y ≤ 40
    3. 2x + y ≥ 40
    4. 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. 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?

    1. 4x + 6y ≤ 24
    2. 6x + 4y ≥ 24
    3. 4x + 6y ≥ 24
    4. 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. 4. Which of these CANNOT be the objective function of a linear programming problem?

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

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

Privacy · Terms · Refunds · Delivery