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

Tibor Illés, Katalin Mészáros

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)15-30
Number of pages16
JournalYUGOSLAV JOURNAL OF OPERATIONS RESEARCH
Volume11
Issue number1
Publication statusPublished - 1 Jan 2001
Externally publishedYes

Keywords

  • farkas lemma
  • strong duality theorem
  • criss-cross type pivot rules
  • linear programming

Fingerprint Dive into the research topics of 'A new and constructive proof of two basic results of linear programming'. Together they form a unique fingerprint.

Cite this