Title

Comments on two direct methods in linear programming.

Date of Award

2004

Degree Type

Thesis

Degree Name

M.Sc.

Department

Mathematics and Statistics

First Advisor

Caron, R.

Keywords

Operations Research.

Rights

CC BY-NC-ND 4.0

Abstract

In this thesis we will analyse the two algorithms for linear programming (LP) presented by Stojkovic and Stanimirovic [15] in 2001. One of the methods, which the authors call the "minimal angles method" (MA method) was designed to determine either an optimal extreme point or an extreme point adjacent to an optimal extreme point. Unfortunately, the theorem upon which the MA method is based is not valid. This was shown by Li [10] in 2004 with two counterexamples. We will show that one of the counterexamples itself is not valid, and will provide an alternate, valid counterexample. We will also provide a careful study of the MA method to see if there is a class of LP, where it can be applied. This leads to a method we call the "active cone method" which can be used for 2 variable LPs. The second method of Stojkovic and Stanimirovic [15] in 2001 uses an analogy to Game Theory to devise a process, based on "dominated strategies", to simplify a certain class of LP. We extend this idea and present an iterative method which provides further reduction to a large class of LPs.Dept. of Mathematics and Statistics. Paper copy at Leddy Library: Theses & Major Papers - Basement, West Bldg. / Call Number: Thesis2004 .W365. Source: Masters Abstracts International, Volume: 43-03, page: 0987. Advisers: R. J. Caron; T. Traynor. Thesis (M.Sc.)--University of Windsor (Canada), 2004.