CBSE Class 12 Mathematics Linear Programming Geometry VBQs Set A

BASIC CONCEPTS

• Definition: Linear programming (LP) is an optimisation technique in which a linear function is optimised (i.e., minimised or maximised) subject to certain constraints which are in the form of linear inequalities or/and equations. The function to be optimised is called objective function.
• Applications of Linear Programming: Linear programming is used in determining optimum combination of several variables subject to certain constraints or restrictions.

Formation of Linear Programming Problem (LPP): The basic problem in the formulation of a linear programming problem is to set-up some mathematical model. This can be done by asking the following questions: For this, let \( x_1, x_2, x_3, \dots, x_n \) be the variables. Let the objective function to be optimized (i.e., minimised or maximised) be given by \( Z \). The problem of determining the values of \( x_1, x_2, \dots, x_n \) which makes \( Z \), a minimum or maximum and which satisfies (ii) and (iii) is called the general linear programming problem.

(a) What are the unknowns (variables)?

(b) What is the objective?

(c) What are the restrictions?

(i) \( Z = c_1 x_1 + c_2 x_2 + \dots + c_n x_n \), where \( c_i x_i (i = 1, 2, \dots, n) \) are constraints.

(ii) Let there be \( mn \) constants and let a be a set of constants such that
\( a_{11} x_1 + a_{12} x_2 + \dots + a_{1n} x_n (\leq, = \text{ or } \geq) b_1 \)
\( a_{21} x_1 + a_{22} x_2 + \dots + a_{2n} x_n (\leq, = \text{ or } \geq) b_2 \)
\(\dots \dots \dots\)
\(\dots \dots \dots\)
\( a_{m1} x_1 + a_{m2} x_2 + \dots + a_{mn} x_n (\leq, = \text{ or } \geq) b_m \)

(iii) Finally, let \( x_1 \geq 0, x_2 \geq 0, \dots, x_n \geq 0 \), called non-negative constraints.

• General LPP:

(a) Decision variables: The variables \( x_1, x_2, x_3, \dots, x_n \) whose values are to be decided, are called decision variables.

(b) Objective function: The linear function \( Z = c_1 x_1 + c_2 x_2 + \dots + c_n x_n \) which is to be optimized (maximised or minimised) is called the objective function or preference function of the general linear programming problem.

(c) Structural constraints: The inequalities given in (ii), are called the structural constraints of the general linear programming problem. The structural constraints are generally in the form of inequalities of \( \geq \) type or \( \leq \) type, but occasionally, a structural constraint may be in the form of an equation.

(d) Non-negative constraints: The set of inequalities (iii) is usually known as the set of non-negative constraints of the general LPP. These constraints imply that the variables \( x_1, x_2, \dots, x_n \) cannot take negative values.

(e) Feasible solution: Any solution of a general LPP which satisfies all the constraints, structural and non-negative, of the problem, is called a feasible solution to the general LPP.

(f) Optimum solution: Any feasible solution which optimizes (i.e., minimises or maximises) the objective function of the LPP is called optimum solution.

Requirements for Mathematical Formulation of LPP

Before getting the mathematical form of a linear programming problem, it is important to recognize the problem which can be handled by linear programming problem. For the formulation of a linear programming problem, the problem must satisfy the following requirements:

(i) There must be an objective to minimise or maximise something. The objective must be capable of being clearly defined mathematically as a linear function.

(ii) There must be alternative sources of action so that the problem of selecting the best course of actions may arise.

(iii) The resources must be in economically quantifiable limited supply. This gives the constraints to LPP.

(iv) The constraints (restrictions) must be capable of being expressed in the form of linear equations or inequalities.

Solving Linear Programming Problem

To solve linear programming problems, Corner Point Method is adopted. Under this method following steps are performed:

Step I. At first, feasible region is obtained by plotting the graph of given linear constraints and its corner points are obtained by solving the two equations of the lines intersecting at that point.

Step II. The value of objective function \( Z = ax + by \) is obtained for each corner point by putting its \( x \) and \( y \)-coordinate in place of \( x \) and \( y \) in \( Z = ax + by \). Let \( M \) and \( m \) be largest and smallest value of \( Z \) respectively.
Case I: If the feasible region is bounded, then \( M \) and \( m \) are the maximum and minimum values of \( Z \).
Case II: If the feasible region is unbounded, then we proceed as follows:

Step III. The open half plane determined by \( ax + by > M \) and \( ax + by < m \) are obtained.
Case I: If there is no common point in the half plane determined by \( ax + by > M \) and feasible region, then \( M \) is maximum value of \( Z \), otherwise \( Z \) has no maximum value.
Case II: If there is no common point in the half plane determined by \( ax + by < m \) and feasible region, then \( m \) is minimum value of \( Z \), otherwise \( Z \) has no minimum value.

Fill in the Blanks

Question. The corner points of the feasible region of an LPP are (0, 0), (0, 8), (2, 7), (5, 4) and (6, 0). The maximum profit \( P = 3x + 2y \) occurs at the point ____________.
Answer: We have, \( P = 3x + 2y \). At point (5, 4), \( P = 3 \times 5 + 2 \times 4 = 15 + 8 = 23 \) will be maximum profit. Therefore, the answer is (5, 4).

Question. The common region determined by all the linear constraints of a LPP is called the ____________ region.
Answer: feasible

Question. If the feasible region for a LPP is ____________, then the optimal value of the objective function \( Z = ax + by \) may or may not exist.
Answer: unbounded

Question. The feasible region for an LPP is always a ____________ polygon.
Answer: convex

Short Answer Questions-I

Question. A small firm manufactures necklaces and bracelets. The total number of necklaces and bracelets that it can handle per day is at most 24. It takes one hour to make a bracelet and half an hour to make a necklace. The maximum number of hours available per day is 16. If the profit on a necklace is ₹ 100 and that on a bracelet is ₹ 300. Formulate an LPP for finding how many of each should be produced daily to maximise the profit. It is being given that at least one of each must be produced.
Answer: Let \( x \) and \( y \) be the number of necklaces and bracelets manufactured by small firm per day. If \( P \) be the profit, then objective function is given by \( P = 100x + 300y \) which is to be maximised under the constraints:
\( x + y \leq 24 \)
\( \frac{1}{2}x + y \leq 16 \)
\( x \geq 1, y \geq 1 \)

Question. Two tailors, A and B, earn ₹ 300 and ₹ 400 per day respectively. A can stitch 6 shirts and 4 pairs of trousers while B can stitch 10 shirts and 4 pairs of trousers per day. To find how many days should each of them work and if it is desired to produce at least 60 shirts and 32 pairs of trousers at a minimum labour cost, formulate this as an LPP.
Answer: Let A and B work for \( x \) and \( y \) days respectively. Let \( Z \) be the labour cost. \( Z = 300x + 400y \). Subject to constraints:
\( 6x + 10y \geq 60 \)
\( 4x + 4y \geq 32 \)
\( x, y \geq 0 \)

Question. A company produces two types of goods A and B, that require gold and silver. Each unit of type A requires 3 g of silver and 1 g of gold while that of type B requires 1 g of silver and 2 g of gold. The company can produce a maximum of 9 g of silver and 8 g of gold. If each unit of type A brings a profit of ₹ 40 and that of type B ₹ 50, formulate LPP to maximize profit.
Answer: Let \( x \) and \( y \) be the number of goods A and goods B respectively. If \( P \) be the profit then \( P = 40x + 50y \) which is to be maximised under constraints:
\( 3x + y \leq 9 \)
\( x + 2y \leq 8 \)
\( x \geq 0, y \geq 0 \)

Question. A firm has to transport at least 1200 packages daily using large vans which carry 200 packages each and small vans which can take 80 packages each. The cost for engaging each large van is ₹ 400 and each small van is ₹ 200. Not more than ₹ 3,000 is to be spent daily on the job and the number of large vans cannot exceed the number of small vans. Formulate this problem as a LPP given that the objective is to minimize cost.
Answer: Let the number of large vans and small vans be \( x \) and \( y \) respectively. Here transportation cost \( Z \) be objective function, then \( Z = 400x + 200y \), which is to be minimized under constraints:
\( 200x + 80y \geq 1200 \Rightarrow 5x + 2y \geq 30 \)
\( 400x + 200y \leq 3000 \Rightarrow 2x + y \leq 15 \)
\( x \leq y, x \geq 0, y \geq 0 \)

Question. (Diet problem) 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 contain 3 units of calcium, 20 units of iron, 4 units of cholesterol and 3 units of vitamin A. The diet requires at least 240 units of calcium, at least 460 units of iron and at most 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?

Answer: 15 packets of food P and 20 packets of food Q, minimum amount of vitamin A is 150 units.

Question. One kind of cake requires 300 g of flour and 15 g of fat, another kind of cake requires 150 g of flour and 30 g of fat. Find the maximum number of cakes which can be made from 7.5 kg of flour and 600 g of fat, assuming that there is no shortage of the other ingredients used in making the cakes. Make it as an LPP and solve it graphically?

Answer: 20 cakes of type 1 and 10 cakes of type II to get maximum number of cakes

Question. In order to supplement daily diet, a person wishes to take some X and some Y tablets. The contents of iron, calcium and vitamins in X and Y (in miligrams per tablet) are given below:
Tablets: Iron, Calcium, Vitamins
X: 6, 3, 2
Y: 2, 3, 4
The person needs at least 18 milligrams of iron, 21 milligrams of calcium and 16 milligrams of vitamins. The price of each tablet of X and Y is ₹2 and ₹1 respectively. How many tablets of each should the person take in order to satisfy the above requirement at the minimum cost?

Answer: \( x = 1, y = 6 \) minimum value 8.

Question. A company manufactures three kinds of calculators: A, B and C in its two factories I and II. The company has got an order for manufacturing at least 6400 calculators of kind A, 4000 of kind B and 4,800 of kind C. The daily output of factory I is of 50 calculators of kind A, 50 calculators of kind B, and 30 calculators of kind C. The daily output of factory II is of 40 calculators of Kind A, 20 of kind B and 40 of kind C. The cost per day to run factory I is ₹12,000 and factory II is ₹15,000. How many days do the two factories have to be in operation to produce the order with the minimum cost? Formulate this problem as an LPP and solve it graphically.

Answer: Factory I run for 80 days and Factory II run for 60 days to get minimum cost 2184000.
Hint: Objective function \( Z = 12000x + 15000y \)
Subject to constraints:
\( 5x + 4y \geq 640 \); \( 5x + 2y \geq 400 \); \( 3x + 4y \geq 480 \); \( x, y \geq 0 \)

Question. A dealer deals in two items only – item A and item B. He has ₹50,000 to invest and a space to store at most 60 items. An item A costs ₹2,500 and an item B costs ₹500. A net profit to him on item A is ₹500 and on item B ₹150. If he can sell all the items that he purchases, how should he invest his amount to have maximum profit? Formulate an LPP and solve it graphically.

Answer: Dealer deals in 10 items of A and 50 items of B to get maximum profit ₹12500
Hint: Objective function: \( Z = 500x + 150y \)
Subject to constraints:
\( x + y \leq 60 \); \( 5x + y \leq 100 \); \( x, y \geq 0 \)

Question. The postmaster of a local post office wishes to hire extra helpers during the Deepawali season, because of a large increase in the volume of mail handling and delivery. Because of the limited office space and the budgetary conditions, the number of temporary helpers must not exceed 10. According to past experience, a man can handle 300 letters and 80 packages per day, on the average, and a woman can handle 400 letters and 50 packets per day. The postmaster believes that the daily volume of extra mail and packages will be no less than 3400 and 680 respectively. A man receives ₹225 a day and a woman receives ₹200 a day. How many men and women helpers should be hired to keep the pay-roll at a minimum? Formulate an LPP and solve it graphically.

Answer: Minimum payroll 6 men and 4 women must be hired minimum cost ₹2150
Hint: Objective function, \( Z = 225x + 200y \)
Subject to constraints: \( x + y \leq 10 \); \( 3x + 4y \geq 34 \); \( 8x + 5y \geq 68 \); \( x, y \geq 0 \)

Question. A retired person wants to invest an amount of ₹50,000. 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 at least 20,000 in bond ‘A’ and at least 10,000 in bond ‘B’. He also wants to invest at least as much in bond ‘A’ as in bond ‘B’. Solve this linear programming problem graphically to maximise his returns.

Answer: ₹40000 in bond A and ₹10,000 in bond B for a maximum return of ₹4900.

Question. A company manufactures two types of cardigans: type A and type B. It costs ₹360 to make a type A cardigan and ₹120 to make a type B cardigan. The company can make at most 300 cardigans and spend at most ₹72000 a day. The number of cardigans of type B cannot exceed the number of cardigans of type A by more than 200. The company makes a profit of ₹100 for each cardigan of type A and ₹50 for every cardigan of type B. Formulate this problem as a linear programming problem to maximise the profit of the company. Solve it graphically and find maximum profit.

Answer: 150 cardigans of type A and 150 of type B for a maximum profit of 22,500.

Question. There are two types of fertilisers ‘A’ and ‘B’. ‘A’ consists of 12% nitrogen and 5% phosphoric acid whereas ‘B’ consists of 4% nitrogen and 5% phosphoric acid. After testing the soil conditions, farmer finds that he needs at least 12 kg of nitrogen and 12 kg of phosphoric acid for his crops. If ‘A’ costs ₹10 per kg and ‘B’ costs ₹8 per kg, then graphically determine how much of each type of fertiliser should be used so that nutrient requirements are met at a minimum cost.

Answer: Minimum cost ₹1980, 30 kg of fertiliser A and 210 kg of fertiliser B should be used.

Question. 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 hours and that of second machine is 9 hours per day. Each unit of product A requires 3 hours on both machines and each unit of product B requires 2 hours on first machine and 1 hour on second machine. Each unit of product A is sold at ₹7 profit and that of B at a profit of ₹4. Find the production level per day for maximum profit graphically.

Answer: Manufacturer will get maximum profit of ₹26 by producing 2 units of A and 3 units of B.

Question. A manufacturer produces nuts and bolts. It takes 1 hour of work on machine A and 3 hours on machine B to produce a package of nuts. It takes 3 hours on machine A and 1 hour on machine B to produce a package of bolts. He earns a profit of ₹17.50 per package on nuts and ₹7.00 per package on bolts. If he operates his machines for at the most 12 hours a day, the formulate the linear programming problem and solve it graphically.

Answer: Maximum profit is ₹73.5, when 3 package of nuts and 3 package of bolts are produced.

Question. A dietician wishes to mix two types of foods in such a way that the vitamin contents of the mixture contains at least 8 units of vitamin A and 10 units of vitamin C. Food I contains 2 units/kg of vitamin A and 1 unit/kg of vitamin C while Food II contains 1 units/kg of vitamin A and 2 units/kg of vitamin C. It costs ₹5 per kg to purchase Food I and ₹7 per kg to purchase Food II. Determine the minimum cost of such a mixture. Formulate the above as a LPP and solve it graphically.

Answer: Minimum cost of food mixture is ₹38, when 2kg of Food I and 4 kg of food II are mixed.