Steps to Solve Linear Programming by Graphical Method with Examples
It is not hidden that the simplex method is a well-studied and widely used method for solving Linear Programming problems. But as far as non-Linear Programming is concerned, such a universal method does not exist. With graphical methods, any optimization programming problems consisting of only two variables can easily be solved. These variables can be referred as x₁ and x₂ and with the help of these variables, most of the analysis can be done on a two-dimensional graph. Although we cannot generalize a large number of variables using a graphical approach, the basic concepts of Linear Programming in a two-variable context can be easily demonstrated. We can always turn to two-variable problems if the problems seem to be complicated and we find ourselves in a pool of questions. And we can always search for answers in a two-variable case using graphs, that is solving Linear Programming problems graphically.
The graphical approach wraps itself with another advantage and that is its visual nature. It provides us with a picture to get along with the algebra of Linear Programming. This picture can quench our thirst for understanding the basic definitions and possibilities. These reasons are proof that the graphical approach works smoothly with Linear Programming concepts.
Now, for solving Linear Programming problems graphically, we must two things:
Inequality constraints
And the objective function.
The Graphical Method of Solving Linear Programming problems is based on a well-defined set of logical steps. With the help of these steps, we can master the graphical solution of Linear Programming problems.
Methods used for Solving Linear Programming
Following two methods used for Graphical Method of Solving Linear Programming:
Extreme point solution method
Iso-profit (cost) performance line method to find the perfect solution to the LP problem.
Important Points
A set of variable values xj (j = 1, 2,3..., N) that satisfies the issues of the LP problem is said to form the solution to that LP problem.
Potential Solution Set of variable values xj (j = 1, 2,3.., N) that satisfies all the barriers and non-negative conditions of the LP problem at the same time is said to form a possible solution to that LP problem.
Unlikely solution A set of variable values xj (j = 1, 2,3..., N) that do not satisfy all the barriers and non-negative conditions of the LP problem at one time is said to form an impossible solution for that. LP problem.
With an m-group of simultaneous n (n> m) variables in the LP problem, the solution obtained by placing (n - m) zero-equal variables and solving the remaining m-variables of m is called the basic solution. of that LP problem. Variables (n - m) whose value did not appear in the basic solution are called non-core variables and the remaining variables of m are called the base variables.
A possible basic solution A possible solution to the LP problem and a basic solution is called a possible basic solution. That is, all basic changes take non-negative values.
The Basic Solution is two Types
Degenerate A basic solution that is possible is called degenerate if the value of at least one basic element is zero.
Non-degradable The basic practical solution is called non-degenerate if the value of all the basic variables is zero and positive.
Ways to Solve the LP Problem Law
Point Method
To resolve the issue using the existing point method you need to follow these steps:
Step 1: Create statistical design from a given problem. If not provided.
Step 2: Now plan the graph using the given obstacles and find a region that you can use.
Step 3: Find the possible location links (vertices) that we found in step 2.
Step 4: Now check the objective function in each of the possible location areas. Assume that N and n represent the largest and smallest values in these points.
Step 5: If the possible region is bound then N and n are the maximum and minimum values of the objective function. Or if the area is likely to have no boundaries then:
N is the highest value of the target function if the open half system is obtained with an ax + by> N without a common point in the possible area. If not, purpose work has no solution.
n a small amount of objective work if the open half system is found by the ax + by <n does not have a common point in the probable location. If not, purpose work has no solution.
Iso-Cost Method
The term iso-cost or iso-profit method provides a combination of points that produce the same cost/profit as any other combination in the same line. This is done by arranging the lines corresponding to the slope of the equation.
Follow the following steps for the Iso-cost method solution:
Step 1: Create a statistical design from a given problem. If not provided.
Step 2: Now plan the graph using the given obstacles and find a region that you can use.
Step 3: Now find the possible location links we found in step 2.
Step 4: Find the correct Z (objective function) and draw a line for this objective activity.
Step 5: If the objective function is high type, draw a line corresponding to the objective performance line and this line is farther from the root and has only one common point in the possible area. Or if the target function is a small type then draw a line that corresponds to the target performance line and this line is very close to the source and has one common point in the possible position.
Step 6: Now find the links to the common point we find in step 5. Now, this point is used to find the right solution and the amount of objective work.
Information for the Wooden Tables and Chairs Linear Programming Problem
Table 1 gives us the information for the Linear Programming problem. We can go step-by-step for solving the Linear Programming problems graphically.
Step 1) The aforementioned table can help us to formulate the problem. The bottom row will serve the objective function. The objective function of the company is to maximize unit profit. The woods and the laborers are the constraint set. The nonnegativity conditions are also stated.
Maximize Z = 6x2+8x2 (is the objective function)
Subject to: 30x1+20x2≤ 300 (300 bf available)
5x1+10x2 ≤ 110 (110 hours available)
x1+x2≥ 0 (non - negative conditions)
The two variables (wood and labor) in this problem, can be solved graphically.
Step 2) This is the graph plotting step. With the x-axis as the number of tables and y-axis as the number of chairs, we can find the two constraint lines. This can be found if we find the x and y-intercepts for the two constraint equations. But before that, we have to rewrite the constraint inequalities as equalities.
Wood
30x1+20x2= 300
Setting x₂ = 0 to solve x₁
30x₁ = 300
x₁ =300/30 = 10 tables (Wood used to make tables)
Next:
Setting x₁ = 0 to solve x₂
20x₂ = 300
x₂ =300/20 = 15 chairs (Wood used to make chairs)
Labor
50x1+10x2= 110
Setting x₂ = 0 to solve x₁
5x₁ = 110
x₁ = 110/5= 22 tables(labors used to make tables)
Setting x₁ = 0 to solve x₂
10x₂ = 110
x₂ = 110/10= 11 chairs (labors used to make chairs)
Now, plot the wood constraint line (x1= 10 and x2=15) and labor constraint line (x1=22
and x2=11)
(Image will be uploaded soon)
Step 3) To check the valid side for both constraint lines use the origin (0,0).
30(0) + 20(0) < 300 is the valid side of the wood constraint line. In the same way 5(0) + 10(0) < 110 also is a valid side of the labor constraint line. Now, draw the arrows indicating the valid side of each constraint line.
(Image will be uploaded soon)
Step 4) Identify the feasible region which is the area on the valid side of both constraint lines.
Step 5) Find x1 and x2 using Z = 48 and 72.
In the first case, the values will be x1 = 8 and x2= 12
In the second case, the values will be x1= 6 and x2= 9
Plot the objective function lines when Z = 48 and Z = 72.
The two objective function lines move away from the origin (0,0), Z increases.
(Image will be uploaded soon)
Step 6) Find the most attractive corner.
(Image will be uploaded soon)
Step 7) Calculate the coordinates and find the values of x and y.
Therefore, according to the company’s optimal solution four tables and nine chairs can be manufactured.
Step 8) finally, determine the value of the objective function for the optimal solution by plugging in the number of tables and chairs and solve for Z:
Z =$6(4) +$8(9) =$96
Thus, by producing four tables and nine chairs we can achieve the maximum profit of $96.
FAQs on Graphical Method for Solving Linear Programming Problems
1. What is the graphical method in linear programming?
The graphical method in linear programming is a technique used to solve linear programming problems with two variables by plotting constraints on a graph and identifying the optimal solution visually. It involves:
- Converting inequalities into linear equations.
- Plotting each constraint line on a coordinate plane.
- Identifying the feasible region.
- Evaluating the objective function at the corner points.
2. How do you solve a linear programming problem using the graphical method?
To solve a linear programming problem using the graphical method, plot the constraints and evaluate the objective function at the corner points of the feasible region. Follow these steps:
- Step 1: Formulate the objective function (e.g., Z = 3x + 2y).
- Step 2: Write constraints as linear equations.
- Step 3: Draw each constraint line on the graph.
- Step 4: Shade the feasible region.
- Step 5: Find coordinates of all corner (extreme) points.
- Step 6: Substitute these points into the objective function to find the maximum or minimum value.
3. What is a feasible region in the graphical method?
The feasible region is the common area on a graph that satisfies all the given linear constraints simultaneously. It is obtained by:
- Graphing each inequality constraint.
- Shading the region that satisfies each inequality.
- Identifying the overlapping area of all shaded regions.
4. Why does the optimal solution occur at the corner points in the graphical method?
In linear programming, the optimal solution occurs at a corner point (extreme point) of the feasible region because the objective function is linear. As the objective line moves parallel to itself, the maximum or minimum value is reached at a vertex of the feasible region. This property is known as the Corner Point Theorem.
5. What is the objective function in linear programming?
The objective function is a linear equation that represents the quantity to be maximized or minimized in a linear programming problem. It is generally written as Z = ax + by, where:
- x and y are decision variables,
- a and b are constants (coefficients),
- Z is the value to be optimized.
6. Can you give an example of a graphical method linear programming problem?
A simple example of the graphical method is: Maximize Z = 2x + 3y subject to x + y ≤ 4, x ≥ 0, y ≥ 0. Solution steps:
- Plot the line x + y = 4.
- Shade the region below the line in the first quadrant.
- Corner points are (0,0), (4,0), and (0,4).
- Evaluate Z:
- Z(0,0) = 0
- Z(4,0) = 8
- Z(0,4) = 12
7. What are the limitations of the graphical method in linear programming?
The main limitation of the graphical method is that it can only solve linear programming problems with two variables. Other limitations include:
- Not suitable for three or more variables.
- Less practical for large-scale problems.
- Accuracy depends on precise graph plotting.
8. What is an unbounded solution in the graphical method?
An unbounded solution occurs when the feasible region is open and the objective function can increase or decrease indefinitely. This happens when:
- The feasible region is not closed.
- The objective function does not reach a maximum or minimum at any corner point.
9. What is an infeasible solution in linear programming?
An infeasible solution occurs when no common region satisfies all the given constraints. Graphically, this means:
- The shaded regions do not overlap.
- There is no feasible region.
10. What are the steps to graph a linear inequality in the graphical method?
To graph a linear inequality in the graphical method, first draw its boundary line and then shade the appropriate region. Steps include:
- Replace the inequality with an equation (e.g., x + y = 5).
- Draw the straight line using intercepts.
- Choose a test point like (0,0).
- If the test point satisfies the inequality, shade that side of the line.
