 The Complete Research Material is averagely 52 pages long and it is in Ms Word Format, it has 15 Chapters.
 Major Attributes are Abstract, All Chapters, Figures, Appendix, References.
 Study Level: MTech, MSc or PhD.
 Full Access Fee: ₦8,000
Get the complete project »
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 branchandbound methods for mixedinteger 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 mid20th 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 bigM 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 generalpurpose solution algorithm, called PushandPull, 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 PushandPull 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 interdependent 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 multicommodity 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 subproblems. 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 everchanging, 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 multiobjective 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
Share a Comment
You can find more project topics easily, just search

SIMILAR COMPUTER SCIENCE FINAL YEAR PROJECT RESEARCH TOPICS

1. DESIGN AND IMPLEMENTATION OF A COMPUTERISED TRAFFIC OFFENCE DOCUMENTATION SYSTEM. (CASE STUDY OF FEDERAL ROAD SAFETY COMMISSIONER, ENUGU)
» CHAPTER ONE INTRODUCTION BACKGROUND OF THE STUDY Around the world road traffic injuries are a major public health challenges that requires concerted e...Continue Reading »42 pages  584 hits  Source: COMPUTER SCIENCE

2. DESIGN AND IMPLEMENTATION OF AN ONLINE JOURNAL MANAGEMENT SYSTEM (A CASE STUDY OF SOKOTO INTERNATIONAL JOURNAL OF COUNSELLING PSYCHOLOGY).
» ABSTRACT This project research titled “Design and Implementation of an Online Journal Management System which is a case study of Sokoto Internationa...Continue Reading »68 pages  195 hits  Source: COMPUTER SCIENCE

3. DESIGN AND IMPLEMENTATION OF CAR RENTAL SYSTEM
» CHAPTER ONE INTRODUCTION A car rental or car hire agency is a company that rents automobiles for short period of time for a fee whether in a few hours...Continue Reading »41 pages  177 hits  Source: COMPUTER SCIENCE

4. DESIGN AND IMPLEMENTATION OF A COMPUTERIZED DOCUMENTATION SYSTEM OF COURT PROCEEDINGS (A Case Study Of Federal High Court Enugu State)
» ABSTRACTAs the complexity and degress of crimes widen, system using new technology will have to be utilized to aid lawyers etc to fight this tends.Jus...Continue Reading »65 pages  0 hits  Source: COMPUTER SCIENCE

5. SOFTWARE PIRACY IN NIGERIA
» CHAPTER ONE 1.0 INTRODUCTION 1.1 BACKGROUND OF STUDY The rate of internet fraud and software piracy has increased overtime in Nigeria. The federal gov...Continue Reading »66 pages  147 hits  Source: COMPUTER SCIENCE

6. DESIGN AND IMPLEMENTATION OF STUDENT RATING OF TEACHER EFFECTIVENESS SYSTEM
» CHAPTER ONE1.0 INTRODUCTION Teacher rating is one of the topics which require pertinent attention by our education regulatory system. As teachers are ...Continue Reading »54 pages  254 hits  Source: COMPUTER SCIENCE

7. COMPUTERIZATION OF PHONE BILLING SYSTEM
» CHAPTER ONE 1.0 INTRODUCTION In some years back many operation were carried out manually. The method used to prepare bills was manual which possibly g...Continue Reading »24 pages  230 hits  Source: COMPUTER SCIENCE

8. DESIGN AND IMPLEMENTATION OF AN ONLINE MOTOR VEHICLE LICENSING SYSTEM
» ABSTRACT Motor vehicle administration is a composite process and revolves around the management and the control of motor licensing. Vehicle licensing ...Continue Reading »50 pages  272 hits  Source: COMPUTER SCIENCE

9. DESIGN AND INPLEMENTATION OF INTERNET CAFÉ BILLING SYSTEM
» CHAPTER ONE 1.1 INTRODUCTION The internet stands for international network; it is a huge web of network system connecting million of people all over t...Continue Reading »52 pages  513 hits  Source: COMPUTER SCIENCE

10. DESIGN AND IMPLEMENTATION OF ENCRYPTED DATA BASE SYSTEM
» CHAPTER ONE 1.0 INTRODUCTION In the past, security was simply a matter of locking the door or storing files in a locked filing cabinet or safe. Today,...Continue Reading »70 pages  226 hits  Source: COMPUTER SCIENCE