Dual linear program¶

The linear program constructed from a specified primal by exchanging variables and constraints, transposing the coefficient matrix, reversing objective direction, and applying the corresponding sign and inequality rules.

Version: v1 · 2026-09-28 · History
Domain-specific #: 7630
Origin domain: Linear Programming
Subdomain: Duality → Linear Programming

Core Idea¶

A dual linear program is the linear optimization problem constructed from a given primal program by exchanging the roles of variables and constraints and reversing the objective direction. For the standard primal [ \max c^Tx\quad\text{subject to }Ax\leq b, x\geq0, ] the dual is [ \min b^Ty\quad\text{subject to }A^Ty\geq c, y\geq0. ] Each primal constraint supplies one dual variable, each primal variable supplies one dual constraint, and the matrix is transposed.

How would you explain it like I'm…

The Flipped Partner Puzzle

Imagine one puzzle: make the biggest pile of toys you can, following some rules. You can build a partner puzzle by flipping the first one around: find the smallest number that the pile can never go above. The two puzzles are made from each other, and when both have a best answer, those answers are the same number.

Best Plan and Its Partner

Many problems ask for the best plan, like making the most money with a limited amount of wood and paint. That is called a linear program. Its dual is a partner problem built from it by swapping things around: each rule in the first becomes an unknown in the second, and each unknown becomes a rule. The first problem looks for the biggest value, and the partner looks for the smallest. Any answer to the partner gives a ceiling the first problem can't beat, and when the best answers exist, they meet at the same number. You can think of the partner as figuring out what each bit of wood and paint is really worth.

Primal–Dual Linear Programs

A dual linear program is built from an original, or primal, linear program by swapping the roles of variables and constraints and flipping maximize to minimize. If the primal is: maximize c times x subject to Ax at most b and x at least 0, the dual is: minimize b times y subject to A-transpose times y at least c and y at least 0. Each primal constraint becomes a dual variable, each primal variable becomes a dual constraint, and the matrix gets transposed. Weak duality says any feasible dual solution gives an upper bound on the primal objective; strong duality says that when an optimum exists, the two optimal values are equal. In a production problem, the dual variables can be read as the value, or shadow price, of each resource. The dual is defined by this construction, not just by having the same optimal value.

A dual linear program is the LP constructed from a given primal by exchanging the roles of variables and constraints and reversing the direction of optimization. For the primal max cᵀx subject to Ax ≤ b, x ≥ 0, the dual is min bᵀy subject to Aᵀy ≥ c, y ≥ 0. Each primal constraint supplies one dual variable, each primal variable one dual constraint, and the coefficient matrix is transposed. Constraint senses and variable sign restrictions determine one another, so an equality constraint yields an unrestricted dual variable, with analogous rules in other standard forms. The payoff is certified bounds: weak duality gives cᵀx ≤ bᵀy for any feasible pair, and strong duality states that when an optimum exists, both programs attain the same optimal value. In resource-allocation terms, primal variables choose production levels while dual variables act as resource valuations or shadow prices. The identity is the paired derivation: a separately written LP that happens to share the optimum is not the dual, equal optimal values are a theorem about a correctly built pair, and applying the transformation twice returns the primal.

Scope of Application¶

A dual linear program operates within linear optimization wherever a specified primal LP supplies the objective, coefficient matrix, constraint senses, and variable restrictions from which its partner is derived. - Standard-form dual construction. — max–min pairs with nonnegative variables and one-sided inequalities expose the basic exchange of primal variables and constraints through A^T. - Mixed constraint and sign forms. — equality constraints, free variables, reversed inequalities, and nonpositive variables are handled by the corresponding dual sense and sign rules. - Weak-duality bounds. — every feasible dual solution supplies a certificate bounding every feasible primal objective in the direction fixed by the pair. - Optimality certification. — equal objective values for a feasible primal–dual pair certify optimality under LP duality without enumerating either feasible region.

Clarity¶

Naming the dual linear program distinguishes a rule-governed partner from any other optimization problem that shares a value or interpretation with the primal. The correspondence is exact: each primal constraint becomes a dual variable, each primal variable becomes a dual constraint, and every inequality, equality, and sign restriction determines the matching dual condition.

Manages Complexity¶

A linear program may contain many variables, constraints, coefficient signs, and inequality directions, yet dual construction reduces their reorganization to a fixed correspondence. For a primal with n variables and m constraints, the analyst tracks the shared coefficient matrix, its transpose, the exchange of the objective and right-hand-side vectors, and the sign/inequality conversion table. The result has m dual variables and n dual constraints.

Abstract Reasoning¶

The constructive inference runs from a primal program's objective direction, coefficient matrix, constraint senses, and variable signs to its dual. Each primal constraint becomes a dual variable, each primal variable becomes a dual constraint, A becomes A^T, and the sign/sense correspondence fixes the remaining branches. Applying the correspondence again provides a diagnostic check: the dual of the dual must recover the primal in the matched form.

Knowledge Transfer¶

Within linear programming, dual construction transfers literally across resource allocation, production planning, and any other application that can be expressed as an LP. The application's nouns change, but the coefficient matrix, objective and right-hand-side vectors, constraint senses, and variable signs still determine the primal-to-dual map. The same diagnostics carry with them: a feasible dual vector certifies a bound, equality of feasible objective values certifies optimality, and the dual variables can be interpreted against the primal constraints that generated them.

Relationships to Other Abstractions¶

Current abstraction Dual linear program Domain-specific

Parents (1) — more general patterns this builds on

Dual linear program is a kind of Linear Programming (LP) Prime

A dual has continuous decision variables, a linear scalar objective, and a feasible region cut out by linear equalities or inequalities, so it realizes the parent's complete optimization object rather than merely assisting one.

Hierarchy paths (2) — routes to 2 parentless roots

Dual linear program → Linear Programming (LP) → Optimization

Show alternative path (1)

Neighborhood in Abstraction Space¶

Dual linear program sits in a sparse region of the domain-specific corpus (88^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2551 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08