Omni Calculator logo

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:

  1. Decision variables are the variables in a problem or system that we must optimize. Algebraic symbols represent them, say xx,yy, or x1x_1, x2x_2 etc.

  2. 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.

  3. 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:

  1. The decision variables must be continuous within a given range.
  2. 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:

Maximize/minimize P=pxx+pyy\scriptsize \text{Maximize/minimize } P = p_x x + p_y y

subject to a1x+b1y=c1a2x+b2y=c2anx+bny=cn\scriptsize\begin{align*} &\leq\\ \text{subject to }\kern{4em} a_1 x + b_1 y &= c_1\\ & \geq\\\\ &\leq\\ a_2 x + b_2 y &= c_2\\ & \geq\\ \vdots \kern{1.5em}&\\ &\leq\\ a_n x + b_n y &= c_n\\ & \geq\\ \end{align*}

where:

  • PPObjective function;
  • px,pyp_x, p_yCoefficients of the decision variables in the objective function;
  • x,yx,yDecision variables;
  • a1,a2,an,b1,b2,bna_1,a_2, a_n, b_1,b_2,b_nCoefficients of the decision variables in the constraints; and
  • c1,c2,cnc_1, c_2, c_nConstants in the equality or inequality used to express the constraints.

Commonly, the decision variables need to be non-negative, i.e., x0x\geq0, y0y\geq0. These are also constraints on the model, and we can express them by choosing appropriate values for the coefficients ana_n and bnb_n 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.

Graphical representation of feasible region and corner points.
Feasible region (shaded) and its corner points on a graph. Note how every point in the feasible region satisfies every constraint.

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:

Maximize P=30x+40y\scriptsize \text{Maximize }\kern{4.4em} P = 30 x + 40 y
subject to 2x+3y18x+y9x+2y16x0y0\scriptsize\begin{align*} \text{subject to }\kern{5em} 2 x + 3 y &\leq 18\\ x + y &\leq 9\\ x+2y &\leq 16\\ x& \geq 0\\ y& \geq 0 \end{align*}

We can find the corner points algebraically by following these steps:

  1. Convert the inequalities in the constraints into equalities. We shall obtain the following system of linear equations:
2x+3y=18x+y=9x+2y=16x=0y=0\kern{4.8em}\scriptsize\begin{align*} 2 x + 3 y &= 18\\ x + y &=9\\ x+2y &=16\\ x& = 0\\ y& = 0 \end{align*}
  1. 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:
2x+3y=18x+y=9\kern{4.8em}\scriptsize\begin{align*} 2 x + 3 y &= 18\\ x + y &=9\\ \end{align*}
Multiplying x+y=9 by 2\qquad \scriptsize\text{Multiplying } x + y = 9 \text{ by 2}
2x+3y=182x+2y=18\kern{4.8em}\scriptsize\begin{align*} 2 x + 3 y &= 18\\ 2x + 2y &=18\\ \end{align*}
Subtracting the 2nd equation from 1st\qquad \scriptsize\text{Subtracting the 2}^{nd}\text{ equation from 1}^{st}
y=0\kern{6em}\scriptsize y = 0
Substituting y=0 into 2nd equation\qquad \scriptsize\text{Substituting }y=0\text{ into 2}^{nd}\text{ equation}\\
x=9\kern{6em}\scriptsize x = 9

Therefore, the point (9,0)(9,0) is a solution for the equations 2x+3y=182x+3y=18 and x+y=9x+y=9. 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!

Solutions (intersection points) for each set of linear equations.

Equations

Intersecting point

2x+3y=182x+3y=18,x+y=9x+y=9

(9,0)(9,0)

2x+3y=182x+3y=18,x+2y=16x+2y=16

(12,14)(-12,14)

2x+3y=182x+3y=18,x=0x=0

(0,6)(0,6)

2x+3y=182x+3y=18,y=0y=0

(9,0)(9,0)

x+y=9x+y=9, x+2y=16x+2y=16

(2,7)(2,7)

x+y=9x+y=9, x=0x=0

(0,9)(0,9)

x+y=9x+y=9, y=0y=0

(9,0)(9,0)

x+2y=16x+2y=16, x=0x=0

(0,8)(0,8)

x+2y=16x+2y=16, y=0y=0

(16,0)(16,0)

x=0x=0, y=0y=0

(0,0)(0,0)

  1. 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 (9,0)(9,0) satisfies all of the constraints:

2(9)+3(0)=1818(9)+(0)=99(9)+2(0)=916(9)=90(0)=00\scriptsize\begin{align*} 2 (9) + 3 (0) &= 18 \leq 18\\ (9) + (0) &=9 \leq 9\\ (9)+2(0) &=9 \leq16\\ (9)& = 9 \geq 0\\ (0)& = 0 \geq 0 \end{align*}

Hence, (9,0)(9,0) is a corner point. On the other hand, the point (12,14)(-12,14) doesn't satisfy the constraint x0x\geq0, 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:

  1. Convert the inequalities in the constraints into equalities. We shall obtain the following line equations:
2x+3y=18x+y=9x+2y=16x=0y=0\kern{4.8em}\scriptsize\begin{align*} 2 x + 3 y &= 18\\ x + y &=9\\ x+2y &=16\\ x& = 0\\ y& = 0 \end{align*}
  1. 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 2x+3y=182x+3y=18, substitute y=0y=0; we get x=9x=9. Therefore, (9,0)(9,0) is the x-intercept. Similarly, substitute x=0x=0 to obtain the y-intercept (0,6)(0,6). You can use our y intercept calculator to find the intercepts from the equation of a line.
Plot of all constraints and their intersection points
Plot of all constraints and their intersection points.
  1. 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.
Feasible region and corner points.
Feasible region (shaded) and its corner points.
  1. Extract the corner points from the vertices of the boundary of the feasible region. The corner points thus obtained are:

Corner points of the feasible region.

Corner points

(9,0)(9,0)

(0,6)(0,6)

(0,0)(0,0)

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:

  1. 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:

Corner point

P=30x+40yP = 30x+40y

(9,0)(9,0)

270270

Maximum

(0,6)(0,6)

240240

(0,0)(0,0)

00

Since our objective was to maximize P=30x+40yP = 30x+40y, the optimal solution is 270270, and occurs at the corner point (9,0)(9,0).

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:

  1. Enter the coefficients pxp_x and pyp_y of the objective function.
  2. Choose whether this linear programming calculator must minimize or maximize the objective function.
  3. Select the number of constraints in the linear program.
  4. Enter the coefficients aa, bb and cc of each constraint.
  5. 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 00 and 11 as the variable coefficients! For example, to apply the constraint x0x \geq 0, input a1a_1 as 11, b1b_1 as 00, and c1c_1 as 00. 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.

FAQ

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:

  1. Evaluate the objective function at every corner point of the feasible region.
  2. 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.

Krishna Nelaturu
Objective function P = pₓx + pᵧy
pₓ
pᵧ
Maximise or minimise?
Maximize
Number of constraints
3
First constraint: a₁x + b₁y ? c₁
a₁
b₁
Equality/inequality
c₁
Second constraint: a₂x + b₂y ? c₂
a₂
b₂
Equality/inequality
c₂
Third constraint: a₃x + b₃y ? c₃
a₃
b₃
Equality/inequality
c₃
Check out 35 similar linear algebra calculators 🔢
Adjoint matrixCharacteristic polynomialCholesky decomposition… 32 more
People also viewed…

Binary fraction

Discover how to convert fractional numbers from and to the binary representation with our binary fraction converter!

Body fat

Use our free Body Fat Calculator, based on BMI, to determine your body fat percentage and explore your ideal body fat range.

Plant spacing

Optimize your garden layout with our garden spacing calculator. Perfect for precise plant spacing. Plan your dream garden effortlessly now!

Right triangle trigonometry

Discover the relationship between trigonometry and triangles with Omni's right triangle trigonometry calculator!
Copyright by Omni Calculator sp. z o.o.
Privacy, Cookies & Terms of Service