Graphical Method in LP
Problem 3.1: Solve the following LPP by graphical method
Minimize Z= 20X1 + 10X2
Subject to: X1 + 2X2 40
3X1 + X2 30
4X1 + 3X2 60
X1,X2 0
Solution
Replace all the inequalities of the constraints by equation
So, X1 + 2X2 = 40
If X1 = 0 => X2 = 20
If X2 = 0 => X1 = 40
Therefore,
X1 + 2X2 = 40 passes through (0,20) (40,0)
3X1 + X2 = 30 passes through (0,30) (10,0)
4X1 + 3X2 = 60 passes through (0,20) (15,0)
Plotting each equation on the graph:
The feasible region is ABCD.
C and D are points of intersection of lines.
From,
X1 + 2X2 = 40, 3X1 + X2 = 30 and 4X1 + 3X2 = 60
X1 + X2 = 30
On solving we get
C = (4,18)
D = (6,12)
Corner points
A(15,0)
B(40,0)
C(4,18)
D(6,12)
Value of Z = 20X1 + 10X2
300
800
260
240 (Minimum Value)
Therefore, the minimum value of Z occurs at D (6, 12). Hence, the optimal solution is
X1=6, X2=12.
Problem 3.2 :
Solve graphically the following LPP
Maximize
Subject to
Z = 3X1 + 2X2
X1 + 2X2 6
2X1 + X2 8
X2 X1 1
X2 2
X1 0
X2 0
Solution
The following graph shows all the six constraints plotted as straight lines. The region in
which each constraint holds when the inequality is actuated by the direction of the arrow
on the associated straight line is the solution space. The solution space is thus determined.
The optimal solution can always be identified with one of the feasible corner points
A,B,C,D,E and F of the solution space .Thus
At A
At B
At C
At D
At E
At F
X1=0
X1=4
X1=3.33
X1=2
X1=1
X1=0
X2=0
X2=0
X2=1.33
X2=2
X2=2
X2=1
Z=0
Z=12
Z=12.66
Z=10
Z=7
Z=2
Thus maximum value of Z occurs at C. The optimal solution is
X1=3.33, X2=1.33, Zmax = 12.66
The optimal solution may be determined by another way. Plot the objective line passing
through the origin. Move this line as far away from the origin as possible and yet within
or touching the boundary of the solution space as in the graph. The optimum solution
occurs at the point C. The coordinates of the point C give the optimum values of X1 and
X2.
The coordinates of C may be noted from the graph. The coordinates may also be
determined analytically. Since C is the intersection of lines (1) and (2), the values of X1
and X2 may be determined by solving simultaneously the equations
X1+2X2 = 6 and
2X1+X2 = 8
The values are 3.33 and 1.33. Zmax = 3*3.33 + 2*1.33 = 12.66.
Problem 3.3
Find the maximum value of Z = 5X1 + 7X2
Subject to
X1 + X2 4
3X1 + 8X2 24
10X1 + 7X2 35
X1, X2 > 0
Solution
Replace all the inequalities of the constraints by forming the equations
X1 + X2 = 4
3X1 + 8X2 = 24
10X1 + 7X2 = 35
passes through (0, 4) (4, 0)
passes through (0, 2) (8, 0)
passes through (0, 5) (3.5, 0)
Plot these lines in the graph and mark the region below the line as the inequality of the
constraint is and is also lying in the first quadrant.
The feasible region is OABCD. B and C are points of intersection of lines.
X1+X2 = 4, 10X1+7X2 = 35 and 3X1+8X2 = 24, X1+X2 = 4
On solving, we get
B = (1.6, 2.4)
C = (2.3, 1.7)
Corner points
O (0, 0)
A (3.5, 0)
B (1.6, 2.4)
C (2.3, 1.7)
D (0,3)
Value of Z=5X1 + 7X2
0
17.5
24.8 (Maximum Value)
23.4
21
Therefore, the maximum value of Z occurs at B (1.6, 2.4) and the optimal solution is
X1=1.6 and X2=2.4
Problem 3.3 a
A company produces 2 types of hats. Every hat A requires twice as much labor as the
second hat B. If the company produces only hat B it can produce a total of 500 hats a day.
The market limits daily sales of the hat A and hat B to 150 and 200 hats. The profits of
hat A and B are Rs.8 and Rs.5 respectively. Solve graphically to get the optimal solution.
Solution
Let X1 and X2 be the number of hats of type A and type B respectively
Max Z=8X1 + 5X2
Subject to 2X1 + 2X2 500
X1 150
X2 250
X1, X2 0
First rewrite the inequality of the constraint into an equation and plot the lines in the
graph
2X1 + X2 = 500
passes through (0,500) (250, 0)
X1 = 150
passes through (150, 0)
X2 = 250
passes through (0, 250)
We mark the region below the lines lying in the first quadrant as the inequality of the
constraints are . The feasible region is OABCD. B and C are the points of intersection of
lines.
2X1 + X2 = 500
X1 =150 and
2X1 + X2 =500
X2 = 250
Corner Points
O (0, 0)
A (150, 0)
B (150, 200)
C (125, 250)
D (0, 250)
Value of Z = 8X1 + 5X2
0
1200
2200
2250 (Maximum)
1250
The maximum value of Z is attained at C (125, 250)
Therefore, the optimal solution is X1 = 125, X2 = 250
i.e. the company should produce 125 hats of type A and 250 hats of type B in order to get
a maximum profit of Rs. 2250/-
Example 3.4
By Graphical Method solve the following LPP.
Max Z = 3X1 + 4X2
Subject to
5X1 + 4X2 200
3X1 + 5X2 150
5X1 + 4X2 100
8X1 + 4X2 80
And X1, X2 0
Corner Points
O (20, 0)
A (40, 0)
B (30.8, 11.5)
C (0, 30)
D (0, 25)
Value of Z = 3X1 + 4X2
60
120
138.4 (Maximum)
120
100
The maximum value of Z is attained at B (30.8, 11.5)
Therefore, the optimal solution is X1 = 30.8, X2 = 11.5
Example 3.5
Use graphical Method to solve the LPP
Maximize Z = 6X1+4X2
Subject to
-2X1+X2 2
X1- X2 2
3X1 + 2X2 9
X1, X2 0
Solution
Feasible region is given by ABC
Corner Points
A (2, 0)
B (3, 0)
C (13/5, 3/5)
Value of Z = 6X1 + 4X2
12
18
98/5 = 19.6 (Maximum)
The maximum value of Z is attained at C (13/5, 3/5)
Therefore, the optimal solution is X1 = 13/5, X2 = 3/5.
Example 3.6 for Unbounded
Use graphical Method to solve the LPP
Minimize Z = 3X1 + 2X2
Subject to
5X1 + X2 10
X1 + X2 6
X1 + 4X2 12
X1, X2 0
Solution
Corner Points
A (0, 10)
B (1, 5)
C (4, 2)
D (12, 0)
Value of Z = 3X1 + 2X2
20
13 (Minimum)
16
36
Since the minimum value is attained at B (1,5) the optimum solution is X1 = 1, X2 = 5.
Note: In the above problem if the objective function is maximization then the solution is
unbounded, as maximum value of Z occurs at infinity.
3.1.1 Some more cases
There are some linear programming problems which may have:
1. a unique optimal solution
2. an infinite number of optimal solutions
3. an unbounded solution
4. no solution.
5. Redundant Case
The following problems will illustrate these cases.
Example 3.7 for Multiple/Infinite Solutions case and Redundant
Constrain case.
Solve the LPP by graphical method
Maximize Z = 100X1 + 40X2
Subject to
5X1 + 2X2 1000
3X1 + 2X2 900
X1 + 2X2 500
X1+ X2 0
Solution
The solution space is given by the feasible region OABC.
Corner Points
O (0, 0)
A (200, 0)
B (125, 187.5)
C (0,250)
Value of Z = 100X1 + 40X2
0
20000
20000
10000
Therefore, the maximum value of Z occurs at two vertices A and B.
Since there are infinite number of points on the line joining A and B gives the same
maximum value of Z.
Thus, there are infinite numbers of optimal solutions for the LPP.
Example 3.8 for unbounded solution
Solve the following LPP
Maximize
Z = 3X1 + 2X2
Subject to
X1 - X2 1
X1 + X2 3
X1, X2 0
Solution
The solution space is unbounded. The value of the objective function at the vertices A and
B are Z (A) = 6, Z (B) = 8. But there exist points in the convex region for which the value
of the objective function is more than 8. In fact, the maximum value of Z occurs at
infinity. Hence, the problem has an unbounded solution.
No feasible Solution
When there is no feasible region formed by the constraints in conjunction with nonnegativity conditions, then no solution to the LPP exists.
Example 3.9 for No feasible Solution
Solve the following LPP
Maximize
Subject to
Solution
Z = X1 + X2
X1 + X2 1
-3X1 + X2 3
X1, X2 0
There being no point common to both the shaded regions, we cannot find a feasible
region for this problem. So the problem cannot be solved. Hence, the problem has no
solution.
