Geodesic
A New and Constructive Proof of Two Basic Results of Linear Programming
Yugoslav journal of operations research, Tome 11 (2001) no. 1, p. 15 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

In this paper a new, elementary and constructive proof of Farkas' lemma is given. The basic idea of the proof is extended to derive the strong duality theorem of linear programming. Zhang's algorithms used, in the proofs of Farkas' lemma and the strong duality theorem, are criss-cross type algorithms, but the pivot rules give more flexibility than the original criss-cross rule of T. Terlaky. The proof of the finiteness of the second algorithm is technically more complicated than that for the original criss-cross algorithm. Both of the algorithms defined in this paper have all the nice theoretical characteristics of the criss-cross method, i.e. they solve the linear programming problem in one phase; they can be initialized with any, not necessarily primal feasible basis, bases generated during the solution of the problem, are not necessarily primal or dual feasible.
Classification : 90C05
Keywords: Farkas lemma, strong duality theorem, criss-cross type pivot rules. 
@article{YJOR_2001_11_1_a1,
     author = {Tibor Ill\`es and Katalin M\`esz\^eros},
     title = {A {New} and {Constructive} {Proof} of {Two} {Basic} {Results} of {Linear} {Programming}},
     journal = {Yugoslav journal of operations research},
     pages = {15 },
     publisher = {mathdoc},
     volume = {11},
     number = {1},
     year = {2001},
     zbl = {1075.90537},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2001_11_1_a1/}
}
TY  - JOUR
AU  - Tibor Illès
AU  - Katalin Mèszêros
TI  - A New and Constructive Proof of Two Basic Results of Linear Programming
JO  - Yugoslav journal of operations research
PY  - 2001
SP  - 15 
VL  - 11
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/YJOR_2001_11_1_a1/
LA  - en
ID  - YJOR_2001_11_1_a1
ER  - 
%0 Journal Article
%A Tibor Illès
%A Katalin Mèszêros
%T A New and Constructive Proof of Two Basic Results of Linear Programming
%J Yugoslav journal of operations research
%D 2001
%P 15 
%V 11
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/YJOR_2001_11_1_a1/
%G en
%F YJOR_2001_11_1_a1
Tibor Illès; Katalin Mèszêros. A New and Constructive Proof of Two Basic Results of Linear Programming. Yugoslav journal of operations research, Tome 11 (2001) no. 1, p. 15 . http://geodesic.mathdoc.fr/item/YJOR_2001_11_1_a1/