Linear Programming · Lesson 2 of 4

Feasible Regions and Corner-Point Solutions

“Use graphs and vertex values to find unique or multiple optimal solutions in bounded regions.”

Learning Objectives

• Construct a feasible region as the intersection of all constraint half-planes. • Distinguish feasible points, vertices, and optimal solutions. • Use the corner-point theorems for a nonempty bounded feasible region. • Calculate and compare objective values at every vertex. • Explain why a whole edge can contain optimal solutions.

From restrictions to a region

Each pair of variable values is a point in the coordinate plane. A linear inequality selects one side of a straight boundary line, and a system of inequalities selects only the points common to all the chosen sides. This turns the list of allowed decisions into a picture.

To graph an inequality, first draw its boundary equation. For $5 x + y \leq 100$ , the boundary is $5 x + y = 100$ , with intercepts $(20, 0)$ and $(0, 100)$ . Test a point away from the line: $(0, 0)$ satisfies the inequality, so choose the side containing the origin. Because equality is allowed, keep the boundary line solid.

Repeat for $x + y \leq 60$ , then restrict to $x, y \geq 0$ . The common part is the dealer's feasible region. A point on a boundary is included if it satisfies the other constraints too; the entire boundary line is not automatically feasible.

Definition

Feasible region

The feasible region is the common set of points satisfying all the constraints, including non-negative restrictions. Points inside it or on its included boundary are feasible solutions. Points outside it are infeasible solutions.

The dealer’s feasible region— The blue quadrilateral is the overlap of the budget, storage, and non-negative restrictions.

Example — Find the dealer’s corner points

Problem
Find all vertices of the dealer's feasible region and test the point $(10, 50)$ .

1.On the $x$ -axis, $y = 0$ . The budget gives $x \leq 20$ and storage gives $x \leq 60$ , so the feasible endpoint is $(20, 0)$ .
2.On the $y$ -axis, $x = 0$ . Storage restricts $y$ to 60, so the feasible endpoint is $(0, 60)$ . The origin is also feasible.
3.For the intersection of the two sloping boundaries, subtract $x + y = 60$ from $5 x + y = 100$ . This gives $4 x = 40$ , so $x = 10$ and $y = 50$ .
4.The vertices are $(0, 0)$ , $(20, 0)$ , $(10, 50)$ , and $(0, 60)$ . At $(10, 50)$ both resource inequalities are equalities, so the plan uses the entire budget and storage capacity.

Definition

Corner point or vertex

A vertex is a feasible point where boundary lines meet to form a corner of the region. An intersection of extended boundary lines outside the feasible region is not a feasible vertex.

Definition

Bounded region

A region is bounded if it can be enclosed inside a sufficiently large circle. An unbounded region continues indefinitely in at least one direction.

Feasible regions formed by linear inequalities are convex: the straight segment between any two feasible points remains feasible. To see why, consider one resource limit. A mixture of two plans that each stay below that limit also stays below it. This remains true for every linear constraint, so it holds for their intersection.

Why the corners are enough

The region contains infinitely many points, so testing them one by one is impossible. Linear objectives and straight boundaries give a powerful shortcut. The following two corner-point results justify the method; formal proofs are not required here.

Corner-point theorems

For the nonempty feasible regions studied here, if a linear objective has an optimal value, at least one vertex attains that value. If the feasible region is bounded, both a maximum and a minimum exist, and each is attained at a vertex. Other points may also share the same optimal value.

An intuitive way to see the result is to draw lines $a x + b y = k$ for different values of $k$ . Each line represents a constant objective value. Moving between these parallel lines changes the value; a last or first contact with a bounded polygon occurs at a vertex or along an edge containing vertices. This explains why a table of vertex values is sufficient.

Definition

Optimal feasible solution

An optimal feasible solution is a point in the feasible region where the objective reaches the required maximum or minimum. “Feasible” describes permission; “optimal” describes the best objective value among permitted choices.

Graph all constraints and keep only their common region.
Check that the region is nonempty and bounded for the method used in this lesson.
Find every vertex, solving simultaneous boundary equations where necessary.
Evaluate the objective at each vertex.
Select the required maximum or minimum and interpret both the point and its objective value.

Example — Complete the dealer’s optimisation

Problem
Find the maximum profit for $Z = 250 x + 75 y$ in the dealer's feasible region.

1.Evaluate profit at the four feasible vertices, not at arbitrary intercepts outside the region.
2.At $(0, 0)$ the profit is 0; at $(20, 0)$ it is $250 (20) = 5000$ ; at $(10, 50)$ it is $250 (10) + 75 (50) = 6250$ ; at $(0, 60)$ it is $75 (60) = 4500$ .
3.The region is bounded, so its largest vertex value is the true maximum. The best purchase is 10 tables and 50 chairs, earning ₹6,250.
4.The point $(10, 50)$ gives the quantities to buy. The number 6,250 gives the profit. These answer different parts of the question.

Vertex	Profit in rupees
$(0, 0)$	0
$(20, 0)$	5,000
$(10, 50)$	6,250 — maximum
$(0, 60)$	4,500

Maximisation and minimisation

The same procedure works for either goal. Changing the objective changes which point is best without changing the feasible region. The largest value of one variable or the intersection using both resources is not automatically the optimum.

A maximum at an axis vertex— The intersection of the two sloping lines is feasible, but it does not maximise this objective.

Example — The best point need not use both limits

Problem
Maximise $Z = 4 x + y$ subject to $x + y \leq 50$ , $3 x + y \leq 90$ , and $x, y \geq 0$ .

1.The axes give feasible endpoints $(30, 0)$ and $(0, 50)$ , along with the origin. Subtracting $x + y = 50$ from $3 x + y = 90$ gives $2 x = 40$ , so the other vertex is $(20, 30)$ .
2.The feasible region is bounded. Evaluate the objective at its four vertices: $Z (0, 0) = 0$ , $Z (30, 0) = 120$ , $Z (20, 30) = 110$ , and $Z (0, 50) = 50$ .
3.The maximum is 120 at $(30, 0)$ . The intersection $(20, 30)$ uses both sloping boundary equalities but has a smaller objective value.
4.Resource use alone does not determine optimality; the objective coefficients must also be considered.

Vertex	Value of the objective
$(0, 0)$	0
$(30, 0)$	120 — maximum
$(20, 30)$	110
$(0, 50)$	50

A bounded minimisation region— One lower-limit constraint and one upper-limit constraint enclose a feasible triangle against the y-axis.

Example — Minimise over a feasible triangle

Problem
Minimise $Z = 200 x + 500 y$ subject to $x + 2 y \geq 10$ , $3 x + 4 y \leq 24$ , and $x, y \geq 0$ .

1.The first inequality selects the side away from the origin; the second selects the side containing it. Their first-quadrant overlap is a bounded triangle.
2.On the $y$ -axis the allowed endpoints are $(0, 5)$ and $(0, 6)$ . Double $x + 2 y = 10$ to obtain $2 x + 4 y = 20$ , then subtract this from $3 x + 4 y = 24$ : $x = 4$ , giving $y = 3$ .
3.At $(0, 5)$ , $(4, 3)$ , and $(0, 6)$ , the objective values are 2,500, 2,300, and 3,000 respectively.
4.The minimum is 2,300 at $(4, 3)$ . A negative objective coefficient is not necessary for a minimum; the feasible region determines which values are accessible.

Vertex	Value of the objective
$(0, 5)$	2,500
$(4, 3)$	2,300 — minimum
$(0, 6)$	3,000

When an entire edge is optimal

A vertex table can have a tie for the best value. For a linear objective, equal optimal values at two vertices imply the same optimal value all along the segment joining them. Convexity ensures that this segment remains feasible.

Multiple optimal solutions on an edge— The highlighted edge joins two maximum points; every point on that edge has the same objective value.

Example — One minimum and many maxima

Problem
Find both extrema of $Z = 3 x + 9 y$ subject to $x + 3 y \leq 60$ , $x + y \geq 10$ , $x \leq y$ , and $x, y \geq 0$ .

1.The bounded feasible quadrilateral has vertices $A = (0, 10)$ , $B = (5, 5)$ , $C = (15, 15)$ , and $D = (0, 20)$ . The intersections on $x = y$ follow from $2 x = 10$ and $4 x = 60$ .
2.The objective values at A, B, C, D are respectively 90, 60, 180, and 180. Thus the minimum is 60 at B.
3.Both C and D give the maximum 180. On the whole joining edge, $x + 3 y = 60$ , so $Z = 3 (x + 3 y) = 180$ .
4.For example, the midpoint $(7.5, 17.5)$ is feasible and gives $3 (7.5) + 9 (17.5) = 180$ . The maximum occurs at infinitely many points, not just at the two listed vertices.

Vertex	Value of the objective
$A = (0, 10)$	90
$B = (5, 5)$	60 — minimum
$C = (15, 15)$	180 — maximum
$D = (0, 20)$	180 — maximum

More generally, a point dividing a feasible segment can be written as $P = (1 - t) A + tB$ with $0 \leq t \leq 1$ . A linear objective obeys $Z (P) = (1 - t) Z (A) + tZ (B)$ . If both endpoint values equal the same optimal value, this expression stays equal to that value for every point on the segment.

An optimum at a vertex need not be unique

The theorem guarantees that a vertex attains an existing optimum. It does not say that only vertices can be optimal. Also, two vertices with equal values produce an optimal edge only when their common value is actually the required maximum or minimum.

Quick check

Which point belongs to the dealer’s feasible region?

Quick check

What is guaranteed for a nonempty bounded feasible region and a linear objective?

Quick check

For $Z = 4 x + y$ , which vertex gives the largest value among $(0, 0)$ , $(30, 0)$ , $(20, 30)$ , and $(0, 50)$ ?

Quick check

In the minimisation example $Z = 200 x + 500 y$ , what is the objective value at $(4, 3)$ ?

Quick check

Two feasible vertices attain the same maximum. What follows for the segment joining them?

Quick check

Why is an intersection of two extended boundary lines sometimes excluded from a vertex table?

Practice Problems

Maximise $Z = 3 x + 4 y$ subject to $x + y \leq 4$ and $x, y \geq 0$ . Draw the region and make a vertex table.
Minimise $Z = - 3 x + 4 y$ subject to $x + 2 y \leq 8$ , $3 x + 2 y \leq 12$ , and $x, y \geq 0$ .
Maximise $Z = 5 x + 3 y$ subject to $3 x + 5 y \leq 15$ , $5 x + 2 y \leq 10$ , and $x, y \geq 0$ . Keep exact fractions when finding intersections.
Maximise $Z = 3 x + 2 y$ subject to $x + 2 y \leq 10$ , $3 x + y \leq 15$ , and $x, y \geq 0$ .
Find both extrema of $Z = 5 x + 10 y$ subject to $x + 2 y \leq 120$ , $x + y \geq 60$ , $x - 2 y \geq 0$ , and $x, y \geq 0$ . Describe every maximum point.
Find both extrema of $Z = x + 2 y$ subject to $x + 2 y \geq 100$ , $2 x - y \leq 0$ , $2 x + y \leq 200$ , and $x, y \geq 0$ . Describe the minimum set.
Explain why the whole dealer budget line is not part of the feasible region, even though it satisfies the budget equality.
If two non-optimal vertices have the same objective value, what can you conclude about the segment between them? What can you not conclude?

Key Takeaways

The feasible region is the intersection of every constraint half-plane. For a nonempty bounded region, evaluate the objective at all feasible vertices to find both extrema. Solve boundary equations to find vertices, then check the remaining restrictions. Equal optimal values at two vertices give a whole feasible segment of optimal solutions. Interpret both the optimal decision and the objective value.

Previous · Lesson 1

Modeling Decisions with Linear Programming

Next · Lesson 3

Unbounded and Infeasible Problems

From restrictions to a region

Why the corners are enough

Maximisation and minimisation

When an entire edge is optimal

Quiz

Practice Problems

Key Takeaways