About

In linear programming, the optimal value of an objective function occurs at a corner point (vertex) of the feasible region. A corner point is defined as the intersection of exactly two boundary lines from a system of linear inequalities. Misidentifying these vertices leads to incorrect optimal solutions and flawed resource allocation decisions. This calculator solves all pairwise intersections of your linear equations using Cramer's rule, computes the determinant D = a₁b₂ − a₂b₁, and reports each vertex coordinate with configurable decimal precision.

The tool detects parallel lines (determinant = 0) and coincident lines automatically. Note: this calculator finds geometric intersection points of lines. It does not evaluate inequality feasibility. You must verify that each corner point satisfies all constraints in your system. For systems with n lines, there are at most n(n − 1)2 possible intersection points.

Formulas

Given two lines in standard form:

a₁x + b₁y = c₁

a₂x + b₂y = c₂

The system determinant (Cramer's rule):

D = a₁b₂ − a₂b₁

If D ≠ 0, the unique intersection point is:

x = c₁b₂ − c₂b₁D

y = a₁c₂ − a₂c₁D

If D = 0, the lines are parallel (no intersection) or coincident (infinite intersections). The total number of pairwise intersections for n lines:

C(n, 2) = n!2!(n − 2)!

Where a₁, b₁, c₁ are coefficients of the first line, a₂, b₂, c₂ are coefficients of the second line, D is the system determinant, and x, y are the coordinates of the intersection (corner) point.

Reference Data

Number of Lines	Max Corner Points	Pairwise Combinations	Typical Application
2	1	1	Single constraint intersection
3	3	3	Triangle feasible region
4	6	6	Quadrilateral LP region
5	10	10	Pentagon feasible region
6	15	15	Complex multi-constraint LP
7	21	21	Production scheduling
8	28	28	Portfolio optimization
9	36	36	Transportation problems
10	45	45	Network flow models
12	66	66	Multi-resource allocation
15	105	105	Large-scale LP
20	190	190	Industrial optimization
n	n(n − 1)2	C(n, 2)	General formula

Frequently Asked Questions

When the determinant D = a₁b₂ − a₂b₁ equals 0, the two lines are either parallel (no intersection) or coincident (infinitely many points in common). The calculator detects this condition and reports the pair as having no valid corner point. In linear programming, parallel constraints simply reduce the feasible region without contributing a vertex.

IEEE 754 double-precision arithmetic carries approximately 15-17 significant decimal digits. For most LP problems with coefficients under 10⁶, precision loss is negligible. However, near-parallel lines (determinant D close to 0 but not exactly 0) can produce intersection coordinates with large magnitudes and reduced accuracy. The calculator flags pairs where |D| < 10⁻¹⁰ as effectively parallel. You can adjust the decimal precision from 0 to 10 places for display rounding.

This calculator computes geometric intersections of lines (equalities), not inequality feasibility. After obtaining all corner points, you must substitute each point back into every inequality constraint to verify feasibility. A corner point is feasible only if it satisfies all constraints simultaneously. This two-step process - find vertices, then filter - is the standard Corner Point Method in linear programming.

Rearrange y = mx + b to −mx + y = b, giving a = −m, b = 1, c = b. For example, y = 3x + 2 becomes −3x + y = 2 (or equivalently 3x − y = −2). The calculator accepts direct standard form coefficients a, b, and c for each line. If your line passes through two points (x₁, y₁) and (x₂, y₂), compute a = y₂ − y₁, b = x₁ − x₂, and c = a·x₁ + b·y₁.

The calculator supports up to 20 lines, yielding a maximum of C(20, 2) = 190 pairwise intersection points. For n lines, the computation involves n(n−1)/2 determinant evaluations, each in O(1) time, so the total complexity is O(n²). Even at 20 lines, this completes in under 1 millisecond on modern hardware.

After finding all feasible corner points, substitute each (x, y) coordinate into your objective function Z = px + qy, where p and q are the objective coefficients. The corner point yielding the largest Z is the maximum; the smallest Z is the minimum. This works because linear functions on convex polytopes always attain their extrema at vertices (Fundamental Theorem of Linear Programming).