Chapter 12: Linear Programming

Given: Z = 11x + 7y and the constraints 2x + y £ 6, x £ 2, x ³ 0, y ³ 0

Let 2x + y = 6

Now, plotting all the constrain equations we see that the shaded area OABC is the feasible region determined by the constraints.

The feasible region is bounded. So, the maximum value will occur at a corner point of the feasible region.

Corner points are (0, 0), (2, 0), (2, 2) and (0, 6).

On evaluating the value of Z, we get

From the above table it’s seen that the maximum value of Z is 42.

Therefore, the maximum value of Z is 42 at (0, 6).

Given: Z = 3x + 4y and the constraints x + y £ 1, x ³ 0,

y ³ 0

Taking x + y = 1, we have

Now, plotting all the constrain equations we see that the shaded area OAB is the feasible region determined by the constraints.

The area is feasible. So, maximum value will occur at the corner points O(0, 0), A(1, 0), B(0, 1).

On evaluating the value of Z, we get

From the above table it’s seen that the maximum value of Z is 4.

Therefore, the maximum value of Z is 4 at (0, 1).

Given: Z = Z = 11x + 7y and the constraints x £ 3, y £ 2, x ³ 0, y ³ 0.

Plotting all the constrain equations we see that the shaded area OABC is the feasible region determined by the constraints.

The feasible region is bounded with four corner points O(0, 0), A(3, 0), B(3, 2) and C(0, 2).

So, the maximum value can occur at any corner.

On evaluating the value of Z, we get

From the above table it’s seen that the maximum value of Z is 47.

Therefore, the maximum value of the function Z is 47 at (3, 2).

Given: Z = 13x – 15y and the constraints x + y £ 7, 2x – 3y + 6 ³ 0, x ³ 0, y ³ 0.

Taking x + y = 7, we have

And, taking 2x – 3y + 6 = 0 we have

Now, plotting all the constrain equations we see that the shaded area OABC is the feasible region determined by the constraints.

The feasible region is bounded with four corners O(0, 0), A(7, 0), B(3, 4) and C(0, 2).

So, the maximum value can occur at any corner.

On evaluating the value of Z, we get

From the above table it’s seen that the minimum value of Z is -30.

Therefore, the minimum value of the function Z is -30 at (0, 2).

As shown in the figure, OAED is the feasible region.

At A, y = 0 in equation 2x + y = 104 we get,

x = 52

This is a corner point A = (52, 0)

At D, x = 0 in equation x + 2y = 76 we get,

y = 38

This is another corner point D = (0, 38)

Now, solving the given equations x + 2y = 76 and 2x + y = 104 we have

2x + 4y = 152

2x + y = 104

(-)___(-)____(-)____

3y = 48 ⇒ y = 16

Using the value of y in the equation, we get

x + 2(16) = 76 ⇒ x = 76 – 32 = 44

So, the corner point E = (44, 16)

On evaluating the maximum value of Z, we get

From the above table it’s seen that the maximum value of Z is 196.

Therefore, the maximum value of the function Z is 196 at (44, 16).

Given: Z = 5x + 7y and feasible region OABC.

The corner points of the feasible region are O(0, 0), A(7, 0), B(3, 4) and C(0, 2).

On evaluating the value of Z, we get

From the above table it’s seen that the maximum value of Z is 43.

Therefore, the maximum value of the function Z is 43 at (3, 4).

In the given figure, it’s seen that the feasible region is ABCA. The corner points are C(0, 3), B(0, 5) and for A, we have to solve equations

x + 3y = 9 and

x + y = 5

(-)_(-)_(-)

2y = 4 ⇒ y = 2

And, putting value of y in the equation we get x = 3

So, the corner point is A(3, 2).

Now, evaluating the value of Z we get

From the above table it’s seen that the minimum value of Z is 21.

Therefore, the minimum value of the function Z is 21 at (0, 3).

In the evaluating table for the value of Z, it’s clearly seen that the maximum value of Z is 47 at (3, 2)

Given: Z = 4x + y

In the given figure, ABC is the feasible region which is open unbounded.

Here, we have

x + y = 3 … (i)

and x + 2y = 4 …. (ii)

On solving equations (i) and (ii), we get

x = 2 and y = 1

So, the corner points are A(4, 0), B(2, 1) and C(0, 3)

Now on evaluating the value of Z, we have

Now, the minimum value of Z is 3 at (0, 3) but as, the feasible region is open bounded so it may or may not be the minimum value of Z.

Hence, in order to face such a situation, we usually draw a graph of 4x + y < 3 and check whether the resulting open half plane has no point in common with feasible region. Otherwise Z will have no minimum value. So, from the graph, we can conclude that there is no common point with the feasible region.

Therefore, the function Z has the minimum value at (0, 3).

From the given figure, it’s seen that the corner points are as follows:

R(7/2, 3/4), Q(3/2, 15/4), P(3/13, 24/13) and S(18/7, 2/7).

Now, on evaluating the value of Z for the feasible region RQPS.

From the above table it’s seen that the minimum value of Z is 22/7 and maximum value of Z is 9.

Therefore, the maximum value of Z is 9 at (3/2, 15/4) and the minimum value of Z is 22/7 at (18/7, 2/7).