Enumerate and Evaluate - Linear Programming is Geometry

Once vertices are known, exact objective values choose the maximum. This lesson keeps the geometry and the arithmetic side by side with tables for each objective. The winning row is the same point highlighted by the diagram.

highlighted = computed this step

Flagship values

For the flagship problem, the table lists each recomputed vertex and z=x+y. The largest value is z=8/3 at (4/3, 4/3). Why: the table and the highlighted corner are two views of the same exact recomputation.

\begin{array}{ccc}x&y&z\\0&0&0\\2&0&2\\0&2&2\\4/3&4/3&8/3\end{array}

Asymmetric values

For the asymmetric problem, the table evaluates z=x plus 2y at every recomputed vertex. The largest value is z=22/5 at (6/5, 8/5). Why: the winning row tells you which plotted corner the objective selects.

\begin{array}{ccc}x&y&z\\0&0&0\\2&0&2\\0&2&4\\6/5&8/5&22/5\end{array}

Tilted values

On the flagship polygon with z=3x+y, enumeration picks (2, 0) with z=6. Why: this table is the arithmetic version of the tilted last-touch contour.

\begin{array}{ccc}x&y&z\\0&0&0\\0&2&2\\4/3&4/3&16/3\\2&0&6\end{array}

Pick the maximum

Enumeration is exact: evaluate every vertex, then choose the greatest objective value. The flagship max is 8/3; the asymmetric max is 22/5; and the tilted max is 6. Why: once the vertex list is finite, optimization becomes comparison.

\max z_{\text{flag}}=8/3\quad \max z_{\text{asym}}=22/5

Diagram note

Every row is computed from a recomputed vertex and the stated objective. Pixel positions are rounded for layout; every number shown is exact.

\text{enumerate vertices, evaluate, compare}