Farkas’ lemma is a celebrated result on the solutions of systems of linear inequalities, which finds application pervasively in mathematics and computer science. In this work we show how to formulate and prove Farkas’ lemma in diagrammatic polyhedral algebra, a sound and complete graphical calculus for polyhedra. Furthermore, we show how linear programs can be modeled within the calculus and how some famous duality results can be proved.
From Farkas’ lemma to linear programming: An exercise in diagrammatic algebra / Bonchi F.; Di Giorgio A.; Zanasi F.. - ELETTRONICO. - 211:(2021), pp. 9.1-9.19. (Intervento presentato al convegno 9th Conference on Algebra and Coalgebra in Computer Science, CALCO 2021 tenutosi a University of Salzburg, aut nel 2021) [10.4230/LIPIcs.CALCO.2021.9].
From Farkas’ lemma to linear programming: An exercise in diagrammatic algebra
Bonchi F.;Zanasi F.
2021
Abstract
Farkas’ lemma is a celebrated result on the solutions of systems of linear inequalities, which finds application pervasively in mathematics and computer science. In this work we show how to formulate and prove Farkas’ lemma in diagrammatic polyhedral algebra, a sound and complete graphical calculus for polyhedra. Furthermore, we show how linear programs can be modeled within the calculus and how some famous duality results can be proved.| File | Dimensione | Formato | |
|---|---|---|---|
|
LIPIcs-CALCO-2021-9.pdf
accesso aperto
Tipo:
Versione (PDF) editoriale
Licenza:
Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione
902.56 kB
Formato
Adobe PDF
|
902.56 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
