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

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61988987%3A17310%2F07%3AA08009W6" target="_blank" >RIV/61988987:17310/07:A08009W6 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

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

Original language description

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 paper. In this setting, we state a generalised version of Farkas' Lemma and prove it in a purely linear-algebraic way. Afterwards, we present Theorems of Motzkin, Tucker, Carver, Haar, Dax, and some other theorems of the alternative that characterise 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 as well as, e.g., lexicographic linear programming.

Czech name

Farkasovo lemma, další věty o alternativě a lineární programování v nekonečněrozměnrých prostorech: čistý lineárně algebraický přístup

Czech description

Nejprve stručně připomínáme několik formulací Farkasova lemmatu. Ve zbytku článku již uvažujeme kontext dvou vektorových prostorů, z nichž jeden je lineárně uspořádán, nad společným lineárně uspořádaným tělesem. V tomto kontextu formulujeme zobecněnou verzi Farkasova lemmatu a dokazujeme ji čistě lineárně algebraickým způsobem. Pak uvádíme větu Motzkinovu, Tuckerovu, Carverovu, Haarovu, Daxovu a některé další věty o alternativě, které charakterizují řešitelnost konečné soustavy lineárních nerovnic. Zmiňujeme také tzv. klíčovou větu, která je souvisejícím výsledkem. Nakonec používáme Farkasovo lemma, abychom dokázali princip duality pro úlohy lineárního programování (s konečným počtem lineárních omezení). Princip duality, který je zde dokázán, pokrývá mj. lineární programování v reálném vektorovém prostoru konečné nebo nekonečné dimenze, jakož i, například, lexikografické lineární programování.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BB - Applied statistics, operational research

OECD FORD branch

—

Project

—

Continuities

V - Vyzkumna aktivita podporovana z jinych verejnych zdroju

Publication year

2007

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Linear and Multiliear Algebra

ISSN

0308-1087

e-ISSN

—

Volume of the periodical

55

Issue of the periodical within the volume

7

Country of publishing house

GB - UNITED KINGDOM

Number of pages

27

Pages from-to

327-353

UT code for WoS article

—

EID of the result in the Scopus database

—