CHAPTER

12 Linear Programming
 Previous Years' CBSE Board Questions
12.2 Linear Programming Problemand the maximum value is
(c) 25 (d) 30
its Mathematical Formulation (a) 0 (b) 4
(Term 1, 2021-22) Ap
MCQ 9. The corner points of the feasible region determined
Which of the following points satisfies both the by the system of linear inequalities are (0. O). (4. 0).
inequations 2x +y< 10 and x+2y>8? (2. 4) and (0, 5). If the maximum value of z ax + by,
ia) (-2,4) (b) (3,2) (c) (-5,6) (d) (4,2) where a, b >0 occurs at both (2, 4) and (4, 0). then
(2023)(U (a) a=2b (b) 2a=b
2 The solution set of the inequation 3x + 5y <7 is (c) a=b (d) 3a =b (2020) U
(a) whole xy-plane except the points lying on the 10, In an LPP, if the objective function 2 =ax +by has the
line 3x + 5y=7. same maximum value on two corner points of the
(b) whole xy-plane along with the points lying on feasible region, then the number of points at which
the line 3x +5y =7. Zmax 0CCUrs is
(c) open half plane containing the origin except the (a) 0 (b) 2 (c) finite (d) infinite
points of line 3x +5y=7. (2020) U)
(d) open half plane not containing the origin.
11, The feasible region for an LPP is shown below:
(2023) U Let z = 3x - 4y be the objective function. Minimum
3 If the corner points of the feasible region of an LPP
of z occurs at
are (0,3), (3, 2) and (0,5), then the minimum value of
YA
Z= 11x + 7y is (4.10)
(a) 21 (b) 33 (c) 14 (d) 35
(Term l, 2021-22) (Ev) 8
(0. l 6 . 8 )
The number of solutions of the system of
inequations x+ 2y s 3, 3x +4y >12, x >0,y> 1 is 8Gis 6.5)
(a) 0 (b) 2 (c) finite (d) infnite,
(Term 1, 2021-22)(U}
5. The màximum value of Z = 3x + 4y subject to the (0,0) (5,0)
constraints x>0, y 20 and x+ys 1 is (a) (0,0)
(a) 7 (b) 4 (c) 3 (b) (0,8)
(d) 10 (c) (5,0) (d) (4, 10)
(Term 1, 2021-22) Ev
6. The feasible region of an LPP is given in the following
(NCERT Exemplar, 2020) Ap
figure 12. The graph of the inequality 2x +3y >6 is
(a) half plane that contains the origin
N0, 104) (b) half plane that neither contains the origin nor
the points of the line 2x + 3y =6.
(0,38) (c) whole XOY-plane excluding the points on the
line 2x+3y= 6.
(d) entire XOY-plane. (2020)(U)
13. The objective function of an LPP is
(52,0)\(76.,O)N (a) aconstant
(b) a linear function to be optimised
Then, the constraints of the LPP are x >0, y >0 and (c) an inequality
(a) 2x +ys 52and x + 2y<76 (d) aquadratic expression (2020)(R
(b) 2x + ys 104 and x + 2y s 76 SA II (3 marks)
(c) x+2ys 104 and 2x + y s 76
(d) x+2y <104 and 2x + ys 38 14. Solve the following linear programming problem
(Term I1, 2021-22) Ap) graphically:
7. If the minimum value of an objective function Maximise z= -3x - 5y
Z= ax + by occursat two points (3, 4) and (4, 3) then Subject to the constraints
(a) a+b=0 (b) a =b -2x + ys4
(c) 3a =b (d) a= 3b
(Term I, 2021-22) (U) X+y3
8. For the following LPP, maximise Z =3x +4y subject X- 2ys 2,
toconstraints x - y 2 -1, xs 3, x >0, y 20 X>0, y> 0. (2023) EV)
 LÀI (4 marks) 18. Solve the following LPP graphically:
Minimise Z= 5x+ 10y
15. Solve the following linear progranmming problem
graphically: Subject to constraints x+2ys 120, x+y> 60.
Maximize z = 3x + 9y X-2y20 and x, y> 0
Subject to constraints (NCERT Exemplar, Delhi 2017) E
X+3y< 60 19. Maximise Z=x +2y
X+ y> 10 Subject to the constraints:
X<y x+2y> 100,2x -y <0, 2x +ys 20, x, y>0
X, y0 (2021) (Ev Solve the above LPP graphically.
16. The corner points of the feasible region determined by (NCERT, AI 2017) Ev
the system of linear inequations are as shown below: LA II (5/6 marks)
y
20. Solve the following linear programming problem
4+ C(3, 4) graphically.
Maximize:P=70x+ 40y
34 Subject to :3x +2ys9, 3x +y s 9, x>0, y2 0.
DI0,2) K BI5, 2) (2023) E
1
21. Solve the following linear programming problem
graphically.
A4,0)
Minimize:Z=60x +80y
2 4 5 6 7
Subject to constraints:
Answer each of the following: 3x + 4y >8
() Let z = 13x - 15y be the objective function. Find 5x + 2y> 11
the maximum and minimum values of z and also X,y0 (2023) Cr
the corresponding points at which the maximum
and minimum values occur. 22. Find graphically, the maximum value of z = 2x + 5y,
(i) Let z = kx + y be the objective function. Find k, if subject to constraints given below:
the value of z at A is same as the value of z at B. 2x + 4ys8, 3x + ys6, x+ys4; x> 0, y20
(2021) (Delhi 2015) (Ev
17. Solve the following LPP graphically : 23. Maximise z = 8x +9y subject to the constraints given
Minimize z= 5x+7y below:
Subject to the constraints 2x +3y<6,3x- 2y s6,ys1; x, y>0
2x + y>8, x+2y> 10, x, y>0 (2020) Ev (Foreign 2015) Ev
 Detailed SOLUTIONS
Previous Years' CBSE Board Questions
1. (d):We have, 2x+y< 10 andx +2y>8
Let us check which of the given points satisfy the given B(O,
inequation one by one.
(a) (-2,4) (0,0) O A(1,0)
2x(-2) + 4= -4+4=0<10
and -2+2 x4=-2+8=6 8
(b) (3, 2)
2x3+2=6+2 =8s 10
3+2x2=3+4=7 8
The shaded portion OAB is the feasible region, where
(c) (-5,6)
O0,0), A(1,0) and B(0, 1) are the corner points.
2x(-5) +6=-10 +6= -4<10 At O(0,0), Z= 3x0+ 4x0=0
AtA(1,0), Z=3x1+4x 0=3
-5+2x6=-5+12 =78 At B(0, 1), Z=3x0+ 4x 1=4
(d) (4,2)
2x4+2=10< 10;4+2x2 =8>8 . Maximum value of Z is4, whichóccurs at B(0,1).
(4. 2)satisfy both the inequations. Concept Applied (G)
2. (c): Given inequation is 3x +5y <7
Let us draw thegraph of 3x +5y =7 Any point in the feasible region of a linear
2.33 programming problemthat gives the optimal value
1.4 4 (maximum or minimum) of the objective function is
called an optimal solution.
3
Substitute, x = 0 and 20,14) 6. (b): Clearly, the pair of points given in graph, and
y= 0 in the inequation, 1 (0, 104);: (52, 0) and (0, 38); (76,0) satisfy thecorresponding
we get (2.33, 0) equations given in option(b) i.e., 2x+ y< 104 and
3(0) +5(0) <7 x+2ys 76.
i.., 0<7 which is true. 1 2 3.4
7. (b):Since, minimum value of Z = ax + by occurs at two
The solution set
of the inequality is 3x +5y =7
points (3,4) and (4, 3).
3a +4b= 4a+3b q=b
an open half plane
containing the origin 8. (c): Given, Z=3x +4y
except the points on Subject to constraints, x-y-1, x<3; x> 0,y 20
line 3x +5y=7.
3. (a): Given, Z=11x+ 7y B(3,4)
At (0, 3),Z=11 x0+7x3 =21
At(3, 2), Z=11 x3+7x2 =47 A(0, 1)|
At (0,5), Z= 11 x0+7x5=35
Thus, Zis minimum at (0,3) and minimum value of Z is 21. C(3,0)
4. (a):Given,
x+2ys3, 3x +4y >12, x>0, y21
The graph of given constraints isshown here.
The shaded region OABC is the feasible region, where
corner points are O(0, 0), A(0, 1), B(3, 4) and C(3, 0)
x*2(0,y 1.5=3 No,3) 3x +4y =12
y=1
At O(0,0), Z=3(0) + 4(0) =0
AtA (0, 1), Z= 3(0)+4(1) =4
(0, 1)| At B(3,4),Z= 3(3) +4 (4) =25
X N4.0)
(3, 0) AtC(3,0),Z =3(3) +4 (0) =9
Maximum value of Zis 25, which occurs at B(3, 4).
Since, there is no common region, so, no solution exists. 9. (a):Since, maximum value of z=ax+by occurs at both
Key Points (2,4) and (4,0).
2a + 4b = 4a+0 =4b=2a ’ 2b= a
A
feasible region is an area defined by aset of
coordinates that satisfy asystem of inequalities. 10. (d) : In an LPP, if the objective function z =ax +bY
has the same maximum value on two corner points of the
5. (b): We have to maximise Z= 3x+ 4y feasible region, then the number of points at which Zmax
Subject to constraints, x20, y20 andx +ys1 Occurs is infinite.
 bnow that minimum of objective function The shaded region ABCO is the feasible region and is
corner points. region are
sat
xcUrS
bounded. The corner points af the foasible
Cornerpoints Value of23x- 4y A(0. 10),B. 5), C15. 15) and DIO, 20)
(0,0)
(5,0) 15
(6,5) -2
(6.8) -14 DO. 20)
C15. 15)
(4,10) -28
(0.8) -324-Minimum KB(5. 5) (60,0)
X
(b):From tthe graphnof inequality 2x + 3y>6.Itis clear
12
doesSnot contain theeorigin nor the points of the line
*+3y 60
thatit (10.0)
+3y=6. X+y= 10

Corner Points Value of 2-3x +9y

J(, 2) A(0, 10) 90
B
B(5, 5) 60
(3,0) C(15, 15) 180 Maximum(Multiple
A
D(0, 20) 180 optimal solutions)
linear function to be optimized is called an
13. (b):A The maximum value of Z on the feasible region occurs
at
obiectivefunction. D{0, 20) and it is 180
the two corner points C(15. 15) and
44 We have, maximise z=-3x - 5y ineach case.
Convertingthe giveninequations into equations, we get z= 13x-15y
16. () Corner Points
-2x+y= 4 .)
x+y=3 .() O(0,0)
x-2y=2 ..i) A(4,0) 52 (Maximum)
B(5,2) 35
C3,4) -21
X+2y =2 D(0, 2) -30 (Minimum)
JA(0,4) Thus, maximum value of Z is 52 at A(4, 0) and minimum
Co, 3) 8 1) value of Zis -30 at D(0,2)
O0,0 (ii) Since value ofz = kx +y at A(4,0) is same as the value
of Zat B(5, 2).
D(3, 0) k- 4+0=k-5+2’ 4k= 5k+2’k=-2
xty=3
17. We have, minimize z =5x + 7y,
Subject to constraints, 2x + y>8,x +2y> 10, x, y20
We draw the graph of these lines.
To solve LPP graphicaly, we convert inequations into
equations.
As, x20, y>0 so the solution lies in first quadrant.
From graph, corner point of feasible region are A(0., 4), NoW,l,: 2x +y=8,,:x+ 2y =10 and x=0, y=0
BI8/3, 1/3) and C(0, 3) I, and I, intersect at E(2, 4).
The value of zat these corner points are shown as: Let us draw the graph of these equations as shown below.
Corner points z=-3x- 5y YA

A(0,4) -20
B(8/3, 1/3) -29/3 -Maximum 8DIO, 8)
C(0,3) -15
C(0, 5)
Hence maximum value of z= -29 E(2,4)
3
15. We have, maximize z = 3x+ 9y
Subject toconstraints, x +3y<60, x+y2 10, x<y, x, y20 B(10, 0)
O SOlve L.PP. graphically, we convert inequations into X ol i23 456 7 910 ,
equations. 5x +7y =38
4ix+3y= 60, I,:x+y= 10,I3 :X =y,x=0and y=0 The corner points of the feasible region are D(0, 8),
2and l, intersect at (5.5). I, and l, intersect at (15, 15). B(10,0) and E(2, 4).
 Corner points Value of z= 5x +7y I,:x+ 2y =100
I,: 2x- y=0
D(0,8) 56
la:2x +y =200
B(10, 0) 50
l,:x=0
E(2,4) 38 (Minimum) and I5:y=0
From the table, we fnd that 38 is the minimum value of z at By intercept form, we get
E(2,4). Since the region is unbounded, so we draw the graph
of inequality 5x +7y <38 to check whether the resulting X=1
1'100 50
open half plane has any point common with the feasible The linel, meets the coordinate axes at (100,0) and (o0. 501
region. Since it has no point in common. So, the minimum
value of z is obtained at E(2, 4) and the minimum value of:2x=y
z=33. ’ The line l, passes through origin and cuts lË and I, a
Answer Tips (20,40) and (50, 100) respectively.
3If the region is unbounded, then a maximum or 100 200
minimum value of the objective function may not exist.
Ifit exists, it must occurat acorner point of region. The line l3 meets the coordinates axes at (100,0) and
(0, 200).
18. We have, Minimise Z=5x+ 10y, l4:x=0isthe y-axis, l,:y =0 is the x-axis
Subject toconstraints:
X+ 2y<120
X+y>60 200 C(0, 200)
X-2y>0 and x, y> 0
To solve LPP graphically, we convert inequations into 180\3
equations. 160
1,:x+2y =120,I,:x ty=60,1 :x-2y =0 and x=0,y=0 140
l,and l, intersect at E(0, 60), 1, and I, intersect at C(60,30),
I, and I, intersect at D[40, 20). 120
The shaded region ABCD is the feasible region and is bounded. 100 B(50,100)
The corner points of the feasible region are A(60,0), B(120,0),
C|60, 30) and D(40, 20). 80

60 D
(0,50)
120 40+

100+ 20+ 20,40)

80 + D(40, 20) (100,0) >X

E(0, 60) (0.0)/0 20 40 60 80 109, 120

40
CI60,30) Now, plotting the above points on the graph, we get
20 the feasible region of the LPP as shaded region ABCD. The
A(60,0) B(120, 0)
+x coordinates of the corner points of the feasible region
20 40 60\80 100 120 140 160 ABCD are A(20,40),B(50, 100), C(0, 200), DÊ0, 50).
Now, ZA =20+2 x40= 100
Za= 50 +2x 100 = 250, Z =0+2x 200= 400
Corner points Value of Z= 5x+ 10y Z =0+2 x 50 = 100
A(60, 0) 3004-(Minimum) Zis maximum at C(O, 200) and having value 400.
B(120,0) 600
C(60, 30) 20. We have, maximize P= 70x + 40y
600
DI40, 20) 400
Subject to:3x+2y<9
3x +ys9
Hence, Zis minimum at A(60, 0) i.e., 300. X>0,y>0
Commonly Made Mistake (A Convert allinequations into equation, we get
Remember to convert inequations into equations, 3x + 2y = 9 ...()
3x +y=9 ..(i)
19. Maximise Z =X+ 2y, Subject to constraints: X=0 and y=0
x+ 2y> 100, 2x - y<0, 2x+ y< 200 and x, y>0. Solving (i) and (i), we get
Converting the inequations into equations, we obtain the x=3, y =0
lines So, point of intersection of equation (i) and (ii) are (3,0).
 and check whether the resulting half plane has points in
Common with the feasible region or not.
(0,9) hrom graph, it can be seen that feasible region has no
Common point with 3x +4y <8
Minimum value of Z is 160 at the line joining the
points (8/3, 0) and (2, 1/2).
(0,9/2) 22. Letl,:2x +4y =8,1,:3x +y=6,la:x+y= 4;x*0,y=0
Solving l, and l, we get
(3, 0)
3 + 2y =9
3x +y=9
6

givensshaded region isthe feasible region.

The Corner points of the feasible region are O(0, 0),
4
The 3
B(3,0).
AIO.9/2)and A(0,2) 2 86
Cornerpoints Value ofp=70x+40y ais ic 14
000) 70 x0+ 40 x 0 =0 X |(204
(0,0),0 i 2l 3
A(0912) 70 x 0+ 40x 2 - 180
Shaded portion OABC is the feasible region, where
BI3,O) 70x3+40 x0 =210 (maximum) cOordinates of the corner points are O0, 0), A(0, 2),
So. Pis maximum at point B|3, 0).
BEEC2, 0)
1. We have, minz =60x +80y: The value of objectivefunction at these points are:
Subject to constraints :
3x +4y2 8,5x+ 2y>11; x,y>0 Corner points Value of the objective functionz=2x+5y
|O(0,0) |2x0+5x0=0
A(0,2) 2x0+5x2 =10(Maximum)
CIO 112) 86) 8 6
2x+5+5x-92
C(2,0) 2x2+5x0= 4
J0,2) The maximum value of z is 10, which is at A(0,2).

A(8/3,0) Concept Applied (G)

Ifthe region is bounded then the objective function Z
has both maximum and minimum value of region.
(11/5,0) 3x+ 4y =8
23. Let l:2x +3y=6,lh:3x-2y =6, l3:y =1; x=0,y=0
5x +2y=11 AY
y
Hrom graph,it is clear that feasible region is unbounded.
Ihe corner point of the feasible region are A(8/3, 0),
B(2, 1/2) and C|0, 11/2).
Ihe value of Zat these corner points are as follows: 1 D(1.5,1),
A(0,1) 30 6 3
Corner Points Z= 60x +80y B(2,0)13'13) ’X
(0,0) O
A(8/3,0) 160 1 /2 3

B(2, 1/2) 160

}(Minimum)
C(0, 11/2) 440
Asthe feasible region is unbounded, Solving l, and l, We get D(1.5, 1)
l60 may or may not be the minimum value of Z. 30 6
0, we graph the inequality 60x +80y <160 ie, 3x +4y <8
Solving |, and l, we get C|aa
Shaded portion OADCB is the feasible region, where
coordinates of the corner points are O(0, 0), A(0, 1),
D(1.5, 1), c30 6 ,B(2, 0).
The value of the objective function at these points are :

Corner points Value of the objective function

Z= 8x+ 9y
O
(0,0) 8 x0+9x0=0
A (0, 1) 8x0+9x1=9
D(1.5, 1) 8x 1.5 +9x1=21
30 6 30 6
c 8x+9x=22.6 (Maximum)
13 13. 13 13

B(2,0) 8x2+9 x0= 16

30 6
The maximum value of z is 22.6, which is at C
13'13)
Commonly Made Mistake (A
Remember the difference between feasible solutions
and infeasible solutions.