Linear Programming ISC Class 12: Formulation, Graphical Method and Solved Problems

What Linear Programming is about

Weightage: Linear Programming is part of the unit Linear Programming, which carries 5 of the 80 marks in the ISC Mathematics. Questions on it can appear in any section of the paper.Source: CISCE ISC Mathematics syllabus, examination year 2027, distribution of marks

Key concepts

Terminology and assumptions

Decision variables: the unknowns we control (number of tables, kilograms of food). Objective function: the linear function Z = ax + by to optimise. Constraints: linear inequalities ($\le$, $\ge$) expressing limits on resources or requirements; non-negativity: x ≥ 0, y ≥ 0. Feasible region: the common region satisfying all constraints; points in it are feasible solutions, points outside are infeasible. Optimal solution: a feasible point giving the best Z. Linear programming assumes linearity (proportional profits and resource use), certainty of data, divisibility and a single objective.

Worked example

A bakery makes cakes A and B. Cake A needs 200 g flour and 25 g fat; cake B needs 100 g flour and 50 g fat. There are 5 kg flour and 1 kg fat. Identify the decision variables, objective and constraints to make as many cakes as possible.

Try it first, then show the solutionSolution

1. Decision variables: x = number of A, y = number of B.
2. Objective: maximise Z = x + y.
3. Flour: 200x + 100y ≤ 5000 ⇒ 2x + y ≤ 50; fat: 25x + 50y ≤ 1000 ⇒ x + 2y ≤ 40; x, y ≥ 0.

Answer: Maximise Z = x + y subject to 2x + y ≤ 50, x + 2y ≤ 40, x ≥ 0, y ≥ 0

Formulating a linear programming problem

Steps: (1) read the problem and define the decision variables with units; (2) write the objective function (profit to maximise, cost to minimise) in terms of them; (3) translate each limitation into an inequality: 'at most', 'cannot exceed', 'available' give ≤; 'at least', 'minimum requirement' give ≥; (4) add x, y ≥ 0. A table of the data (rows for resources, columns for products) prevents mixing up coefficients.

Worked example

A carpenter makes tables (₹250 profit each) and chairs (₹100 each). A table needs 3 h of cutting and 1 h of polishing; a chair needs 1 h of cutting and 2 h of polishing. There are 60 h of cutting and 40 h of polishing a week. Formulate the LPP.

Try it first, then show the solutionSolution

1. x tables, y chairs per week.
2. Maximise Z = 250x + 100y.
3. Cutting 3x + y ≤ 60; polishing x + 2y ≤ 40; x, y ≥ 0.

Answer: Maximise Z = 250x + 100y subject to 3x + y ≤ 60, x + 2y ≤ 40, x, y ≥ 0

Graphical method and the corner point theorem

Draw each constraint as a line (find two intercepts), test a point such as the origin to decide which side satisfies the inequality, and shade. The feasible region is the overlap, including the non-negativity restrictions (first quadrant). Corner point theorem: if the feasible region is bounded, the maximum and minimum of Z occur at corner points. Find each corner (intercepts or intersections of two lines by solving simultaneously) and tabulate Z. An alternative check is the iso-profit line method: slide the line ax + by = k parallel to itself across the region.

Worked example

Solve the carpenter's problem: maximise Z = 250x + 100y subject to 3x + y ≤ 60, x + 2y ≤ 40, x, y ≥ 0.

Try it first, then show the solutionSolution

1. Corners: O(0, 0), A(20, 0), C(0, 20), and B from 3x + y = 60 and x + 2y = 40: x = 16, y = 12.
2. Z: O 0; A 5000; B 4000 + 1200 = 5200; C 2000.
3. The region is bounded, so the maximum is at B.

Answer: 16 tables and 12 chairs; maximum profit ₹5200

Unbounded feasible regions

If the feasible region is unbounded, an optimum may not exist. For a minimum candidate m found at a corner, draw (or test) the open half-plane Z < m: if it has no point in common with the feasible region, m is the minimum; otherwise Z has no minimum. Similarly for a maximum M, test Z > M. Minimisation problems with '≥' constraints (diet, cost) typically have unbounded regions that still have a minimum, but usually no maximum.

Worked example

Minimise Z = 3x + 2y subject to x + y ≥ 4, x + 3y ≥ 6, x, y ≥ 0.

Try it first, then show the solutionSolution

1. Corners of the unbounded region: (6, 0), (3, 1) [from x + y = 4 and x + 3y = 6], (0, 4).
2. Z: (6, 0) 18; (3, 1) 11; (0, 4) 8. Candidate minimum 8.
3. Half-plane 3x + 2y < 8: since 3x + 2y = 2(x + y) + x ≥ 8 for every feasible point, it has no common point with the region, so 8 is the minimum.

Answer: Minimum Z = 8 at (0, 4)

Multiple optimal solutions and infeasible problems

If the objective line is parallel to a boundary edge and the optimum occurs at two adjacent corners, every point on the segment joining them is optimal: infinitely many optimal solutions (so 'if an LPP has two optimal solutions, it has infinitely many'). If the constraints have no common region, the problem is infeasible: no feasible solution, hence no optimum. Not every LPP has an optimal solution.

Worked example

In the carpenter's problem, suppose the profits change to ₹300 per table and ₹100 per chair. Find the maximum profit and all the optimal production plans.

Try it first, then show the solutionSolution

1. Z = 300x + 100y at corners: A(20, 0) 6000; B(16, 12) 4800 + 1200 = 6000; C(0, 20) 2000; O 0.
2. Maximum 6000 at both A and B: the objective line is parallel to 3x + y = 60.
3. Every point on segment AB is optimal (in practice, integer points such as (18, 6) also give 6000).

Answer: Maximum ₹6000, attained at every point of the segment from (20, 0) to (16, 12)

Advantages, limitations and applications

Advantages: shows how to make the best use of limited resources; gives a clear, objective basis for decisions; reveals bottlenecks (binding constraints); adapts to changed conditions by re-solving. Limitations: assumes linear relationships and fixed, known data; handles only one objective at a time; may give fractional answers when items must be whole; the graphical method works only for two variables. Applications: production and product mix, diet planning, transport and distribution, investment portfolios, staff scheduling, agriculture (crop mix).

Worked example

Give one advantage and one limitation of linear programming, illustrated by the carpenter's problem.

Try it first, then show the solutionSolution

1. Advantage: it identifies the best mix (16 tables, 12 chairs) and shows both cutting and polishing time are fully used (binding constraints).
2. Limitation: it assumes each table always earns exactly ₹250 and uses exactly 3 h, whatever the quantity; if demand or prices change with quantity, the linear model fails.

Answer: Advantage: best use of limited time; limitation: linearity and certainty assumptions

Maths in real life: Linear Programming

Each concept, met in an everyday situation. Read the situation, try the problem, then check the solution. The one-line hook is what to remember.

Topics in this chapter

• Graphical Method of Solving an LPP
• Formulating Linear Programming Problems
• Unbounded and Infeasible Regions in LPP

Linear Programming formula sheet

General LPP (two variables)

$\text{Optimise }Z=ax+by\text{ subject to }{a}_{i}x+b_{i}y\le c_i(\text{or}\ge ),x,y\ge 0$

Corner point method

$Z_{opt}=\text{best of }Z\text{ at the corner points of the feasible region}$

Bounded region: max and min both exist.

Unbounded check (minimum m)

$\{ax+by<m\}\cap \text{feasible region}=\varnothing \Rightarrow m=Z_{min}$

For maximum M, test ax + by > M.

Intercepts of a constraint line

$px+qy=r:\left(\frac{r}{p},0\right),\left(0,\frac{r}{q}\right)$

Join them to draw the line.

Multiple optima

$Z(P)=Z(Q)=Z_{opt}\Rightarrow \text{every point of }PQ\text{ is optimal}$

Objective parallel to an edge.

Linear Programming: diagrams to practise

Practise each one on paper: draw it from the checklist, then tick off every label.

How the board asks Linear Programming

The question patterns to expect, and the method that works for each.

Tricks to remember Linear Programming

Short memory aids. Say each one aloud once, then use it on a question the same day.

• VOCS

  Variables, Objective, Constraints, Sign (non-negativity): the four parts of every formulation.

  Use it when: Formulating an LPP.

• Origin test

  Plug (0, 0) into each inequality: true → shade towards the origin, false → away.

  Use it when: Shading the right side.

• Corners carry the crown

  Optima live at corners; check every corner, not just the obvious one.

  Use it when: Corner point method.

• Unbounded? Test the half-plane

  For min m, the region Z < m must miss the feasible region.

  Use it when: Unbounded regions.

• Two winners means infinite winners

  Same Z at two adjacent corners: the whole edge is optimal.

  Use it when: Multiple optimal solutions.

Linear Programming: board-level solved questions

Ordered from board level to HOTS. Cover the solution, write your own, then compare step by step.

Case-study practice (Section D style)

Read the situation, then answer every part. In the board paper this is a 5-mark question split into 1 + 1 + 2 + 1 marks.

Where the marks are

How a typical answer is split into step marks. Show every step: a right final answer alone rarely earns full marks.

Where students lose marks in Linear Programming

The slips examiners see most often, and what to write instead.

• ✗Mistake: Wrong feasible region and corner points

  CISCE examiners' comments, 2024 and 2025: candidates could not identify the feasible region from the inequalities, identified wrong corner points, and graphed the inequalities unclearly.

  Wrong working

  Shades away from the origin for a '≤' constraint, giving the wrong corners.

  Right working

  Test (0, 0): for 3x + y ≤ 60, 0 ≤ 60 is true, so shade towards the origin.

  ✓Do this: Use the origin test for every constraint and label each line.

  Usually costs: 2-3 marks.

• ✗Mistake: Writing the wrong objective function

  CISCE examiners' comments, 2025: in a bookshelf problem asking for the maximum number of books, candidates wrote the objective function wrongly.

  Wrong working

  Maximise Z = 6x + 4y (total thickness) when the number of books is wanted.

  Right working

  Maximise Z = x + y (number of books); thickness and weight go into the constraints.

  ✓Do this: Read the last line of the question: it tells you what Z must measure.

  Usually costs: 2 marks (everything after it fails).

• ✗Mistake: Not checking an unbounded region

  A frequent error: the smallest corner value is declared the minimum without testing the half-plane.

  Wrong working

  Minimum = smallest corner value, no further check.

  Right working

  Test whether Z < m meets the feasible region; only if it does not is m the minimum.

  ✓Do this: Write the half-plane check in one line.

  Usually costs: 1 mark.

• ✗Mistake: Thinking every LPP has an optimal solution

  The 2027 specimen tests the statement 'every LPP has at least one optimal solution'; it is false.

  Wrong working

  An optimum always exists.

  Right working

  Infeasible problems have no solution, and unbounded regions may have no maximum (or minimum).

  ✓Do this: Remember the two exceptions: infeasible and unbounded.

  Usually costs: 1 mark.

Practice questions on Linear Programming

Write each answer on paper first. Open the hint only if you are stuck, and the answer only when you have finished.

1. Q1 · 1 mark · MCQBoard level

   The set of all points satisfying all the constraints of an LPP, including non-negativity, is called the:
   (a) objective region
   (b) feasible region
   (c) optimal set
   (d) infeasible region

   Hint

   Feasible solutions.

   Answer

   (b)

2. Q2 · 1 mark · MCQBoard level

   In an LPP, the constraints x ≥ 0, y ≥ 0 are called:
   (a) objective constraints
   (b) non-negativity restrictions
   (c) slack conditions
   (d) optimal conditions

   Hint

   Quantities cannot be negative.

   Answer

   (b)

3. Q3 · 1 mark · MCQBoard level

   The corner points of a bounded region are (0, 0), (6, 0), (4, 3), (0, 5). The maximum of Z = 4x + 6y is:
   (a) 24
   (b) 30
   (c) 34
   (d) 36

   Hint

   Evaluate at each corner.

   Answer

   (c) 34

4. Q4 · 1 mark · Very short answerBoard level

   State one limitation of linear programming.

   Hint

   Assumptions.

   Answer

   It assumes all relationships are linear and all data are known with certainty (or: it handles only one objective; may give fractional answers).

5. Q5 · 2 marks · Short answerBoard level

   The corner points of a bounded region are (2, 1), (6, 1), (4, 5). Find the minimum and maximum of Z = 3x − y.

   Hint

   Tabulate.

   Answer

   Z = 5, 17, 7: min 5 at (2, 1); max 17 at (6, 1).

6. Q6 · 2 marks · Short answerHarder board level

   Formulate (do not solve): a farmer has 50 hectares for wheat and rice. Wheat needs ₹4000/ha and gives ₹10 000/ha profit; rice needs ₹6000/ha and gives ₹14 000/ha; he has ₹2 40 000.

   Hint

   Land and money constraints.

   Answer

   Maximise Z = 10 000x + 14 000y subject to x + y ≤ 50, 4000x + 6000y ≤ 240 000 (i.e. 2x + 3y ≤ 120), x, y ≥ 0.

7. Q7 · 2 marks · Short answerHarder board level

   Show that the constraints x + y ≤ 2, x + y ≥ 5, x, y ≥ 0 have no feasible region. What does this mean for the LPP?

   Hint

   Parallel lines.

   Answer

   x + y cannot be both at most 2 and at least 5; the half-planes do not overlap, so the problem is infeasible and has no optimal solution.

8. Q8 · 2 marks · Short answerHOTS / competency

   For the region with corners (0, 0), (20, 0), (16, 12), (0, 20), find p in terms of q (p, q > 0) so that Z = px + qy is maximum at both (20, 0) and (16, 12).

   Hint

   Equate the two values.

   Answer

   20p = 16p + 12q ⇒ p = 3q

9. Q9 · 3 marks · Short answerHarder board level

   Minimise C = 50x + 40y subject to 3x + y ≥ 9, x + 2y ≥ 8, x, y ≥ 0.

   Hint

   Unbounded region; check the half-plane.

   Answer

   Corners (0, 9), (2, 3), (8, 0): 360, 220, 400; 50x + 40y < 220 does not meet the region, so min ₹220 at (2, 3).

10. Q10 · 3 marks · Short answerHarder board level

    Maximise Z = 5x + 3y subject to 3x + 5y ≤ 15, 5x + 2y ≤ 10, x, y ≥ 0.

    Hint

    Find the intersection carefully.

    Answer

    Corners (0, 0), (2, 0), (0, 3), (20/19, 45/19). Z = 0, 10, 9, 235/19 ≈ 12.37. Max 235/19 at (20/19, 45/19).

11. Q11 · 3 marks · Short answerHarder board level

    Give two advantages and two application areas of linear programming.

    Hint

    Resources, decisions.

    Answer

    Advantages: optimal use of scarce resources; objective, quantitative basis for decisions (also shows binding constraints). Applications: production planning (product mix), diet planning, transport scheduling, investment allocation.

12. Q12 · 5 marks · Long answerHarder board level

    A shopkeeper has ₹5000 to buy fans (₹300) and lamps (₹200), room for 20 items, and earns ₹25 per fan and ₹20 per lamp. Formulate and solve graphically to maximise profit.

    Hint

    Corner (10, 10).

    Answer

    Maximise Z = 25x + 20y subject to x + y ≤ 20, 3x + 2y ≤ 50, x, y ≥ 0. Corners (0, 0), (50/3, 0), (10, 10), (0, 20); Z = 0, 416.7, 450, 400. Maximum ₹450 with 10 fans and 10 lamps.

13. Q13 · 2 marks · Short answerHarder board level

    Is the feasible region of x + y ≥ 4, x + 3y ≥ 6, x, y ≥ 0 bounded or unbounded? Does Z = 3x + 2y have a maximum on it?

    Hint

    Can x grow forever?

    Answer

    Unbounded (it extends without limit in the first quadrant). Z has no maximum, since Z increases without bound as x or y increases.

Test your recall

Answer in your head or on paper first, then open the card. Pulling an answer out of memory makes it stick far better than re-reading.

1. 1.What is an objective function?Show answer

   The linear function Z = ax + by to be maximised or minimised.

2. 2.What is a feasible region?Show answer

   The common region of all constraints, including x, y ≥ 0.

3. 3.State the corner point theorem.Show answer

   On a bounded feasible region, the max and min of Z occur at corner points.

4. 4.When is an LPP infeasible?Show answer

   When no point satisfies all the constraints.

5. 5.What if two corners give the same optimum?Show answer

   Every point on the segment joining them is optimal.

6. 6.How do you test a minimum on an unbounded region?Show answer

   Check that the half-plane Z < m has no point in common with the feasible region.

7. 7.One application of LP?Show answer

   Production planning, diet, transport or investment.

8. 8.Up to how many non-trivial constraints are used in ISC graphical problems?Show answer

   Three.

Quick revision checklist

The night before the exam: can you do each of these without looking?

• ☐Can you define decision variables, objective, constraints and feasible region?
• ☐Can you formulate an LPP from a story with a data table?
• ☐Can you draw and shade constraints correctly?
• ☐Can you find all corner points, including intersections?
• ☐Can you apply the corner point method?
• ☐Can you handle an unbounded region correctly?
• ☐Can you recognise multiple optimal solutions and infeasibility?
• ☐Can you state two advantages and two limitations?

Linear Programming: frequently asked questions