USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Graphical method of solving LPP

The various steps in solving the LP problem using the graphical method are as follows:

  1. Formulate the problem with mathematical form by
    1. Specifying the decision variables.
    2. Identifying the objective function and
    3. Writing the constraint equations
  2. Plot the constraint equations on a graph
  3. Identify the area of feasible solution.
  4. Locate the corner points of the feasible region.
  5. Plot the objective function.
  6. Choose the points where objective functions have optimal value.

Example 2.26.A manufacturing company is producing Iwo products A and B. Each requires processing on two machines 1 and 2. Product A requires 3 hours of processing on machine and 2 hours on machine 2. Product B requires 2 hours of processing on machine 1 and 6 hours on machine 2. The unit profits for product A and B are Rs 10 and Rs 20 respectively. The available time in a given quarter on
machine and machine 2 are 1200 hours and 1500 hours respectively. The market survey has predicted that not more than 400 units of product A and not more than 250 units of product B can be sold in the given quarter. The company wants to determine the product mix to maximize the profits. Formulate the problem as linear programming mathematical model and solve it graphically.

Sol. Formulating the problem into a mathematical model.

Step 1. Let X be the number of product A manufactured in a quarter and Y be the number of product B manufactured in a quarter.

Z = profit in a quarter (objective function)

Z is to be maximized under the following constraints.

Z=10X+20Y

3X + 2Y ≤ 1200 (Time constraint of machine 1)

2X + 6Y ≤ 1500 (Time constraint of machine 2)

X ≤ 400 (Selling constraint of product A)

Y ≤250 (Selling constraint of product B)

X ≥ 0 (Non-negativity constraint)

Y ≥ 0 (Non-negativity constraint)

Step 2. Plot the constraint equations in the graph as shown in Fig 2.1.

This can be done by converting the inequalities in to equalities.

3X + 2Y = 1200

When X=0

Y =600

When Y =0

X =400

Hence plot X = 400 and Y = 600 and draw a line joining these two points. Similarly draw time constraint of machine 2. Also the selling constraints of product A and product B can be drawn.

Step 3. Identify the area of feasible solutions as shown by the shaded are in the figure.

Step 4.Plot the objective function. This can be done by assuming some arbitrary profit figures, which can be related within the feasible area (shaded area). For example, if we assume a profit of Rs 2000, it can be obtained by manufacturing 200 units of product A or 100 units of product B. Plot 200 on product A axis and 100 on product B axis. When we join these two points we get the iso-profit line. It is called iso (same) profit line because any point on this line will give different combinations of product A and B, which will give the same profit i.e. Rs2000/-. Many different lines with different profits Rs 4000, Rs 6000 etc can be plotted.

Step 5 Determine the optimal solution

To do this, draw a straight line parallel to the iso-profit line already drawn in such a manner that it is farthest from the origin but also intersects the feasible area at some point. This point where the line drawn parallel to the iso-profit line and which is farthest from the origin intersects the feasible area is called optimal point (P). In the present problem this point P is represented by P (300, 150).

It means 300 units of product A and ISO units of product B should be manufactured to give maximum profit to the company.

Maximum profit Z = 10X + 20Y

X =300

Y= 150

Z=300 × 10+20 × 150 =Rs 6000/-

Example 2.27.A company produces two types of pens say A and B. Pen A is superior quality and pen B is a lower quality. Profit on pen A and B is Rs.5 and 3 respectively. Raw material required for pen A is twice that of pen B. The supply of raw material is sufficient only for 1000 pens of type B per day. Pen A requires a special clip and only 400 such clips are available per day. Pen B requires special clips and only 700 clips are available per day. Formulate a linear programming problem and find graphically the product mix so that the company can make maximum profit.

Sol.

Step 1. Let X be the number of pens of type A.

And Y be the number of pens of type B.

Z = profit generated per day (objective function)

Z is to be maximized under the following constraints

Z= 5X + 3Y

2X + Y s 1000 (Raw material constraint)

X ≤ 400 (Special clips for pen A constraint)

Y ≤ 700 (Special clips for pen B constraint)

X ≥0

Y ≥0

Step 2. Plot the constraint equations on the graph as shown in Fig. This can be done by converting the inequalities into equalities i.e.

2X+Y=1000

X=400

Y=700

From (i), if X = 0, Y = 1000 (0, 1000)

If Y= 0 X = 500 (500, 0)

Fig. 2.2

Step 3.Identify the area of feasible solution as indicated by ODQPE as the shaded area.

Step 4. Plot the objective function

Let us assume a profit of Rs 2000

5X+3Y=2000

Y=0, X =400

X = 0, Y = 667

Plot points (400, 0) and (0, 667)

Step 5. Determine the optimal solution.

To do this draw a line parallel to iso-profit line, farthest from the origin and intersecting the feasible area. It is point P. Coordinates of point Pare (150, 700).

Hence, max profit Z = 5X + 3Y

=5 × 150+3 × 700

=750+2100

=Rs 2850

Example 2.28.A firm makes product X and Y and has a total production capacity of 9 tons per day, X and Y requiring the same production capacity. The firm has a permanent contract to supply at least 2 tons of X and at-least 3 tons of Y per day to another company. Each ton of X requires 20 machine hours production time and each ton of Y requires 50 machine hours production time. The daily maximum possible number of machine hours is 360. All the firm’s output can be sold and the profit made is Rs 80 per tons of X and Rs 120 per tons of Y. It is required to determine the production schedule for maximum profit and to calculate the profit.

Sol. Formulation of LP mathematical model

Step 1.Let X be the production of product X

and Y be the Production of product Y

and Z = Profit (objective function)

Z is to be maximized under the following constraint

Z=80X + 120Y

X + Y ≤ 9 (Capacity constraint)

X ≥ 2 (Demand constraint of product X)

Y ≥ 3 (Demand constraint of product Y)

20X + 50Y ≤ 360 (Constraint of availability of machine hours)

X ≥ 0

Y≥0

Step 2.Plotting the constraint equations on the graph as shown in Fig 2.3.this can be done by converting the inequalities into equalities.

i.e. X + Y = 9    X = 0

X=2 Y=9

Y = 3 Y =0, X =9

20X + 50Y = 360

X =0, y= 7.2 (0, 7.2)

Y=0,  X=18 (18, 0)

Step 3. Identify area of feasible solution. It can be seen from the figure that RQPS is the area of feasible solution as indicated by shaded area.

Step 4. Plot the objective function. It is clear that solution is at R, Q, P and S by inspection from the graph

R=(2, 3)

Q=(6, 3)

P = value of point P can be found out by solving the two equations which intersect at P i.e.

20X + 50Y = 360                            … (i)

X+Y=9                            … (ii)

Solution of these two equations can be found out by multiply equation (ii) by 20

20X + 20Y = 180                            … (iii)

Subtract(ii) from (i) 30Y = 180 therefore Y = 6

If Y = 6 putting this value of Y in equation (i)

X=3

Point P (3, 6)

Similarly, we can find the value of point S by solving the two equations 20X + 50Y = 360 and X = 2 because S is the intersection of these two line

If X = 2

S (2, 6.4)

Let us now calculate the value of all the corner points to find out which point gives the maximum value.

Corner Point

Coordinates

X,Y

Value of objective function

80X+120Y

R

(2,3)

520

Q

(6,3)

840

P

(3,6)

960

S

(2,6.4)

928

Maximum profit is at point P

Hence Z maximum = 960

ALTERNATIVE METHOD FROM STEP 4 ONWARDS

Step 4 Plotting the objective function. The aim here is to find out the combination of products X and Y, which maximizes the objective function of profit Objective function 80X + 120Y can be plotted on the graph by selecting an arbitrary profit which can be achieved by production of some quantity of product X and some of product Y, within the feasible area. For example, let us consider a profit of Rs 600, it can be obtained by production of 5 tons of product X or 7· 5 tons of product Y. The line joining these two points i.e. (0. 5) and (7· 5, 0) is called the isoprofit line. A number of points on this line will give different quantities of product X and product Y to give the same (iso) profit.

Step 5 Determining the optimal solution. To determine the optimal solution, now draw a line parallel to the iso profit line (AB) in such a way that it is the farthest away from the origin and also intersects the feasible area (shaded area) at some point. This is line CD in the figure. In this problem the point is P and its coordinates are P (3, 6) as can be seen from the figure.

Hence Z = 80X + 120Y

Z =960

Same as was found out by the other method.

Example 2.29. Solve the following graphically

Maximize Z = 3X + 2Y

Subject to X + Y ≤ 35

X-T ≥ 0

X ≤ 20

Y ≥ 5

X ≥ 0

Y≥ 0

Sol. Convert the above constraints inequalities in equalities.

X+Y=35                               … (i)

Y=5                               … (ii)

Y=15                               … (iii)

X-Y=0                               … (iv)

X=20                               … (v)

From (i) When X=0, When Y=35 (0, 35)

When X=35, Y=0 X=35 (35, 0)

From (iv) X=0

Y=0

The feasible solution region is shown with shaded area. Let us find out which point gives the maximum value of objective function Z.

Point

Coordinates

Max value 3X + 2Y

P

(5, 5)

25

Q

(20, 5)

70

R

(20, 14)

88

T

(15, 15)

75

S

(18, 15)

84

Hence max Z = 88 at point R.

Example 2.30. Solve graphically the following linear programming problem

Minimize Z = 3X1 + 5X2

Subject to the conditions

-3X1+4X2 ≤ 12

2X1+3X2 ≤ 12

2X1-X2

X1 ≤ 4

X2 ≥ 2

whereas X1, X2 ≥ 0

Sol. To solve the problem graphically, we have to convert the inequalities into equalities.

- 3X1 + 4X2 = 12                                … (i)

2X1 + 3X2 = 12                                 … (ii)

2X1-X2=-2                                 … (iii)

X1 =4

X2=2

whereas X1 , X2 ≥ 0

From (i) X1 = 0 (0, 3)

X2 = 3

X2=0

X1 =-4 (-4, 0)

From (ii) X1 = 0 (0, 4)

X2 =4

X2 =0

X1 = 6 (6, 0)

From (iii) X1 = 0 (0, 2)

X2=2

X2 = 0

X1=-1 (-1,0)

From (iv) X1 = 4 (4, 0)

From (v) X2 = 2 (0, 2)

Now let us plot the above lines on the graph. The values of points A, B, C, D and E can be found out graphically by reading the value on the graph or by solving the equations, For example, coordinates of point A can be found out by solving equations 2X1 – X2 = – 2 and 2X1 + 3X2 = 12 as lines representing these
equations intersect at point A.

 

Point

Coordinates

Z=3X1+5X2

A

(0.75, 3.4)

19.25

B

(0.8, 3.7)

20.90

C

(4, 6)

42.00

D

(4, 2)

22.00

E

(3, 2)

19.00

 

It may be seen Z is minimum (19.00) at point E.

Note that slight difference in the values of points A, B etc found by solving the equations and by reading from the graph can be attributed to graphical error and are negligible, so can be ignored.

Example 2.31. Solve graphically.

Maximize Z = 9X + 10Y

Subject to 11X+ 9Y ≤ 9900

7X+ 12Y ≤ 8400

6X + 6Y ≤ 9600

where X ≥ 0

Y≥ 0

Sol. Convert the inequalities into equalities,

11X+9Y=9900                       … (i)

7X + 12Y = 8400                        … (ii)

6X + 6Y = 9600                        … (iii)

X=0

Y=0

From (i) X=0

Y = 1100 (0, 1100)

Y=0

X=900 (900, 0)

From (ii) X=0

Y=700 (0,700)

Y=0

X = 1200 (1200, 0)

From (iii) X=0

Y = 1600 (0, 1600)

Y=0

X = 1600 (1600,0)

Plot the above lines on the graph PQRST (shaded’ area) is the feasible solution area coordinates and values of points PQRST are as follows:

Point

Coordinates

Value of Z=9X+10Y

P

(626, 335)

8984

Q

(0, 1100)

12000

R

(0, 1600)

14400

S

(1600, 0)

14400

T

(1200, 0)

10800

 

Z maximizes at P as all other points are on the axis and not within the feasible area.
Also, assume profit of Rs 4500 and solve objective function

Z=9X + 10Y

If X=0 If Y=0

Y=450 X=500

Draw this iso-profit line AB on the graph. Now draw a line parallel to AB farthest from origin which intersects the feasible area (shaded area) at any point. The line is CD and the point is P, where coordinates graphically are 627 and 335.

 Example 2.32. Solve the following linear programming problem by graphic method.

Maximize Z = 2X1 – 3X2

Subject to 4X1 + 5X2 ≤ 40

2X1 + 6X2 ≤ 24

3X1-3X2 ≥ 6

X1 ≥ 4

X1, X2 ≥ 0

Sol. Convert the inequalities into equalities

4X1 + 5X2 =40                                  … (i)

2X1 + 6X2 = 24                                   … (ii)

3X1 -3X2 = 6                                   … (iii)

X1=4                                  … (iv)

From (i) X1 = 0

X2 = 8 (0, 8)

X2=0

X1=10 (10, 0)

From (ii) X1 = 0

X2=4 (0, 4)

X2=0

X1 = 12 (12, 0)

From (iii) X1 = 0, X2 = – 2 (0, – 2)

X1 = 2, X2 = 0 (2, 0)

Subject to 2X1 + 3X2 ≤ 12

2X1 + X2 ≤ 8

X1 ≥ 0

X2 ≥ 0

Convert inequalities into equalities

2X1+3X2=12

2X1 + X2 = 8

From (i) X1 = 0

X2 = 4 (0,4)

X1 =6

X2 = 0 (6,0)

From (iii) X1 = 0

X2 = 8 (0, 8)

X1 =4

X2=0   (4, 0)

Coordinates and values of point OPQR (the shaded area corresponding the feasible solution area) are as follows.

Point

Coordinates

Value of Z=6X1+7X2

O

(0, 0)

0

P

(0, 4)

28

Q

(3, 2)

32

R

(4, 0)

24

Maximum Z = 32 at point Q (3, 2)

Coordinates of point Q have been found out by solving the equation 2X1 + 3X2 = 12
and 2X1+X2 =8 which intersect at Q.

2X1 + 3X2= 12                            … (iv)

2X1 + X2 = 8                             … (v)

Subtract (v) from (iv) we get

2X2=4

X2=2

Now substitute X2 = 2 in equation (iv) or (v) X1 = 3

Example 2.34. Solve graphically

Maximize Z = 5X1 + 4X2

 

Subject to 4X1 + X2 ≤ 40

2X1 + 3X2 ≤ 90

whereas X1,X2 ≥ 0

Sol. Convert the inequalities into equalities

4X1 + X2 =40                     … (i)

2X1 + 3X2 =90                      … (ii)

From (i) X1 = 0, X2 = 40    (0, 40)

X2 = 0, X1 = 10 (10, 0)

From (ii) X1 = 0, X2 = 30   (0, 30)

X2 = 0, X1 = 45 (45, 0)

Coordinates and values of points OPQR (the shaded area representing the feasible solution area) are as follows.

Example 2.35 A company produces two types of products say type A and type B. Product B is superior and product A is a lower quality. Profits on the two types of products are Rs 30 and Rs 40 respectively. The data about resources required and availability of resources are given below.

 

Requirement

Capacity available

Product A

Product B

Raw material (kgs)

60

120

12000

Machine hours (per piece)

8

5

630

Assembly

3

4

500

How should the company manufacture the two types of products in order 10 get the maximum overall profits?

Sol. Step 1. Formulate the linear programming problem.

Z= 30A +40B

Subject to constraint of

 

60A + 120B ≤ 12000 (Constraint of raw material)

8A + 50B ≤ 630 (Constraint of machine hours)

3A + 4B ≤ 500 (Constraint of assembly)

A ≥ 0

B ≥ 0

Convert the inequalities into equalities

60A + 120B = 12000                         … (i)

8A + 50B = 630                          … (ii)

3A + 4B = 500                          … (iii)

From (i) A = 0, B = 100     (0, 100)

B = 0, A = 200 (200, 0)

From (ii) A = 0, B = 126    (0, 126)

B = 0, A = 78· 6 (78. 6)

From (iii) A = 0, B = 125 (0, 125)

Exalllple2.36 A retailer deals in two items only, Item A and item B. He has Rs 50,000 to invest and a space to store at the most 60 pieces. An item A costs him Rs 2500 and B costs Rs 500. A net profit to him on item A is Rs 500 and item B is Rs 150. If he can sell all the items he purchases, how should he invest his amount to have maximum profit?

  1. Give all mathematical formulation to the linear programming problem.
  2. Use graphical method to solve the problem.
  3. Indicate the feasible region on the graph.

Sol. (a) Z = 500 A + 150 B is to be maximized (objective function)

Subject to 2500A + 500 B ≤ 50.00 (Constraint of amount to be invested)

A + B ≤ 60 (Constraint of space)

A ≥ 0

B ≥ 0

To solve it graphically, convert inequalities into equalities

2500A + 500B = 50,00                 … (i)

A + B = 60                                … (ii)

From (i) A = 0, 8 = 100 (0,100)

B = 0, A = 20 (0, 20)

From (ii) A = 0, B = 60 (0, 60)

B=0, A=60 (60,0)

Shaded area represents the feasible area of the solution. Point B can be found out by solving the equation (i) and (ii). Multiply (ii) by 50 and subtract from (ii).

A = 10

B = 50

Graphically point B can be read as (10, 50)

Max Z=10×500+50×150

=5000+7500=12,500

Example 2.37 (a) Maximize 6A + 5B

Subject to 3A + 4B ≤120

3A + 1B ≤ 40

A + B = 30

A ≥ 0 B ≥ 0

Using graphical method

(b) Three products are produced all three different operations. The limits all the available time for the three operations are respectively 430, 460 and 420 minutes and the profit per unit for three products are Rs 3, Rs 2 and Rs 5 respectively. Time in minutes per unit all each machine operation is as follows:-

Product

Operation

I

II

III

1

1

2

3

2

3

0

2

3

1

4

0

Sol. (a) maximize Z = 6A + 4B

Convert inequalities into equalities.

3A + 4B = 120                           … (i)

3A + 1B =40                            … (ii)

A + B =30                            … (iii)

From (i) When A=0 B=30 (0, 30)

B=0 A=40 (40, 0)

From (ii) When A=0 B=40 (0, 40)

Example 2.38 A landlord has set up a stud farm where he wants to breed the best horses. His vetenary doctor has advised him to use two special diets, say A and B, for the horses. The nutrition value of these diets and minimum requirement of these nutrients is as follows.

Nutrients

Availability of nutrients in the products

Minimum requirement

A

B

1

40

12

120

2

20

10

60

3

8

36

108

If special diet A costs Rs 60 per unit and diet B costs 80 per unit, using LP graphics method. determine how much of products A and B must be purchased by the landlord so as to provide the horses not less than the minimum required as per the advise of the vet.

Sol. Mathematical formulation of the problem

Let X1 and X2 be the number of units of diet A and diet 8 to be purchased. The other data given in the problem can be summarized in the table below.

Decision Variable (units)

Product

Nutrient available

Cost (Rs)

X1

A

40

20

8

60

X2

B

12

10

36

80

Minimum requirement

120

60

108

Minimize Z = 60X1 + 80X2 with the following constraints

40X1 + 12X2 ≥ 120

20X1 + 10X2 ≥ 60

8X1 + 36X2 ≥ 108

X1, X2 > 0

Plotting the constraint equations in the graph

First, the inequalities have to be converted into equations

40X1 + 12X2 = 120                  … (i)

20X1 + 10X2 = 60                   … (ii)

8X1 + 36X2 = 108                   … (iii)

From (i) X1 = 0, X2 = 10

X2=0, X1=3   (3, 10)

From (ii) X1 = 0, X2 = 6

X2 = 0, X1 = 3 (3, 6)

From (iii) X1 = 0, X2 = 3

X2=0, X1=13.5          (13.5, 3)

These can be plotted in the figure as shown below.

Coordinates of P can be found out by solving the equations

20X1 + 10X2 = 60 and 8X1 + 30X2 = 108

X1 = 1·7

X2 =2·6

Point

Coordinates

Objective function 60X1+80X2

B

(0, 3)

240

P

(1.7, 2.6)

102+208=310

Q

(3, 0)

180

 

Since the minimum cost is at point Q, the landlord should purchase 1·7 units of product X1 and 2.6 units of product X2.

Example 2.39 An advertising agency has been hired by a client launching a new product which can be used by middle income group and higher income group. The entrepreneur wants to reach two types of potential customers, one’s with income bracket more than Rs 2,00,000 per annum and the other which has lesser income than this. The total money he wants to spend on this exercise is Rs 4,00,000 TV and Radio advertising is being considered. Each TV telecast or advertisement for 10 seconds costs Rs 60,000 and not more than 4 must be taken. Each Radio broadcast for 1 minute costs Rs 40,000 and at least 6 must be taken. Viewer and listener’s survey carried out by advertising agency indicates that TV advertisement reaches 12,00,000 potential customers with income bracket higher than Rs 2,00,000 per annum and reaches 50,000 potential customers in the lower bracket of income. Radio programme reaches 50,000 customer in higher income group bracket and 4,00,000 in lower category. Determine the media mix by using LP graphic method.

Sol. Mathematical formulation of the problem

Let X1 and X2 be the number of programmes on TV and Radio respectively. Maximise the objective function Z for maximum total TV and Radio audience.

Z = X1 (12,00,000 + 60,000) + X2 (50,000 + 4,00,000)

or Z = 1260000X1 + 4,50,000X2 with the following constraints (Maximise)

60,000X1 + 40,000X2  4,00,000

or 3X1 + 2X2  20 (Budget constraint)

X1  4

X2  6

Convert inequalities into equations and plot as follows.

X1 = 0, X2 = 10, (0, 10) 

 

Point B can be determined by solving equations which intersect at B

X1=2.7, X2=6.

Point

Coordinates

Objective function

A

(10, 0)

12,60,0000

B

(2.7, 6)

3,40,2000+27,00,000=6,10,2000

C

(4, 6)

50,40,000+27,00,000=77,44,000

Since maximum value occurs at point C, to maximise number of audience, the advertising agency should go for at least 4 programmes on TV and six on radio.

(b) Formulate following LPP. One unit of product P1 contributes Rs 70 and requires 30 units of raw material and 20 hours of labour. One unit of P2 contributes Rs 50 and requires 10 units of raw material and 10 hours of labour. Availability of raw material is 480 units and time available is 400 hours.

Sol. (a) Convert inequalities into equalities

X1 + 2X2 = 720                            … (i)

5X1 + 4X2 = 1800                             … (ii)

3X1 + X2 = 900                             … (iii)

From (i) X1=0, X2=360 (0, 360)

X2=0 X1=720 (720, 0)

From (ii) X1= 0 X2 =360 (0, 450)

X2 = 0 X1 = 450 (360, 0)

From (iii) X1= 0 X2 = 900 (0, 900)

X2 = 0 X1 = 300 (300, 0)

Now these points and lines connecting these points can be joined to determine the feasible solution area as follows. Point P can be found out by solving equations (i) and (ii) and point C can be found out by solving equations (ii) and (iii). Point P (120, 300) and C (257,129)

Example 2.41 Orient paper mills produces two grades of papers X and Y. Because of raw material restrictions not more than 400 tons of grade X and not more than 300 tons of grade Y can be produced in a weak There are 160 production hours in a weak. It requires 0.2 and 0.4 hours 10 produce a ton of product X and Y respectively, into corresponding profit of Rs 20 and Rs 50 per ton. Formulate a linear programming problem to optimize the product mix for maximum profit.

Example 2.42 A firm manufactures three products A, B and C. Time to manufacture product A is twice that for B and thrice that for C and they are 10 be produced in the ratio 2 : 3 : 4. The relevant data is given below. If the whole labour is engaged in manufacturing product a, 2000 units of the product can be produced. There is demand for at least 200, 300 and 400 units of product A, B and C and the profit earned per unit is Rs 100, Rs 70 and Rs 50 respectively. Formulate the problem as a linear programming problem

Example 2.43 A firm uses lathes, milling machines and grinding machines to produce two machine parts A and B. Tile machining time required for each part, the machining time available all different machines and the profit on each machine part are as follows :-

Type of machine

Machining time required for the machine part (minutes)

Maximum time available per month hours

A

B

Lathes

15

9

600

Milling Machine

8

10

400

Grinding Machine

2

3

150

Profit per unit

50

120

 

Find the number of parts A and B to be manufactured per month to maximize the profit.

Convert the inequalities into equalities

15A + 8B = 600                  … (i)

8A + 10B = 400                   … (ii)

2A+3B=160                   … (iii)

From (i) A = 0 B=75 (0, 75)
B =0  A=40 (40, 0)
From (ii) A = 0 B=45 (0, 40)
B =0 A=50 (50, 0)
From (iii) A = 0 B=50 (0, 50)
B =0 A=75 (75, 0)

Plotting these equations as straight line.

Point Q can be determined by solving equations (i) and (ii)

Point Q (32.5, 14)

Shaded area is the feasible solution area.

Coordinates and values of OPQR.

Point

Coordinates

Value of Z=50A+120B

O

(0, 0)

0

P

(0, 40)

4800

Q

(32, 20)

4840

R

(40, 0)

4800

 

Point R gives the maximum value of Z. Note that equation 2A + 3B = 150 is a redundant constraint as it does not effect the feasible solution area.

Example 2.44 A firm manufactures two products P1 and P2 all which the profits earned are Rs 5 and Rs 8 respectively. Each product is prepared on two machines M1 and M2 the machine time required for these products all the two machines and their availability is as shown below.

 

Product P1

Product P2

Availability of machine (minutes) per day

Machine M1

2

1

400

Machine M2

4

1

600

Find the number of units of products P1 and P2 to be manufactured per day to get maximum profits.

Convert the inequalities into equalities.

2P1 +P2=400                             … (i)

4P1+P2=600                             … (ii)

From (i) P1 = 0 P2 = 400 (0, 400)

P2 = 0 P1 =2 (200, 0)

From (ii) P1 = 0 P2 = 600 (0, 600)

P2=0   P1=150 (150, 0)

Plotting the equation on the graph

Shaded area is the feasible solution area. Coordinates of OABC and value of Z.

Point

Coordinates

Value of Z=5P1+8P2

O

(0, 0)

0

A

(0, 400)

3200

B

(100, 200)

2100

C

(150, 0)

750

Max value of Z = 3200 at point A

Example 2.45 A patient wants to decide the constituents of a diet, which will fulfill his daily requirement of proteins, fats and carbohydrates at the minimum cost. The choice is to be made from three different types of foods. The yields per unit of these foods are as follows.

Food Type

Yields per unit

Cost per unit (Rs)

Proteins

Fats

Carbohydrates

1

2

2

4

40

2

4

2

4

50

3

8

10

8

60

Minimum requirement

1200

400

800

 

Formulate linear programming model for the problem.

Example 2.46 A firm manufactures three products A, B and C. The profits are Rs 3, Rs 2 and Rs 4 respectively. The firm has two machines and the required processing time in number/or each machine on each product is given below.

Product

A

B

C

Machine

C

4

3

5

D

2

2

4

Machines C and D have 2000 and 2500 machine-minutes respectively. The firm must manufacture 100A’s. 200B’s and 50C’s but no more than 150A’s. Set up an LP model to maximize the profit.

Example 2.47 A firm can produce three types of clothes, A, B and C. Three kinds of wool are required for it say red wool, green wool and blue wool. One unit length of type A cloth needs 2 yards of red wool and 3 yards of blue wool, one unit length of type B cloth needs 3 yards of red wool, 2 yards of green wool and two yards of the blue wool and one unit length of type C cloth needs 5 yards of green wool and 4 yards of blue wool. The firm has a stock of only 8 yards of red wool 10 yards of green wool and 15 yards of blue wool. It is assumed that the income obtained from one unit length of type A cloth is 3 of type B cloth is Rs 5 and that of type C cloth is Rs 4. Formulate the problem as linear programming problem.

Example 2.48 A plant manufactures two products A and B. The profit contribution of each product has been estimated is Rs 20 for product A and Rs 24 for product B. Each product passes through three departments of the plant. The time required of each product and total time available in each department lire as follows :-

 

Hours Required

Available hours during the month

Department

Product A

Product B

1

2

3

1500

2

3

2

1500

3

1

1

600

 

The company has a call tract to supply at least 250 units of product B per month. Formulate the problem as a linear programming model and solve by graphical method.

To solve this problem graphically, convert the inequalities into equalities.

2A + 3B = 1500                   … (i)

3A + 2B = 1500                    … (ii)

A+B=600                    … (iii)

B =250

From (i) A = 0 B =500 (0, 500)

B=0 A=750 (750, 0)

From (ii) A = 0 B = 750 (0, 750)

Point P and Q can be determined by solving equations (i) and (ii) and (ii) and (iii). In fact, it is the same point with coordinates (300, 300).

B =0   A=500 (500, 0)

From (iii) A = 0 B = 600 (0, 600)

B=0 A=600 (600, 0)

Shaded area is the area of feasible solution.

Point

Coordinates

Value of Z=20A+24B

A

(0, 500)

12,000

B

(300, 300)

13, 200

C

(500, 0)

10,000

Max profit at point P (300, 300) equal to 13200.

Example 2.49 The ABC electric company produces two products refrigerators and cooking ranges. Production takes place in two separate departments, Refrigerators are produced in department I and ranges are produced in department II. The company’s two products are produced and sold on a weekly basis. The weekly production cannot exceed 25 refrigerators in department I and 35 ranges in department II. Because of limited available facilities in the two departments the company regularly employs a total of 60 workers in the two departments. A refrigerator requires two men-weeks of labour, while a range requires I man-week of labour. A refrigerator contributes a profit of Rs 60 and a range contributes a profit of Rs 40. Formulate the problem as a LP problem. How many units of refrigerators and ranges should the company produce to reduce a maximum profit?

To solve the problem, convert the inequalities into equalities

X=25

Y=35

2X + Y=60

X=0 Y=60 (0, 60)

Y = 0 X = 30 (30, 0)

Plot these equations as straight line on the graph.

Points B and C can be determined by solving equations Y = 35 and 2X + Y = 60.
B is (12.5, 35) and C is (25, 10)

Point

Coordinates

Value of Z=60A+40Y

O

(0, 0)

0

A

(0, 35)

1400

B

(12.5, 35)

2150

C

(25, 10)

1900

D

(25, 0)

1500

Profit is maximum at point B (12.5, 35) of Rs 2150.

Example 2.50 The ABC company wishes to plan its advertising strategy. There are two medias under consideration call them Magazine I and Magazine II respectively. Magazine I has a reach of 2500 potential customers. The cost per page of advertising is Rs 400 and Rs 600 in magazine I and II respectively. The firm has a monthly budget of Rs 6000. There is all important requirement that the total reach for income group under 20.000 per annum should not exceed 4000 potential customers. The reach in magazine I and II for this income group is 400 and 200 potential customers. How many pages should be brought in the two magazines to maximize the total reach?

Sol. Let X and Y be the number of pages in Magazine I and Magazine II respectively which ABC company should buy

Maximize Z = 2000X + 2500Y (Objective function as in this case the reach of two magazines has to be maximized)

X > 0

Y > 0

Now convert the inequalities into equalities

400X + 600Y = 6000                                  … (i)

400X + 200Y = 4000                                  … (ii)

From (i) X=0 Y= 10 (0,10)

Y=0 X=15 (15, 0)

From (ii) X = 0 Y = 20 (0, 20)

Y=0    X=10 (10, 0)

Plotting these equations as straight lines on the graph to find the feasible solution area.

OABC is the feasible solution area.

Coordinates of these points and value of Z is as follows.

Point

Coordinates

Value of Z=2000X+2500Y

0

(0, 0)

0

A

(0, 10)

25000

B

(7.5, 5)

27500

C

(10, 0)

25000

Coordinates of point B can also be found out by solving equations (i) and (ii) subtract (ii) from (i)

400Y = 2000

Y = 5

Putting Y= 5 in (ii) X= 7·5

The company should produce 7.5 pages in Magazine 1 and 5 pages in magazine II to maximize its reach i.e. to 27,500 people.

Exceptional Cases. We have so far discussed the linear programming problems where there is a unique optimal solution always available. However, it may not be the case for all the problems, In general, a LPP should have the following.

(a)             A definite and unique optimal solution,

(b)             An unbounded solution.

(c)             No solution.

Let us discuss the case of an unbounded solution.

Convert the inequalities into equalities and plot them on the graph.

2X-4Y= 10

X + 2Y = 6

The feasible solution area is shown shaded in the figure.

Let us plot Z = 10X + 5Y = 0

X=0 X=I X=2

Y=0 Y=-2 Y=-4

Draw PQ as iso-profit line.

If we move the iso-profit line towards the right as Z increases, we still get Z maximum at a point (corner) farthest from the origin. It can be seen that the farthest point from the region will occurs at infinity. This is the case of an unbounded solution.

From (i) X=0 Y=3 (0, 3)

Y=0, X=-6 (-6, 0)

From (ii) X=0 Y=1 (0, 1)

Y=0 X=-3 (-3, 0)

Plotting these equations as straight lines on the graph.

 

The fig above indicates two shaded regions as feasible solution areas since these two shaded regions don’t overlap, there is no point common to the shaded regions. It means no solution exists and the problem cannot be solved either graphically or by any other method.

Sol. Converting the constraints into equalities

x1 +x2= 1

3x1+x2=4

From equation (i)

x1 =0

x2 =1

The two points are (0, 1) and (1, 0)

and x2 = 0

x1 = 1

From equation (ii) x1 = 0, x2 = 4

Sol. Converting the above constraints into equalities

-2x1 +x2= 1                         … (i)

x1 =2                          … (ii)

x1+x2=3                          … (iii)

From (i)

Shaded region is the feasible area.

Point O, A and C are known.

Point B is the intersection of two lines putting x1 = 2, x2 = 1

Point

Coordinates

Z=3x1+2x2

O

(0, 0)

0

A

(0, 3)

6

B

(2, 1)

8

C

(2, 0)

6

Hence Z is maximum at B (2, 1) at 8.

Sol. Converting the above constraints into equations.

5x1 + 4x2 = 200

3x1 + 5x2 = 150

5x1 + 4x2 = 100

8x1 + 4x2 = 80

From equation (i) (0, 50) and (40, 0)

From equation (ii) (0, 30) and (50, 0)

From equation (iii) (0, 25) and (20, 0)

From equation (iv) (0, 20) and (10, 0)

Since the above problem is of mixed constraints feasible region is as shown in the figure i.e., between BCIHF. All other points are known except I which is the. intersection of lines 3x1 + 5x2 = 150 and 5x1 + 4x2 = 200, solving these we get point I= (30.8, 11.5)

Point

Coordinates

Z=3x1+2x2

B

(0, 25)

100

C

(0, 30)

120

I

(30.8, 11.5)

138.4

H

(40, 0)

120

F

(20, 0)

60

Z is maximum at I (30.8, 11.5)=135.4.

Example 2.56. A manufacturer produces two types of products X and Y, Both these products go through machines M1 and M2. Product X requires 2 hours of M1 and one hour of M2‘s time. Product Y requires one hour of M1 and 2 hours of M2‘s time. M1 has 104 hours at M2 has 76 hours available each month. Profit on one unit of product X is Rs 6 and on product Y is Rs 11. Assuming that he can sell all that he produces, how many units of each product should be manufacturer produce?

Converting the above constraints into equalities.

2x+y= 104                                     … (i)

x + 2y= 76                                      … (ii)

From (i) the two points are (0, 104) and (52, 0)

From (ii) the points are (0.38), (76.0)

Plotting on the graph, we get

Feasible solution is shown in the figure as shaded area OABC. All other points are known except point D which is the intersection of the lines 2X + Y = 104 and X + 2Y = 76. Point B is (44, 16)

Point

Coordinates

Z=6x+11y

O

(0, 0)

0

A

(0, 38)

418

B

(44, 16)

440

C

(52, 0)

312

So Z is maximum at B (44, 16) of Rs 440.

Sol. Converting the above constraints into equalities

2x1 + x2 = 3

x1 +x2 = 2

Point B can be found by solving equations 2x1 + x2 = 3 and x1 + x2 = 2.
It is (1, 1).

Now the maximum value of Z at different points can be find out

Point

Coordinates

Z=5x1+3x2

A

(0, 3)

9

B

(1, 1)

8

C

(2, 0)

10

Example 2.58. DSC Ltd. has two products A and B. To produce one unit of A 2 units of material X and units of material Y are required. To produce one unit of B, 3 units of material X and 2 units of material Y are required. Only 16 units of material X and 16 units of material Y are available. Material X costs Rs 2 ·50 per unit and material Y costs Rs 0.25 per unit respectively.

Formulate an LP model and solve the problem graphically to minimise the cost of material.

Sol. Formulation of LP Model.

Calculating the cost per unit of each type of product.

 

Product A

Product B

Material X

(2.5 × 2)=5

2.5×3=7.50

Material Y

(0.25×4)=1

(0.25×2)=0.50

Total

6

8

Let x represent number of units of product A and y represent the number of units of product B.

 

Converting the inequalities into equalities.

2x + 3y= 16

4x+2y= 16

Optimal solution is at 0 i.e. Z = 0, where no production is achieved. Actually optimal solution is at B equal to 42.67. Hence 2 units of product A and 4 units of product B should be produced to minimize the cost of material.

Example 2.59 A firm manufacture two products. The products must be processed through one department. Product A requires 4 hours per unit and product B requires 2 hours per unit. Total production time available for the coming week is 60 hours. A restriction in planning the production schedule, therefore, is that total hours used-in prolll1tliig two products cannot exceed 60 hours or if x1 equals the number of units produced of product A and x2, equals the number of units produced of product B. the restriction is represented by the inequality.

 

All combinations of the two products represented by points A and B would use all 60 hours.

Example 2.60. If we assume, that ill the last example, the products also have to be processed through another department and product A requires 3 hours per unit and product B requires 5 hours per unit. If the second department has 75 hours available each week the inequality describing production possibilities in this department is

x1=0, x2=15

x2 = 0, x1 = 25 Points are (25, 0) and (0, 15)

If our objective is to determine the combination of the two products which can be processed through both the departments, we are looking for the solution for the system of following linear inequalities.

The solution set for the system contains the set of points which are common to the solution sets in these figures. The solution set is the shaded area ABCD.

The student should note that the combination of the two products within area AEB and area BCF are not possible.

Example 2.61. Graphically determine the solution set for the following system.

Sol. The three lines can be drawn by finding two points each

First inequality x1 = 0, x2 = 4 x2 = 0, x1 = 10

Second inequality x1 = 0, x2 = 12 x2 = 0, x1 = 12

Third equality x1 = 0, x2 = 10 x2 = 0, x1 = 5

There are no points (x1, x2) which satisfy all the relationship in the system.

Example 2.62. Determine the optimal solution to the LPP given below graphically.

Minimize Z = 3x1 + 6x2

Sol. For equation (i) x1 = 0, x2 = 20, x2 = 0, x1 = 5

For equation (ii) x1 = 0, x2 = 20, x2 = 0, x1 = 20

For equation (iii) x1 =0, x2= 10, x2 =0, x1 = 10

To find out the optimal solution, let us assume an arbitrary value for Z say 60.

Z = 3x1 + 6x2 = 60

x1=0, x2=10 and x2=0, x1=20.

This is graphed on the right hand side figure.

To determine the direction of the movement of the objective function, we can choose a point on either side of the line 3x1 + 6x2 = 60 and determine the corresponding value of Z. If we select the origin, the value of objective function at (0, 0) is

Z=O

Since the value of Z at origin is less than 60, our conclusion is that movement of the objective function towards origin results in lower value of Z. Since we want to minimize Z, we will want to move the objective function, parallel to itself, as close to the origin as possible while still having it touch a point in the area of feasible solution. The last point touched before the objective function moves out of the area of feasible solution is D (10, 0). Given that minimum value of Z occurs at (10, 0) the minimum value is

Z = 3 × 10 + 6 × 0 = 30.