Corner Point Calculator
This corner point calculator will help you solve a linear programming problem and find the corner points of the feasible region. It will also find the corner point where the maximum or minimum value of the objective function occurs.
If any of these terms are perplexing, don't worry. We're here to make your life easier😉. In this article, we shall discuss linear programming, calculating and finding feasible regions, how to find corner points algebraically and graphically, and maximizing or minimizing the objective function. So please grab a cup of coffee ☕️ and let's break down corner point math together!
Linear programming problem (LPP)
A constrained optimization model is a mathematical model that finds the best solution (or optimal solution) that satisfies a given set of constraints.
A constrained optimization model has three essential parts:
Decision variables are the variables in a problem or system that we must optimize. Algebraic symbols represent them, say ,, or , etc.
Objective function is the evaluating criterion that we must maximize or minimize. It is a function of the decision variables and maybe a measure of profit, processing time, etc., that we must maximize or minimize.
Constraints are a system of equalities or inequalities representing any limitations due to technology, physics, economics, etc. For example, a constraint can restrict the amount of money spent in each process, the amount of weight allowed in each bag, etc. The optimum solution for the problem must satisfy every constraint.
A linear program is a constrained optimization model which meets the following requirements:
- The decision variables must be continuous within a given range.
- The objective function and the left-hand side of the constraints (inequalities) must be linear functions.
Mathematically, we can write a linear programming problem (LPP) as:
- – Objective function;
- – Coefficients of the decision variables in the objective function;
- – Decision variables;
- – Coefficients of the decision variables in the constraints; and
- – Constants in the equality or inequality used to express the constraints.
Commonly, the decision variables need to be non-negative, i.e., , . These are also constraints on the model, and we can express them by choosing appropriate values for the coefficients and in the constraints.
Feasible region and corner points
The set of points that satisfy the constraints of an LPP is called a feasible set. If we plot all of the constraints on a graph, the region intersecting all these inequalities contains the feasible set. We call this region a feasible region.
The corner points (or extreme points) of a feasible region are the points of intersection between two (or more) constraints. A feasible region may be bounded or unbounded but shall have at least one corner point.
Although every point in the feasible set is technically a solution for the LPP, the optimal solution is one that shall maximize or minimize the objective function. In linear programming, at least one corner point is an optimal solution.
How to find corner points algebraically
Let's try to understand how to find corner points algebraically with the help of an example. Consider the following LPP:
We can find the corner points algebraically by following these steps:
- Convert the inequalities in the constraints into equalities. We shall obtain the following system of linear equations:
- Solve these linear equations, taking a set of any two equations simultaneously to find the intersecting point that satisfies both equations. Let's illustrate this for the first two equations:
Therefore, the point is a solution for the equations and . Similarly, find the solutions for every other set of equations to get their intersection points. Alternatively, you can use our system of equations calculator or substitution method calculator to find the solutions faster and easier!
- Apply the inequality constraints to this set of intersecting points and extract the points which satisfy all the given inequalities. These points are our corner points! Any point that doesn't fulfill every constraint inequality lies outside the feasible region.
For example, the point satisfies all of the constraints:
Hence, is a corner point. On the other hand, the point doesn't satisfy the constraint , and hence lies outside the feasible region.
Test your understanding by applying the constraints for the remaining points to acquire the remaining corner points. You can check your answer against the table of corner points at the end of the next section.
How to find corner points of inequalities graphically
Let's continue to use the same LPP problem we introduced in the previous section. To find the corner points of the feasible region graphically, follow these steps:
- Convert the inequalities in the constraints into equalities. We shall obtain the following line equations:
- Plot these lines on a graph. One easy method is to find the x- and y-intercepts. To obtain the x-intercept for the line , substitute ; we get . Therefore, is the x-intercept. Similarly, substitute to obtain the y-intercept . You can use our y intercept calculator to find the intercepts from the equation of a line.
- Shade the area of the graph that satisfies all of the constraints. It is the feasible region of the LPP. It is the intersection of all of the inequalities of the constraints.
- Extract the corner points from the vertices of the boundary of the feasible region. The corner points thus obtained are:
How do I find the optimal solution using corner points?
The optimal solution for a linear programming problem will occur at least one of the corner points. To find the optimal solution from the corner points, follow these steps:
- Evaluate the objective function at every corner point.
- If the goal is to maximize the objective function, find the corner point that yields the largest value of the objective function.
- If the goal is to minimize the objective function, find the corner point that yields the smallest value of the objective function.
Remember that it is possible to find multiple corner points that provide an optimal solution.
Let's evaluate the objective function in our example to find the optimal solution:
Since our objective was to maximize , the optimal solution is , and occurs at the corner point .
How to use this corner point calculator (online LP solver)
This corner point calculator is a simple tool to solve a given LPP by finding the corner points of inequalities (or constraints) and calculating the objective function. It can handle two decision variables and up to five constraints:
- Enter the coefficients and of the objective function.
- Choose whether this linear programming calculator must minimize or maximize the objective function.
- Select the number of constraints in the linear program.
- Enter the coefficients , and of each constraint.
- This corner point calculator will generate a table of all the corner points, followed by the optimal solution, by calculating the objective function and constraints.
💡 Tip: Struggling to add non-negative (or non-positive) constraints on the decision variables? You can do that by entering and as the variable coefficients! For example, to apply the constraint , input as , as , and as . Make sure you choose the correct inequality sign!
If no results appear, then the calculator found no corner points based on your inputs, and it is an infeasible problem. Try relaxing the constraints so you create a feasible region.
What point in the feasible region maximizes the objective function?
The maximum (or minimum) value of the objective function shall occur at anyone of the corner points of the feasible region. To determine this point, follow these steps:
- Evaluate the objective function at every corner point of the feasible region.
- Determine the maximum among these calculated values. The corner point at which this value occurs is the point that maximizes the objective function.
In some cases, it is possible to find more than one corner point that maximizes the objective function.
Can the feasibility region be in two separate parts?
No. The feasibility region in a linear programming problem is an intersection of different regions, each of which satisfies a particular constraint (inequality). Hence, its feasibility region is always one region of space that satisfies all of the constraints, bounded or unbounded.
Does every system of inequalities have a feasible region?
No. Some problems may not have an intersecting region that satisfies all constraints (inequalities). We call such a problem an infeasible problem. You may have to relax some constraints to allow a feasible region and optimal solution.