### Abstract

Original language | English |
---|---|

Pages (from-to) | 15-30 |

Number of pages | 16 |

Journal | YUGOSLAV JOURNAL OF OPERATIONS RESEARCH |

Volume | 11 |

Issue number | 1 |

Publication status | Published - 1 Jan 2001 |

Externally published | Yes |

### Fingerprint

### Keywords

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

### Cite this

*YUGOSLAV JOURNAL OF OPERATIONS RESEARCH*,

*11*(1), 15-30.

}

*YUGOSLAV JOURNAL OF OPERATIONS RESEARCH*, vol. 11, no. 1, pp. 15-30.

**A new and constructive proof of two basic results of linear programming.** / Illés, Tibor; Mészáros, Katalin.

Research output: Contribution to journal › Article

TY - JOUR

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

AU - Illés, Tibor

AU - Mészáros, Katalin

PY - 2001/1/1

Y1 - 2001/1/1

N2 - 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.

AB - 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.

KW - farkas lemma

KW - strong duality theorem

KW - criss-cross type pivot rules

KW - linear programming

UR - http://yujor.fon.bg.ac.rs/index.php/journal/article/view/522

M3 - Article

VL - 11

SP - 15

EP - 30

JO - YUGOSLAV JOURNAL OF OPERATIONS RESEARCH

JF - YUGOSLAV JOURNAL OF OPERATIONS RESEARCH

SN - 0354-0243

IS - 1

ER -