Chapter 12

Linear Programming

Linear programming: It is the method used in decision making our business for
obtaining the maximum or minimum values of a linear expression subject is the
satisfying certain given inequations. This linear expression is known as an objective
function and the linear inequations areknown as linear constraints.

Linear constraints: In business or industry we want to make the best use of our
limited resources, be these in the form of money labour, expenses etc.
The limitations on the resources 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 an objective
function.

Optimal value of an objective function: The maximum or minimum value of the

objective function is known as its optimalvalue.

Feasible solution: A set of values of the variables satisfying all the constraints is
known as a feasible solution.

Optimal solution: A feasible solution which leads to an optimalvalue of the objective

function is known as an optimal solution.

Optimization techniques: The process of obtaining the optimal values are called
optimization techniques.

Linear Programming Problem (LPP): A general line programming consists of

maximizing or minimizing an objective function subject to certain given constraints.
 EXERCISE 12.1
1. Maximise Z = 3x + 4y

Subject to the constraints: x + y ≤ 4, x, y ≥ 0

Solution:

 Draw the graph of the line x + y = 4

x 0 4

y 4 0

Putting (0, 0) in the inequality x + y ≤ 4, we have 0 ≤ 4 (which is true)

So, the half plane is towards the origin. Since x, y ≥ 0
The feasible region lies in the first quadrant.
 The feasible region is OABO
 The corner points of the feasible region are O(0, 0), A(4, 0) and

B(0, 4). The values of Z at these points are as follows

Corner point Z = 3x + 4y

O (0, 0) Z = 3(0)+ 4(0) = 0

A (4, 0) Z = 3(4) + 4(0) = 12

B (0, 4) Z = 3(0)+ 4(4) = 16 Maximum

 Hence, the maximum value of Z is 16 at the point B( 0,8)4)

 0, 4)

2. Minimise Z = −3x + 4y

subject to x + 2y ≤ 8 , 3x + 2y≤ 12 ,x, y ≥ 0 .

Solution:

 Draw the graph of the line x + 2y = 8

x 0 8
y 4 0

Putting (0, 0) in the inequality x + 2y ≤8, we have 0 ≤8 (which is true)

So, the half plane is towards the origin. Since x, y ≥ 0
The feasible region lies in the first quadrant.
 Draw the graph of the line 3x + 2y = 12

x 0 4
y 6 0

Putting (0, 0) in the inequality 3x + 2y ≤12, we have 0 ≤12 (which is true)

So, the half plane is towards the origin.
 The feasible region is OABCO.
 On solving equations x + 2y = 8, and 3x +2y = 12 we get x =2 and y = 3
The point of intersection B is (2, 3)
 The corner points of the feasible region are O(0, 0), A(4, 0),B(2, 3) and
(0, 4). The values of Z at these points are as follows

Corner point Z = −3x + 4y

O (0, 0) Z = -3(0)+ 4(0) = 0

A (4, 0) Z = -3(4) + 4(0) = -12 Minimum

B (2, 3) Z = -3(2)+ 4(3) = 6

C(0, 4) Z = -3(0)+ 4(4) = 16

 Hence, the minimum value of Z is – 12 at the point (4, 0).

3. Maximise Z = 5x + 3y

subject to 3x + 5y ≤ 15, 5x +2y ≤ 10, x, y ≥ 0 .

Solution:

 Draw the graph of the line 3x + 5y = 15 x 0 5

y 3 0

Putting (0, 0) in the inequality 3x + 5y ≤15, we have 0 ≤15 (which is true)

So, the half plane is towards the origin. Since x, y ≥ 0
The feasible region lies in the first quadrant.

 Draw the graph of the line 5x + 2y = 10 x 0 2

y 5 0

Putting (0, 0) in the inequality 5x + 2y ≤ 10, we have 0 ≤ 10 (which is true)

So, the half plane is towards the origin.
 The feasible region is OABCO.
20 45
 On solving equations 3x + 5y = 15, and 5x +2y = 10 we get x = and y =
19 19
20 45
 The point of intersection C is ( , )
19 19
 The corner points of the feasible region are O(0, 0), A(2, 0),B(0, 3) and
20 45
C( , ). The values of Z at these points are as follows
19 19

Corner point Z = 5x + 3y

O (0, 0) Z = 5(0)+ 3(0) = 0

A (2, 0) Z = 5(2) + 3(0) = 10

B (0, 3) Z = 5(0)+ 3(3) = 9

20 45 20 45 235 Maximum
C( , ) Z = 5( )+ 4( ) =
19 19 19 19 19

235 20 45
 Hence, the maximum value of Z is at the point ( , ).
19 19 19
4. Minimise Z = 3x + 5y

such that x + 3y ≥ 3, x + y ≥ 2, x, y ≥ 0 .
x 0 3
 Solution:Draw the graph of the line x + 3y = 3
y 1 0
Putting (0, 0) in the inequality x + 3y ≥3, we have 0 ≥3 (which is false)
So, the half plane is away from the origin. Since x, y ≥ 0
The feasible region lies in the first quadrant.
 Draw the graph of the line x + y = 2 x 0 2
y 2 0

Putting (0, 0) in the inequality x + y ≥2, we have 0 ≥2(which is false)

So, the half plane is away from the origin.
 The feasible region is unbounded
3 1
 On solving equations x + y = 2, and x +3y = 3 we get x = and y =
2 2
3 1
 The point of intersection B is ( , )
2 2
3 1
 The corner points of the feasible region are A(3, 0),B( , ) and
2 2

C(0, 2). The values of Z at these points are as follows

Corner point Z = 3x + 5y

A (3, 0) Z = 3(3) + 5(0) = 9

3 1 3 1
B( , ) Z = 3( )+ 5( ) = 7 Minimum
2 2 2 2

C(0, 2) Z = 3(0)+ 5(2)= 10

 The feasible region is unbounded therefore 7 may or may not be the minimum
value of Z
 We draw the graph of the inequality, 3x + 5y < 7 and check whether the
resulting half plane has points in common with the feasible region or not
 The feasible region has no common point with 3x + 5y < 7.
3 1
 Therefore, the minimum value of Z is 7 at ( , )
2 2
5. Maximise Z = 3x + 2y

subject to x + 2y ≤ 10, 3x + y ≤15, x, y ≥ 0.

Solution:
x 0 10
 Draw the graph of the line x + 2y = 10
y 5 0

Putting (0, 0) in the inequality x + 2y ≤ 10, we have 0 ≤ 10 (which is true)

So, the half plane is towards the origin. Since x, y ≥ 0
The feasible region lies in the first quadrant.

 Draw the graph of the line 3x + y = 15 x 0 5

y 15 0

Putting (0, 0) in the inequality 3x + y ≤ 15, we have 0 ≤ 15 (which is true)

So, the half plane is towards the origin.
 The feasible region is OABCO.
 On solving equations x + 2y = 10, and 3x +y = 15 we get x =4 and y = 3
 The point of intersection B is (4, 3)
 The corner points of the feasible region are O(0, 0), A(5, 0),B(4, 3) and
C(0, 5). The values of Z at these points are as follows

Corner point Z = 3x + 2y

O (0, 0) Z = 3(0)+ 2(0) = 0

A (5, 0) Z = 3(5) + 2(0) = 15

B (4, 3) Z = 3(4)+ 2(3) = 18 Maximum

C(0, 5) Z = 3(0)+ 2(5)= 10

 Hence, the maximum value of Z is 18 at points (4, 3).

6. Minimise Z = x + 2y

subject to 2x + y ≥ 3, x + 2y ≥ 6, x, y ≥ 0

Solution:
x 0 3/2
 Draw the graph of the line 2x + y = 3
y 3 0

Putting (0, 0) in the inequality 2x + y ≥ 3, we have 0 ≥3 (which is false)

So, the half plane is away from the origin. Since x, y ≥ 0
The feasible region lies in the first quadrant.
 Draw the graph of the line x + 2y = 6 x 0 6
y 3 0

Putting (0, 0) in the inequality x + 2y ≥6, we have 0 ≥6(which is false)

So, the half plane is away from the origin.
 On solving equations 2x + y = 3, and x +2y = 6 we get x =0 and y = 3
 The point of intersection B is (0, 3)
 The corner points of the feasible region are A(6, 0) and B(0, 3).
The values of Z at these points are as follows

Corner point Z = x + 2y

A (6, 0) Z = 6 + 2(0) = 6


B(0,3) Z = 0 + 2(3) = 6 



 Here, the values of Z at points A and B are same. If we take any other point,
such as (2, 2) on line x + 2y = 6, then Z = 6. Hence, the minimum value of Z
occurs for more than 2 points.

 Therefore, the value of Z is minimum at every point on the line x + 2y = 6.

7. Minimise and Maximise Z = 5x + 10y subject to x + 2y ≤ 120, x + y ≥60,
x – 2y ≥ 0, x, y ≥ 0.
Solution: x 0 120
 Draw the graph of the line x + 2y = 120 y 60 0

Putting (0, 0) in the inequality x + 2y ≤ 120, we have 0 ≤ 120 (which is true)

So, the half plane is towards the origin. Since x, y ≥ 0
The feasible region lies in the first quadrant.
 Draw the graph of the line x + y = 60 x 0 60
y 60 0
Putting (0, 0) in the inequality x + y ≥ 60, we have 0 ≥60 (which is false)
So, the half plane is away from the origin.
 Draw the graph of the line x – 2y = 0 x 0 10
y 0 5
Putting (5, 0) in the inequality x - 2y ≥ 0, we have 5 ≥ 0 (which is true)
So, the half plane is towards the X axis
 The feasible region is ABCDA.
 On solving equations x – 2 y = 0, and x + y = 60 we get D(40, 20)
and solving equations x – 2y = 0 and x + 2y = 120 we get C(60, 30)
 The corner points of the feasible region are A(60, 0) , B(120, 0), C(60, 30) and
D(40, 20). The values of Z at these points are as follows

Corner point Z = 5x + 10y

A(60, 0) Z = 5(60)+ 10(0) = 600 Minimum

B (120, 0) Z = 5(120) + 10(0) = 600 Maximum

C (60, 30) Z = 5(60)+ 10(30) = 600 Maximum

D(40, 20) Z = 5(40)+ 10(20)= 400

 The minimum value of Z is 300 at (60, 0) and the maximum value of Z is 600 at
all the points on the segment joining the points (120, 0) and (60, 30)
8. Minimise and Maximise Z = x + 2y
subject to x + 2y ≥100, 2x – y ≤0, 2x + y ≤200; x, y ≥ 0.
Solution x 0 100
 Draw the graph of the line x +2 y = 100 y 50 0

Putting (0, 0) in the inequality x + 2y ≥ 100, we have 0 ≥ 100 (which is false)

So, the half plane is away from the origin. Since x, y ≥ 0
The feasible region lies in the first quadrant. x 0 50
 Draw the graph of the line 2x – y = 0
y 0 100
Putting (0, 5) in the inequality 2x – y ≤ 0, we have -5 ≤ 0 (which is true)
So, the half plane is towards Y axis .
x 0 100
 Draw the graph of the line 2x + y = 200
y 200 0
Putting (0, 0) in the inequality 2x + y ≤ 200, we have 0 ≤ 200 (which is true)
So, the half plane is towards the origin.
 The feasible region is ABCDA.
 On solving equations 2x – y = 0, and x + 2y = 100 we get B(20, 40)
and solving equations 2x – y = 0 and 2x + y = 200 we get C(50, 100)
 The corner points of the feasible region are A(0, 50) , B(20, 40), C(50, 100) and
D(50, 100). The values of Z at these points are as follows

Corner point Z = x + 2y

A(0, 50) Z = 0 +2(50) = 100 Minimum

B (20, 40) Z = 20 + 2(40) = 100 Minimum

C (50, 100) Z = 50 + 2(100) = 250

D(0, 200) Z = 0 + 2(200)= 400 Maximum

 The maximum value of Z is 400 at (0, 200) and the minimum value of Z is 100 at
all the points on the segment joining the points B(20, 40) and C(50, 100)
9. Maximise Z = − x + 2y, subject to the constraints x ≥ 3, x + y ≥ 5, x + 2y ≥ 6, y ≥ 0
Solution:
 Draw the graph of the line x = 3
Putting (0, 0) in the inequality x ≥ 3, we have 0 ≥ 3 (which is false)
So, the half plane is away from the Y axis. Since x, y ≥ 0
The feasible region lies in the first quadrant. x 0 5
 Draw the graph of the line x + y = 5
y 5 0

Putting (0, 0) in the inequality x + y ≥ 5, we have 0 ≥ 5 (which is false)

So, the half plane is away from the origin.
x 0 6
 Draw the graph of the line x + 2y = 6
y 3 0

Putting (0, 0) in the inequality x + 2y ≥ 6, we have 0 ≥ 6 (which is false)

So, the half plane is away from the origin.
x 0 -1
 Draw the graph of the line -x + 2y = 1
y 1/2 0
Putting (0, 0) in the inequality -x + 2y ≥ 1, we have 0 ≥ 1 (which is false)
So, the half plane is away from the origin.
 On solving equations x= 3, and -x + 2y = 1 we get C(3, 2)
and solving equations x + 2y = 6 and x + y = 5 we get B(4, 1)
 The feasible region is unbounded.
 The corner points of the feasible region are A(6, 0) , B(4, 1), and C(3, 2).
The values of Z at these points are as follows

Corner point Z = − x + 2y

A (6, 0) Z = -6 + 2(0) = -6

B(4,1) Z = -4 + 2(1)= -2

C(3, 2) Z = -3+ 2(2)= 1 Maximum

 The feasible region is unbounded therefore 1 may or may not be the minimum
value of Z
 We draw the graph of the inequality, -x + 2y >1 and check whether the
resulting half plane has points in common with the feasible region or not
 The feasible region has points in common point with the feasible region .
 Therefore, Z = 1 is not the maximum value. Hence Z has no maximum value.
10. Maximise Z = x + y, subject tox – y ≤ -1, -x + y ≤ 𝟎, x, y ≥ 0.

Solution:

 Draw the graph of the line x - y = -1

x 0 -1
y 1 0
Putting (0, 0) in the inequality x - y ≤-1, we have 0 ≤-1 (which is false)
So, the half plane is away from the origin. Since x, y ≥ 0
The feasible region lies in the first quadrant.

 Draw the graph of the line -x + y = 0

x 0 1
y 0 1
Putting (2, 0) in the inequality -x + y ≤ 0 , we have -2≤0 (which is true)
So, the half plane is towards the X axis

 From the graph it is clearly shown that

there is no common region

 There is no feasible region, and

therefore, z has no maximum value.