A corner point calculator finds the corner points of the feasible region of a linear programming problem in two variables, and, if you give it an objective such as P = 3x + 2y, the corner where the objective is largest or smallest. Type the constraints, add the objective and press the button. It also tells you if the region is empty or unbounded. The method follows the Wikipedia pages on linear programming, the feasible region and the fundamental theorem of linear programming, and the work is done in your browser.
How to use the corner point calculator
- Type each constraint on its own line, such as x + y <= 4.
- Choose whether x and y must be at least 0.
- To find the best corner, enter the objective coefficients and choose maximize or minimize.
- Press Find the corners.
Linear programming in two variables
The Wikipedia page describes linear programming as the optimization of a linear objective function subject to linear equality and inequality constraints. In its standard form, you maximize c·x subject to Ax ≤ b and x ≥ 0. With two variables, each constraint is a straight boundary line, and the feasible region, the set of all points that satisfy every constraint, is a convex polygon. The page notes that the region of a solvable two-variable problem is a convex simple polygon if it is bounded. The corner points are the vertices of that polygon.
Why corners matter
The fundamental theorem of linear programming on Wikipedia says that if a linear function has an optimum over a bounded region, it is reached at a vertex of the region, or on a whole face of optimal points. In two dimensions, that means the best value of an objective like 3x + 2y is found at one of the corners. If the best value occurs at two corners, it also occurs at every point on the segment between them. So you only need to compute the objective at each corner and compare. The calculator lists the corners, shows the objective value at each and picks the best.
How the corners are found
A corner point is where two boundary lines cross and where the point also satisfies all the other constraints. The calculator takes every pair of boundary lines, including x = 0 and y = 0 when you require non-negative values, finds where they cross, and keeps the crossings that satisfy every constraint. It lists them in order around the polygon. For the single constraint x + 2y ≤ 4 with x and y at least 0, the page's bounded example, the corners are (0, 0), (4, 0) and (0, 2).
A worked example
Maximize P = 3x + 2y subject to x + y ≤ 4, x + 3y ≤ 6, x ≥ 0 and y ≥ 0. The boundary lines cross at (0, 0), (4, 0), (3, 1) and (0, 2), and all four are feasible. The values of P are 0, 12, 11 and 4. The largest is 12, at (4, 0). To minimize instead, the best corner is (0, 0) with a value of 0. If the objective is x + y, the corners (4, 0) and (3, 1) both give 4, so the calculator reports a tie, and every point on the edge between them gives 4.
No solution and unbounded problems
The pages describe two ways that a problem can fail. If the constraints contradict each other, the feasible region is the empty set and the problem is infeasible. For example, x ≥ 2 together with x ≤ 1 cannot be satisfied. The other failure is an unbounded problem. The page's example is the region with x ≥ 0 and y ≥ 0 only: maximizing x + y has no optimum, since you can always improve it by increasing x or y, while minimizing x + y gives the corner (0, 0). The calculator detects both cases and reports them, and for an unbounded region it states that the region goes on forever.
Typing the constraints
Each line is one constraint with x and y, a sign and a number. You can write 2x + 3y <= 12, x - y >= -2, y >= 1 or x + y = 5, and you can use the symbols ≤ and ≥. Terms can be on both sides, so 3x - y <= 2x + 4 means x − y ≤ 4. An equality constraint is a line, and the feasible region lies on it. You may enter up to 12 constraints.
A second worked example
Maximize P = 5x + 4y subject to 6x + 4y ≤ 24, x + 2y ≤ 6, x ≥ 0 and y ≥ 0. The two boundary lines cross at (3, 1.5), because 6 × 3 + 4 × 1.5 is 24 and 3 + 2 × 1.5 is 6. The corners are (0, 0), (4, 0), (3, 1.5) and (0, 3), and the values of P are 0, 20, 21 and 12. The maximum is 21 at (3, 1.5). Type the two constraints, enter 5 and 4 as the coefficients, and the calculator gives the same result. The point where the two constraints meet is the best corner here, which is common when both resources are used up.
Common mistakes
- Forgetting the sign limits. If x and y cannot be negative, keep the option on.
- Reading a corner that is not feasible. A crossing must satisfy every constraint.
- Expecting a maximum for any region. An unbounded region may have none.
- Mixing up the inequality direction. Check each sign.
- Ignoring ties. Two best corners mean a whole best edge.
What next
Use this often? Add Corner Point to your Home screen.
Frequently asked questions
What is a corner point calculator?
A tool that finds the vertices of the feasible region of a two-variable linear program and compares the objective value at each.
What is the corner point method?
Find the corner points of the feasible region, evaluate the objective at each, and take the largest or smallest. The optimum of a linear objective is at a corner.
What are the corner points of x + 2y ≤ 4 with x, y ≥ 0?
(0, 0), (4, 0) and (0, 2).
What if the problem has no solution?
If the constraints contradict each other, the feasible region is empty and the problem is infeasible. If it is unbounded, the objective has no maximum.
What happens if two corners give the same best value?
Every point on the segment between them is also optimal.
Sources
Was this tool helpful?
What went wrong?
We only receive the reason you pick, never what you typed into the tool.
Thanks for your feedback.