Skip to content
NumeriveMATHUniversity mathematics

TOPIC 1 / 2

Feasible Regions, Vertices & Dual Bounds

Useful preparation: Graphing Inequalities & Feasible Regions

For a long equation, swipe sideways inside its formula box to see every term.

Meaning & notation

A linear program chooses values that satisfy all linear restrictions while making a linear objective as large or small as possible. In two variables, each restriction cuts out a half-plane. Their intersection is the feasible region. Sliding a straight objective-level line explains why corners are useful, while a weighted combination of constraints can prove that no feasible point does better.

Feasible point and objective
A feasible point satisfies every constraint, including sign restrictions. The objective c transpose x assigns a value to each feasible point and must be stated separately from the restrictions.
Vertex
A vertex is an extreme point: it cannot be written as a nontrivial convex combination of two distinct feasible points. In a polygon, vertices are its corners.
Dual bound
For a maximization problem, a valid upper bound follows from constraints by operations that preserve their inequality directions. A feasible point attaining that bound is provably optimal.

Conditions before calculation

  • Linear objectives and constraints contain no products of decision variables, powers above one, or variable-dependent coefficients. Ordinary linear programming allows fractional variable values.
  • For a nonempty bounded polygon, a linear objective attains a maximum and minimum, each at at least one vertex. There can be additional optimal points along an edge or throughout the region.
  • First check feasibility and boundedness of the objective. An unbounded feasible region need not make every objective unbounded, and arbitrary polyhedra may have no vertices.

Why the method works

1. Translate the model

Define each decision variable with units, then express resources and requirements as inequalities. A graph is useful only after the directions and nonnegativity conditions match the application.

2. Enumerate feasible corners

Find boundary intersections, but keep only those satisfying every constraint. Compare objective values at the retained vertices when the bounded-polygon theorem applies.

3. Certify with constraint weights

For max c transpose x with Ax at most b and x nonnegative, choose a nonnegative vector u with A transpose u at least c. Every feasible objective is bounded by b transpose u.

cTx≤uTAx≤uTbc^{\mathsf T}x\le u^{\mathsf T}Ax\le u^{\mathsf T}b

Worked examples

EXAMPLE 1

Maximize 3 x+2 y\displaystyle 3\, x + 2\, y subject to x+y\displaystyle x + y at most 4, 2 x+y\displaystyle 2\, x + y at most 5, and x,y nonnegative.

  1. The two slanted boundaries intersect at (1,3). Together with the axes, the feasible vertices are (0,0), (2.5,0), (1,3), and (0,4).

  2. Evaluate the objective at each vertex.

    0,7.5,9,80,\quad 7.5,\quad 9,\quad 8

  3. Add the two resource inequalities to certify the upper bound; the candidate meets both with equality.

    3x+2y=(x+y)+(2x+y)≤4+5=93x+2y=(x+y)+(2x+y)\le4+5=9

Conclusion: The feasible point (1,3) attains 9 and is therefore optimal; the bound is a proof that covers all feasible points.

EXAMPLE 2

For x,y nonnegative and x−y\displaystyle x - y at most 1, compare maximizing and minimizing x+y\displaystyle x + y.

  1. The origin is feasible. For every nonnegative t, the point (t,t) is also feasible because its coordinate difference is zero.

  2. Along this feasible ray, the objective grows without bound.

    x+y=2t⟶∞x+y=2t\longrightarrow\infty

  3. For minimization, nonnegativity supplies a lower bound that the origin attains.

    x+y≥0,(x,y)=(0,0)x+y\ge0,\qquad (x,y)=(0,0)

Conclusion: The maximum is unbounded, but the minimum is 0. The same unbounded feasible region produces different objective behavior.

Pitfalls & counterexamples

Tempting claim: An optimal solution must be a unique vertex.

Correction: At least one optimal vertex exists under the stated bounded-polygon conditions, but uniqueness is a separate question.

Test the claim: Maximizing x+y\displaystyle x + y over the nonnegative triangle x+y\displaystyle x + y at most 1 makes every point on the edge x+y=1\displaystyle x + y = 1 optimal.

Check your understanding

Can multiplying a less-than-or-equal constraint by a negative weight preserve its direction?

Write a reason before opening the explanation. This reflection is not graded or saved.

Compare your reasoning

No.

A negative multiplier reverses the inequality. Nonnegative dual weights prevent this error for the displayed upper-bound construction.

Connect this idea

Duality interprets constraints as certificates and resource values. Integer programming adds discrete restrictions; sensitivity analysis asks how the optimal value changes when resource limits change.

Practise this topic →Review concept flashcards

Reference reading

Use these texts to study the underlying definitions and theorems in greater depth. The explanations and examples above are written for Numerive.

Numerive