After reading this article you will learn about the graphical method for solution of L.P.P with the help of examples.
The graphic solution procedure is method of solving two variable linear programming problems for LPPs that have one two variables, it is possible that the entire set of feasible solution can be displayed graphically by plotting linear constraints on a graph paper to locate the best solution. This method is called as graphical method for solution of LPP.
This method consists following steps:
(1) Formulate the problem in terms of a series of mathematical constraints and on objective function.
ADVERTISEMENTS:
(2) Plot each of the constraints as follows:
Each inequality in the constraints equation be written as equality. Give any arbitrary value to one variable and get the value of other variable by solving the equation. Similarly, give another arbitrary value to the variable and find the corresponding value of the other variable.
Now plot these two sets of values. Connect these points by a straight line. This exercise is to be carried out for each of the constraint equations. Thus there will be as many straight lines as there are equations; each straight line representing one constraints.
(3) Identify the feasible region [r solution space]:
ADVERTISEMENTS:
i.e., the area which satisfies the constraints simultaneously. For greater than (>) constraints the feasible region will be the area which lies above the constraints lines. For less than (≤)’ Constraints this area is generally the region below these tines.
For greater than or equal to or less than or equal to constraints the feasible region includes the points on the constraints line also. And shade this feasible region. The final common shaded area is called the feasible region of the given LPP. All points lying in the feasible region will satisfy all the constraints simultaneously.
(4) Corner Point Method:
By this method we find graphic solution.
ADVERTISEMENTS:
This method involves following step:
(а) Identify each of the corner (or extreme points) of the feasible region either by visual inspection or the method of simultaneous equations.
(b) Complete the value of objective function at each corner point by substituting the co-ordinates of the point.
(c) Identify the optimal solution at that corner point which shows highest profit (in a maximization problem) lowest cost (in a minimization problem).
ADVERTISEMENTS:
Solution by Graphical Method:
Example 1:
Solve the following LP problem graphically.
Maximize z = 3x1 + 5x2
ADVERTISEMENTS:
Subject to constraints x1 +2x2 ≤ 2000
x1 + x2 ≤ 1500
x2 ≤ 600
x1 ≥ 0; x2 ≥ 0
Solution:
Step 1:
(Graph the inequality constraints) Consider two mutually perpendicular lines 0x1, and 0x2 as axes of coordinates. Obviously, any point (x1, x2) in the positive quadrant will certainly satisfy non-negativity restrictions: x1 ≥ 0; x2 ≥ 0
(a) To plot the line x1 + 2x2 = 2000
put x1 = 0 then x2 = 1000
and put x2 = 0 then x1 = 2000
To mark the point L such that OL = 2000 by assuming a suitable scales say 100 units = 2 cm
Similarly mark another Point M such that OM = 1000
Now join the point L and M. This line will represent the equation x1 + 2x2 = 2000 as shown in the following figure.
Clearly any point P lying on or below the line x1 + 2x2 = 2000 will satisfy the inequality x1 + 2x2 ≤ 2000 [if x1 = 500, x2 = 500 then 500 + 2 x 500 < 2000 which is true]
(b) Similarly procedure is now adopted to plot the other two lines.
x1 + x2 < 1500 and x2 = 600 as shown in the fig. (2) and fig (3) respectively.
Any point on or below the lines x1 + x2 = 1500 and x2 = 600 will also satisfy others two inequalities.
x1 + x2 < 1500 and x2 ≤ 600 respectively.
Step 2:
Find the feasible region or solution space and combine the Fig. (1), (2), and (3) together, a common shaded area OABCD is obtained (see Fig. 4) which is a set of points satisfying the inequality constraints.
x1 + 2x2 ≤ 2000; x1 + x2 ≤ 1500; x2 < 600
and non-negativity restriction as x1 ≥ 0, x2 ≥ 0
Hence any point in the shaded area (including its boundary) is a feasible solution to the given LPP.
Step 3:
Find the coordinate of corner point of feasible region O, A, B, C & D
Step 4:
Make the following table:
Hence from above table max. value of z = 5500 because maximum value of z is attained at the corner point B(1000,500)
Example 2:
Solve graphically the following problem:
Maximize z = 8x1, + 10x2 =
So by these conditions, we can say that solution will be in first quadrant as both x & y both are positive.
Step 4:
Find the co-ordinate of corner point of feasible region OABC & make following table:
Hence from above table max. value of z = 82
Zmax = 82
Required solution is x1 = 4, x2 = 5 because maximum value of z is attained at the corner point B (4, 5)
Example 3:
Maximize z = 5x1 + 4x2
Subject to x1 – 2x2 ≤ 1
x1 + 2x2 ≥ 3
x1, x2 ≥ 0
Solution:
The solution space satisfying the constraints
x1 – 2x2 ≤ 1
x1 + 2x2 ≥ 3 and
Non-negative condition x1 ≥ 0; x2 > 0 is shaded in Fig (1). This shaded convex region is unbounded.
The objective function, When z = 0 gives the equation 5x1 + 4x2 = 0, which is shown by the dotted line passing through the origin 0. As z is increased from zero, this dotted line moves to the right, parallel to itself.
Since we are interested in maximizing z, we increase the value of z till the dotted line passes through the farthest corner of the shaded region from the origin. As it is not possible to get the farthest corner for the shaded corner region, the maximum value of z cannot be found as it occurs at infinity only. The problem therefore, has an unbounded solution.
Example 4:
Maximize z = 3x + 2y
subject to – 2x + 3y ≤ 9
3x -2y ≤ -20
x, y ≥ 0
Solution:
The following figure indicates two shaded regions, one satisfying the constraints -2x + 3y ≤, 9 and the other satisfying the constraints 3x-2y ≤ -20. These two shaded regions in the first quadrant do not overlap with the result that there is no point (x, y) common to the two shaded regions. The problem cannot be solved graphically or by any other method of solving L.P problems i.e., the solution of the problem does not exist.
Example 5:
A small-scale industry manufactures electrical regulators, the assembly of which being accomplished by a small group of skilled workers, both men and women. Due to the limitations of space and finance, the member of workers employed cannot exceed and their salary bill not more than Rs. 60,000 per month.
The male members of the skilled workers are paid Rs. 6000 per month, while the female worker doing the same work as the male member gets Rs. 5000. Data collected on the performance of these workers indicate that a male member contributes Rs 10,000 per month to total return of the industry, while the female worker contribute Rs.8500 per month. Determine the member of male and female workers to be employed in order to maximize the monthly total return.
Solution:
Step 1:
Formulate the linear programming – Problem.
The given problem stated is appropriately mathematical form as LP model is as follows:
Maximize (total monthly return) z = 10.000x1 + 8500 x2
Subject to the constraints,
x1 + x2 ≤ 11
6000x1, +5000x2 ≤ 60,000 or 6x1 + 5x2 ≤ 60
x1 ≥ 0; x2 ≥ 0
Where x1 = no. of male workers to be employed
x2 = no. of female workers to be employed
Step 2:
Construct the Graph:
Next we construct the graph by drawing a horizontal and vertical axis which are represented by the x1 -axis and x2-axis in the certain Xx O X2, plane, since any point which satisfies the conditions x1 ≥0 and x2 ≥0 lies in the first quadrant only and thus our search for the desired pair (x1, x2) is restricted to the points of the first quadrant only.
Now inequalities are graphed taking them as equalities, e.g., the first constraint x1 + x2 ≤ 11 will be graphed as x1 + x2 = 11 and the second constraints 6x1+ 5x2 ≤ 60 as 6x1 + 5x2 = 60 and the third constraints x1, x2 ≥ 0, merely restricts the solution to non-negative values.
Further, since the function to be graphed are linear, we need plot only two points per constraints. Thus, to graph each constraints, we arbitrarily assign a value to x1 and determine the corresponding value of x2. The procedure is then repeated for another pair of values for the same constraints, then for the first constraint we have two such points A (0.11) and B (11,0) which upon joining represent x1 + x2= 11.
Similarly, by considering the set of points satisfying x1 ≥ 0, x2 ≥ 0 and second constraints 6x1 + 5x2 ≤ 60, we obtain the shaded area of fig as shown below.
Step 3:
Identify the feasible region:
The feasible region i.e., solution space is the area of the graph which contains all pairs of values that satisfy all the constraints. In other words, feasible region will be bounded by the two axes and two lines x1, x2 = 11, 6x1, + 5x2 = 60 and will be the common area which falls to the left of these constraints equations as both the constraints are of the less than equal to type.
Step 4:
Locate the extreme (or corner) points 2
For this we have to combine Fig (1) and (2)
The shaded area OAPD represents the set of all feasible solutions.
The coordinates of extreme points of the feasible region are:
0 = (0.0), A = (0,11), P=(5,6), D= (10,0)
Step 5:
Evaluate the objective function at extreme points. The mathematical theory behind linear programming states that an optimal solution to any problem, (i.e., the values of x1, x2 that yield the maximum return) will lie at a corner of extreme points of the feasible region. Hence it is only necessary to find the values of the variable at each corner the maximum return or optimal solution will lie at one of them.
The value of objective function at each of these extreme points is as follows:
Step 6:
Determine the optimal value of the objective function. The maximum value of the objective function z = 101000 occurs at the extreme point P (5,6). Hence, optimal solution to the given LP problem is; x1 = 5, x2 – 6
Max z = 101000