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
Domain group: Formal Sciences
Origin domain: Operations Research
Subdomain: Duality → Operations Research

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.^[1] 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.^[2] Constraint directions and variable sign restrictions determine one another, so equality constraints correspond to unrestricted dual variables and analogous sign reversals apply in other standard forms.^[3]

The construction turns feasible dual solutions into certified bounds on feasible primal objectives.^[4] Weak duality gives \(c^Tx\leq b^Ty\); strong duality states that, when an optimum exists under the linear-program conditions, both programs attain the same optimal value.^[5] In resource-allocation form, primal quantities choose production while dual variables act as resource valuations or shadow prices.^[6]

The paired derivation is the identity of the abstraction. An independently written linear program that happens to share an optimum is not thereby the dual, and the equality of optimal values is a theorem about a correctly constructed pair rather than the construction itself.^[7] Applying the transformation twice returns the primal.^[8]

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.

Structural Signature¶

Sig role-phrases:

the primal program — a linear objective, coefficient matrix, right-hand-side vector, constraint senses, and variable sign restrictions supply the program to be transformed.
the objective reversal — a primal maximization becomes dual minimization, or primal minimization becomes dual maximization.
the constraint–variable exchange — each primal constraint generates one dual variable and each primal variable generates one dual constraint.
the transposed coefficient relation — the shared coefficient matrix appears as A in the primal and A^T in the dual.
the sign-and-sense correspondence — primal inequality directions, equality constraints, and variable restrictions determine the matching dual restrictions and constraint senses.
the bound certificate — every feasible primal–dual pair satisfies weak duality, so the dual objective bounds the primal objective in the direction fixed by the pair.
the equality guarantee — under the linear-program strong-duality conditions, attained primal and dual optima have the same value.
the involutive check — applying the matched dual construction again recovers the primal program in the corresponding standard form.
the interpretation branch — in resource-allocation models, dual variables may be read as valuations tied to the particular primal constraints that generated them.
the derivation boundary — coincident objective values, opposing viewpoints, or an independently formulated optimization problem do not make a dual linear program without the prescribed construction.
the feasibility limitation — duality organizes infeasible and unbounded cases, but it does not guarantee that both members of every constructed pair possess optimal solutions.

What It Is Not¶

Not just another linear program. A dual must be derived from a specified primal by the constraint–variable exchange, objective reversal, transposed coefficient relation, and matched sign-and-sense rules.
Not the algebraic inverse or simple negation of the primal. The construction does not solve for inverse variables or negate every coefficient; it systematically retypes primal constraints as dual variables and primal variables as dual constraints.
Not any optimization problem with the same optimum. Coincident objective values do not create the derivation relation, and applying the dual construction twice is a stronger identity check than numerical agreement.
Not the weak- or strong-duality theorem. The dual program is the constructed partner; bounding and equality of optima are results that apply to a correctly formed primal–dual pair.
Not a guarantee that both programs have optimal solutions. A constructed pair can include infeasibility or unboundedness, so strong-duality conclusions require the relevant existence conditions.
Not inherently an integer linear program. The ordinary LP duality construction uses continuous variables and constraints; adding integrality changes the problem class and does not preserve the same strong-duality guarantee.
Not always a literal market-pricing problem. Shadow-price and resource-valuation readings depend on an application-specific primal interpretation; the formal dual exists without those economic nouns.

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. The scope follows the exact constraint–variable exchange, transposition, objective reversal, and sign correspondence; an independently formulated problem or a coincident optimum is not a dual without that construction.

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.
Feasibility and unboundedness analysis — the constructed pair organizes the possible branches among finite optimum, infeasibility, and unboundedness without assuming both members attain solutions.
Resource-allocation models — primal production or allocation variables are paired with a dual valuation problem whose variables correspond to the constrained resources.
Shadow-price and sensitivity interpretation — dual values are interpreted against the exact primal constraints that generated them, with nonuniqueness and application assumptions retained.
Production-planning applications — goods, resource stocks, technologies, and market values provide concrete LP carriers while the formal primal-to-dual map remains unchanged.

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. A coincident optimum does not establish this relationship unless those mappings hold.

The label lets an optimizer ask: Which primal constraint generated this dual variable, and does the resulting feasible dual objective certify the claimed bound? That question separates construction from theorem. Weak duality supplies a bound for every feasible primal–dual pair; equality of optimal values belongs to strong duality and requires attainment conditions. It also clarifies shadow-price interpretations by tying each price to a particular constrained resource rather than treating the dual variables as arbitrary coefficients.

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.^[9] The result has m dual variables and n dual constraints.^[10] Equality constraints, free variables, and reversed inequalities enter as explicit branches of that same table rather than requiring a new derivation for every program form.

Once the pair is formed, a high-dimensional search acquires compact certificates. Any feasible dual vector provides one scalar bound on every feasible primal objective; a primal and dual feasible pair with equal objective values certifies optimality. Feasibility and boundedness also organize the principal failure branches: an unbounded primal rules out dual feasibility, and an unbounded dual rules out primal feasibility, though both programs may be infeasible. The compression does not calculate an optimum by itself, guarantee a unique dual solution, or preserve the application-specific meaning of every coefficient. It makes the structural relation—and therefore the available bounds, shadow-price interpretation, and duality gap—readable without enumerating the primal feasible region point by point.

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.

The central certificate move runs from any feasible primal–dual pair (x, y) to the bound c^T x ≤ b^T y for the displayed max–min form. If both sides are feasible and their objective values coincide, the common value certifies primal and dual optimality without enumerating either feasible region. A positive gap leaves only a bound; equality of values for unrelated programs would not establish duality because the construction must already be satisfied.

A regime move runs from feasibility, boundedness, and attainment to which conclusion duality licenses. An unbounded primal implies an infeasible dual, and an unbounded dual implies an infeasible primal, while both may be infeasible. When an optimum exists under the linear-program hypotheses, strong duality predicts equal attained optima. Changing a primal inequality or sign restriction predicts the corresponding dual sign or constraint change; treating shadow prices as meaningful requires preserving the exact resource constraint from which each dual variable arose.

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. Thus a production schedule/resource valuation interpretation is one realization of the construction, not a different duality.

Beyond LP, the defensible reach is (B) a shared abstract mechanism within optimization: a primal problem may be paired with a derived problem whose feasible solutions provide bounds and whose optimum can coincide with the primal optimum under a suitable duality theorem. What transfers is the strategy of exchanging a direct search for certificates, bounds, and sensitivity information. The exact LP conversion table—variables to constraints, constraints to variables, matrix transposition, and sign/sense rules—remains home-bound; nonlinear or other optimization duals require their own constructions and hypotheses. A feasible LP dual can also serve in the limited (C) instrument role of an optimality certificate, but it does not measure arbitrary non-LP problems. Calling two rival formulations “dual” because they offer opposing viewpoints is only (A) analogy. Transfer stops unless one problem is derived from the other by the applicable formal rule.

Examples¶

Canonical¶

Take the primal program “maximize 3x₁ + 4x₂ subject to 5x₁ + 6x₂ = 7, with x₁, x₂ ≥ 0.” Its one equality constraint produces one unrestricted dual variable y; its two primal variables produce the constraints 5y ≥ 3 and 6y ≥ 4; and maximization becomes minimization of 7y. The stricter lower bound is y = 2/3, so the dual minimum is 14/3.^[11] In the primal, x₁ = 0 and x₂ = 7/6 attain the same value, certifying both optima.^[12]

Mapped back: The displayed maximization is the primal program; minimization is the objective reversal, and the one-variable/two-constraint partner exhibits the constraint–variable exchange. Reuse of coefficients by columns instantiates the transposed coefficient relation, while the equality's unrestricted y instantiates the sign-and-sense correspondence. The common value 14/3 supplies the equality guarantee and, through weak duality, the bound certificate.

Applied / In Practice¶

In a farm-planning LP, primal variables specify quantities of wheat and barley, the objective maximizes sales revenue, and land, fertilizer, and pesticide stocks impose resource constraints. The derived dual gives one nonnegative value to each resource and minimizes the value of the available stock, subject to each crop's imputed input cost being at least its selling price. Any feasible valuation bounds achievable farm revenue; at a shared optimum, the dual values can be read as shadow prices for the particular constrained inputs.

Mapped back: The production schedule and resource inequalities form the primal program. Turning the three resource constraints into prices and the two crop variables into valuation constraints performs the constraint–variable exchange and the transposed coefficient relation. The revenue upper bound is the bound certificate, equality at optimum is the equality guarantee, and reading the three dual variables as resource shadow prices is the interpretation branch rather than part of the formal construction itself.

Structural Tensions¶

T1: Bound certificate versus solution existence (duality informs before it guarantees). Every feasible dual solution bounds every feasible primal objective in the appropriate direction, so useful information is available without solving either problem optimally. Strong duality is stronger but conditional: it does not make both members feasible and bounded merely because the pair was constructed. Treating any dual as an attained certificate overstates the theorem; withholding all conclusions until optima are found wastes weak duality's force. The pair must be classified by feasibility, boundedness, and attainment before equality is invoked. Diagnostic: Does the available dual point supply only a valid bound, or have the hypotheses and matching primal evidence needed for an optimality certificate also been established?

T2: Formal symmetry versus interpretive asymmetry (paired programs, different application roles). The dual-of-the-dual check makes primal and dual mathematically reciprocal, yet an application commonly assigns them different meanings: quantities on one side and valuations or certificates on the other. Treating the interpretation as part of the formal construction makes LP duality depend on economic nouns; treating the two sides as semantically interchangeable loses why shadow prices answer a distinct practical question. Structural symmetry and modeling asymmetry can therefore coexist. Diagnostic: Which claims follow from the formal primal–dual map alone, and which rely on the particular resource or valuation interpretation assigned to one side?

T3: Uniform conversion rule versus representation dependence (standardization and bookkeeping). The constraint–variable exchange and sign-and-sense correspondence provide a mechanical derivation, but their displayed form depends on how equalities, free variables, and inequality directions are represented. Converting everything to a standard form simplifies the rule while potentially hiding which original modeling choice generated a dual restriction; working directly with mixed forms preserves meaning but increases sign errors. The involutive check helps, yet it also requires consistent conventions. Diagnostic: Can every dual variable and constraint be traced back to the original primal condition under one declared conversion convention, and does dualizing again recover that representation?

T4: Equal optimal value versus nonunique valuation (certificate and interpretation part company). Strong duality can fix the optimal objective value while leaving several dual solutions. Equality therefore certifies primal optimality without necessarily identifying a unique set of shadow prices. Assuming uniqueness gives an application more determinate valuations than the LP supports; dismissing nonunique solutions loses the common bound and sensitivity information they still provide. The theorem equates values, not solution vectors or interpretations. Diagnostic: Is the argument using the unique common objective value, or does it require a particular dual variable whose uniqueness and application meaning must be established separately?

T5: Dual-linear-program autonomy versus reduction to Linear Programming. Every qualifying dual linear program is a strict specialization of the exact parent Prime Linear Programming (LP) (Linear Programming (LP)): it has continuous decision variables, a linear objective, and a feasible region defined by linear constraints. Reduction preserves that optimization structure, but loses derivation from a specified primal through transposition, constraint–variable exchange, objective reversal, sign-and-sense rules, and the resulting bound certificates. Treating the dual as wholly autonomous would obscure that it remains an LP; treating any second LP as a dual erases the pairing test.
Diagnostic: Is the object merely a linear program, or is it provably generated from a paired primal by the complete LP-duality construction?

Structural–Framed Character¶

Dual linear program is structural-leaning on the structural–framed spectrum: its identity is fixed by a formal derivation that can be checked independently of application, although that derivation is specifically the one defined by linear optimization.

On evaluative_weight, neither primal nor dual is intrinsically preferable; maximization, minimization, and the objective itself are supplied by the modeled problem. On human_practice_bound, people formulate and solve the pair, but the constraint–variable exchange, transposition, sign correspondence, and duality bounds hold as formal relations rather than as constituted practices. On institutional_origin, no authority creates a dual instance, though mathematical convention fixes equivalent standard forms. On vocab_travels, variable, constraint, bound, transpose, feasibility, and optimum have broader formal use, whereas primal, dual program, shadow price, sign-and-sense correspondence, weak duality, and strong duality are optimization-typed. On import_vs_recognize, a correctly derived partner can be recognized from the two programs themselves; calling two opposing formulations “dual” without the conversion rule imports a perspective not present in their structure.

The smallest reviewed portable skeleton is Linear Programming (LP): continuous decision variables, a linear objective, linear feasibility restrictions, and optimization over the resulting feasible region remain fully present in the derived program. That portable reach belongs to the Linear Programming Prime. Dual linear program remains in situ because it additionally requires a specified primal, objective reversal, constraint–variable exchange, matrix transposition, matched sign rules, and the bound/equality relations that collapse when the derivation is absent.

Its character: a structural-leaning formal specialization whose linear-program skeleton is portable while its paired derivation and duality guarantees remain optimization-specific.

Structural Core vs. Domain Accent¶

This decomposition shows why Dual Linear Program is a domain-specific abstraction rather than a Prime.

What is skeletal (could lift toward a cross-domain prime). A set of continuous decision variables is optimized by a linear scalar objective over a feasible region defined by linear restrictions. That carrier, operation, feasibility invariant, and optimality test are inherited by strict subsumption from Linear Programming (LP): a dual remains an LP before its paired derivation is considered. Remove the primal-derived correspondence and an ordinary linear program remains; remove the linear variables, objective, or constraints and both the parent structure and the dual program disappear.

What is domain-bound. Dual Linear Program adds a specified primal and a formal conversion: primal constraints become dual variables, primal variables become dual constraints, maximization and minimization exchange, A becomes A^T, and sign restrictions determine matching constraint senses. Weak duality turns feasible pairs into bound certificates, strong duality equates attained optimum values under its hypotheses, and dualizing again recovers the primal. Those pairing rules distinguish a true dual from an independently written LP with the same value, from a theorem about duality, and from an integer program for which the ordinary LP guarantee does not simply carry over.

Why this does not clear the prime bar. The complete primal-LP, constraint–variable exchange, transposition, sign-and-sense correspondence, and dual-bound signature does not recur literally in three unrelated domains such as stellar astronomy, institutional linguistics, and materials processing. Applications in farming, logistics, or finance are literal only because each is formulated as the same LP object; opposing perspectives elsewhere are merely analogical. Portable formal reach therefore belongs to Linear Programming (LP). Removing the paired-duality accent leaves LP, not Dual Linear Program. Conversely, retaining primal, dual, or shadow-price vocabulary while removing the linear optimization carrier and exact derivation leaves an interpretation or coincident formulation rather than the candidate-level abstraction.

This entry is a kind of Linear Programming (LP).

Instantiates — Linear Programming (LP) (Linear Programming (LP)). 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. Its coefficients, objective vector, right-hand side, constraint senses, and sign restrictions are supplied by the paired primal through constraint–variable exchange, transposition, objective reversal, and the sign-and-sense correspondence. Feasibility remains the admissibility invariant, and optimizing the linear objective over that region is still the operative rule; weak and strong duality add certificates about the paired optimum without replacing the LP operation. Stripping away the primal-derived correspondence leaves an ordinary linear program. Removing linear variables, objective, or constraints destroys the dual LP as well as the parent. This is therefore strict subsumption: the full LP signature survives, while the derivation from a specified primal is the child's distinguishing condition and collapse test.

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

Not to Be Confused With¶

Primal linear program. The primal is the specified optimization problem from which the dual is constructed; the two are paired roles rather than interchangeable labels. Tell: identify which formulation was given first and verify that the other exchanges its variables and constraints, transposes the coefficient matrix, and reverses the objective direction.
Weak and strong duality theorems. Duality theorems state bounding or optimal-value relations between a correctly formed primal–dual pair; they are consequences of the construction, not the derived program itself. Tell: distinguish a program with variables, constraints, and objective from a proposition asserting (c^T x \leq b^T y) or equality of optimal values under stated conditions.
Integer linear program. An integer linear program adds integrality restrictions to an optimization model and does not thereby become the ordinary continuous LP dual. Tell: inspect whether the variables range continuously under the primal–dual sign rules or are constrained to integer values.

References¶

[1] Tim Roughgarden, Linear Programming Duality, Stanford University CS261 lecture notes (accessed 2026-09-13). registry ↩

[2] Unverified encyclopedia synthesis; no authoritative source located for the claim as written. ↩

[3] Unverified encyclopedia synthesis; no authoritative source located for the claim as written. ↩

[4] Unverified encyclopedia synthesis; no authoritative source located for the claim as written. ↩

[5] Unverified encyclopedia synthesis; no authoritative source located for the claim as written. ↩

[6] Unverified encyclopedia synthesis; no authoritative source located for the claim as written. ↩

[7] Unverified encyclopedia synthesis; no authoritative source located for the claim as written. ↩

[8] Unverified encyclopedia synthesis; no authoritative source located for the claim as written. ↩

[9] Unverified encyclopedia synthesis; no authoritative source located for the claim as written. ↩

[10] Unverified encyclopedia synthesis; no authoritative source located for the claim as written. ↩

[11] Unverified encyclopedia synthesis; no authoritative source located for the claim as written. ↩

[12] Unverified encyclopedia synthesis; no authoritative source located for the claim as written. ↩