In this article, we will explore the graphical solution method for a linear programming problem and discuss the fundamental theorem of linear programming.
Let’s consider a furniture production problem where we aim to maximize the total revenue generated by producing chairs and tables. The problem involves two types of constraints: the mahogany constraint and the labor constraint. We will solve this problem graphically, using a Cartesian plane to represent the feasible solutions.
To begin, we represent the number of tables on the horizontal axis and the number of chairs on the vertical axis of the Cartesian plane. The non-negativity constraints indicate that both variables must be greater than or equal to zero, allowing us to focus on the upper right-hand quadrant.
Next, we graph the equation that represents the mahogany constraint, which states that 5 times the number of chairs plus 20 times the number of tables should be equal to 400 units of mahogany. By expressing the number of tables in terms of the number of chairs, we can plot this equation on the graph.
Similarly, we graph the equation representing the labor constraint, which states that 10 times the number of chairs plus 15 times the number of tables should be less than or equal to 450 units of labor. We express the number of tables in terms of the number of chairs and plot this equation on the graph.
The intersection of the mahogany and labor constraint lines defines the feasible region where both constraints are satisfied. Any point within this region represents a production plan that meets the constraints. We identify the corner points or vertices of this feasible region as potential solutions.
The objective function in this problem is to maximize revenue, which is given by the equation 45 times the number of chairs plus the number of tables. By expressing the number of tables in terms of the number of chairs, we can plot the objective function line on the graph.
We analyze the direction of increasing revenue by following the slope of the objective function line. By examining the corner points within the feasible region, we can determine the optimal solution. It is important to note that an optimal solution must be a corner point.
The fundamental theorem of linear programming states that if an LP problem has an optimal solution, there will be at least one optimal solution that is a corner point. This theorem emphasizes the significance of corner points in finding optimal solutions.
To further illustrate the concept, we enumerate various points of interest, representing possible production plans. By checking the feasibility of these points, we can evaluate the objective function value associated with each plan. Among the feasible solutions, the one with the highest objective function value represents the optimal solution.
The number of points of interest increases exponentially with the number of variables and constraints. While enumeration is feasible for smaller problems, the complexity grows rapidly, making it unmanageable for larger-scale linear programming problems.
Graphical solution methods provide a visual representation of linear programming problems and help identify feasible and optimal solutions. The fundamental theorem of linear programming emphasizes the importance of corner points in finding optimal solutions. While enumeration of points of interest is effective for smaller problems, it becomes impractical for larger-scale linear programming problems. Advanced algorithms and computer-based optimization techniques are required to tackle complex linear programming problems efficiently.
Download the complete Linear Programming Tutorial Series slide deck.
View the entire series:
GUROBI NEWSLETTER
Latest news and releases
Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.
Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.