Linear Programming

way of transporting the product from factories to

IMPORTANT CONCEPTS different markets.
The word programmig means ‘Planning’ and refers to iv) Problem related to investment market :

Ghonse Maths Academy, Ahmednagar *Ghonse Maths Academy, Ahmednagar *Ghonse Maths Academy, Ahmednagar *
the method of determining a plan of action for the In this type of problem, we establish the investment
optimum use of available resources to obtain the portfolio from a variety of stocks or bonds to maximize
desired objective. The limitations on the resources are the company’s returns on investments.
called constraints. If these limitations when written v) Problem in the advertising firms :
mathematically are of degree one, i.e. linear, the In this type of problem we maximize the
programming is called Linear Programming. effectiveness of advertising activity in the fields of T.V.,
x  0, y  0 are called as non negativity radio, newspaper by allocation of limited advertsing
constraints. budget.
* Converting Business problems into mathematical * Working Rule to Formulate LPP. :
formulation : The formulation of LPP as a mathmatical model involves
Objective function, constraints and non-negativity the following steps.
restrictions are linear functions of two variables in x i) Identify the aim or objective which is to be maximize
and y i.e. index of each of the variable x and y is one. or minimize and denote it by z.
Such problem is called Linear Programming ii) Identify the variables and assign symbols x, y, .... or
Problem.(LPP). x1 , x 2 , x 3 ,......, etc.
i) Linear Programming Problem (LPP) : iii) Identify all the restrictions or constraints in the problem
If the restrictions, when expressed mathematically, are and express them as linear inequalities or equations in
in the form of linear inequalities, the programming terms of variables.
problem is called Linear Programming Problem iv) Express the hidden conditions, generally involves non-
(LPP). negativity of variables.
ii) Objective Function : * Terms Related to the Solution of LPP.
The linear function z  c1 x1  c 2 x 2  c 3 x 3 ....c n x n , 1) Feasible Region : The solution set, i.e., the common
whose maximum or minimum (i.e., optimum) value is region of the graphical representation of the constraints
to be found out, is called an objective function. It can is called the feasible region of the LPP.
be denoted by Z, P or C. 2) Infeasible Region : The region other than the feasible
region is called infeasible region of the LPP.
* Areas in which Linear Programming Can be 3) Solution of LPP : The set of values of the decision
Applied : variables which satisfy the constraints of the linear
i) Manufacturing Problem : programming problem is called a solution to that
In this type of problem ,we determine the number of problem.
unit of different products which should be produced 4) Feasible Solution : A solution which satisfies the given
and sold by a firm when each product requires a fixed system of inequalities is called a feasible solution.
manpower, machine hours, labour hours per unit of 5) Optimal Feasible Solution : A feasible solution which
product, warehouse space per unit of the output etc., optimizes (i.e., maximizes or minimizes) the objective
in order to make the maximum profit. function is called an optimal feasible solution.
ii) Diet Problem : 6) Optimization Technique : The process of obtaining
In this type of problem, we determine the amount of the optimal fessible solution to a LPP is called
different kinds of constitutents which should be optimization technique.
included in the diet in order to minimize the cost 7) Convex Set : Let S be a set of points and A, B be
such that it contains a certain amount of each any two distinct points of S. If the line segment joining
constituent. the points A and B lies wholly in S, then the set S is
iii) Transportation Problem : called convex set.
In this type of problem, we determine the
transportation schedule in order to find the cheapest

Linear Programming [1] Ghonse Maths Academy, A’nagar

MHT CET – 2025
 ii) Unbounded solutions:
In some linear programming problems, we come
across the solutions which are not bounded. Hence,
the value of the objective function can be increased
indefinitely and therefore these is no finite value of the
objective function within the feasible region.

Ghonse Maths Academy, Ahmednagar *Ghonse Maths Academy, Ahmednagar *Ghonse Maths Academy, Ahmednagar *
iii) Infeasible solution:
In some linear programming problems, the feasible
region is empty. This is called the condition of
infeasibility and hence there is no solution for the
problem.

Note :
1) If the feasible region of a L.P.P. is bounded and
8) Convex Polygon Theorem or Fundamental the slope of the line represented by an objective
Theorem of extreme points for Feasible Region: function lies between the slopes of two lines
If the feasible region of a linear programming problem represented by the constraints, then the optimum
is a convex polygon, then the problem has an optimum (maximum or minimum) value occurs at the point
solution and it lies on at least one of the vertices of intersection of that two lines.
(corners) of the polygon. 2) If the line represented by an objective function is
parallel to any one of the line represented by the
* Solution of LPP By Graphical method : constraints, then the L.P.P. has infinite number of
optimum (maximum or minimum) solutions.
* Corner Point Method : i) If the problem involves only two constraints, then
i) If an inequality ax  by  c or ax  by  c is given, the optimum value of z occurs at the point of
then draw the line ax + by = c. Draw the lines intersection of the two lines represented by the
corresponding to all the given inequalities [Consider constraints.
the points of intersection of the line with the coordinate ii) If the problem involves more than two constraints,
axes]. and the slope of the lines represented by an
ii) Shade the graph of solution set of the given system of objective function lies between the slope of the lines
inequalities (i.e,constraints). represented by the constraints, then the optimum
iii) Find the coordinates of the vertices of the above graph. value of z occurs at the point of intersection of that
iv) Find the values of the objective function at these lines.
vertices. 3) If the slope of the lines represented by an objective
v) Determine which of these values is the maximum or function does not lie between the slopes of any two
the minimum. lines represented by the constraints, then the L.P.P.
The coordinates of these points are the optimal may have unbounded solution or infeasible solution.
solutions. 4) i) If the feasible region of an L.P.P. is bounded, then
Note : Graphical method can be used for solving LPP, if the minimum value of an objective function may
only two variables are involved in the LPP. occur at the vertex which is at a minimum distance
from the origin.
Special Cases of LPP : ii) If the feasible region of an L.P.P. is bounded, then
i) Infinite number of optimal solutions: the maximum value of an objective function may
If the objective function has the same maximum (or occur at the vertex which is at a maximum distance
minimum) value at two consecutive vertices say A and from the origin.
B of the feasible region, then the objective function
has the extreme (maximum or minimum) value at all Multiple Choice Questions
the points of the segment AB. In this case the LPP has 1) Objective function of L.P.P. is
infinite number of optimum solutions. a) a constranit b) an inequality
Note: In this case the line representing the objective c) a function to be optimized d) feasible region
function is parallel to any one of the lines representing 2) The function to be maximized or minimized is called
the constraint.
Linear Programming [2] Ghonse Maths Academy, A’nagar
MHT CET – 2025
 a) the contraints b) an objective function d) Maximize z = x + y, subject to
c) an inequality d) the non-negative constraints x y
3) The optimal value of the objective function is   1,5x  8y  600, x  0, y  0
60 90
a) given by intersection of inequalities with the 3) Shalmali wants to invest s 50,000 in saving certifi-
axes only cates and PPF.She wants to invest at least s 15,000
b) given by corner points of the feasible region

Ghonse Maths Academy, Ahmednagar *Ghonse Maths Academy, Ahmednagar *Ghonse Maths Academy, Ahmednagar *
in saving certificates and at least s 20,000 in
c) given by intersection of inequalites with X-axis PPF.The rate of interest on saving certificates is 8%
only p.a. and that on PPF. is 9% p.a.
d) given by intersection of inequalites with Y-axis Formulate the above problem as L.P.P to determine
only maximum yearly income.
4) Under which condition an optimum solution cannot
be obtained ? a) Maximize z  8x1  9x 2 subject to
a) Maximize the objective function when the feasible x1  x 2  50000, x1  15000, x 2  20000
region is unbounded.
b) Maximize the objective function when the feasible b) Maximize z  8x1  9x 2 subject to
region is bounded. x1  x 2  50000, x1  15000, x 2  20000, x1  0
c) Maximize the objective function when more
than one optimum solution is found. c) Maximize z  0.08x1  0.09x 2 subject to
d) All of these. x1  x 2  50000, x1  15000, x 2  20000

Formation of LPP : d) Maximize z  0.8x1  0.9x 2 subject to

1) Two tailors P and Q earn s 350 and s 450 per day x1  x 2  50000, x1  15000, x 2  20000
respectively. Tailor P can stitch 6 shirts and 3 4) Old hens can be bought for s 20 each but young
trousers while Tailor Q can stitch 7 shirts and 3 ones cost s 50 each.The old hens lay 3 eggs per
trousers per day. How many days should each of week and young ones 5 egges per week,each egg
them work, if it is desired to produce at least 51 being worth s 3.Cost of feeding each hen is s 10
shirts and 24 trousers at a minimum labour cost? per week, Mr. Amir has only s 800 to spend for
The formulation of this L.P.P. is purchasing the hens.Formulate the above problem
a) Minimize z = 350 x + 450 y ,subject to as L.P.P. to maximize the profit per week assuminig
6x  7y  51,3x  3y  24, x  0, y  0 he cannot house more than 20 hens.
b) Minimize z = 350 x + 450 y ,subject to a) Maximize z = x + y, subject to
6x  7y  51,3x  3y  24, x  0, y  0
x  y  20, 20x  50y  800, x  0, y  0
c) Minimize z = 350 x + 450 y ,subject to
6x  7y  51,3x  3y  24, x  0, y  0 b) Maximize z = 9x + 15y, subject to
d) Minimize z = 350 x + 450 y ,subject to x  y  20, 20x  50y  800, x  0, y  0
6x  7y  51,3x  3y  24, x  0, y  0 c) Maximize z = x + 5y, subject to
2) If salim drives a car at a speed of 60 km/hr, he has x  y  20, 20x  50y  800, x  0, y  0
to spend s 5 per km on petrol. If he drives at a d) Maximize z = 5y - x, subject to
faster speed of 90km/hr, the cost of petrol increases
x  y  20, 20x  50y  800, x  0, y  0
to s 8 per km. He has s 600 to spend on petrol
and wishes to travel the maximum distance within 5) An owner of a lodge plans an extension which
an hour.The formulation of this problem as L.P.P. is contains not more than 50 rooms. At least 5 must be
executive single rooms.The number of executive
a) Maximize z = x + y, subject to
double rooms should be at least 3 times the number
60x  90y  1,5x  8y  600, x  0, y  0 of executive single room .He charges s 3000 for
b) Maximize z = x + y, subject to executive double room and s 1800 for executive
x y single room per day.Formulate the above problem
  1,5x  8y  600, x  0, y  0 as L.P.P.to maximize the profit.
60 90
c) Maximize z = 60x + 90y, subject to a) Maximize z  1800x1  3000x 2 , subject to
x  y  1,5x  8y  600, x  0, y  0 x1  x 2  50, x1  5, x 2  3x1
b) Maximize z  1800x1  3000x 2 , subject to
Linear Programming [3] Ghonse Maths Academy, A’nagar
MHT CET – 2025
 x1  x 2  50, x1  5, x 2  3x1 c) only one point d) unbounded region
7) Which of the following is true from the graph of the
c) Maximize z  1800x1  3000x 2 , subject to
inequalities 2x + 3y  12 and 4x + 6y  12 ?
x1  x 2  50, x1  5, x 2  3x1 a) both contain the origin.
d) Maximize z  1800x1  3000x 2 , subject to b) both graphs are disjoint.
x1  x 2  50, x1  5, x1  3x 2 c) both graphs lie in second and third quadrants.

Ghonse Maths Academy, Ahmednagar *Ghonse Maths Academy, Ahmednagar *Ghonse Maths Academy, Ahmednagar *
d) both have some points in common.
Graphs and Solution Set of LPP : 8) The common solution set of the inequalities
1) The solution set of inequality 2x + 3y  6 is ...... x 3 y6
2x  1  11,  5,  0, x  0, y  0
a) origin side of 2x + 3y = 6 and excluding the points 3 2
on 2x+ 3y = 6. from .......
b) non-origin side of 2x + 3y = 6 and including the a) square b) rectangle
points on 2x + 3y = 6. c) rhombus d) trapezium
c) origin side of 2x + 3y = 6 and including the points 9) The common solution set of the inequalities
on 2x + 3y = 6.  2x 
4  x  1  2x  10,  x  2     and
d) non-origin side of 2x + 3y = 6 and excluding the  3 
points on 2x + 3y = 6. x  0, y  0 is ........
2) The solution set of 3x + 5y > 15 is ........ a) an empty set. b) bounded region.
a) non-origin side of 3x + 5y = 15 and including the c) unbounded region.
points on 3x + 5y = 15. b) in the first and second quadrant.
b) origin side of 3x + 5y = 15 and excluding the 10) The common solution set of x – y  0 , x  5,
points on 3x + 5y – 15. x + y  0, x  0, y  0 forms ........
c) origin side of 3x + 5y = 15 and including the a) an isosceles right angled triangle.
points on 3x + 5y = 15. b) an equilateral triangle.
d) non-origin side of 3x + 5y = 15 and excluding the c) a square. d) a rectangle.
points on 3x + 5y = 15. 11) The common region represented by x  y  3 ,
3) The solution set of the inequality 2x – 3y  0 is .... 2x  y  5, x  2, x  0 lies fully in
a) half plane containing the point (4, 0) and including a) first quadrant b) first and second quadrant
the points on 2x – 3y = 0. c) third quadrant d) first and fourth quadrant
b) half plane not containing the point (0, 4) and 12) The common region represented by x  2y  10,
excluding the points on 2x – 3y = 0. 3x  y  12, x  0, y  0 is
c) half plane containing the point (0, 4) and including a) bounded b) unbounded
the points on 2x – 3y = 0. c) both bounded and unbounded d) a single point
d) half plane not containing the point (4, 0) and 13) The common region represented by 5x  y  10,
excluding the points on 2x – 3y = 0. x  y  6, x  0, y  0 is
4) For an L.P.P with decision variables x and y which of a) bounded b) unbounded
the following cannot be an objective function ? c) both bounded and unbounded d) a single point
a) z = 2x + 3y b) z = 4x – 3y 14) The graph of the inequalities 3x  4y  12,
x y x  1, x  0, y  0 lies fully in
c) z   d) z = x2 + y2 a) first quadrant b) second quadrant
2 3
c) third quadrant d) fourth quadrant
5) The position of the points P (2, 1) and Q (11, 2) in
15) The feasible solution of L.P.P. belongs to
the region of graph of inequation 4x – 5y > 20 will
a) only in first quadrant b) first and third quadrant
be ........
c) first and fourth quadrant d) any quadrants
a) P is outside and Q is inside the region.
16) The common region represented by the inequalities
b) P is inside and Q is outside the region.
x  y  3, y  2, 2x  y  1, x  0, y  0 is
c) both P and Q are inside the region.
a) a triangle b) a quadrilateral
d) both P and Q are outside the region.
c) a pentagon d) a rectangle
6) The solution set of the following set of inequations
17) The common region for the inequalities x  y  10 ,
x + 2y  6, 3x + 4y  24, x  0, y  0 is ........
x  5, y  10, x  0, y  0 is
a) bounded region b) empty set

Linear Programming [4] Ghonse Maths Academy, A’nagar

MHT CET – 2025
 20) For the following shaded area, the linear constraints
except x  0 and y  0 are

a) b)

Ghonse Maths Academy, Ahmednagar *Ghonse Maths Academy, Ahmednagar *Ghonse Maths Academy, Ahmednagar *
a) 2x  y  2, x  y  1, x  2y  8
b) 2x  y  2, x  y  1, x  2y  8
c) d) c) 2x  y  2, x  y  1, x  2y  8
d) 2x  y  2, x  y  1, x  2y  8
21) For the following shaded region, the linear
constraints except x  0 and y  0 are
18) The common region represented by the inequalities
x  y  0, 2x  y  2 is

a) b)

a) x  4, y  3, x  y  5, 4x  y  4
b) x  4, y  3, x  y  5, 4x  y  4
c) d)
c) x  4, y  3, x  y  5, 4x  y  4
d) x  4, y  3, x  y  5, 4x  y  4
22) For the following shaded region, the linear
19) The common region represented by the inequalities constraints except x1  0, x 2  0 ,are
x  y  1, x  y  0, x  0, y  0 is

a) b)

a) 5x1  9x 2  90, x1  x 2  4, x 2  8
b) 5x1  9x 2  90, x1  x 2  4, x 2  8
c) d)
c) 5x1  9x 2  90, x1  x 2  4, x 2  8
d) 5x1  9x 2  90, x1  x 2  4, x 2  8

Linear Programming [5] Ghonse Maths Academy, A’nagar

MHT CET – 2025
23) Shaded region is represented by 118 120
a) 30 b) c) d) 25
7 7
6) The maximum value of z = 3x + 5y subject to
3x  y  9, 4x  3y  17, x, y  0 occurs at
 17 
a) (0,0) b) (2,3) c) (3,0) d)  0, 3 

Ghonse Maths Academy, Ahmednagar *Ghonse Maths Academy, Ahmednagar *Ghonse Maths Academy, Ahmednagar *
 
7) The minimum value of z = 5x + 2y subject to
10x  2y  20, 5x  5y  30, x  0, y  0 occurs at
a) 4x  2y  3 b) 4x  2y  3 a) (1,5) b) (6,0) c) (0,6) d) (3,2)
c) 4x  2y  3 d) 4x  2y  3 8) The minimum value of z = 3x + y subject to
24) Which of the following is not the vertex of the 2x  3y  6, x  y  1, x  0, y  0 is
feasible region represented by a) 0 b) -3 c) 1 d) 2
x  y  5, 0  x  4, y  2 ? 9) The maximum value of z = 3x + 4y subject to
a) (4,2) b) (0,5) c) (3,2) d) (4,1) x  y  450, 2x  y  600, x  0, y  0 is
a) 2000 b) 900 c) 1800 d) 1650
25) Which of the following is not the vertex of the 10) The minimum value of z = 5x + 8y subject to
feasible region bounded by the inequalities x  y  5, 0  x  4, y  2 occurs at
2x  3y  6,5x  3y  15, x  0, y  0 ? a) (4,2) b) (3,2) c) (0,5) d) (5,5)
a) (0,0) b) (0,2) c) (3,0) d) (0,5) 11) The maximum value of z = 5x + 3y subject to
26) The solution set of the constraints x  2y  11, 3x  5y  15, 5x  2y  10, x, y  0 occurs at
3x  4y  30, 2x  5y  30, x  0, y  0 includes  10   20 45 
a)  19 , 5  b)  19 , 19  c) (2,3) d) (1,1)
the point    
a) (2,3) b) (3,2) c) (3,4) d) (4,3) 12) The maximum value of z = 6x + 4y subject to
27) Which of the following represent a convex set? 3x  2y  12, x  y  5, 0  x  4, 0  y  4 is
a)  x, y  / x 2  y 2  9
a) 24 b) 28 c) 40 d) 12
13) The maximum value of z  10x1  25x 2 subject to
b)  x, y  /16  x  y  36
2 2
0  x1  3, 0  x 2  3, x1  x 2  5 occurs at
c)  x, y  / 2x  3y  6
2 2 a) (3,0) b) (3,2) c) (2,3) d) (0,3)
14) The minimum value of z = 3x + 5y subject to
d)  x, y  / x  y  16
2 2
2x  3y  12,  x  y  3, x  4, y  3 occurs at
a) (0.6,3.6) b) (1.5, 3) c) (4,3) d) (4,7)
Solution of LPP
1) The L.P.P., maximize z = 3x + 4y subject to
x  y  0 ,  x  3y  3, x  0, y  0 has
a) unique solution b) no solution
c) infinite solutions d) two solutions
2) The L.P.P, maximize z  5x  10y subject to
x  2y  10,3x  y  12, x  0, y  0 has
a) unique solution b) no solution
c) infinite solutions d) two solutions
3) The maximum value of z = 3x + 2y subject to
constraints x  y  4, x  y  2, x, y  0 is given by
a) 10 b) 11 c) 6 d) 8
4) The minimum value of z = 5x + 8y subject to the
constraints x  4, y  2, x  y  5, x, y  0 is
a) 28 b) 30 c) 31 d) 24
5) The maximum value of P = 3x + 5y subject to
4x  3y  12, y  x  2, x  0, y  0 is

Linear Programming [6] Ghonse Maths Academy, A’nagar

MHT CET – 2025