Read a linear objective on a polyhedron

Try

A synthetic allocation problem maximizes 2x+y subject to x+y≤5, x≤3 and x,y≥0. Draw the feasible polygon and list its vertices: (0,0), (3,0), (3,2), (0,5). Their objective values are 0,6,8,5, suggesting (3,2). A stronger certificate is 2x+y=(x+y)+x≤5+3=8, attained at that point. This short inequality proves a global optimum without relying on the accuracy of a drawing or an exhaustive numerical grid.

Predict

Predict what happens if the objective becomes x+y. Every point on the feasible top edge from (0,5) to (3,2) is optimal. Therefore “every optimizer is a vertex” is false. A correct bounded-polytope theorem says at least one optimal vertex exists. An algorithm returning one vertex may hide a whole face of alternative optimal decisions. The choice among them can matter for unmodeled considerations such as fairness, simplicity or robustness.

Experiment

Compare objective contours by evaluating the same feasible vertices. Keep the feasible set fixed so the effect of changing preferences is isolated.

Vertex	2x+y	x+y	x−y
(0,0)	0	0	0
(3,0)	6	3	3
(3,2)	8	5	1
(0,5)	5	5	−5

For the last column, prove the upper bound x−y≤x≤3. Then identify the equality conditions. This exercise shows how a supporting linear inequality explains the result and why it can be more informative than a table of candidate values alone.

Understand

A linear program, or LP, has a linear objective and affine equality or inequality constraints. Its feasible set is a polyhedron, an intersection of finitely many half-spaces and affine hyperplanes. A bounded polyhedron is a polytope. Linear objectives are both convex and concave; maximization over a convex set can therefore have strong global certificates even though the gradient never vanishes.

For a nonempty bounded polytope, compactness gives an optimum. The polytope is the convex hull of its finitely many vertices. Since a linear objective at a convex combination is the same convex combination of vertex values, some vertex attains at least that value. This yields existence of an optimal vertex, while allowing optimal edges and faces. The next lesson proves the algebraic vertex characterization used by simplex. The convex-hull representation is a finite-dimensional polytope theorem, not a consequence of sampling a few boundary points.

Apply

Unbounded feasible geometry does not necessarily mean an unbounded objective. On x≥0, maximizing −x gives the finite maximum zero. In contrast, if x₀ is feasible for Ax≤b,x≥0 and a direction d satisfies d≥0, Ad≤0 and cᵀd>0, then x₀+td remains feasible for all t≥0 while cᵀ(x₀+td) grows indefinitely. This is an explicit feasible-ray certificate of unboundedness. The feasible starting point is essential: an inconsistent system does not become “unbounded” merely because its homogeneous inequalities admit an improving direction.

Translate the workshop model into units. If x and y must count whole items, the polygon is only a continuous relaxation, not the actual integer feasible set. Its optimum still supplies a useful bound, but rounding a fractional vertex requires a new feasibility check. A continuous LP solver cannot silently enforce a constraint absent from its model.

Continue

Report the feasible status, objective direction and a verifiable bound with every proposed optimum. A plotted polygon is explanatory evidence; exact inequalities certify the result. Continue to Basic feasible solutions for the independent-column description of vertices. This supplies the bridge from two-dimensional pictures to high-dimensional linear algebra without suggesting that all useful LPs can be inspected visually.