ABSTRACT

This research work focused on solving Linear Programming Problems with the objective of identifying and reducing the computational complexities or complications involved in solvling these problems. In this work, we presented two algorithms; the Standard Simplex method and a newer solution algorithm called Push and Push algorithm. The Simplex method has been one of the oldest and the best methods for efficiently solving Linear Programming (LP) problems until recently. In this work, a manual and computerized comparison for the Simplex algorithm and the Push and Pull algorithm has been achieved. We presented an automated software for the Simplex and the Push and Pull algorithms for solving a wide range of Linear Programming problems, in which the computational comparison of the two methods was carried out. The software was developed using Visual Basic 6.0 on a Visual Studio .NET Framwork 3.5, and on a Windows Vista operating system. This research work was carried out using theoretical methodology. The software was designed using an algorithm called, Algorithm Implementation Modules. In the course of this work, we found out that for LP Problems with ≤ constraints (Maximization cases), the computational complexity slightly differed, though the Push and Pull method still exhibits less number of computations, while for LP Problems with ³ constraints (Minimization cases), the computational complexity greatly differed; with the Push and Pull method having much lesser number of computations. We therefore concluded that the Push and Pull method is a preferable alternative to the Simplex method in solving LP problems.

ix

CHAPTER ONE

INTRODUCTION

1.1         BACKGROUND TO THE STUDY

The world of computing is rapidly gaining priority in almost every area of human endeavour that involves the use of data that can be converted into digital form for processing. The various branches of computer technology where developed to meet the needs and requirements of other fields of study such as; mathematics, engineering, business, education, medicine etc, with mathematics has its closest field. Before the introduction of computer, many concepts, laws, precepts, procedures and methods in real life situations have been converted into mathematical models to solve the problems that come along with them. The development and evolution of computer was to tackle complicated, solvable mathematical problems with great speed and accuracy. In this work, we looked into Linear Programming, a branch of operation research in the field of mathematics. We are interested in this topic due to its importance to the fields of business and economy which are bases of national growth and development. Linear Programming has become one of the most applied basic forms of optimization for desirable, expected, realistic and deterministic values which may be an input to or an output from activities or transaction of profitable field labours, especially in commercial field. Due to the complicated nature of solving and determining accurate results from linear programming problems, various methods and algorithms have been developed, and various computer application programs have been designed and developed using one or more of these methods and algorithms to efficiently solve such problems with reliable outcomes and speed.

Linear programming is one of the most basic forms of optimization. Its theory and algorithms can not only be applied to linear optimization problems but also to relaxations of nonlinear problems and branch-and-bound methods for mixed-integer and global optimization problems. Frederick et al (2001) stated that the development of linear programming has been ranked among the most important scientific advances of the mid-20th century, and we must agree with this assessment. Its impact since just 1950 has been extraordinary. Today, it is a standard tool that has saved thousands to millions of dollars for most companies or businesses of even moderate size in the various industrialized countries of the world; and its use in other sectors of society has been spreading rapidly. A major proportion of all scientific computation on computers is devoted to the use of linear programming. The Simplex method is one of the oldest, most widely used, and arguably a remarkable efficient solution procedure for solving linear programming.

An active research area of linear programming is to construct initial Simplex tableau, and to improve its pivoting selection strategies efficiently, Vieira and Lins (2005). In this study, we

1

present a new approach to the problem of initialization and pivoting rules: the algorithm is free from any artificial variables and artificial constraints, known as the big-M methods. By supplying the Simplex method without using any large numbers, therefore the result is computationally stable and provides a better initial basis that reduces the number of pivoting iterations efficiency.

This thesis discusses a new general-purpose solution algorithm, called Push-and-Pull, which obviates the use of artificial variables. The algorithm consists of preliminaries for setting up the initialization followed by two main phases. The Push Phase develops a basic variable set (BVS) which may or may not be feasible. Unlike simplex and dual simplex, this approach starts with an incomplete BVS initially, and then variables are brought into the basis one by one. If the BVS is complete, but the optimality condition is not satisfied, then Push Phase pushes until this condition is satisfied, using the rules similar to the ordinary simplex. Since the proposed strategic solution process pushes towards an optimal solution, it may generate an infeasible BVS. The Pull Phase pulls the solution back to feasibility using pivoting rules similar to the dual simplex method. All phases use the usual Gauss pivoting row operation and it is shown to terminate successfully or indicates unboundedness or infeasibility of the problem. A computer application software which is capable of executing the Push-and-Pull and simplex algorithms simultaneously, and also displaying the computational complexity of each algorithm at the end of each execution has been presented for this research.

According to Frederick and Gerald (2001), “Linear programming uses a mathematical model to describe the problem of concern. The adjective linear means that all the mathematical functions in this model are required to be linear functions. The word programming does not refer here to computer programming; rather, it is essentially a synonym for planning. Thus, linear programming involves the planning of activities to obtain an optimal result, i.e., a result that reaches the specified goal best (according to the mathematical model) among all feasible alternatives”.

According to Ikpotokin (2012), Linear programming (LP) is essentially a method of determining an optimum program of the candidates or inter-dependent activities which are competing for limited resources under assumptions of linearity. He went further to explain that Linear programming is a type of solution method in Operation Research for solving problems in order to obtain the best or optimal solution for the problem under various considerations.

Over the years, many authors have presented various application software that are capable of solving linear programming problems which include; Microsoft Excel solver, Lindo, Lingo, MATLAB, LiPS, TORA, GLPK, LP_Solve, CLP, SCIP, Cplex, Xpress, Gurobi, etc. These LP solvers although accurate, but some are strenuous in inputting data items especially for large variable and constraints, and all are also designed to specifically input linear programming

2

problem data and give out only desired output. This will not be the case for the proposed or expected application software that will be presented in this research.

Linear programming is considerably a field of optimization for several reasons. Many practical problems in operations research can be expressed as linear programming problems. Certain special cases of linear programming, such as network flow problems and multi-commodity flow problems are considered important enough to have generated much research on specialized algorithms for their solution. A number of algorithms for other types of optimization problems work by solving LP problems as sub-problems. Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as duality, decomposition, and the importance of convexity and its generalizations. Likewise, linear programming is heavily used in planning, production, transportation, technology and other issues. Although the modern management issues are ever-changing, most companies would like to maximize profits or minimize costs with limited resources. Therefore, many issues can be characterized as linear programming problems.

A typical example would be taking the limitations of materials and labor, and then determining the "best" production levels for maximal profits under those conditions.

In "real life", linear programming is part of a very important area of mathematics called "optimization techniques". This field of study (or at least the applied results of it) is used every day in organizations and allocation of resources. These "real life" systems can have dozens, hundreds or more variables. These problems are converted into mathematical model such that they meet some conditions to become a linear program (LP). The conditions for mathematical model to become a linear program include;

a.       All variables must be continuous. This is to say that all variables may take up fractional values.

b.      There should be a single objective to be maximized or minimized; otherwise, we have a multi-objective programming problem.

c.       The objectives and constraints must be linear; this implies that any term is either a constant or a constant multiple of an unknown.

1.1.1 STANDARD FORMS AND EXPRESSIONS OF LINEAR PROGRAMMING PROBLEMS

Standard form simply means is the usual and most intuitive form of description; in this case, describing a linear programming problem. A linear programming problem consists of the following three parts:

3

a.       A linear function to be maximized or minimized

f (x1, x2, …., xn) =                      n

∑         cj xj

j = 1                                            ………………. (1.1)

b.       Problem constraints

n

∑           aij xij  ≤ bi