See discussions, stats, and author profiles for this publication at: https://www.researchgate.
net/publication/298178045
Linear Programming (Graphical Method)
Chapter · March 2015
CITATIONS READS
0 77,212
Some of the authors of this publication are also working on these related projects:
Improvement in Efficiency and Productivity through Fault Diagnosis in Fans and Blowers using Vibration Signature Analysis View project
Lean Manufacturing, Lean Sigma, Flexible Manufacturing Systems View project
All content following this page was uploaded by Dalgobind Mahto on 14 March 2016.
The user has requested enhancement of the downloaded file.
2015
ESSENTIALS OF
OPERATIONS RESEARCH
Chapter 3: Linear Programming-Ii (Graphical Method)
In linear programming models there is a function
called an objective function, which is to be
maximized or minimized while satisfying several
conditions or constraints. If there are only two
variables, one can use a graphical method of
solution. Let us begin with the set of constraints and
consider them as a system of inequalities. The
solution of this system of inequalities is a set of points,
S. Each point of the set S is called a feasible solution.
The objective function can be evaluated for different
feasible solutions and the maximum or minimum
values obtained. Graph (Linear): A linear graph
consists of a number of nodes or junction points, each
joined to some or all of the others by arcs or lines.
Prof (Dr.) Dalgobind Mahto
3/10/2015
CHAPTER 3
LINEAR PROGRAMMING-II (GRAPHICAL METHOD)
3.1 GRAPHICAL PROBLEM
In the previous section, we have looked at some models called linear programming
models. In each case, the model had a function called an objective function, which was to
be maximized or minimized while satisfying several conditions or constraints.
If there are only two variables, one can use a graphical method of solution. Let us begin
with the set of constraints and consider them as a system of inequalities. The solution of
this system of inequalities is a set of points, S. Each point of the set S is called a feasible
solution. The objective function can be evaluated for different feasible solutions and the
maximum or minimum values obtained.
Graph (Linear): A linear graph consists of a number of nodes or junction points, each
joined to some or all of the others by arcs or lines.
3.2: METHODS FOR SOLVING GRAPHICAL PROBLEM
There are three methods of solving graphical problem. They are
i. General Graphical Method
ii. Corner Point Solution, and
iii. Computer Solution Method
3.2 STEPS FOR SOLVING GNERAL GRAPHICAL PROBLEM
The various steps for solving Graphical problems are as follows
Formulate te problem with mathematical form by
o Specifying the decision variables
o Identifying the objective function
o Writing the constraint equations
Plot the constraint equation on a graph
Identify the area of feasible solution
Locate the corner points of the feasible region
Plot the objective function
Choose the points where objective functions have optimal values
3.4 CORNER POINT SOLUTION
The search procedure adopted in can be simplified by taking advantage of the first
characteristics of feasible solution and the objective function
The following statements are of fundamental importance in linear programming
The solution set for a group of linear inequalities is a convex set. Therefore the
area of feasible solution for a linear programming problem is a convex set
Given a linear objective function linear programming problem , the optimal
solution will always include a corner point in the area of feasible solution.
Thus the corner point method for solving linear programming problem has the following
steps
Step !: Graphically identify the area of feasible solution
Step 2: Determine the co ordinates of each corner point on the area of feasible
solution
Step 3: Substitute the co ordinates of the corner point in the objective function to
determine the corresponding value of Z
Step 4: An optimal solution occurs in a maximization problem at the corner point
yielding the highest value of Z and in a minimization problem at the corner point
yielding the lowest value of Z
3.5 COMPUTER SOLUTION METHOD
In actual application, LP problems are solved by computer methods as today
much efficient computer softwares are readily available. The person who knows
in detail about the LP problem can use these softwares effectively. Yet, following
guidelines will be helpful for the person who wants to use computer softwares
One should fully understand the LP model
One may be able to make assumptions
Have necessary skill to formulate the problem
Ability to arrange solutions using a computer
Capable of interpreting the output from such packages
SOLVED EXAMPLES OF GRAPHICAL PROBLEM
Example 3. 1
Maximize: Z 4x 5y
Subject to:
2x 5y 25
6x 5y 45
49
x 0 , y 0
SOLUTION
To solve the above linear programming model using the graphical method, we shall turn
each constraints inequality to equation and set each variable equal to zero (0) to obtain
two (2) coordinate points for each equation (i.e. using double intercept form). Having
obtained all the coordinate points, we shall determine the range of our variables which
enables us to know the appropriate scale to use for our graph. Thereafter, we shall draw
the graph and join all the coordinate points with required straight line.
2x 5y 25 [Constraint 1]
When x 0 , y 5 and when y 0 , x 12.5 .
6x 5y 45 [Constraint 2 ]
When x 0 , y 9 and
when y 0 , x 7.5 .
Minimum value of x is x 0 .
Maximum value of x is x 12.5 .
Range of x is 0 x 12.5.
Minimum value of y is y 0 .
Maximum value of y is y 9 .
Fig.3.1
The constraints give a set of feasible solutions as graphed above. To solve the linear
programming problem, we must now find the feasible solution that makes the objective
function as large as possible. Some possible solutions are listed below:
Table 3.1
Feasible solutions Objective function
( A point in the solution set of the system) Z= 4x + 5y
(2,3) 4(2)+5(3) = 8 + 15 = 23
(4,2) 4(4)+5(2) = 16 + 10 = 26
(5, 1) 4(5)+5(1) = 20 + 5 = 25
(7, 0) 4(7)+5(0) = 28 + 0 = 28
(0, 5) 4(0)+5(5) = 0 + 25 = 25
In this list, the point that makes the objective function the largest is (7,0) . But, is this the
largest for all feasible solutions? How about (6,1)? or (5,3)? It turns out that (5,3) provide
the maximum value: 4(5) 5(3) 20 15 35 .
Hence, maximum profit at point (5,3) and it is the objective functions which have optimal
values
Example 3. 2
Find the corner points for:
2x 5y 25
6x 5y 45
x 0 , y 0
This is the set of feasible solution for Example 6 .
SOLUTION:
The graph for Example 3.1 is repeated here and shows the corner points.
Fig.3.2
Some corner points can usually be found by inspection. In this case, we can see A (0,0)
and D (0,5) . Some corner points may require some work with boundary lines (uses
equations of boundaries not the inequalities giving the regions).
Point C:
System: 2x 5y 25 … (1)
6x 5y 45 … (2)
(1) (2) 4x 20
x 5 .
If x 5 , then from (1) or (2) :
y 3.
Point B:
System: y 0 … (1)
6x 5y 45 … (2)
Solve by substitution:
6x 5(0) 45 =7.5
The corner points for example 7 are: (0,0) , (0,5) , (7.5,0) and (5,3) .
Convex sets and corner points lead us to a method for solving certain linear programming
problems.
Example 3.3
Solve the following linear programming problem:
Minimize: Z 60x 30y
Subject to:
2x 3y 120
2x y 80
x 0 , y 0 .
SOLUTION:
Fig.3.3
Corner points A (0,80) and C (60,0) are found by inspection.
Point B:
System: 2x 3y 120 … …………………………………..(1)
2x y 80 ………………………………………………… (2)
(1) (2) =2y 40
y 20 .
Substitute for y 20 in (2) :
2x 20 80 .
2x 60 .
x 30 .
Point B: 30,20.
Table 3.2
Extreme Values
Corner point Objective function Z = 60x + 30 y
(0, 80) 60(0) + 30(80) = 2400
(30, 20) 60(30) + 30(20) = 2400
(60, 0) 60(60) + 30(0) = 3600
From the table above, there are two minimum values for the objective function: A
(0,80) and B 30,20. In this situation, the objective function will have the same
minimum value (2,400) at all points along the boundary line segment A and B.
Example 3.4
Maximize: z 2x 3y
Subject to:
x 2y 40
6x 5y 150
x 0 , y 0
SOLUTION
The feasible area is defined by the constraints as shown in the figure below in fig 3.4.
Fig.3.4
Suppose that in addition to the existing constraints, the company is contracted to produce
at least 30 units each week. This additional constraint can be written as: x y 30 . As a
boundary solution, the constraint would be: x y 30 , (x 0, y 30)(x 30, y 0) . The
three structural constraints are shown in the figure below in fig 3.5.
This case presents the manager with demands which cannot simultaneously be satisfied.
Fig.3.5
Example 3.5
Minimize: z 600x 900y
Subject to:
40x 60y 480
30x 15y 180
x 0 , y 0
SOLUTION
If we let z Rs 8100 , then:
8100 600x 900y , (x 0, y 9)(x 13.5, y 0) .
The resultant trial cost is shown in the figure below.
Fig.3.6
This line is parallel to the boundary line BC. The lowest acceptable cost solution will be
coincidental with the line BC making point B, point C and any other points on the line
BC optimal. Multiple optimum solutions present the manager with choice and hence
some flexibility.
Example 3.6 (116): Solve the following problem graphically:
Maximize Z = -x1+4x2,
Subject to -3x1+x2 ≤ 6,
x1+2 x2 ≤ 4 ,
x2 ≤ -3,
No lower bound constraint for x1.
Solution
: The third constraint can be re-written as - x2 ≥ 3.The solution space satisfying the
constraints is shown shaded in fig 1.1.
FIG(1.1)
The co-ordinates of the two vertices of the region of solution are:
A(-3,-3) and B(10,-3).value of the objective function Z = - x1+4 x2 at these vertices are
Z(A) = 3-12=-9, Z(B)= -10-12=-22.
Thus the maximum value of Z occurs at A. Hence the solution to the problem is
x1 = -3, x2 = -3; Zmax = -9.
QUESTION BANK: 3.1
1. Maximize Z = 3x1 + 4x2 by using graphical method
Subject to 6x1 + 12 x2
x1 + 0.5 x2
x1 + 0.4 x2
x1 0 , x2 0
2. Maximize Z = 5x1 + 3x2 by using graphical method
Subject to 3x1 + 5x2
x1 + 2 x2
x1 0 , x2 0
3. Solve graphically the following linear programming problem
Minimize, Z = 2500x1 + 3500x2
Subject to 50x1 + 60x2
x1 + 60 x2
x1 0 , x2 0
4. Maximize 6A + 5B
Subject to
3A + 4B
A 0 , B 0
View publication stats
