Linear Programming

Download CBSE Class 12th Standard CBSE Maths question papers, sample papers, important questions, and previous year solved papers in PDF format. Get free study materials, NCERT solutions, and exam preparation resources for Class 12th Standard CBSE Maths

Questions:

True or False

1 x 1 = 1

The objective function is maximum or minimum, which lies on the boundary of the feasible region.

Generic 3

14 x 3 = 42

Two tailors A and B earn Rs. 150 and Rs. 200 per day respectively. A can stitch 6 shirts and 4 pants while B can stitch 10 shirts and 4 pants per day. How many days shall each work if it is desired to produce (at least) 60 shirts and 32 pants at a minimum labour cost? Make it an LLP and solve the problem graphically.

(Manufacturing Problem) A manufacturing company makes two types of teaching aids A and B of Mathematics for class XII. Each type of A requires 9 labour hours of fabricating and 1 labour hour for finishing. Each type of B requires 12 labour hours for fabricating and 3 labour hours for finishing. For fabricating and finishing, the maximum labour hours available per week are 180 and 30 respectively. The company makes a profit of Rs. 80 on each piece of type A and Rs. 120 on each piece of type B. How many pieces of type A and B should be manufactured per week to get maximum profit? Make it as an LPP and solve graphically. What is the maximum profit per week?

A furniture firm manufactures chairs and tables, each requiring the use of three machines -A, B and C. Production of one chair requires 2 hours on machine C. Each table requires 1 hour each on machine A and B and 3 hours on machine C. The profit obtained by selling one chair is Rs. 30 while by selling one table the profit is Rs. 60. The total time available per week on machine A is 70 hours, on machine B is 40 hours and on machine C is 90 hours. How many chairs and tables should be made per week so as to maximize profit? Formulate the problem as LLP and solve it graphically.

Kellogg is a new cereal formed of a mixture of bran and rice that contains at least 88 grams of protein and at least 56 milligrams of iron. Knowing that bran contains 80 grams of protein and 40 milligrams of iron per kilogram, and that rice contains 100 grams of protein and 30 milligrams of iron per kilogram, find the minimum cost of producing this new cereal if bran costs Rs. 5 per kilogram and rice costs Rs. per kilogram.

Minimize and Maximize Z = 5x + 2y, subject to the following constraints:
\(x-2y\le 2,3x+2y\le 12,-3x+2y\le 3,x\ge 0,y\ge 0.\)

Verify that the following problem has no feasible solution:
Maximize Z = 4x₁+ 4x_2,subject to the constraints:
\(2x_{ 1 }3x_{ 2 }\le 18,x_{ 1 }+x_{ 2 }\ge 12,x_{ 1 },x_{ 2 }\ge 0.\)

A company manufactures two types of novelty souvenirs made of plywood. Souvenirs of type A require 5 minutes each for cutting and 10 minutes each for assembling. Souvenirs of type B require 8 minutes each for cutting and 8 minutes each for assembling. There are 3 hours 20 minutes available for cutting and 4 hours for assembling. The profit is Rs. 5 each for type A and Rs. 6 each for type B souvenirs. How many souvenirs of each type should be company manufacture in order to maximise the profit?

A factory makes tennis rackets and cricket bats. A tennis racket takes 1.5 hours of machine time and 3 hours of craftman's time in its making while a cricket bat takes 3 hours of machine time and 1 hour of craftman's time. In a day, that factory has the availability of not more than 42 hours of machine time and 24 hours of craftman's time.
(i) What number of rackets and bats must be made if the factory is to work at full capacity?
(ii) If the profit on a racket and on a bat is Rs. 20 and Rs. 10 respectively, find the maximum profit of the factory when it works at full capacity

10.

Reshma wishes to mix two types of food P and Q in such a way that the vitamin contents of the mixture contain at least 8 units of vitamin A and 11 units of vitamin B. Food P costs Rs. 60/kg and Food Q costs Rs. 80/kg. Food P contains 3 units/kg of Vitamin A AND 4 units/kg of vitamin B. Food Q contains 5 units/kg Vitamin A and 2 units/kg of vitamin B. Determine the minimum cost of the mixture.

11.

Solve the following Linear Programming Problems graphically:
Minimise Z = x + 2y
subject to 2x + y ≥ 3, x + 2y ≥ 6, x, y ≥ 0.

12.

Solve the following Linear Programming Problem graphically:
Minimise Z = – 3x + 4 y
subject to constraints
\(x+2 y \leq 8,3 x+2 y \leq 12\)
and \(x, y \geq 0 \text {. }\)

13.

Solve the following Linear Programming Problems graphically:
Maximise Z = 3x + 4y
subject to the constraints:
\(x+y\le 4,x\ge 0,y\ge 0.\)

14.

(Manufacturing Problem) A manufacturer has Three machines I,II and III installed in his factory. Machines I and II are capable of being operated for at most 12 hours whereas machine III must be operated for at least 5 hours a day. She produces only two items M and N each on the three machines are given in the following table:

Items	Number of hours required on machines
Items	I	II	III
M	1	2	1
N	2	1	1.25

She makes a profit of RS.600 and Rs 400 on items M and N respectively. How many of each item should she produce so as to maximise her profit assuming that she can sell all the items that she produced? What will be the maximum profit?

15.

Solve the following linear programming problem graphically:
Maximise Z = 4x + y
subject to the constraints:
\(x+y\le 50,\)
\(3x+y\le 90,\)
\(x\ge 0,y\ge 0.\)

Visit QB365-SLMS - https://www.qb365.in/slms/

Answers Key:

True or False

1 x 1 = 1

True.

Generic 3

14 x 3 = 42

A:5 Days; B: 3 Days; Minimum cost = Rs.1,350.

Let 'x' and 'y' be the number of pieces of type A and type B respectively.
Then the problem is:
Maximize Z - 80x + 120y subject to:
\(9x+12y\le 180,\quad x+3y\le 30,\quad x\ge 0,\ge 0.\)

For solution set, we draw the lines:
x = 0, y = 0, 9x + 12y = 180 and x + 3y = 30.
The feasible region OAED is bounded whose vertices are:
O(0, 0), A(20, 0), D(0, 10) and E(12, 6)
[Solving 9x +12y = 180 and x + 3y = 30; x = 12, y = 6]
Applying Corner Point Method, we have:

Corner Point	Z = 80x + 120y
O: (0, 0)	0
A : (20, 0)	1600
E : (12, 6)	1680 (Maximum)
D : (0, 10)	1200

Hence, the maximum profit is Rs. 1680 when 12 pieces of Type A and 6 pieces of Type B are manufactured per week.

We have the data:

Machine	Chairs	Table	Available time (In hours) per week
A B C	2 1 1	1 1 3	70 40 90
Profit	Rs. 30	Rs. 60

Let 'x' chairs and 'y' tables be produced per week.
Then we have:
\(2x+y\le 70\) ...(1)
\(x+y\le 40\)...(2)
\(x+3y\le 90\) ...(3)
\(x\ge 0,y\ge 0\) ....(4)
and \(Z=30x+60y\) .....(5)

The feasible region (shaded) OAPF is bounded, where O is (0, 0), A is (35, 0), P(24, 22) and F is (0, 30).
Applying Corner Point Method, we have:

Corner Point	Z = 30x + 60y
O : (0,0)	0
A : (35, 0)	1050
P : (24, 22)	2040 (Maximum)
F : (0, 30)	1800

Hence, the maximum profit is Rs. 2,040 when 24 chairs and 22 tables are made per week.

Let 'x' kg bran and 'y' kg of rice be required.
Minimize: Z = 5x + 4y subject to:
\(x\ge 0,y\ge 0,80x+100y\ge 88\) and \(40x+30y\ge 56\)
i.e. \(x\ge 0,\quad y\ge 0,20x+25y\ge 22\)
and \(20x+15y\ge 28\)

The feasible region (shaded) is unbounded.
Let us evaluate Z at the corner points:

Corner Point	Z = 5x + 4y
\(C:\left( \frac { 14 }{ 10 } ,0 \right) \) \(D:\left( 0,\frac { 28 }{ 15 } \right) \)	7 (Minimum) \(\frac { 112 }{ 15 } \)

Hence, the minimum cost is Rs. 7 when \(\frac { 14 }{ 10 } \) kg of bran is used.

The system constraints is:
\(x-2y\le 2\)....(1)
\(3x+2y\le 12\) ..(2)
\(-3x+2y\le 3\) ..(3)
and \(x\ge 0,y\ge 0\) ..(4)

The line x - 2y and 3x + 2y = 12 meet at H \(\left( \frac { 7 }{ 2 } ,\frac { 3 }{ 4 } \right) \).
The lines -3x + 2y = 3 and 3x + 2y = 12 meet at G \(\left( \frac { 3 }{ 2 } ,\frac { 15 }{ 4 } \right) \)
The shaded portion in the above figure is the feasible region, which is bounded.
Applying Corner Point Method, we are to determine the maximum and minimum values of Z, where Z = 5x + 2y.

Corner Point	Z = 5x + 2y
O : (0, 0)	0
A : (2, 0)	10
H : \(\left( \frac { 7 }{ 2 } ,\frac { 3 }{ 4 } \right) \)	19
G : \(\left( \frac { 3 }{ 2 } ,\frac { 15 }{ 4 } \right) \)	15
F : \(\left( 0,\frac { 3 }{ 2 } \right) \)	3

Hence, Z_min = 0 at (0,0) and Z_max = 19 at \(\left( \frac { 7 }{ 2 } ,\frac { 3 }{ 4 } \right) \)

The given system of constraints is:
\(2x_{ 1 }3x_{ 2 }\le 18\) ...(1)
\(x_{ 1 }+x_{ 2 }\ge 12\)..(2)
\(x_{ 1 },x_{ 2 }\ge 0\) ...(3)

Since there is no shaded portion, which is feasible region of the given constraints,
∴ the problem has no feasible solution.

Let the company manufacture x souvenirs of type A and y souvenirs of type B. Therefore,
x ≥ 0 and y ≥ 0
The given information can be complied in a table as follows

	Type A	Type B	Availability
Cutting (min)	5	8	3 × 60 + 20 = 200
Assembling (min)	10	8	4 × 60 = 240

The profit on type A souvenirs is Rs. 5 and on type B souvenirs is Rs. 6. Therefore, the constraints are
5x + 8y ≤ 200
10x + 8y ≤ 240
i.e., 5x + 4y ≤ 120
Total profit, Z = 5x + 6y
The mathematical formulation of the given problem is
Maximize Z = 5x + 6y … (1)
subject to the constraints,
5x + 8y ≤ 200… (2)
5x + 4y ≤ 120 … (3)
x, y ≥ 0 … (4)
The feasible region determined by the system of constraints is as follows.

The corner points are A (24, 0), B (8, 20), and C (0, 25).
The values of Z at these corner points are as follows.

Corner point	Z = 5x + 6y
A(24, 0)	120
B(8, 20)	160	→ Maximum
C(0, 25)	150

The maximum value of Z is 200 at (8, 20).
Thus, 8 souvenirs of type A and 20 souvenirs of type B should be produced each day to get the maximum profit of Rs. 160.

(i) Let the number of rackets and the number of bats to be made be x and y respectively.
The machine time is not available for more than 42 hours.
1.5x+3y<= 42
The craftsman’s time is not available for more than 24 hours.
3x+y<= 24
The factory is to work at full capacity. Therefore,
1.5x + 3y = 42
3x + y = 24
On solving these equations, we obtain
x = 4 and y = 12
Thus, 4 rackets and 12 bats must be made.
(ii) The given information can be complied in a table as follows.

	Tennis Racket	Cricket Bat	Availability
Machine Time (h)	1.5	3	42
Craftsman’s Time (h)	3	1	24

∴ 1.5x + 3y ≤ 42
3x + y ≤ 24
x, y ≥ 0
The profit on a racket is Rs 20 and on a bat is Rs. 10.
∴ Z = 20x + 10y
The mathematical formulation of the given problem is
Maximize Z =20x + 10y … (1)
subject to the constraints,
1.5x + 3y ≤ 42 … (2)
3x + y ≤ 24 … (3)
x, y ≥ 0 … (4)
The feasible region determined by the system of constraints is as follows.

The corner points are A (8, 0), B (4, 12), C (0, 14), and O (0, 0).
The values of Z at these corner points are as follows.

Corner point	Z = 20x + 10y
A(8, 0)	160
B(4, 12)	200	→ Maximum
C(0, 14)	140
O(0, 0)	0

Thus, the maximum profit of the factory when it works to its full capacity is Rs. 200.

10.

Let the mixture contain x kg of food P and y kg of food Q. Therefore, x ≥ 0 and y ≥ 0
The given information can be compiled in a table as follows.

	Vitamin A (units/kg)	Vitamin B (units/kg)	Cost (Rs/kg)
Food P	3	5	60
Food Q	4	2	80
Requirement (units/kg)	8	11

The mixture must contain at least 8 units of vitamin A and 11 units of vitamin B. Therefore, the constraints are
3x + 4y ≥ 8
5x + 2y ≥ 11
Total cost, Z, of purchasing food is, Z = 60x + 80y
The mathematical formulation of the given problem is
Minimise Z = 60x + 80y … (1)
subject to the constraints,
3x + 4y ≥ 8 … (2)
5x + 2y ≥ 11 … (3)
x, y ≥ 0 … (4)
The feasible region determined by the system of constraints is as follows.
It can be seen that the feasible region is unbounded.
The corner points of the feasible region are and \(A\left(\frac{8}{3}, 0\right), B\left(2, \frac{1}{2}\right) \text { and } C\left(0, \frac{11}{2}\right)\)

Corner points	z = 60x +80 y
\(A\left(\frac{8}{3}, 0\right)\)	160
\(B\left(2, \frac{1}{2}\right) \)	160
\(C\left(0, \frac{11}{2}\right)\)	440

As the feasible region is unbounded, therefore, 160 may or may not be the minimum value of Z.
For this, we graph the inequality, 60x + 80y < 160 or 3x + 4y < 8, and check whether the resulting half plane has points in common with the feasible region or not.
It can be seen that the feasible region has no common point with 3x + 4y < 8
Therefore, the minimum cost of the mixture will be Rs 160 at the line segment joining the points \(\left(\frac{8}{3}, 0\right) \text { and }\left(2, \frac{1}{2}\right)\)

11.

The feasible region determined by the constraints, 2x + y ≥ 3, x + 2y ≥ 6, x ≥ 0, and y ≥ 0, is as follows.

The corner points of the feasible region are A (6, 0) and B (0, 3).
The values of Z at these corner points are as follows.

Corner point	Z = x + 2y
A(6, 0)	6
B(0, 3	6

It can be seen that the value of Z at points A and B is same. If we take any other point such as (2, 2) on line x + 2y = 6, then Z = 6
Thus, the minimum value of Z occurs for more than 2 points.
Therefore, the value of Z is minimum at every point on the line, x + 2y = 6

12.

Given, Z = -3x + 4y
Subject to the constraints
x + 2y \( \leq\) 8; 3x + 2y \( \leq\) 12 and x \(\geq\)0, y \(\geq\) 0
Now, considering the inequations as equations, we get
x + 2y = 8 ...(i)
3x + 2y = 12 ...(ii)
Table for line x + 2y = 8 is

x	8	0
y	0	4

On putting (0, 0) in the inequality x + 2y \( \leq\) 8
0 \( \leq\) 8 (which is true)
So, half plane is towards the origin.
Table for line 3x + 2y = 12

x	4	0
y	0	6

On putting (0, 0) in the inequality 3x + 2y \( \leq\)12
0 \( \leq\) 12 (which is true)
So, half plane is towards the origin.
Also, x \(\geq\) 0 and y \(\geq\) 0, so the feasible region lies in the Ist quadrant.
The point of intersection of Eqs. (i) and (ii) is (2, 3).
The graphical representation of the above system of inequations is given below.

Corner points	Value of Z = -3x + 4y
A(0, 4)	16
B(2, 3)	6
C(4, 0)	-12 (Minimum)
O(0, 0)	0

Hence, Z = -12 is minimum at (4, 0).

13.

The system of constraints is:
\(x+y\le 4\) ..(1)
and \(x\ge 0,y\ge 0.\) ...(2)
The shaded region in the following figure is the feasible region determined by the system of constraints (1)-(2)
It is observed that the feasible region OAB is bounded.
Thus we use Corner Point Method to determine the maximum value of Z, where:
Z = 3x + 4y...(3)

The co-ordinates of O, A and B are (0, 0), (4, 0) and (0, 4) respectively.
We evaluate Z at each corner point.

Corner Point	Corresponding Value of Z
O : (0,0)	0
A : (4,0)	12
B : (0,4)	16 (Maximum)

Hence, \(Z_{ max }=16\) at the point (0, 4)

14.

Let x and y be the number of items M and N respectively.
Total profit on the production = Rs. (600 x + 400 y)
Mathematical formulation of the given problem is as follows:
Maximise Z = 600 x + 400 y
subject to the constraints:
x + 2y ≤ 12 (constraint on Machine I) ... (1)
2x + y ≤ 12 (constraint on Machine II) ... (2)
\(x+\frac{5}{4} y \geq 5 \) (constraint on Machine III) ...(3)
x ≥ 0, y ≥ 0 ... (4)

Let us draw the graph of constraints (1) to (4). ABCDE is the feasible region (shaded) as shown in Figure determined by the constraints (1) to (4). Observe that the feasible region is bounded, coordinates of the corner points A, B, C, D and E are (5, 0) (6, 0), (4, 4), (0, 6) and (0, 4) respectively.
Let us evaluate Z = 600 x + 400 y at these corner points.

Corner Point	Z=600x+400y
C : (6,0)	3600
D : (4,4)	4000 (Maximum)
B : (0,6)	2400
F : (0,4)	1600
E : (5,0)	3000

We see that the point (4, 4) is giving the maximum value of Z. Hence, the manufacturer has to produce 4 units of each item to get the maximum profit of Rs. 4000.

15.

The shaded region is the feasible region determined by the system of constraints (2) to (4). We observe that the feasible region OABC is bounded. So, we now use Corner Point Method to determine the maximum value of Z.
The coordinates of the corner points O, A, B and C are (0, 0), (30, 0), (20, 30) and (0, 50) respectively. Now we evaluate Z at each corner point.
\(x+y\le 50\)...(1)
\(3x+y\le 90\) ..(2)
and \(x\ge 0,y\ge 0\)..(3)

It is observed that the feasible region OCEB is bounded.
Thus we use Corner Method to determine the maximum value of Z, Where:
Z = 4x + y ..(4)
The co-ordinates of O,C,e and B are (0,0), (30,0), (20,30) [Solving x + y = 50, 3x + y = 90; x = 20, y = 3] and (0, 50) respectiely.