Question

Solve the following LPP:

Maximize z = 6x + 10y subject to 3x + 5y ≤ 10, 5x + 3y ≤ 15, x ≥ 0, y ≥ 0.

Answer 1

First we draw the lines AB and CD whose equations are 3x + 5y = 10 and 5x + 3y = 15 respectively.

Line	Equation	Points on the X-axis	Points on the Y-axis	Sign	Region
AB	3x + 5y = 10	A`(10/3, 0)`	B(0, 2)	≤	origin side of line AB
CD	5x + 3y = 15	C(3, 0)	D(0, 5)	≤	origin side of line CD

The feasible region is OCPBD which is shaded region in the graph.

The vertices of the feasible region are O(0, 0), C(3, 0), P and B(0, 2).

P is the point of intersection of lines

3x + 5y = 10  ....(1)

and 5x + 3y = 15  ....(2)

Multiplying equation (1) by 5 and equation (2) by 3, we get

15x + 25y = 50

15x + 9y = 45

On subtracting, we get

16y = 5

∴ y = `5/16`

Substituting y = `5/16` in equation (1), we get

`3x + 25/16` = 10

∴ 3x = `10 - 25/16 = 135/16`

∴ x = `45/16`

∴ P ≡ `(45/16, 5/16)`

The values of objective function z = 6x + 10y at these vertices are

z(O) = 6(0) + 10(0)

= 0 + 0

= 0

z(C) = 6(3) + 10(0)

= 18 + 0

= 18

z(P) = `6(45/16) + 10(5/10)`

= `270/16 + 50/16`

= `320/16`

= 20

z(B) = 6(0) + 10(2)

= 0 + 20

= 20

The maximum value of z is 20 at P`(45/16, 5/16)` and B(0, 2) two consecutive vertices.

∴ z has maximum value 20 at each point of line segment

PB where B is (0, 2) and P is `(45/16, 5/16)`

Hence, there are infinite number of optimum solutions.