How to Solve a Linear Programming Problem Using the Graphical Method

Summary

In this lesson, Mirzaei from Cal Poly Pomona explains how to solve linear programming problems using the graphical method, which is ideal for problems with two decision variables. The process involves drawing constraint lines and identifying the feasible region. The objective function is then plotted to determine the optimal solution, typically found at a corner point of the feasible region. The video also covers an example of an infeasible problem, illustrating when no feasible solution exists due to conflicting constraints. This method is effective for simple maximization and minimization problems, providing a visual approach to optimization.

Takeaways

• 😀 The graphical method is primarily used for solving linear programming problems with two decision variables.
• 😀 For problems with more than two variables, the graphical method becomes too complex, and the Simplex method is introduced.
• 😀 The first step in solving a linear programming problem graphically is to draw the constraints.
• 😀 Constraints in an optimization problem usually appear as inequalities, which define the feasible region when plotted.
• 😀 To draw a line from an inequality, assume the inequality is an equation and find two points by setting X1 and X2 to zero.
• 😀 After drawing each constraint line, use the point (0,0) to determine which side of the line satisfies the inequality.
• 😀 The feasible region is the intersection of all areas formed by the constraints.
• 😀 To optimize the objective function, we select a value for the objective function (e.g., Z=60) and draw the corresponding line.
• 😀 For a maximization problem, the next value for the objective function should be greater than the initial value to indicate the direction of improvement.
• 😀 The optimal solution for a maximization problem occurs at the last corner of the feasible region where the objective function line intersects.
• 😀 In cases of infeasible solutions, such as when two constraints define non-intersecting areas, the linear programming problem has no feasible solution.

Q & A

Why is the graphical method typically used only for problems with two decision variables?

The graphical method is most effective for problems with two decision variables because it allows for a clear visual representation of constraints and the feasible region. For problems with more than two decision variables, visualizing the solution becomes more complex, which is why the Simplex method is used instead.

What is the feasible region in a linear programming problem?

The feasible region is the area formed by the intersection of the constraints of a linear programming problem. It represents all the possible solutions that satisfy the given constraints.

How do you determine which side of a constraint line to consider when graphing?

To determine which side of a constraint line to consider, you substitute a point not on the line (usually the origin, (0,0)) into the inequality. If the point satisfies the inequality, the side containing that point is the feasible side.

What is the role of the objective function in linear programming?

The objective function in linear programming defines the goal of the problem—either maximization or minimization. The solution to the problem is the point within the feasible region that either maximizes or minimizes the objective function's value.

Why do we use arbitrary values when plotting the objective function?

Arbitrary values are used for the objective function to plot lines representing equal objective function values. This helps visualize the direction of improvement and identify the point that maximizes or minimizes the objective function.

How do we determine the direction of improvement in an optimization problem?

For a maximization problem, the direction of improvement is to move the objective function line to the right. For a minimization problem, the direction is to move the objective function line to the left. This shows how the objective function’s value changes as you move through the feasible region.

What does it mean when the objective function line hits the last corner of the feasible region?

When the objective function line hits the last corner of the feasible region, it indicates the optimal solution. In a maximization problem, this is the point where the objective function has its highest value within the feasible area.

What is the Simplex method and when is it used?

The Simplex method is an algorithm used to solve linear programming problems with more than two decision variables. It is used when the graphical method becomes impractical due to the complexity of visualizing solutions in higher dimensions.

What happens if there is no feasible solution in a linear programming problem?

If there is no feasible solution, it means that the constraints of the problem contradict each other, and no region exists where all constraints are satisfied. In such cases, the linear programming problem has no feasible answer.

How do we find the optimal solution to a linear programming problem?

The optimal solution is found by determining the point in the feasible region where the objective function line touches the last corner of the region. This point is then used to calculate the maximum or minimum value of the objective function.