Linear programming

Mathematical statement

A linear program consists of a linear objective and linear constraints and seeks a minimum or maximum on the feasible domain. A finite candidate grid permits complete checking of its listed points, but unless coverage of the general feasible domain has been proved, its conclusion is only best among the supplied candidates.

Representative formula (exact TeX)

L(x,y)

Assumptions

• Exercises use two-variable integer constraints a*x+b*y≤c, integer-coefficient objectives and complete explicitly supplied finite candidates.
• Finite-grid enumeration does not establish a global optimum on a continuous polyhedron or for a general linear program.

Symbol scope

• L — linear-program data
• x — first decision coordinate
• y — second decision coordinate

Intuition, definition, and misconceptions

Check feasibility constraint by constraint before comparing objective values among feasible candidates.

A linear objective can tie at several candidate points; argmin or argmax must retain every optimal index.

The candidate table’s completeness is part of the conclusion’s scope. Without a polyhedral vertex-completeness proof, do not extrapolate beyond it.

Do not choose an infeasible point for its better objective value or pass off a finite-grid best point as a general LP optimum.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Optimization problem — A linear program is an optimization problem with a linear objective and constraints.
• Linear equation in one variable — Constraint boundaries use linear expressions.
• Linear systems in two variables and degenerate constraints — Intersections of constraint boundaries can be described by linear systems.
• Plane vectors in a fixed basis — Objective and constraint coefficients can be viewed through vector dot products.

Verification boundary

Only optimality among the supplied finite candidates is established; general feasible domains, duality and optimality certificates are not developed.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add standard forms, vertices, duality and replayable optimality certificates.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.