May 22 (10:00-11:00) room C.510
David Bartl (Silesian University in Opava, Czechia)
Farkas’ lemma and linear programming in the infinite case
We consider the linear programming problem in the setting of a general vector space over a linearly ordered (commutative or skew) field. The feasible set is constrained by a system of linear inequalities and the objective function is a linear mapping into a linearly ordered vector space over the same linearly ordered field. In this algebraic setting, we recall known results: Farkas’ Lemma, Gale’s Theorem of the alternative, and the Duality Theorem for linear programming with a finite number of linear constraints. Nonetheless, our purpose is to study the infinite case; that is, infinite systems of linear inequalities in an infinite-dimensional space, by using a purely algebraic approach. We formulate and present a new infinite variant of Farkas’ Lemma along with an infinite variant of Gale’s Theorem of the alternative. Moreover, we formulate the problem of an infinite linear programming, its dual problem, and the Duality Theorem for the problems. Finally, we consider an application to the problems of semi-infinite linear programming and discuss balancedness condition for the non-emptiness of the core of a cooperative TU-game with an infinite number of players.