## Chapter 1 Linear Programming

**Linear Inequations in Two Variables**

The inequalities of the form

ax + by ≤ c, ax + by < c, ax + by ≥ c and ax + by > c are called linear inequations in two variables x and y.

The points (x,y) for which the inequation is true, constitute its solution set.

**Graph of a Linear Inequation**

Let us consider an inequation, ax + by ≤ c. For drawing its graph to obtain a solution set, we proceed as under.

Step 1 Consider the equation ax + by = c, and plot the resulting line. In case of strict inequalities < or >, draw the line as dotted, otherwise mark it thick.

Step 2 Choose a point [if possible (0,0)], not lying on this line. Substitute its coordinates in the inequation. If the inequation is statisfied then shade the portion of the plane which containes the chosen point; otherwise shade the portion which does not contain this point.

The shaded portion represents the solution set. The dotted line is not a part of the shaded region while the thick line is a part of it.

**Example Graph the solution set of the inequation 2x – y ≥ 1.**

**Solution**

Consider the equation 2x – y = 1.

We may write it as \(\frac{x}{(1 / 2)}+\frac{y}{-1}=1.\)

This shows that the line 2x – y = 1 makes intercepts of \(\frac{1}{2}\) and -1 on the axes. Thus, the line meets the x-axis at A(\(\frac{1}{2}\), 0) and the y-axis at B(0, -1). We plot these points and join them by a thick line.

Consider O(0,0). Clearly, (0,0) does not satisfy the given inequation. So, out of the portions divided by this line, the one not containing O(0,0), together with the points on the line, forms the solution set.

**Simultaneous Inequations**

The solution set of a system of linear inequations in two variables is the set of all points (x,y) which satisfy all the inequations in the system simultaneously.

So, we find the region of the plane common to all the portions comprising the solutions sets of the given inequations. When there is no region common to all the solutions of the given inequations, we say that the solution set of the system is empty.

The linear inequations are also known as linear constraints.

## Solved Examples

**Example 1 Draw the graph of the solution set of the system of inequations 2x + 3y ≥ 6, 4y ≤ 4, x ≥ 0 and y ≥ 0.**

**Solution**

** 2x + 3y ≥ 6, 4y ≤ 4, x ≥ 0 and y ≥ 0**

Consider the equations

2x + 3y = 6, x + 4y = 4, x = 0 and y = 0.

Now, 2x + 3y = 6 ⇒ \(\frac{x}{3}+\frac{y}{2}=1.\)

This line meets the axes at A(3,1) and B(0,2). Join these points and draw a thick line. Clearly, the portion not containing (0,0) represents the solution set of the inequation 2x + 3y ≥ 6.

Again, x + 4y = 4 ⇒ \(\frac{x}{4}+\frac{y}{1}=1 \text {. }\)

This line meets the axes at C(4,0) and D(0,1). Join these points and draw a thick line. Clearly, the portion containing (0,0) represents the solution set of the inequation x + 4y ≤ 4.

Clearly, x ≥ 0 is represented by the y-axis and the portion on its right-hand side.

Also, y ≥ 0 is represented by the x-axis and the portion above the x-axis.

Hence, the shaded region represents the solution set of the given inequations.

**Example 2 Exhibit graphically the solution set of the system of linear inequations x + y ≥ 1, 7x + 9y ≤ 63, y ≤ 5, x ≤ 6, x ≥ 0 and y ≥ 0.**

**Solution**

** x + y ≥ 1, 7x + 9y ≤ 63, y ≤ 5, x ≤ 6, x ≥ 0 and y ≥ 0**

x + y = 1 meets the axes at A(1,0) and B(0,1).

Join these points by a thick line. Clearly, the portion containing (0,0) is the solution set of x + y ≥ 1.

\(7 x+9 y=63 \Rightarrow \frac{x}{9}+\frac{y}{7}=1 .\)This line meets the axes at C(9,0) and D(0,7). Join these points by a thick line. Clearly, the portion containing (0,0) is the solution set of 7x + 9y ≤ 63.

y = 5 is a line parallel to the x-axis at a distance 5 from the x-axis and the portion containing O(0,0) is the solution set of the inequation y ≤ 5.

x = 6 is a line parallel to the y-axis at a distance 6 from the y-axis and the portion containing (0,0) is the solution set of x ≤ 6.

Clearly, x ≥ 0 has a solution represented by the y-axis and the portion on its right. Also, y ≥ 0 has a solution represented by the x-axis and the portion above it.

The shaded region represents the solution set of the given system of inequations.

**Example 3 Find the linear constraints for which the shaded area in the figure below is the solution set.**

**Solution**

Consider the line 3x + 4y = 18.

Clearly, O(0,0) satisfies 3x + 4y ≤ 18.

Clearly, the shaded area and (0,0) lie on the same side of the line 3x + 4y = 18.

So, we must have 3x + 4y ≤ 18.

Consider the line x – 6y = 3.

Clearly, (0,0) satisfies the inequation x – 6y ≤ 3.

Also, the shaded area and (0,0) lie on the same side of the line x – 6y = 3.

So, we must have x – 6y ≤ 3.

Consider the line 2x + 3y = 3.

Clearly, (0,0) satisfies the inequation 2x + 3y ≤ 3.

But, the shaded region and the point (0,0) lie on the opposite sides of the line 2x + 3y = 3.

So, we must have 2x + 3y ≥ 3.

Consider the line -7x + 14y = 14.

Clearly, (0,0) satisfies the inequation -7x + 14y ≤ 14.

Also, the shaded region and the point (0,0) lie on the same side of the line -7x + 14y = 14.

So, we must have -7x + 14y ≤ 14.

The shaded region is above the x-axis and on the right-hand side of the y-axis, so we have y ≥ 0 and x ≥ 0.

Thus, the linear constraints for which the shaded area in the given figure is the solution set, are

3x + 4y ≤ 18, x – 6y ≤ 3, 2x + 3y ≥ 3, -7x + 14y ≤ 14, x ≥ 0 and y ≥ 0.

## Linear Programming

Linear programming is the method used in decision making in business for obtaining the maximum or minimum value of a liear expression, subject to satisfying certain given linear inequations.

The linear expression is known as an objective function and the linear inequations are known as linear constraints.

**Linear Constrainst** In business or industry we want to make the best use of our limited resources like money,labour, time, materials, ect.

The limitatiions on the resoureces can often be expressed in the form of linear inequations, known as linear constraints.

**Objective Function** A linear function of the involved variables, which we want to maximize or minimize, subject to the given linear constraints, is known as objective function.

**Optimal Value Of An Objective Function** The maximum or minimum value of an function is known as its optimal value.

**Feasible Solution** A set of values of the variables satisfying all the constraints is known as a feasible solution of the system of inequations.

**Optimal Solution** A feasible solution which leads to the optimal value of an objective function is known as an optimal solution of the system of inequations.

**Optimization Techniques** The processes of obtaining the optimal values of a system of inequations are called optimization techniques.

**A Linear Programming Problem (LPP)**

A general linear programming problem consists of maximizing or minimizing an objective function, subject to certain given constraints.

**Formulation of a Linear programming problem (LPP)**

**Working rules**

Step 1 Identify the unknowns in the given LPP. Denote them by x and y.

Step 2 Formulae the objective function in terms of x and y. Be sure whether it is to be maximized or minimized.

Step 3 Translate all the constraints in the form of linear inequations.

Step 4 Solved these inequations simultaneously. Mark the common area by a shaded region. This is the feasible region.

Step 5 Find the coordinates of all the vertices of the feasible region.

Step 6 Find the value of the objective function at each vertex of the feasible region.

Step 7 Find the values of x and y for which the objective function Z = ax + by has maximum or minimum value (as the case may be).

**Graphical Solution of an LPP**

We shall restrict ourselves to the case of an LPP in two variables. We shall consider at least three constraints or inequations. Each inequation gives rise to a line in the plane. For a simultaneous solution of these inequations, we consider the region common to their solution of these inequations, we consider the region common to their solution sets. In each case we obtain such a region, a convex polygon, i.e., a closed region bounded by straingth lines with the property that the line joining any two points of the region lies wholly in the region.

The maximum or minimum value of a linear function over a convex polygon occurs at some vertex of the polygon.

So, we look at the values of the objective function at the vertices of the set of feasible solutions. The largest of these values is the maximum value of the objective function and the smallest of these values is the minimum.

**Graphical Method**

It will be clear from the following solved examples.

## Solved Examples

**Example 1 Solve the following problem graphically: Minimize and maximize z = 3x + 9y, subject to the constraints x + 3y ≤ 60, x + y ≥ 10, x ≤ y, x ≥ 0 and y ≥ 0.**

**Solution**

**Given**

**Minimize and maximize z = 3x + 9y, subject to the constraints x + 3y ≤ 60, x + y ≥ 10, x ≤ y, x ≥ 0 and y ≥ 0.**

Region represented by x + 3y ≤ 60

Consider the equation x + 3y = 60.

x = 0 ⇒ 3y = 60 ⇒ y = 20

y = 0 ⇒ x = 60

Plot the points A(0,20) and B(60,0). Join AB and produce it both ways.

Putting x = 0 and y = 0, we get 0 + 3 x 0 = 0 ≤ 60.

∴ O(0,0) lies in the region x + 3y ≤ 60.

So, the region containing the origin is the solution set of x + 3y ≤ 60.

Region represented by x + y ≥ 10

Consider the equation x + y = 10.

x = 0 ⇒ y = 10

y = 0 ⇒ x = 10

Plot the points C(0,10) and D(10,0). Joint CD and produce it both ways.

Now, x = 0, y = 0 ⇒ 0 + 0 ≥ 10 is not true.

∴ O(0,0) does not lie in the region x + y ≥ 10.

Region represented by x ≤ y, i.e., x – y ≤ 0

Consider the equation x = y, i.e., x – y = 0.

Clearly, x = 0 ⇒ y = 10.

And, x = 20 ⇒ y = 20.

Plot the points E(10,10) and F(20,20). Join EF and produce it both ways.

Clearly, O(0,0) satisfies x – y ≤ 0.

∴ O(0,0) lies in the region x – y ≤ 0.

We know that:

x ≥ 0 is the y-axis and the region on its RHS.

y ≥ 0 is the x-axis and the region above the x-axis.

On solving x = y and x + y = 10, we get the point G(5,5).

On solving x = y and x + 3y = 60, we get H(15,15).

Thus, the feasible region is ACGH, as shown in the figure.

Value of z = 3x + 9y:

(1) At A(0,20) it is (3 x 0 + 9 x 20) = 180.

(2) At C(0,10) it is (3 x 0 + 9 x 10) = 90.

(3) At G(5,5) it is (3 x 5 + 9 x 5) = 60.

(4). At H(15,15) it is (3 x 15 + 9 x 15) = 180.

So, the minimum value of z is 60 and its maximum value is 180.

**Example 2 A furniture dealar deals in only two items: tables and chairs. He has Rs 5000 to invest and a space to store at most 60 pieces. A table costs him Rs 250 and a chair, Rs 50. He can sell a table at a profit of Rs 50 and a chair at a profit of Rs 15. Assuming that he can sell all the items that he buys, how should he invest his money in order that he may maximize his profit?**

**Solution**

**Given**

A furniture dealar deals in only two items: tables and chairs. He has Rs 5000 to invest and a space to store at most 60 pieces. A table costs him Rs 250 and a chair, Rs 50. He can sell a table at a profit of Rs 50 and a chair at a profit of Rs 15. Assuming that he can sell all the items that he buy

This problem can be formulated as under.

Let x and y be the required numbers of tables and chairs respectively. Then, clearly we have

x ≥ 0, y ≥ 0; x + y ≤ 60;

250x + 50y ≤ 5000, i.e., 5x + y ≤ 100.

Let P be the profit function. Then, P = 50x + 15y.

Now, we have to maximize P.

Now, x + y = 60 ⇒ \(\frac{x}{60}+\frac{y}{60}=1 .\)

This line meets the axes at (60,0) and (0,60). Plot these points and join them to get the line x + y = 60.

Also, 5x + y = 100 ⇒ \(\frac{x}{20}+\frac{y}{100}=1 .\)

This line meets the axes at (20,0) and (0,100). Plot these points and join them to get the line 5x + y = 100.

Also, the line x = 0 is the y-axis and the line y = 0 is the x-axis.

These four straight lines enclose the quadrilateral OABC.

The coordinates of the points O, A, B, C are (0,0), (20,0), (10,50) and (0,60) respectively.

At these points, the corresponding values of P = 50x + 15y are 0, 1000, 1250 and 900 respectively.

Clearly, it is maximum at B(10,50).

So, for a maximum profit, the dealer should purchase 10 tables and 50 chairs.

**Example 3 If a young man rides his motorcycle at 25km per hour, he has to spend Rs 2 per kilometre on petrol; it he rides it at a faster speed of 40 km per hour, the petrol cost increases to Rs 5 per kilometer. He has Rs 100 to spend on petrol and wishes to find the maximum distance he can travel within one hour. Express this as a linear programming problem and then solve it.**

**Solution**

**Given**

If a young man rides his motorcycle at 25km per hour, he has to spend Rs 2 per kilometre on petrol; it he rides it at a faster speed of 40 km per hour, the petrol cost increases to Rs 5 per kilometer. He has Rs 100 to spend on petrol

Suppose that the young man rides x km at 25km per hour and y km at 40km per hour. Then, we have to maximize P = x + y.

Clearly, x ≥ 0, y ≥ 0, 2x + 5y ≤ 100.

Since the available time is at most one hour, we have

\(\frac{x}{25}+\frac{y}{40} \leq 1 or 8x + 5y ≤ 200.\)Now, we solve the system of the inequations.

2x + 5y = 100 ⇒ \(\frac{x}{50}+\frac{y}{20}=1 .\)

This line meets the axes at (50,0) and (0,20). Plot these points and join them to get the line 2x + 5y = 100.

Also, 8x + 5y = 100 ⇒ \(\frac{x}{25}+\frac{y}{40}=1 \text {. }\)

This line meets the axes at (25,0) and (0,40). Plot these points and obtain the line 8x + 5y = 200.

x = 0 is the y-axis and y = 0 is the x-axis.

We find that the solution set of the above system is the shaded region OABC.

The coordinates of O, A, B, C are (0,0), (25,0), \(\left(\frac{50}{3}, \frac{40}{3}\right)\), and (0,20) respectively.

The values of P = x + y at these points are 0, 25, 30 and 20 respectively.

So, P = x + y is maximum when x = \(\frac{50}{3}\) and y = \(\frac{40}{3}\).

Thus, the young man can cover the maximum distance of 30km, if he rides \(\frac{50}{3}\) km at 25 km/h and \(\frac{40}{3}\) km at 40 km/h.

**Example 4 Suppose every gram of wheat provides 0.1g of proteins and 0.25g of carbohydrates, and the corresponding values for rice are 0.005 g and 0.5g respectively. Wheat costs Rs 5 and rice Rs 20 per kilogram. The minimum daily requirements of proteins and carbohydrates for an average man are 50g and 200g respectively. In what quantities should wheat and rice be mixed in the daily diet to provide the minimum daily requirements of proteins and carbohydrate at minimum cost, assuming that both wheat and rice are to be taken in the diet?**

**Solution**

**Given**

Suppose every gram of wheat provides 0.1g of proteins and 0.25g of carbohydrates, and the corresponding values for rice are 0.005 g and 0.5g respectively. Wheat costs Rs 5 and rice Rs 20 per kilogram. The minimum daily requirements of proteins and carbohydrates for an average man are 50g and 200g respectively.

Let x g of wheat and y g of rice be mixed to fulfill the requirements.

Then, we have to minimize the cost function

\(Z=\frac{5 x}{1000}+\frac{20 y}{1000}, \text { i.e., } Z=\frac{x}{200}+\frac{y}{50}\) …(1)

xg of wheat and yg of rice must give at least 50g of proteins.

So, we must have

0.1x + 0.05y ≥ 50 or 2x + y ≥ 1000.

Similarly, xg of wheat and yg of rice must give at least 200 g of carbohydrates.

So, we must have

0.25x + 0.5y ≥ 200 or x + 2y ≥ 800.

Thus, we have to minimize \(Z=\frac{x}{200}+\frac{y}{50}\), subject to the constraints

x > 0, y > 0, 2x + y ≥ 1000 and x + 2y ≥ 800.

2x + y = 1000 ⇒ \(\frac{x}{500}+\frac{y}{1000}=1\)

This line meets the axes at A(500,0) and B(0,1000).

Plot these points and join them to obtain the line 2x + y = 100.

Clearly, (0,0) does not satisfy x + 2y ≥ 1000.

Again, x + 2y = 800 ⇒ \(\frac{x}{800}+\frac{y}{400}=1\)

This line meets the axes at C(800,0) and D(0,400).

Plot these points and join them to obtain the line x + 2y = 800.

Clearly, (0,0) does not satisfy x + 2y ≥ 800.

x = 0 is the y-axis and y = 0 is the x-axis.

We obtain the solution set of the above system, as shown by the shaded region.

Solving 2x + y = 1000 and x + 2y = 800, we get the point of intersection of AB and CD, given by E(400,200).

The minimum value of Z = \(\frac{x}{200}+\frac{y}{50}\) would be at some vertex of the unbounded feasible region BEC.

Clearly, at B we have x = 0, and at C we have y = 0.

Also, the value of Z at E(400,200) = \(\frac{400}{200}+\frac{200}{50}=6\).

So, we must have 400 g of wheat and 200 g of rice.

**Example 5 A firm manufactures two types of products, A and B, and sells them at a profit of Rs 5 per unit of type A and Rs 3 per unit of type B. Each product is processed on two machines, M _{1} and M_{2}. One unit of type A requires one minute of processing time on M_{1} and two minutes of processing time on M_{2}; whereas one unit of type B requires one minute of processing time on M_{1} and one minute on M_{2}. Machines M_{1} and M_{2} are respectively available for at most 5 hours and 6 hours in a day. Find out how many units of each type of product should the firm produce a day in order to maximize the profit. Solve the problem graphically.**

**Solution**

**Given:**

A firm manufactures two types of products, A and B, and sells them at a profit of Rs 5 per unit of type A and Rs 3 per unit of type B. Each product is processed on two machines, M_{1} and M_{2}. One unit of type A requires one minute of processing time on M_{1} and two minutes of processing time on M_{2}; whereas one unit of type B requires one minute of processing time on M_{1} and one minute on M_{2}. Machines M_{1} and M_{2} are respectively available for at most 5 hours and 6 hours in a day.

Let x units of A and y units of B be produced in order to have a maximum profit.

Then, clearly x ≥ 0 and y ≥ 0.

x units of A and y units of B will take (x+y) minutes on M_{1}.

∴ x + y ≤ 300.

x units of A and y units of B will take (2x+y) minutes on M_{2}.

∴ 2x + y ≤ 60.

Let Z be the profit function. Then, Z = 5x + 3y.

We have to maximize Z = 5x + 3y, subject to the constraints

x ≥ 0, y ≥ 0, x + y ≤ 300 and 2x + y ≤ 60.

Now, x + y = 300 ⇒ \(\frac{x}{300}+\frac{y}{300}=1.\)

This line meets the axes in (300,0) and (0,300).

Joining these points, we get the line x + y = 300.

Since (0,0) satisfies the inequation x + y ≤ 300, the region below the line x + y = 300 containing O(0,0) represents x + y ≤ 300.

Again, 2x + y = 360 ⇒ \(\frac{x}{180}+\frac{y}{360}=1 .\)

This line meets the axes in (180,0) and (0,360).

Joining these points, we get the line 2x + y = 360.

Since (0,0) satisfies 2x + y ≤ 360, the region below the line 2x + y = 360 containing (0,0)represents 2x + y ≤ 360.

Also x = 0 is the y-axis and y = 0 is the x-axis.

On drawing these lines and shading the feasible region, we obtain a figure, given below.

On solving x = 0 and x + y = 300, we get the point R(0,300).

On solving x + y = 300 and 2x + y = 360, we get the point Q(60,40).

∴ the vertices of the feasible region are

O(0,0), P(180,0), Q(60,240) and R(0,300).

Values of Z = 5x + 3y at O, P, Q, R are 0, 900, 1020, 900 respectively.

∴ Z is maximum when x = 60 and y = 240.

**Example 6 An aeroplane of an airline can carry a maximum of 200 passengers. A profit of Rs 400 is made on each first-class ticket and a profit of Rs 300 is made on each economy-class ticket. The airline reserves at least 20 seats for first class. However, at least 4 times as many passengers prefer to travel by economy class than by first class. Determine how many of each type of tickets must be sold in order to maximize the profit for the airline. What is the maximum profit?**

**Solution**

**Given:**

An aeroplane of an airline can carry a maximum of 200 passengers. A profit of Rs 400 is made on each first-class ticket and a profit of Rs 300 is made on each economy-class ticket. The airline reserves at least 20 seats for first class. However, at least 4 times as many passengers prefer to travel by economy class than by first class.

Let x tickets of first class and y tickets of economy class be sold to maximize the profit. Then,

x ≥ 20, y ≥ 4x, y ≥ 80 and x + y ≤ 200.

The profit function is given by Z = 400x + 300y.

Draw the graphs of the lines x = 20, y = 4x, y = 80 and x + y = 200 as shown below.

Graph of the inequation x ≥ 20

Since (0,0) does not satisfy x ≥ 20, the line x = 20 together with the region to its right-hand side, not containing (0,0), represents the region x ≥ 0.

Graph of the inequation y ≥ 4x

Clearly, since (20,0) does not satisfy the inequation y ≥ 4x, the line y = 4x together with the region to its left, not containing (20,0), represents y ≥ 4x.

Graph of the inequation y ≥ 80

Clearly, the line y = 80 and the region above this line represents y ≥ 80.

Graph of the inequation x + y ≤ 200

Clearly, (0,0) satisfies x + y ≤ 200. So, the line x + y = 200 together with the region containing O(0,0) represents x + y ≤ 200.

Thus, the shaded region in the given figure is the feasible region, whose vertices are A, B and C. A is the point of intersection of x = 20 and y = 80.

So, its coordinates are A(20,80).

On solving y = 4x and x + y = 200, we get B(40,160).

On solving x = 20 and x + y = 200, we get C(20,180).

The values of Z = 400x + 300y at A(20,80), B(40,160) and C(20,180) are respectively Rs 32000, Rs 64000 and Rs 62000.

∴ Z is maximum at x = 40, y = 160.

**Example 7 A chemical industry produces two compounds, A and B. The following tbale gives the units of ingredients C and D (per kg) of compounds A and B as well as minimum requirements of C and D, and costs per kg of A and B.**

**Find the quantities of A and B which would minimize the cost.**

**Solution**

Let x kg of A and y kg of B be produced. Then,

x ≥ 0, y ≥ 0, x + 2y ≥ 80 and 3x + y ≥ 75.

Then cost function is given by Z = 4x + 6y.

Thus, we have to minimize Z = 4x + 6y, subject to the constraints: x ≥ 0, y ≥ 0, x + 2y ≥ 80 and 3x + y ≥ 75.

Draw the graphs of the lines x = 0, y = 0, x + 2y = 80 and 3x + y = 75.

Since (0,0) does not satisfy the inequation x + 2y ≥ 80, the line x + 2y = 80 together with the region not containing (0,0) represents x + 2y ≥ 80.

Since (0,0) does not satisfy the inequation 3x + y ≥ 75, the line 3x + y = 75 together with the region not containing (0,0) represents 3x + y ≥ 75.

Thus, the shaded region is the feasible region.

The vertices of this region are P, Q and R.

On solving x = 0 and 3x + y = 75, we get the point P(0,75).

On solving x + 2y = 80 and 3x + y = 75, we get the point Q(14,33).

On solving y = 0 and x + 2y = 80, we get the point R(80,0).

The values of Z = 4x + 6y at the points P(0,75), Q(14,33) and R(80,0) are 450, 254 and 320 respectively.

Thus, Z is minimum at Q(14,33).

Hence, for a minimum cost, 14 kg of A and 33 kg of B must be taken.

**Example 8 A company makes two types of belts, A and B; profits on these belts being Rs 4 and Rs 3 each respectively. Each belt of type A requires twice as much time as a belt of type B, and if all belts were of type B, the company could make 1000 belts per day. The supply of leather is sufficient for only 800 belts per day (both A and B combined). At the most 400 buckles for belts of type A and 700 for those of type B are available per day. How many belts of each type should the company make per day so as to maximize the profit?**

**Solution**

**Given**

A company makes two types of belts, A and B; profits on these belts being Rs 4 and Rs 3 each respectively. Each belt of type A requires twice as much time as a belt of type B, and if all belts were of type B, the company could make 1000 belts per day. The supply of leather is sufficient for only 800 belts per day (both A and B combined). At the most 400 buckles for belts of type A and 700 for those of type B are available per day.

Let x belts of type A and y belts of type B be made.

Then, x ≥ 0, y ≥ 0, x ≤ 400, y ≤ 700 and x + y ≤ 800.

Now, 1000 belts of type B can be made in 1 day.

∴ 500 belts of type A can be made in 1 day.

∴ time taken to make x belts of type A and y belts of type B

= \(\left(\frac{x}{500}+\frac{y}{1000}\right) \text { days. }\)

∴ \(\frac{x}{500}+\frac{y}{1000} ≤ 1 i.e., 2x + y ≤ 1000\).

We have to maximize Z = 4x + 3y, subject to the constraints x ≥ 0, y ≥ 0, x ≤ 400, y ≤ 700, x + y ≤ 800 and 2x + y ≤ 1000.

We draw the graphs of the lines x = 0, y = 0, x = 400, y = 700, x + y = 800, 2x + y = 1000 as shown below.

Since (0,0) satisfies x ≤ 400, the line x = 400 together with the region containing O(0,0) represents x ≤ 400.

Since (0,0) satisfies y ≤ 700, the line y = 700 together with the region containing O(0,0) represents y ≤ 700.

Since (0,0) satisfies x + y ≤ 800, the line x + y = 800 together with the region containing O(0,0) represents x + y ≤ 800.

Since (0,0) satisfies 2x + y ≤ 1000, the line 2x + y = 1000 together with the region containing O(0,0) represents 2x + y ≤ 1000.

The y-axis and the region to its right-hand side represents x ≥ 0.

The x-axis and the region above it represents y ≥ 0.

Thus, the shaded region represents the feasible region, whose vertices are P, Q, R, S, T and U.

Clearly, the coordinates of P and Q are (0,0) and (400,0) respectively.

On solving x = 400 and 2x + y = 1000, we get R(400,200).

On solving x + y = 800 and 2x + y = 1000, we get S(200,600).

On solving y = 700 and x + y = 800, we get T(100,700).

On solving x = 0 and y = 700, we get U(0,700).

The values of Z = 4x + 3y at the points P, Q, R, S, T and E are respectively 0, 1600, 2200, 2600, 2500 and 2100.

The maximum of these values is 2600 occuring at S(200,600).

∴ Z is maximum when x = 200 and y = 600.

Thus, the company should make 200 belts of type A and 600 belts of type B to have a maximum profit.

**Example 9 A company has factories located at each of the two places P and Q. From thes locations, a certain commodity is delivered to each of the three depots situated at A, B and C. The weekly requirements of the depots are respectively 7, 6 and 4 units of the commodity while the weekly production capacities of the factories at P and Q are respectively 9 and 8 units. The cost of transportation per unit is given below.**

**How many units should be transported from each factory to each depot in order that the transportation cost is minimum? Formulate the above LPP mathematically and then solve it.**

**Solution**

This problem can be explained diagramatically as follows:

Let x units and y units of the commodity be transporated from the factory at P to the depots at A and B respectively. Then, (9-x-y) units will be transporated from the factory at P to the depot at C.

∴ x ≥ 0, y ≥ 0, and 9 – x – y ≥ 0 ⇒ x + y ≤ 9.

The weekly requirement of the depot at A is 7 units. So, (7-x) units will be transporated to A from the factory at Q.

Similarly, (6-y) units will be transporated to B from the factory at Q.

And, 8 – (7 – x + 6 – y) = (x+y-5) units will be transporated to C from the factory at Q.

∴ 7 – x ≥ 0, 6 – y ≥ 0 and x + y – 5 ≥ 0 i.e., x ≤ 7, y ≤ 6 and x + y ≥ 5.

The total cost of transporation is

Z = 16x + 10(7 – x) + 10y + 12(6-y) + 15(9-x-y) + 10(x+y-5)

⇒ Z = x – 7y + 227.

Now, we have to find the values of x and y which minimize

Z = x – 7y + 227, subject to the constraints

x ≥ 0, y ≥ 0, x + y ≤ 9, x ≤ 7, y ≤ 8 and x + y ≥ 5.

We draw the graphs of the lines

x = 0, y = 0, x + y = 9, x = 7, y = 6 and x + y = 5 as shown below.

Since (0,0) satisfies x + y ≤ 9, the line x + y = 9 together with the region containing O(0,0) represents x + y ≤ 9.

Since (0,0) does not satisfy x + y ≥ 5, the line x + y = 5 together with the region not containing O(0,0) represents x + y ≥ 5.

Since (0,0) satisfies x ≤ 7, the line x = 7 together with the region containing O(0,0) represents x ≤ 7.

Since (0,0) satisfies y ≤ 6, the line y = 6 together with the region containing O(0,0) represents y ≤ 6.

The y-axis and the region to its right-hand side represents x ≥ 0.

The x-axis and the region above it represents y ≥ 0.

Thus, the shaded region represents the feasible region whose vertices are R, S, T, U, V and W.

On solving y = 0 and x + y = 5, we get R(5,0).

On solving y = 0 and x = 7, we get S(7,0).

On solving x = 7 and x + y = 9, we get T(7,2).

On solving x + y = 9 and y = 6, we get U(3,6).

On solving x = 0 and y = 6, we get V(0,6).

On solving x = 0 and x + y = 5, we get W(0,5).

The values of Z = x – 7y + 227 at R, S, T, U, V and W are 32, 234, 220, 188, 185 and 192 respectively.

And, the factory at Q must deliver, 7, 0 and 1 units to A, B, C respectively.

**Example 10 A factory owner purchases two types of machines A and B for his factory. The requirements and the limitations for the machines are as follows:**

**He has maximum area of 9000m ^{2} available and 72 skilled labourers who can operate both the machines. How many machines of each type should he buy to maximize the daily output?**

**Solution**

Let x machines of type A and y machines of type B be bought and let z be the daily output.

Then, z = 60x + 40y …(1)

Maximum area available = 9000m^{2}.

∴ 1000x + 1200y ≤ 9000

⇒ 5x + 6y ≤ 45 …(2)

Maximum labour available = 72 men.

∴ 12x + 8y ≤ 72 ⇒ 3x + 2y ≤ 18 …(3)

Now, we have to maximize z = 60x + 40y, subject to the constraints

5x + 6y ≤ 45,

3x + 2y ≤ 18m

x ≥ 0 and y ≥ 0.

Now, 5x + 6y = 45 ⇒ \(\frac{x}{9}+\frac{y}{(15 / 2)}=1\).

This line meets the axes at A(9,0) and B \(\left(0, \frac{15}{2}\right)\).

Plot these points and join them to obtain the line 5x + 6y = 45.

Clearly, (0,0) satisfies 5x + 6y ≤ 45.

So, the region below AB represents 5x + 6y ≤ 45.

Again, 3x + 2y = 18 ⇒ \(\frac{x}{6}+\frac{y}{9}=1\).

This line meets the axes at C(6,0) and D(0,9).

Plot these points and join them to obtain the line 3x + 2y = 18.

Clearly, (0,0) satisfies 3x + 2y ≤ 18.

So, the region below CD represents 3x + 2y ≤ 18.

x ≥ 0 is the region to the right of y-axis.

And, y ≥ 0 is the region above the x-axis.

On solving 5x + 6y = 45 and 3x + 2y = 18 simultaneously, we get x = \(\frac{9}{4}\) and y = \(\frac{45}{8}\).

So, the lines AB and CD intersect at E \(\left(\frac{9}{4}, \frac{45}{8}\right)\).

Thus, the corner points of the feasible region are

O(0,0), C(6,0), E \(\left(\frac{9}{4}, \frac{45}{8}\right)\) and B \(\left(0, \frac{15}{2}\right)\).

Value of daily output z = 60x + 40y :

(1) At O(0,0) it is z = (60 x 0 + 40 x 0) = 0.

(2) At C(6,0) it is z = (60 x 6 + 40 x 0) = 360.

(3) At E \(\left(\frac{9}{4}, \frac{45}{8}\right)\) it is z = \(\left(60 \times \frac{9}{4}+40 \times \frac{45}{8}\right)=360\).

(4) At B \(\left(0, \frac{15}{2}\right)\) it is z = \(\left(60 \times 0+40 \times \frac{15}{2}\right)=300\).

Thus, either (6 machines of type A and no machine of type B) or (2 machines of type A and 6 machines of type B) be used to have maximum output.

[Note \(\frac{9}{4}\) machines = 2 machines and \(\frac{45}{8}\) machines = 6 machines.]

**Example 11 A retired person has Rs 70000 to invest and two types of bonds are available in the market for investment. First type of bond yields an annual income of 8% on the amount invested and the second type of bond yields 10% per annum. As per norms, he has to invest minimum of Rs 10000 in the first type and not more than R 30000 in the second type. How should he plan his investment, so as to get maximum return, after one year of investment?**

**Solution**

**Given**

A retired person has Rs 70000 to invest and two types of bonds are available in the market for investment. First type of bond yields an annual income of 8% on the amount invested and the second type of bond yields 10% per annum. As per norms, he has to invest minimum of Rs 10000 in the first type and not more than R 30000 in the second type.

Let bonds A be at 8% and bonds B be at 10%.

Suppose he plans to invest Rs x in bonds A and Rs y in bonds B.

Then, clearly x + y = 70000 …(1)

He invests minimum of Rs 10000 in bonds A.

∴ x ≥ 10000 …(2)

Also, he invests not more than Rs 30000 in bonds B.

∴ y ≤ 30000 …(3)

Let z be the annual return on these investments. Then,

\(z=\frac{8 x}{100}+\frac{10 y}{100} \Rightarrow z=0.08 x+0.1 y\) …(4)

Thus, we have to maximize z, subject to the conditions

\(\left.\begin{array}{r}x+y=7000 \\

x \geq 10000 \\

y \leq 30000

\end{array}\right\}\)

Now, x + y = 70000 ⇒ \(\frac{x}{70000}+\frac{y}{70000}=1\).

This line meets the axes at A(70000,0) and B(0, 70000).

Plot these points and joint them to obtain the line x + y = 70000.

Clearly, (0,0) satisfies x + y ≤ 70000.

So, the region below AB represents x + y ≤ 70000.

x ≥ 10000 is the region parallel to the y-axis and to the right of it beyond the line x = 10000.

Thus, the region to the right of line CD represents x ≥ 10000.

y ≤ 30000 is the region parallel to the x-axis and above it, but below the line y = 30000.

Thus, the region below the line EF and above the x-axis represents y ≤ 30000.

Thus, the corner points of the feasible region are

D(10000,0), A(70000,0), E(30000,40000) and F(10000,40000).

Value of annual return z = 0,08x + 0.1y :

(1) At D(10000,0) it is z = (0.08 x 10000 + 0.1 x 0) = 800.

(2) At A(70000,0) it is z = (0.08 x 70000 + 0.1 x 0) = 5600.

(3) At E(30000,40000) it is z = (0.08 x 30000 + 0.1 x 40000) = 6400.

(4) At F(10000,40000) it is z = (0.08 x 10000 + 0.1 x 40000) = 4800.

So, in order to get a maximum annual return, he should invest Rs 30000 in bond A and Rs 40000 in bond B.