Chapter 12 · Linear Programming

Linear Programming

2 topics 66 practice questions

Chapter Overview

Businesses, farms and kitchens constantly ask “how much of each should we make or buy to get the best result under our limits?” Linear programming answers such questions when the goal and the limits are linear. In this chapter you will learn the vocabulary, translate word problems into mathematical form, and solve two-variable problems by the graphical (corner-point) method.

Board focus: One 5-mark graphical LPP (formulate, draw, tabulate corner points, conclude) is expected every year, often with a case study or an MCQ on corner points.

How to study Linear Programming

What this chapter covers

Linear programming is about making the best decision when resources are limited. You will learn the terms used (decision variables, objective function, constraints, feasible region, optimal solution), turn a word problem into a linear programming problem, and solve it graphically by evaluating the objective function at the corner points of the feasible region.

None of the rationalised topics is in this chapter, so formulation and the graphical method are both fully in scope. The problems are limited to two variables, which is why a graph is enough.

How it is assessed

The chapter forms its own unit, Linear Programming, worth 5 marks. A full problem with formulation, graph and corner-point table fits naturally as a long answer or a case-based question, while MCQs and Assertion-Reason items can test corner points, feasible regions and the conditions for an optimal value. The question pattern described here is the one this site follows; always confirm it in the latest official sample paper at cbseacademic.nic.in.

How to study it

  1. Learn the vocabulary on terminology and formulation and practise writing constraints from word problems, including \(x\ge 0,\ y\ge 0\).
  2. Draw each constraint line using its intercepts and test the origin to choose the correct side.
  3. On graphical method, shade the feasible region and solve pairs of equations to find corner points.
  4. Make a table of the objective function at every corner point and pick the optimal value.
  5. Practise unbounded regions and check whether the optimum actually exists.

Key tip: For an unbounded feasible region, the corner-point value is only a candidate. To confirm a minimum value \(m\) of \(Z=ax+by\), check that the half-plane \(ax+by<m\) has no point in common with the feasible region; for a maximum \(M\), check \(ax+by>M\).

Topics

  1. 1 Terminology and Formulation 24 questions
  2. 2 Graphical Method of Solution 42 questions

Key Concepts

  • An LPP optimises a linear objective function \(Z=px+qy\) subject to linear constraints and \(x,y\ge0\).
  • The set of points satisfying all constraints is the feasible region; its corners are the corner points.
  • Corner-point theorem: if an optimum exists, it occurs at a corner point of the feasible region.
  • A bounded region always has both a maximum and a minimum; for an unbounded region, test the open half-plane beyond the candidate value.

Formulas

Standard form of an LPP

Linear Programming · Terminology and Formulation

\[\text{Optimise } Z=px+qy\ \text{ subject to }\ a_ix+b_iy\ (\le,\ \ge)\ c_i,\quad x\ge0,\ y\ge0\]

Corner-point theorem

Linear Programming · Graphical Method of Solution

If an LPP has an optimal value, it is attained at a corner point of the feasible region. A bounded feasible region always has both a maximum and a minimum value of \(Z\).

Key Points

Testing a half-plane

Linear Programming · Graphical Method of Solution

To decide which side of \(ax+by=c\) to shade, substitute a point not on the line (usually the origin). If it satisfies the inequality, shade its side.

Multiple optimal solutions

Linear Programming · Graphical Method of Solution

If \(Z\) has the same optimal value at two adjacent corners, all points on the edge joining them are optimal.

Common Mistakes

Reversing inequalities

Linear Programming · Terminology and Formulation

“At least” means ≥ and “at most” means ≤. Reversing one inequality changes the whole feasible region.

Concluding too early on an unbounded region

Linear Programming · Graphical Method of Solution

On an unbounded region the largest value in the table need not be a maximum. Draw \(px+qy>M\) and check whether it meets the region.

Solved Examples

Potter’s problem

Linear Programming · Graphical Method of Solution

Maximise \(Z=60x+90y\) subject to \(x+2y\le16,\ x+y\le10,\ x,y\ge0\).

Practice & Tests

Chapter Practice

Untimed mixed questions from all topics. Answers are revealed after you submit.

Start Practice

Chapter Test

Timed test – about 15 questions in 30 minutes.

Start Test

Unit Test – Linear Programming

A 90-minute board-style test on the whole unit “Linear Programming”, drawn fresh from the question bank for every attempt.

Start Test

Linear Programming – Chapter Test

A board-style chapter test drawn fresh from the question bank each time: MCQs, assertion-reason, numericals, written answers you self-check against model solutions, and a case study.

Start Test

Further reading

Linear Programming – Frequently Asked Questions

What if two corner points give the same maximum value?

Then every point on the line segment joining those two corner points is also optimal, so the problem has infinitely many optimal solutions.

Why do we include \(x\ge 0\) and \(y\ge 0\)?

Decision variables usually stand for quantities such as numbers of items or hours, which cannot be negative. These non-negativity constraints keep the feasible region in the first quadrant.

Which part of the chapter needs most practice?

Formulation from a word problem, because a wrong constraint makes everything after it wrong. Read each sentence and translate it into one inequality.

How should I revise this chapter?

Solve a few complete problems on graph paper, from formulation to the corner-point table. Label every line and corner point clearly so the examiner can follow your work.