A new and constructive proof of two basic results of linear programming

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.