Question

A linear programming problem is given by Z = px + qy, where p, q > 0 subject to the constraints x + y ≤ 60, 5x + y ≤ 100, x ≥ 0 and y ≥ 0.

1. Solve graphically to find the corner points of the feasible region.
2. If Z = px + qy is maximum at (0, 60) and (10, 50), find the relation of p and q. Also mention the number of optimal solution(s) in this case.

Answer 1

i. From the graph, the two boundary lines are:

Line 1 passes through (0, 60) and (60, 0):

`x/60 + y/60 = 1`

x + y = 60

Line 2 passes through (0, 100) and (20, 0):

 `x/20 + y/100 = 1`

5x + y = 100

Since the feasible region lies in the first quadrant:

x ≥ 0, y ≥ 0, x + y ≤ 60, 5x + y ≤ 100

Corner points:

1. Intersection of x = 0 and x + y = 60:

y = 60

⇒ A(0, 60)

2. Intersection of x + y = 60 and 5x + y = 100:

x + y = 60   ...(1)

5x + y = 100  ...(2)

Subtracting (1) from (2):

4x = 40

⇒ x = 10

y = 60 − 10 = 50

⇒ B(10, 50)

3. Intersection of y = 0 and 5x + y = 100:

5x = 100

⇒ x = 20

⇒ C(20, 0)

4. Intersection of the axes:

D(0, 0)

∴ Corner points are A(0, 60), B(10, 50), C(20, 0), D(0, 0)

ii. Z = px + qy

Given that Z is maximum at both corner points (0, 60) and (10, 50). So the value of Z at these two points must be equal.

At (0, 60):

Z = p(0) + q(60) = 60q

At (10, 50):

Z = p(10) + q(50) = 10p + 50q

Since both give maximum,

60q = 10p + 50q

60q − 50q = 10p

10q = 10p

p = q

Since the objective function line is parallel to the boundary segment joining (0, 60) and (10, 50), the maximum value of Z occurs at every point on that segment.

∴ p = q and there are infinitely many optimal solutions.