Duality of Linear Programming

RenĂ© Thiemann đŸ“§

February 3, 2022

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

We formalize the weak and strong duality theorems of linear programming. For the strong duality theorem we provide three sufficient preconditions: both the primal problem and the dual problem are satisfiable, the primal problem is satisfiable and bounded, or the dual problem is satisfiable and bounded. The proofs are based on an existing formalization of Farkas' Lemma.

License

BSD License

Topics

Session LP_Duality

Depends on

Cite

× 
@article{LP_Duality-AFP,
  author  = {René Thiemann},
  title   = {Duality of Linear Programming},
  journal = {Archive of Formal Proofs},
  month   = {February},
  year    = {2022},
  note    = {\url{https://isa-afp.org/entries/LP_Duality.html},
             Formal proof development},
  ISSN    = {2150-914x},
}
Download

Download

× Download latest

Older releases: