The development of algorithms in mathematical programming

Abstract

In this thesis some problems in mathematical programming have been studied. Chapter 1 contains a brief review of the problems studied and the motivation for choosing these problems for further investigation. The development of two algorithms for finding all the vertices of a convex polyhedron and their applications are reported in Chapter 2. The linear complementary problem is studied in Chapter 3 and an algorithm to solve this problem is outlined. Chapter 4 contains a description of the plant location problem (uncapacited). This problem has been studied in some depth and an algorithm to solve this problem is presented. By using the Chinese representation of integers a new algorithm has been developed for transforming a nonsingular integer matrix into its Smith Normal Form; this work is discussed in Chapter 5. A hybrid algorithm involving the gradient method and the simplex method has also been developed to solve the linear programming problem. Chapter 6 contains a description of this method. The computer programs written in FORTRAN IV for these algorithms are set out in Appendices Rl to R5. A report on study of the group theory and its application in mathematical programming is presented as supplementary material. The algorithms in Chapter 2 are new. Part one of Chapter 3 is a collection of published material on the solution of the linear complementary problem; however the algorithm in Part two of this Chapter is original. The formulation of the plant location problem (uncapacited) together with some simplifications are claimed to be original. The use of Chinese representation of integers to transform an integer matrix into its Smith Normal Form is a new technique. The algorithm in Chapter 6 illustrates a new approach to solve the linear programming problem by a mixture of gradient and simplex method.