Linear Programming and Extensions¶
Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
Cited by¶
7 citations across 7 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Allocation
- This separation — between the universal structural skeleton and the domain-specific criterion that fills it — is what makes allocation portable across substrates that share no institutions, no agents, and no goals, an abstraction Dantzig (1963) pushes furthest in the linear-programming treatment of the transportation problem.
This sourceConsolidated treatment of primal-dual LP including the transportation problem and the simplex method; pushes the abstraction of routing limited supply across sinks furthest. SUPPORTS the claim that Dantzig pushes the allocation abstraction furthest in the LP treatment of the transportation problem.
- This separation — between the universal structural skeleton and the domain-specific criterion that fills it — is what makes allocation portable across substrates that share no institutions, no agents, and no goals, an abstraction Dantzig (1963) pushes furthest in the linear-programming treatment of the transportation problem.
- Duality
- Linear Programming (LP)
- Minimax Strategy
- The value is computable by linear programming: Player 1's optimal mixed strategy solves \(\max v\) subject to \(x^\top A \geq v \mathbf{1}\), \(x \geq 0\), \(\sum x_i = 1\).
This sourceEstablishes the linear-programming formulation and LP duality through which finite zero-sum game values (the maximin optimal mixed strategy) are computed.
- The value is computable by linear programming: Player 1's optimal mixed strategy solves \(\max v\) subject to \(x^\top A \geq v \mathbf{1}\), \(x \geq 0\), \(\sum x_i = 1\).
- Network Flow Models
- Sensitivity Analysis (in Operations Research)
Domain-specific¶
- Feasible Region
- The fundamental theorem of linear programming states that if an optimal solution exists, it is attained at a vertex of this polytope, which is the structural fact underlying the simplex method: optimisation over a convex polytope reduces to checking finitely many vertices
This sourceDantzig's statement of the fundamental theorem of linear programming, that if an optimal feasible solution exists a basic feasible solution exists.
Supported in partVerified against the work's full text
“feasible [solution] exists, (ii) if an optimal feasible [solution] exists then a basic feasible [solution] exists”
- The fundamental theorem of linear programming states that if an optimal solution exists, it is attained at a vertex of this polytope, which is the structural fact underlying the simplex method: optimisation over a convex polytope reduces to checking finitely many vertices
Verification¶
Does it exist? Not checked yet. This entry carries no identifier to resolve. It was extracted from the citation as written in the article, normalized, and deduplicated against the rest of the registry.
Does it back the claim? Read against the text for 1 of 7 citations: 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:4b014610f045 · see in the full table