Farkas' Lemma, other theorems of the alternative, and linear programming in infinite-dimensional spaces: a purely linear-algebraic approach

Abstract

We briefly consider several formulations of Farkas' Lemma first. Then we assume the setting of two vector spaces, one of them being linearly ordered, over a linearly ordered field till the end of this article. In this setting, we state a generalized version of Farkas' Lemma and prove it in a purely linear-algebraic way. Afterwards, we present Theorems of Motzkin, Tucker, Carver, Dax, and some other theorems of the alternative that characterize consistency of a finite system of linear inequalities. We also mention the Key Theorem, which is a related result. Finally, we use Farkas' Lemma to prove the Duality Theorem for linear programming (with a finite number of linear constraints). The Duality Theorem that is proved here covers, among others, linear programming in a real vector space of finite or infinite dimension and lexicographic linear programming.

Keywords:

• Systems of linear inequalities
• Linear programming
• Theorems of the alternative
• Duality Theorem
• Linearly ordered vector spaces

Keywords:

• AMS Subject Classifications:
• 15A39
• 90C05
• 90C36
• 90C48
• 06F20
• 06F25

Acknowledgements

The author is grateful for a certain and very incidental meeting with Mr. Pavel Gatnar. The subsequent discussion about Theorems 1.1, 1.2 and 1.3 gave rise to the main idea of the proof of Farkas' Lemma 1.4 and, subsequently, to that of Farkas' Lemma 4.1. This article was written with partial support of the grant GA ČR 201/04/0381.