1

LINEAR PROGRAMMING
Core Components
Every LP problem is composed of four fundamental elements:
• Decision Variables: The unknown quantities that can be controlled or adjusted to find the best solution
(e.g., x and y representing product quantities).
• Objective Function: A linear mathematical expression defining the primary goal to be maximized (e.g.,
profit) or minimized (e.g., cost).
• Constraints: A set of linear inequalities or equations that represent limitations such as resource availability,
budget, or time.
• Non-Negativity Restrictions: A standard requirement that decision variables must be greater than or equal
to zero (x  0, y  0), as negative values are often unrealistic in real-world contexts.
Key Concepts & Theorems
• Feasible Region: The common area on a graph that satisfies all given constraints simultaneously. Any
point within this region is a "feasible solution".
• Optimal Solution: A specific point within the feasible region that yields the best (maximum or minimum)
value for the objective function.
• Corner Point Theorem: States that if an optimal solution exists, it will occur at one of the vertices (corner
points) of the feasible region.
Solution Methods
Graphical Method: A visual technique used for simple problems involving only two decision variables by
plotting constraints on an X-Y plane.

Example:

Graph the constraints stated as linear inequalities :

5x + y < 100 …………………………… Equation (1)

x + y < 60 ………....…………………… Equation (2)

x > 0 ………………………………….... Equation (3)

y > 0 ………………………………….... Equation (4)

For Plotting the Equation (1),

• Let x = 0, Hence we get the point y = 100

• Let y = 0, hence we get the point x = 100/5 = 20
• Equation (1) is obtained by joining the points (20, 100)

For Plotting the Equation (2),

• Let x = 0, Hence we get the point y = 60

• Let y = 0, Hence we get the point x = 60
• Equation (2) is obtained by joining the points (60, 60)

GK INSTITUTE OF COMMERCE
 2

From Equation (3) and Equation (4) we know both x and y are greater than 0

From the graph above,

• Points within and on the boundary of the feasible region represent feasible solutions of the constraints.
• In Fig. 12.1, every point within and on the boundary of the feasible region OABC represents feasible solution
to the problem.
• For example, the point (10, 50) is a feasible solution of the problem and so are the points (0, 60), (20, 0) etc.
• Any point outside the feasible region is called an infeasible solution. For example, the point (25, 40) is an
infeasible solution of the problem.
• Now, we see that every point in the feasible region OABC satisfies all the constraints as given in (1) to (4),
and since there are infinitely many points, it is not evident how we should go about finding a point that gives
a maximum value of the objective function Z = 250x + 75y
Vertex of the Feasible Region Corresponding value of Z (in Rs.)
0 (0, 0) 0
A (0, 60) 4500
B (10, 50) 6250
C (20, 0) 5000

GK INSTITUTE OF COMMERCE
 3

MULTIPLE CHOICE TYPE QUESTIONS

1. The graph of the inequality 2x + 3y > 6 is
(a) half plane that contains the origin
(b) half plane that neither contains the origin nor the points of the line 2x + 3y = 6
(c) whole XOY - plane excluding the points on the line 2x + 3y = 6
(d) entire XOY plane

2. Which of the term is not used in a linear programming problem?

(a) Optimal solution (b) Feasible solution
(c) Concave region (d) Objective function

3. The linear inequalities or equations or restrictions on the variables of a linear programming

problem are called
(a) linear relations (b) constraints
(c) functions (d) objective functions

4. The objective function of an LPP is

(a) a constraint (b) a function to be optimized
(c) a relation between the variables (d) None of the above

5. The corner points of the feasible region determined by the system of linear constraints are (0,10),
(5, 5), (15,15), (0, 20). Let Z = px + qy, where p,q>0. Then, the condition on p and q, so that the
maximum of Z occurs at both the points (15,15) and (0, 20) is
(a) p=q (b) p = 2q
(c) q=2p (d) q = 3p

6. In an LPP, if the objective function has Z=ax + by has the same maximum value on two corner
points of the feasible region, then the number of points at which Zmax occurs is
(a) 0 (b) 2
(c) finite (d) infinite

7. The feasible region for the following constraints L1  0, L2  0, L3 = 0, x  0, y  0 in the diagram

shown is

(a) area DHF (b) area AHC

(c) line segment EG (d) line segment GI

GK INSTITUTE OF COMMERCE
 4

8. A wholesale merchant wants to start the business of cereal with ₹ 24000. Wheat is ₹ 400 per quintal
and rice is ₹ 600 per quintal. He has capacity to store 200 quintal cereal. He earns the profit ₹ 25
per quintal on wheat and ₹ 40 per quintal on rice. If he stores x quintal rice and y quintal wheat,
then maximum profit of the objective function is
(a) 25x + 40y (b) 40x + 25y
400 600
x+ y
(c) 400x + 600y (d) 40 25

ASSERTION REASON BASED QUESTIONS

Directions (Q. Nos. 9-11) Consider the graph of constraints stated as linear inequalities as below
5x + y  100 ...(i)
x + y  60 ...(ii)
x0 ...(iii)
y0 ...(iv)

On the basis of above information, the questions given below has two statements labelled as Assertion (A)
and Reason (R). In the context of the two statements, which one of the following is correct?
(a) Both A and R are correct; R is the correct explanation of A
(b) Both A and R are correct; R is not the correct explanation of A
(c) A is correct; R is incorrect
(d) R is correct; A is incorrect

9. Assertion (A) The points (10, 50), (0, 60) or (20, 0) are feasible solutions.
Reason (R) Points within and on the boundary of the feasible region represent feasible solutions of the
constraints.

10. Assertion (A) The objective function Z = – 50x + 20y

Subject to the constraints 2x – y  – 5, 3x + y  3, 2x – 3y  12, x  0, y  0 in the feasible region has no
minimum value.

GK INSTITUTE OF COMMERCE
 5

Reason (R) If the open half plane determined by ax + by < m, where m is the minimum value of Z, has a
point in common with feasible region, then Z has no minimum value.

11. Assertion (A) The maximum value of Z = 11x + 7y.

Subject to the constraints
2x + y  6, x  2, x  0, y  0
in the feasible region occurs at the corner point (0, 6).

Reason (R) If the feasible region of the given LPP is bounded, then the maximum and minimum value of
the objective function occurs at corner points.

DESCRIPTIVE QUESTIONS

VERY SHORT ANSWER TYPE QUESTIONS

12. Write the linear inequation represented by the shaded region.

13. The corner points of the feasible region determined by the system of linear constraints are (0,10),
(5, 5), (15,15), (0, 20). Let Z = px + qy, where p, q>0. Then, find the condition on p and q, so that the
maximum of Z occurs at both the points (15,15) and (0,10).

GK INSTITUTE OF COMMERCE
 6

14. The feasible region for an LPP is shown in the following figure.

Then, find the minimum value of Z = 11x + 7y.

15. Find the maximum value of Z = Ax + 3y, if the feasible region for an LPP is as shown below.

16. The corner points of the feasible region for the LPP are 4(15,0), B(40,0), C(6,12) and D(4,18) of the
objective function of LPP is Z=20x +10y, then find the minimize value of Z.

SHORT ANSWER TYPE QUESTIONS

17. A diet for a sick person must contain atleast 4000 units of vitamins, 50 units of minerals and 1400
calories. Two foods A and B are available at a cost of ₹ 4 and ₹ 3 per unit, respectively. Food A
contains 200 units of vitamins, 1 unit of minerals and 40 calories. Food B contains 100 units of
vitamins, 2 units of minerals and 40 calories. Express this problem as a linear programming
problem.

18. A man rides his motorcycle at the speed of 50 km/h. He has to spend ₹ 2 per km on petrol. If he
rides it at a faster speed of 80 km/h, the petrol cost increases to ₹ 3 per km. He has atmost ₹ 120 to
spend on petrol and one hour time. He wishes to find the maximum distance that he can travel.
Express this problem as a linear programming problem.

19. Feasible region (shaded) for an LPP is shown in the following figure, Maximise Z =5x + 7y.

GK INSTITUTE OF COMMERCE
 7

Directions (Q. Nos. 20-23) Solve the following LPP graphically.

20. Maximise Z =3x + 2y, subject to constraints are x + y  8, 3x + 5y  15 and x, y  0.

21. Maximise Z = 3x + 4y, subject to constraints are x + y  1; x  0, y  0.

22. Minimise Z = 2x + 4y, subject to constraints are x + y  8, x + 4y  12, x  3, y  2 and x, y  0.

23. Maximise and minimise Z = 3x – 4y, subject to constraints are x – 2y  0, - 3x + y  4, x – y  6 and

x, y  0.

LONG ANSWER TYPE QUESTIONS

24. A dietician has to develop a special diet using two foods P and Q. Each packet (containing 30 g) of
food P contains 12 units of calcium, 4 units of iron, 6 units of cholesterol and 6 units of vitamin A.
Each packet of the same quantity of food Q contains 3 units of calcium, 20 units of iron, 4 units of
cholesterol and 3 units of vitamin A. The diet requires atleast 240 units of calcium, atleast 460 units
of iron and atmost 300 units of cholesterol.
How many packets of each food should be used to minimise the amount of vitamin A in the diet?
What is the minimum amount of vitamin A?

25. A dietician wishes to mix together two kinds of foods X and Y in such a way that the mixture
contains atleast 10 units of vitamin A, 12 units of vitamin B and 8 units of vitamin C.
The vitamin contents of 1 kg food is given below
Food Vitamin A Vitamin B Vitamin C
X 1 2 2
Y 2 2 2
1 kg of food X costs of ₹ 16 and 1 kg of food Y costs ₹ 20. Find the least cost of the mixture, which
will produce the required diet?

26. A manufacturer produces nuts and bolts. It takes 1 hour of work on machine A and 3 h on machine
B to produce a package of nuts while it takes 3 h on machine A and 1 h on machine B to produce a
package of bolts. He earns a profit of ₹ 2.50 per package of nuts and ₹ 1.00 per package of bolts.
How many packages of each type should he produce each day so as to maximise his profit, if he
operates his machines for at most 12 h a day? Formulate this problem as a linear programming
problem and solve it graphically.

27. One kind of cake requires 200 g of flour and 25 g of fat and another kind of cake requires 100 g of
flour and 50 g of fat. Find the maximum number of cakes which can be made from 5 kg of flour
and 1 kg of fat assuming that there is no shortage of other ingredients used in making the cakes.
Formulate the above as a linear programming problem and solve it graphically.

28. A firm deals with two kinds of fruit juice. These are mixed and two mixtures are sold as soft drink
A and B. 1 tin of A requires 4 of pineapple and 1 of orange juice. 1 tin of B requires 2 of pineapple
and 3 of orange juice. The firm has only 46 of pineapple juice and 24 of orange juice. Each tin of A
and B are sold at a profit of ₹ 4 and ₹ 3, respectively. How many tins of each type should the firm
produce to maximise the profit? Solve the problem graphically.

29. A carpenter has 20 and 15 sq m of plywood and sunmica, respectively. He produces products A and
B. Product A requires 2 and 1 sq m and product B requires 1 and 3 sq m of plywood and sunmica,
respectively. If the profit on one piece of product A is ₹ 30 and on one piece of product B is ₹ 20,
then how many pieces of products A and B should he make to maximise his profit?

GK INSTITUTE OF COMMERCE
 8

30. A small firm manufactures gold rings and chains. The total number of rings and chains
manufactured per day is atmost 24. It takes 1h to make a ring and 30 min to make a chain. The
maximum number of hours available per day is 16. If the profit on a ring is ₹ 300 and that on a
chain is ₹ 190, then find the number of rings and chains that should be manufactured per day, so
as to earn the maximum profit, make it as an LPP and solve it graphically.

31. A manufacturer of patient medicines is preparing plan on medicines A and B. There are sufficient
raw materials available to make 20000 bottles of A and 40000 bottles of B, but there are only 45000
bottles into which either of the medicines can be put. Further, it takes 3 h to prepare enough
material to fill 1000 bottles of A, it takes 1 h to prepare enough material to fill 1000 bottles of B and
there are 66 h available for this operation. The profit is ₹ 8 per bottle for A and ₹ 7 per bottle for
B. How should the manufacturer schedule his production in order to maximise his profit?

32. A company manufactures two types of screws A and B. All the screws have to pass through a
threading machine and a slotting machine. A box of type A screw require 2 min on the threading
machine and 3 min on the slotting machine. A box of type B screws requires 8 min on the threading
machine and 2 min on the slotting machine. In a week, each machine is available for 60 h.
On selling these screws, the company gets a profits of ₹ 100 per box on type A screws and ₹ 170 per
box on type B screws. Formulate this problem as an LPP given that the objective is to maximise
profit. Solve the linear programming problem and determine the maximum profit to the
manufacturer.

33. A manufacturer produces two products A and B. Both the products are processed on two different
machines. The available capacity of first machine is 12 h and that of second machine is 9 h per day.
Each unit of product A requires 3 h on both machines and each unit of product B requires 2 h on
first machine and 1 h on second machine. Each unit of product A is sold at a profit of ₹ 7 and B at
a profit of ₹ 4. Find the production level per day for maximum profit graphically.

34. A farmer mixes two brands P and Q of cattle feed. Brand P. costing ₹ 250 per bag, contains 3 units
of nutritional element A, 2.5 units of elements B and 2 units of element C.

Brand Q, costing ₹ 200 per bag. contains 1.5 units of nutritional element A, 2.5 units of element B
and 3 units of element C. The minimum requirements of nutrients A, B and C are 18 units, 45 units
and 24 units, respectively. Determine the number of bags of each brand which should be mixed in
order to produce a mixture having a minimum cost per bag? What is the minimum cost of the
mixture per bag?

35. A merchant plans to sell two types of personal computers, a desktop model and a portable model
that will cost ₹ 25000 and ₹ 40000, respectively. He estimates that the total monthly demand of
computers will not exceed 250 units. Determine the number of units of each type of computers which
the merchant should stock to get maximum profit, if he does not want to invest more than ₹ 70 lakh
and his profit on the desktop model is ₹ 4500 and on the portable model is ₹ 5000. Make it as an
LPP and solve it graphically.

36. A manufacturer makes two types A and B of tea cups. Three machines are needed for this purpose
and the time (in minutes) required for each cup on the machine is given below
Machines
Type
I II III
A 4 6 2
B 2 0 3

GK INSTITUTE OF COMMERCE
 9

Each machine is available for a maximum of 2 h per day. The profit on each cup of type A is ₹ 6
and that on each cup of type B is ₹ 5. Show that 15 tea cups of type A and 30 of type B should be
manufactured in a day to get the maximum profit.

37. A library has to accommodate two different types of books on a shelf. The books are 6 cm and 4 cm
thick and weight 1 kg and 1 ½ kg each, respectively.
The shelf is 96 cm long and atmost can support a weight of 21 kg. How should the shelf be filled
with the books of two types in order to include the greatest number of books? Make it as an LPP
and solve it graphically.

38. A retired person wants to invest an amount of ₹ 50000. His broker recommends investing in two
type of bonds 'A' and 'B' yielding 10% and 9% return respectively on the invested amount.
He decides to invest atleast ₹ 20000 in bond 'A' and atleast ₹ 10000 in bond 'B'. He also wants to
invest atleast as much in bond 'A' as in bond ‘B’. Solve this linear programming problem
graphically to maximise his returns.

39. In number theory, it is often important to find factors of an integer N. The number N has two trivial
factors, namely 1 and N. Any other factor, if exists, is called non-trivial factor of N. Naresh has
plotted a graph of some constraints (linear inequations) with points A(0,50), B(20, 40), C(50,100),
D(0,200) and E(100,0). This graph is constructed using three non-trivial constraints and two trivial
constraints. One of the non-trivial constraints is x + 2y  100.

Based on the above information, answer the following questions.

(i) What are the two trivial constraints?
(ii) (a) If R1 is the feasible region, then what are the other two non-trivial constraints?
OR
(b) If R1 is the feasible region, then what are the other two non-trivial constraints?
(iii) If R1 is the feasible region, then find the maximum value of objective function
Z = 5x + 2y.
40. A factory manufactures tennis rackets and cricket bats. A tennis racket takes 1 ½ h of machine time
and 3 h of craftsmanship in its making, while a cricket bat takes 3 h of machine time and 1 h of
craftsmanship. In a day, the factory has availability of not more than 42 h of machine time and 24
h of craftsmanship. Profit on a racket and on a bat are ₹ 20 and ₹ 10 respectively.
Based on the above information, answer the following questions.
(i) If x and y are the numbers of bats and rackets manufactured by the factory, then write the
expression of total profit.
(ii) Write the constraint that relates the number of craftsmanship hours.
(iii) Determine the maximum profit (in ₹) earned by the factory.
OR
How many bats and rackets respectively, are manufactured to earn maximum profit?

GK INSTITUTE OF COMMERCE
 10

HINS & SOLUTION

1. (b) 2. (c) 3. (b) 4. (d) 5. (d) 6. (d) 7. (c) 8. (c)
9. (a) 10. (a) 11. (a)

12. 4x – 2y  – 3

13. q = – 3p

14. 21

15. 1112

16. 240

17. Min Z = 4x + 3y, subject to constraints 200x + 100y  4000, x + 2y  50, 40y  1400 and x  0, y  0.

18. Max Z = x + y, subject to constraints are 2x + 3y  120, 8x + 5y  400 and x  0, y  0.

19. Z = 43 at B(3, 4)

20. There is no feasible region, so no maximum value exist.

21. Maximum value of Z is 4 at (0, 1).

22. Unbounded solution

23. Maximum value = 12 and no minimum value exist.

24. 15 packets of food P and 20 packets of food Q should minimum amount of vitamin A is 150 units.

25. Mixture contains 2 kg of food X and 4 kg of food Y, Minimum cost = ₹112.

26. The manufacturer should produce 3 packages of nuts and 3 packages of bolts each day for maximum
profit = ₹10.5.

27. Number of first kind cake = 20, number of second kind cake =10, maximum number of cakes =30.

28. For maximise the profit, the firm should produce 9 tins of drink A and 5 tins of drink B and the maximum
profit will be ₹51.

29. He should make 9 pieces of product A and 2 pieces of product B to maximise the profit.

30. 8 rings and 16 chains

31. 10,500 bottles of type A, 34,500 bottles of type B; maximum profit = ₹32,5500.

32. The maximum profit to the manufacturer is ₹138600.

33. Maximum profit, manufacturer produce 2 units of product A and 3 units of product B.

34. 3 bags of brand P and 6 bags of brand Q should be used in the mixture of minimize the cost to ₹1950.

35. The profit is maximum, i.e. ₹11,50,000 when 200 desktop computers and 50 portable computers are
stocked.

GK INSTITUTE OF COMMERCE
 11

36. Hint max, Z = 6x +5y,

Subject to constraints
4x + 2y  120, 6x + 0y  120, 2x +3y  120 and x, y  0

37. 12 and 6

38. To get maximum returns he invest ₹40,000 in Bond A and ₹10,000 in Bond B.

39. (i) x  0, y  0
(ii) (a) 2x – y  0 and 2x + y  200
(b) x + 2y  100 and 2x + y  200
(iii) The maximum value of the objective function Z = 5x + 2y is 450.

40. (i) Let the number of bats and rackets manufactured by the factory be x and y respectively.
 Maximise profit Z = 10x +20y
(ii) Subject to constraints that relates to craftsman hours 3x+1.5y  42, x + 3y  24 and x  0, y  0
(iii) Graph of linear inequality are

The corner points of the feasible region are O(0,0), A(14,0), B(12,4) and C(0,8).
Corner Points Z = 10x + 20y
O(0,0) 0
A(14,0) 140
B(12,4) 200(Maximum)
C(0,8) 160
Maximum profit earn by taking is ₹200 at B(12,4).
OR
The numbers of bats and rackets are manufactured to earn maximum profit is ₹12 and 4
respectively.

GK INSTITUTE OF COMMERCE