Standard form of a linear program

Mathematical statement

A is an exact rational m-by-n matrix with matching b,c and decision vector x. Qualify dimensions and the chosen sign convention first. Nonnegative slack s=b−A*x converts A*x≤b to A*x+s=b, preserving feasibility and c^T*x in both directions between original and slack points. A free variable splits as x_plus−x_minus with both parts nonnegative; negate a ≥ constraint, replace equality by opposite ≤ rows, and negate a minimization objective. These conversions do not prove feasibility, boundedness or an optimal solution, and another standard-form convention is not silently substituted.

Representative formula (exact TeX)

L(A,b,c)=z

Assumptions

• Matrices, vectors and points are bounded exact rationals.
• Statements and outputs consistently use maximize/≤/nonnegative.

Symbol scope

• L — linear-program standard-form representation
• A — constraint matrix
• b — right-hand-side vector
• c — objective vector
• z — objective value

Intuition, definition, and misconceptions

A single convention avoids standard-form ambiguity.

Slack conversion includes both directions of the point correspondence.

Free variables, ≥, equality and minimization have separately stated conversions.

Do not mix objective/inequality conventions or mistake a representation conversion for feasibility or optimality.

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

• Linear programming — Fix the objective and constraints.
• Finite matrices: dimensions, indexing, and transpose — Use matrix-vector multiplication.
• Linear systems in two variables and degenerate constraints — Slack variables give an equality form.
• Usual order on the real numbers — Inequalities are componentwise.

Verification boundary

Only representation and point correspondences are certified, not feasibility, boundedness, optimality or duality. A free-variable split is nonunique even though the slack map has a unique slack for each x.

not_formalized

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

Next obligation

Add linear-programming duality.

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.