Linear Programming

CBSE Class 12 Maths · 11 questions · 26 marks

Linear programming turns a real business or resource-allocation problem into a search for the best value of a linear objective function, subject to constraints that also happen to be linear. This chapter's central idea, the corner point theorem, means you never need to check the entire feasible region — only its vertices, found by graphing the boundary lines — to find the maximum or minimum, whether the goal is maximising profit or minimising cost.

Quick revision

A linear programming problem (LPP) has a linear objective function Z = ax + by to be maximised or minimised, subject to linear inequality constraints and the non-negativity restrictions x≥0, y≥0.
The feasible region is the set of all points satisfying every constraint simultaneously; it is always a convex region (a convex polygon when bounded).
Corner Point Theorem: if the feasible region is bounded, the optimal value of Z occurs at one of the corner (vertex) points of the feasible region.
To solve graphically: plot each constraint as a boundary line, shade the feasible region, identify all corner points, and evaluate Z at each.
If the feasible region is unbounded, a maximum or minimum may or may not exist; the value found at the corners must be checked against the rest of the region using the relevant half-plane of Z.
A feasible region can be empty (infeasible problem) if no point satisfies every constraint simultaneously.
If the objective function's line is parallel to one edge of the feasible region on the optimal side, every point of that edge — not just its endpoints — gives the same optimal value, producing multiple optimal solutions.
Constraints of the form ax+by≤c define the half-plane containing the origin when c>0 and the origin does not satisfy equality; constraints of the form ax+by≥c define the opposite half-plane.
Common real-world LPPs include maximising profit given resource limits (manufacturing) and minimising cost given nutritional or quality requirements (diet problems).

Important questions

1
MCQ1 mark
For the LPP: maximize Z = 3x + 4y subject to x+y≤4, x≥0, y≥0, the maximum value of Z is:
1. A.16
2. B.12
3. C.4
4. D.0
Answer
The maximum value is 16. The corner points of the feasible region are (0,0), (4,0) and (0,4). Z(0,0)=0, Z(4,0)=12, Z(0,4)=16. The largest of these is 16, at (0,4).
2
MCQ1 mark
The feasible region of a linear programming problem is always a:
1. A.Convex polygon
2. B.Circle
3. C.Concave polygon
4. D.Straight line
Answer
The feasible region is always a convex polygon (when bounded). Each linear constraint defines a half-plane, and the intersection of half-planes is always a convex set, since a straight line joining any two points of the region stays within it.
3
MCQ1 mark
In a linear programming problem, the optimal value of the objective function is attained at:
1. A.A corner point of the feasible region
2. B.The centroid of the feasible region
3. C.Any interior point
4. D.The origin always
Answer
The optimal value is attained at a corner point of the feasible region. This is the Corner Point Theorem: for a bounded feasible region, the maximum or minimum of a linear objective function always occurs at one of the vertices, not at an interior point.
4
MCQ1 mark
If the feasible region of an LPP is unbounded, then the maximum value of Z=ax+by (with a,b>0):
1. A.May or may not exist
2. B.Always exists
3. C.Never exists
4. D.Always exists at the origin
Answer
The maximum value may or may not exist. On an unbounded feasible region, Z can sometimes increase without limit as x or y grows, in which case no maximum exists; in other cases the region's shape does cap Z, in which case a genuine maximum can be found. Each unbounded case must be checked individually.
5
Assertion & Reason1 mark
Assertion (A): For the LPP maximize Z = x + y subject to x+y≤4, x≥0, y≥0, the maximum value Z=4 is attained at every point of the line segment joining (4,0) and (0,4), not just a single corner. Reason (R): This happens because the objective function's line x+y=4 coincides with one of the boundary edges of the feasible region, so the entire edge is optimal.
1. A.Both A and R are true and R is the correct explanation of A
2. B.Both A and R are true but R is not the correct explanation of A
3. C.A is true but R is false
4. D.A is false but R is true
Answer
Both A and R are true and R is the correct explanation of A. The constraint boundary is exactly x+y=4, which is the same line as the objective function Z=x+y=4. So every point on the segment from (4,0) to (0,4) satisfies Z=4, and since this is the largest value Z takes over the whole feasible region, all these points are simultaneously optimal. Reason R correctly explains why this coincidence of lines produces multiple optimal solutions, matching Assertion A.
6
Short answer2 marks
Find the corner points of the feasible region determined by x≥0, y≥0, x+y≤6, and evaluate Z=5x+3y at each. State the maximum value.
7
Short answer2 marks
Find the corner points of the feasible region determined by x≥0, y≥0, x+2y≤8, and evaluate Z=3x+2y at each. State the maximum value.
8
Short answer3 marks
A feasible region has corner points (0,0), (5,0), (3,4) and (0,6). If Z = 4x + 6y, find the maximum and minimum values of Z over this region.
9
Long answer5 marks
A furniture dealer has ₹50,000 to invest and storage space for at most 60 pieces of furniture. A table costs ₹2500 and a chair costs ₹500. He estimates a profit of ₹250 on a table and ₹75 on a chair. Formulate this as an LPP to maximize profit and solve it graphically.
10
Long answer5 marks
Minimize Z = 200x + 500y subject to the constraints x+2y≥10, 3x+4y≤24, x≥0, y≥0. Find the minimum value graphically.
11
Case study4 marks
Read the following and answer the questions that follow: A dietician wants to plan a diet containing at least 8 units of vitamin A and at least 10 units of vitamin B, using two food items. Each unit of Food 1 supplies 2 units of vitamin A and 1 unit of vitamin B, and costs ₹5. Each unit of Food 2 supplies 1 unit of vitamin A and 2 units of vitamin B, and costs ₹7. (a) Formulate the LPP to minimize cost, writing the objective function and constraints. (b) Find the corner points of the feasible region. (c) Evaluate the objective function at each corner point. (d) State the minimum cost and the corresponding quantities of Food 1 and Food 2.

Run out of questions?

RowQ generates fresh questions on Linear Programming, marks your answers, and explains every step.

Start free

Linear Programming

CBSE Class 12 Maths · 11 questions · 26 marks

Quick revision

A linear programming problem (LPP) has a linear objective function Z = ax + by to be maximised or minimised, subject to linear inequality constraints and the non-negativity restrictions x≥0, y≥0.

The feasible region is the set of all points satisfying every constraint simultaneously; it is always a convex region (a convex polygon when bounded).

Corner Point Theorem: if the feasible region is bounded, the optimal value of Z occurs at one of the corner (vertex) points of the feasible region.

To solve graphically: plot each constraint as a boundary line, shade the feasible region, identify all corner points, and evaluate Z at each.

If the feasible region is unbounded, a maximum or minimum may or may not exist; the value found at the corners must be checked against the rest of the region using the relevant half-plane of Z.

A feasible region can be empty (infeasible problem) if no point satisfies every constraint simultaneously.

If the objective function's line is parallel to one edge of the feasible region on the optimal side, every point of that edge — not just its endpoints — gives the same optimal value, producing multiple optimal solutions.

Constraints of the form ax+by≤c define the half-plane containing the origin when c>0 and the origin does not satisfy equality; constraints of the form ax+by≥c define the opposite half-plane.

Common real-world LPPs include maximising profit given resource limits (manufacturing) and minimising cost given nutritional or quality requirements (diet problems).

Important questions

MCQ1 mark

For the LPP: maximize Z = 3x + 4y subject to x+y≤4, x≥0, y≥0, the maximum value of Z is:

A.16
B.12
C.4
D.0

MCQ1 mark

The feasible region of a linear programming problem is always a:

A.Convex polygon
B.Circle
C.Concave polygon
D.Straight line

MCQ1 mark

In a linear programming problem, the optimal value of the objective function is attained at:

A.A corner point of the feasible region
B.The centroid of the feasible region
C.Any interior point
D.The origin always

MCQ1 mark

If the feasible region of an LPP is unbounded, then the maximum value of Z=ax+by (with a,b>0):

A.May or may not exist
B.Always exists
C.Never exists
D.Always exists at the origin

Assertion & Reason1 mark

Assertion (A): For the LPP maximize Z = x + y subject to x+y≤4, x≥0, y≥0, the maximum value Z=4 is attained at every point of the line segment joining (4,0) and (0,4), not just a single corner. Reason (R): This happens because the objective function's line x+y=4 coincides with one of the boundary edges of the feasible region, so the entire edge is optimal.

A.Both A and R are true and R is the correct explanation of A
B.Both A and R are true but R is not the correct explanation of A
C.A is true but R is false
D.A is false but R is true

Short answer2 marks

Find the corner points of the feasible region determined by x≥0, y≥0, x+y≤6, and evaluate Z=5x+3y at each. State the maximum value.

Short answer2 marks

Find the corner points of the feasible region determined by x≥0, y≥0, x+2y≤8, and evaluate Z=3x+2y at each. State the maximum value.

Short answer3 marks

A feasible region has corner points (0,0), (5,0), (3,4) and (0,6). If Z = 4x + 6y, find the maximum and minimum values of Z over this region.

Long answer5 marks

A furniture dealer has ₹50,000 to invest and storage space for at most 60 pieces of furniture. A table costs ₹2500 and a chair costs ₹500. He estimates a profit of ₹250 on a table and ₹75 on a chair. Formulate this as an LPP to maximize profit and solve it graphically.

Long answer5 marks

Minimize Z = 200x + 500y subject to the constraints x+2y≥10, 3x+4y≤24, x≥0, y≥0. Find the minimum value graphically.

Case study4 marks

Read the following and answer the questions that follow: A dietician wants to plan a diet containing at least 8 units of vitamin A and at least 10 units of vitamin B, using two food items. Each unit of Food 1 supplies 2 units of vitamin A and 1 unit of vitamin B, and costs ₹5. Each unit of Food 2 supplies 1 unit of vitamin A and 2 units of vitamin B, and costs ₹7. (a) Formulate the LPP to minimize cost, writing the objective function and constraints. (b) Find the corner points of the feasible region. (c) Evaluate the objective function at each corner point. (d) State the minimum cost and the corresponding quantities of Food 1 and Food 2.