# Linear programming

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

Linear programming optimizes a linear objective over a feasible domain defined by linear equalities or inequalities; this exercise slice checks only a complete explicit finite candidate grid.

mko-linear-programming · definition · v0.10.0



## 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

[Linear programming: the best supplied candidate, and why it is not the continuous optimum](https://ocme.evemisslab.com/en/derivations/derivation-mko-linear-programming-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Optimization problem](https://ocme.evemisslab.com/en/mko/mko-optimization-problem/) — A linear program is an optimization problem with a linear objective and constraints.
- [Linear equation in one variable](https://ocme.evemisslab.com/en/mko/mko-linear-equation/) — Constraint boundaries use linear expressions.
- [Linear systems in two variables and degenerate constraints](https://ocme.evemisslab.com/en/mko/mko-system-linear-equations/) — Intersections of constraint boundaries can be described by linear systems.
- [Plane vectors in a fixed basis](https://ocme.evemisslab.com/en/mko/mko-vector/) — 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.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/linear-programming.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-linear-programming/index.md)