Graphical Method for Solving LPP: Steps, Feasible Region and Solved Example
What is the Graphical Method for Solving LPP?
Simple linear programming problems of two variables can be easily solved by the graphical method. The Graphical Method is one of the simplest methods for solving a Linear Programming Problem (LPP) in Operations Research when the problem has two decision variables. It provides a visual representation of the constraints, feasible region, corner points, and the objective function.
The graphical method is a technique for solving a LP Problem in OR involving two decision variables by representing its constraints graphically and determining the optimum value of the objective function from the feasible region.
The method is especially useful for understanding the basic concepts of Linear Programming before studying more advanced solution methods such as the Simplex Method.
In the graphical method, the constraints are represented by straight lines on a two-dimensional coordinate plane. The common region satisfying all the constraints is identified as the feasible region. The objective function is then evaluated at the relevant corner points to determine the optimum solution.
For a maximization or minimization problem, the method generally involves:
- Formulating the LPP.
- Drawing the boundary lines of the constraints.
- Identifying the feasible region.
- Determining the corner points of the feasible region.
- Evaluating the objective function at the corner points.
- Selecting the point that gives the required maximum or minimum value.
The graphical method is therefore also closely related to the corner-point approach to solving a two-variable LPP.
Steps of the Graphical Method for Solving LPP
Step 1: Formulate the LPP
Identify:
- Decision variables
- Objective function
- Constraints
- Non-negativity restrictions
A general two-variable LPP may be written as:
Maximize or Minimize
\[Z=c_1x+c_2y\]
subject to constraints such as:
\[a_1x+b_1y\leq d_1\]
\[a_2x+b_2y\leq d_2\]
and
\[x\geq0,\qquad y\geq0\]
The exact form of the objective function and constraints depends on the particular problem.
Step 2: Convert the Boundary Inequalities into Equations, that is, Consider each inequality-constraint as an equation
For graphical representation, replace each inequality constraint by an equality.
For example,
\[2x+y\leq16\]
is first represented by its boundary equation:
\[2x+y=16\]
Similarly,
\[x+y\leq10\]
becomes
\[ x+y=10\]
Each equation represents a straight line in the two-dimensional coordinate plane.
Step 3: Plot the Constraint Lines, (that is, Sketch the graph of each equation, because each one will represent a straight line geometrically.)
To draw each straight line, find at least two points on the line.
For example, for
\[2x+y=16,\]
put \(x=0\):
\[y=16.\]
Therefore, one point is:
\[(0,16).\]
Now put \(y=0\):
\[2x=16\]
\[x=8.\]
Therefore, the second point is:
\[(8,0).\]
Plot these two points \((0,16)\), \((8,0)\), and join them with a straight line.
Repeat the same procedure for every constraint.
Step 4: Identify the Correct Side of Each Constraint, (that is, each point on the line will satisfy the line's equation), & Shade the Feasible Region
This is an important step. The correct side should be identified using a test point.
Test-Point Method
- Draw the boundary line.
- Select a convenient point that does not lie on the line, usually \((0,0)\) when appropriate.
- Substitute the point into the original inequality.
- If the inequality is satisfied, the side containing the test point is the required region.
- If the inequality is not satisfied, the opposite side is the required region.
For example, consider:
\[2x+y\leq16.\]
Take the test point \((0,0)\):
\[2(0)+0\leq16\]
\[0\leq16.\]
The statement is true. Therefore, the side containing \((0,0)\) is the required region for this constraint.
Short Trick to find correct side of an inequality
If the inequality constraint corresponding to that line is '≤' then the region below the line.
If the inequality constraint corresponding to that line is '≥' then the region above the line.
But note that, the inequality sign alone should not be used as a universal rule such as “≤ always means shade below the line.”
Step 5: Determine the Feasible Region
The feasible region is the common region containing all points that satisfy all the constraints simultaneously, including the non-negativity restrictions.
For a problem with:
\[x\geq0,\qquad y\geq0,\]
only the first quadrant is considered.
After considering all the constraints, the common region satisfying every condition is the feasible region.
Every point in this region is called a feasible solution.
Step 6: Determine the Corner Points
Locate the corner points on the graph or find them by solving the concerned linear equations taken two at a time.
The boundaries of the feasible region meet at certain points called corner points, vertices, or extreme points.
These points can be identified directly from the graph or calculated algebraically by solving the relevant boundary equations simultaneously.
For example, if two boundary lines are:
\[2x+y=16\]
and
\[x+y=10,\]
their intersection can be obtained by solving the two equations.
Step 7: Evaluate the Objective Function
After finding all the corner points, substitute the coordinates of each corner point into the objective function.
That is, calculate the value of the objective function at each corner point.
Find the optimum solution in the feasible region. The corner at which the objective function is optimum (maximum or minimum), will give the optimum solution of the LPP.
- For a maximization problem, select the corner point giving the largest value.
- For a minimization problem, select the corner point giving the smallest value.
For a linear programming problem with an optimum, an optimal solution can be found at an extreme point of the feasible region.
Step 8: State the Optimal Solution Clearly
Finally, state:
- The values of the decision variables.
- The maximum or minimum value of the objective function.
- The corresponding corner point.
This makes the final answer clear and complete for examination purposes.
Read More
Solved Example: Graphical Method for LPP
Example: Solve the following LPP by the graphical method:
2x + y ≤ 16
x + y ≤ 10
and,x, y ≥ 0.
Solution: To solve this linear programming problem, apply the following steps:STEP 1: Identify the Objective Function
STEP 2: Draw the Boundary Lines, that is, Sketch the system of inequalities.
Finding its intercepts:
Put x=0 into 2x + y = 16 and solve for y. So we get, y=16 at x=0, that is, the point (x, y) = (0, 16).
Put y=0 into 2x + y = 16 and solve for x. So we get, x=8 at y=0, that is, the point (x, y) = (8, 0).
Plot (0, 16) and (8, 0). Draw the line passing through these points. This line represents 2x + y = 16 as shown by the red colour in the following figure.
Finding its intercepts:Put x=0 into x + y = 10 and solve for y. So we get, y=10 at x=0, that is, the point (x, y) = (0, 10).Put y=0 into x + y = 10 and solve for x. So we get, x=10 at y=0, that is, the point (x, y) = (10, 0).
STEP 3: Identify the Feasible Region
(Short Trick: The constraint 2x + y ≤ 16 has '≤' then shade the region below the line 2x + y = 16 lying in the first quadrant.)
(Short Trick: The constraint x + y ≤ 10 has '≤' then shade the region below the line x + y = 10 lying in the first quadrant.)
STEP 4: Next, List all the vertices / Find the Corner Points.
STEP 5: Next, find the maximum value of the objective function: Z = 40x + 30y for this region.
◾FINAL ANSWER:
Advantages of the Graphical Method / Utility of Graphical Method for Solving LPP
The graphical method has several important advantages:
-
Simple and easy to understand: It provides a visual approach to solving a two-variable LPP.
-
Visual representation: Another advantage of the graphical approach is its visual nature. It shows the constraints, feasible region, corner points, and optimum solution on a graph.
-
Helps understand basic LPP concepts: Students can clearly see the relationship between constraints, feasible solutions, and the objective function.
-
Useful for two-variable problems: It is particularly suitable for LPPs involving two decision variables. When there are two variables in the problem, we can refer to them as x and y, and we can do most of the analysis on a two-dimensional graph.
-
Good foundation for advanced methods: It helps students understand concepts that are important when studying more advanced LP solution methods.
-
Helps identify special situations: A graph can help illustrate cases such as multiple optimal solutions, infeasibility, and unboundedness.
Graphical methods provide us with a picture to go with the algebra of linear programming, and the picture can anchor our understanding of basic definitions and possibilities. For these reasons, the graphical approach serves as an excellent foundation for working with linear programming concepts.
Limitations of the Graphical Method
The graphical method also has limitations:
-
Primarily suitable for two-variable LPPs: Problems involving many decision variables cannot generally be represented directly on an ordinary two-dimensional graph.
-
Graphical accuracy: When intersection points are difficult to determine from a drawing, algebraic calculation may be necessary.
-
Large problems are impractical: As the number of constraints increases, the graph can become difficult to interpret.
-
Not a general replacement for algebraic methods: Larger linear programming problems require other systematic solution techniques.
Special Cases in Graphical Method
A complete understanding of the graphical method also requires awareness of some special cases.
1. Unique Optimal Solution
A single corner point gives the required maximum or minimum value of the objective function.
2. Multiple Optimal Solutions
Sometimes more than one feasible point can provide the same optimum objective value. In such a case, multiple optimal solutions exist.
For a linear programming problem, this can occur when an objective-function line is parallel to a binding edge of the feasible region.
3. Infeasible Problem
If no point satisfies all the constraints simultaneously, the problem has no feasible solution.
Graphically, this occurs when the constraints have no common feasible region.
4. Unbounded Problem
A problem is unbounded when the feasible region permits the objective function to increase indefinitely in a maximization problem or decrease indefinitely in a minimization problem.
In such a case, a finite optimum does not exist.
Important Terms in Graphical Method
Feasible Solution
A point that satisfies all the constraints of the LPP, including the non-negativity restrictions.
Feasible Region
The common region containing all feasible solutions.
Corner Point
A vertex or extreme point of the feasible region where boundary lines meet.
Optimal Solution
A feasible solution that gives the required maximum or minimum value of the objective function.
Objective Function
The linear function that is to be maximized or minimized.
Constraint
A linear equality or inequality representing a limitation or requirement of the problem.
Common Mistakes Students Make
Mistake 1: Always shading below a “≤” line
This is not a universal rule.
Correct approach: Use a test point to determine the appropriate side of the boundary line.
Mistake 2: Considering only the boundary lines as the feasible region
The boundary lines only represent the equality cases.
The feasible region is the common region satisfying all the inequalities.
The boundary line represents the equality case, while the corresponding inequality determines which half-plane is feasible.
Mistake 3: Forgetting non-negativity restrictions
If the problem contains:
\[x\geq0,\qquad y\geq0,\]
these restrictions must be included when identifying the feasible region.
Mistake 4: Not checking all relevant corner points
Every relevant vertex of the feasible region should be considered when evaluating the objective function.
Mistake 5: Finding the intersection point incorrectly
When two constraint lines intersect, solve their simultaneous equations carefully and verify the resulting point.
Mistake 6: Giving only the value of Z
The final answer should include both:
\[(x,y)\]
and the corresponding optimum value of Z.
For example:
Optimal solution: \(x=6,\ y=4\), and \(Z_{\max}=360\).
Exam-Friendly Answer: 5 Marks
If the examination question is:
“Explain the graphical method for solving an LPP.”
A student can write:
The graphical method is used to solve a Linear Programming Problem involving two decision variables. The constraints are represented graphically on a two-dimensional coordinate plane.
The main steps are:
- Identify the decision variables, objective function, constraints, and non-negativity restrictions.
- Replace each inequality constraint by its corresponding equality and draw the boundary line.
- Use a suitable test point to identify the side satisfying each inequality.
- Determine the common feasible region satisfying all constraints.
- Find the corner points of the feasible region.
- Evaluate the objective function at each corner point.
- Select the corner point giving the maximum or minimum value, according to the objective.
Thus, the graphical method provides a simple visual approach for solving two-variable LPPs.
Exam-Friendly Answer: 10 Marks
For a 10-mark question, students should explain:
- Meaning of graphical method
- Formulation of the LPP
- Drawing boundary lines
- Test-point method
- Feasible region
- Corner points
- Evaluation of objective function
- Optimal solution
- Special cases
- A suitable numerical example
A properly labelled graph should be included wherever the question specifically asks for the graphical method.
Frequently Asked Questions (FAQs on Graphical Method for Solving LPP)
Q. What is the graphical method in LPP?
The graphical method is a technique for solving a two-variable Linear Programming Problem by representing its constraints graphically, identifying the feasible region, and evaluating the objective function at its relevant corner points.
Q. How many variables can be solved using the graphical method?
The standard graphical method is directly applicable to an LPP with two decision variables, because the problem can be represented on a two-dimensional coordinate plane.
Q. What is a feasible region in LPP?
The feasible region is the common region containing all points that satisfy all the constraints, including non-negativity restrictions.
Q. What is a corner point in LPP?
A corner point, or vertex, is a boundary point of the feasible region where relevant boundary lines meet.
Q. How is the optimal solution found graphically?
After identifying the corner points, the objective function is evaluated at each relevant corner point. The point giving the largest value is selected for maximization, while the point giving the smallest value is selected for minimization, provided a finite optimum exists.
Q. What is the test-point method?
The test-point method is used to determine which side of a boundary line satisfies an inequality. A point not lying on the boundary is substituted into the original inequality, and the corresponding side is selected according to whether the inequality is satisfied.
Q. Can the graphical method have multiple optimal solutions?
Yes. More than one optimal solution can occur when multiple feasible points give the same optimum objective value.
Q. What happens if the feasible region does not exist?
If no point satisfies all the constraints simultaneously, the LPP is infeasible and has no feasible solution.
Conclusion
The Graphical Method for solving LPP is a simple and visual technique for solving Linear Programming Problems involving two decision variables. It involves drawing the constraint lines, identifying the feasible region, determining its corner points, and evaluating the objective function at those points.
The method provides an intuitive understanding of important Linear Programming concepts such as constraints, feasible solutions, feasible regions, corner points, and optimal solutions. It also provides a useful foundation for studying more advanced methods of solving Linear Programming Problems.
For examination purposes, students should remember the basic sequence:
Formulate → Draw → Test → Find Feasible Region → Find Corner Points → Evaluate Objective Function → Select Optimum.
References
- Taha, Hamdy A., Operations Research: An Introduction, Pearson.
- Hillier, Frederick S. and Lieberman, Gerald J., Introduction to Operations Research, McGraw-Hill.
- Swarup, Kanti, P. K. Gupta and Man Mohan, Operations Research, Sultan Chand & Sons.
- Sharma, J. K., Operations Research: Theory and Applications, Macmillan India.
Tags: lpp graphical method, lpp graphical method problems, lpp graphical method questions, solve lpp by graphical method, solve the following lpp by graphical method, how to solve lpp by graphical method, solution of lpp by graphical method, limitations of graphical method in lpp, linear programming problem graphical method, linear programming problem graphical method problems, linear programming problem graphical method questions, solve linear programming problem by graphical method, solve the following linear programming problem by graphical method, how to solve linear programming problem by graphical method, solution of linear programming problem by graphical method, limitations of graphical method in linear programming problem
Comments
Post a Comment