TABLE OF CONTENTS
TITLE PAGE i
1.1.2 STANDARD FORMS AND EXPRESSIONS OF LINEAR PROGRAMMING PROBLEMS 3
1.2 STATEMENT OF RESEARCH PROBLEM 5
1.4 JUSTIFICATION OF THE STUDY 5
1.7 DEFINITIONS AND TERMINOLOGIES IN LINEAR PROGRAMMING 7
2.1 OVERVIEW OF LINEAR PROGRAMMING 9
2.3 ALGORITHMS USED IN DEVELOPING LP APPLICATION PROGRAMS 11
2.4 LP APPLICATION SOFTWARE DEVELOPMENT 13
3.2 THEORETICAL METHODOLOGY 15
3.3 ANALYSIS OF EXISTING METHODS FOR MANUALLY SOLVING LINEAR PROGRAMMING PROBLEMS 16
3.4 PROBLEMS OF EXISTING SYSTEMS 17
3.5 ANALYSIS OF THE PROPOSED SYSTEM ALGORITHM 18
3.7 ADVANDTAGES OF THE PROPOSED ALGORITHM AND SOFTWARE 27
4.1 MANUAL IMPLEMENTATION WITH NUMERICAL EXAMPLE 28
4.2 APPLICATION PROGRAM USER INTERFACE 29
4.2 COMPUTER IMPLEMENTATION OF NUMERICAL EXAMPLES 32
4.4 FINDINGS OF THIS RESEARCH 33
4.5 CONTRIBUTION TO KNOWLEDGE 34
CONCLUSION AND RECOMMENDATIONS 35
APPENDIX I: APPLICATION INTERFACES
APPENDIX II: MANUAL IMPLEMENTATION AND RESULT OF NUMERICAL EXAMPLES
APPENDIX III: COMPUTER IMPLEMENTATION AND RESULT OF NUMERICAL EXAMPLES
APPENDIX IV: PROGRAM SOURCE CODES
LIST OF TABLES
Table 1. Previous Applications Software design for solving Linear Programming Problems
LIST OF FIGURES
Figure 3.1 Flowchart showing the algorithmic strategic process
Figure 3.2 Flowchart showing the algorithmic strategic process of the Simplex method.
Figure 3.3 Software Architecture
Figure 4.1: The Single Problem Menu
Figure 4.2: Definition Tab
Figure 4.3: Result Summary Tab
Figure 4.4: Result Details Tab
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.
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 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 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;
- All variables must be continuous. This is to say that all variables may take up fractional values.
- There should be a single objective to be maximized or minimized; otherwise, we have a multi-objective programming problem.
- 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:
| n |
| j = 1 |
| cj xj |
- Alinear function to be maximized or minimized
f (x1, x2, …., xn) =
………………. (1.1)
- Problem constraints
| n |
| j = 1 |
| aij xij ≤ bi |
….…………… (1.2)
- Non-negative variables
xj ≥ 0, j = 1, 2, … , n
The problem is usually expressed in matrix form, and then becomes:
Max{cTx | Ax ≤ b, ˅ x ³ 0} ………………. (1.3)
Other forms, such as minimization problems, problems with constraints on alternative forms, as well as problems involving negative variables can always be rewritten into an equivalent problem in standard form.
1.1.2 Further Illustration
Suppose that a farmer has a piece of farm land, say L km2, to plant either wheat or barley or some combination of the two. The farmer has a limited amount of fertilizer, F kilograms, and insecticide, P kilograms. Every square kilometer of wheat requires F1 kilograms of fertilizer, and P1 kilograms of insecticide, while every square kilometer of barley requires F2 kilograms of fertilizer, and P2 kilograms of insecticide. Let S1 be the selling price of wheat per square kilometer, and S2 be the selling price of barley. If we denote the area of land planted with wheat and barley by x1 and x2 respectively, then profit can be maximized by choosing optimal values for x1 and x2. This problem can be expressed with the following linear programming problem in the standard form:
| Maximize: | (maximize the revenue—revenue is the “objective function”) | |
| Subject to: |
x1 + x2 ≤ L |
(limit on total area) |
| F1 . x1 + F2 . x2 ≤ F | (limit on fertilizer) | |
| P1 . x1 + P2 . x2 ≤ P2 | (limit on insecticide) | |
| x1 ≥ 0, x2 ≥ 0 | (cannot plant a negative area). | |
Which in matrix form becomes:
Maximize:
subject to:
1.2 STATEMENT OF RESEARCH PROBLEM
Since the creation of the Simplex solution algorithm for Linear Programming (LP) problems in 1947 by Dantzig, this topic has enjoyed a considerable and growing interest by researchers and students of many fields. However, experience shows there are still computational difficulties in solving LP problems in which some constraints are in (≥) form with the right-hand side (RHS) non-negative, or in ( = ) form.
One version of the simplex known as the two-phase method introduces an artificial objective function, which is the sum of artificial variables, while the other version adds the penalty terms which is the sum of artificial variables with very large positive coefficients. The latter approach is known as the Big-M method.
The simplex algorithm requires artificial variables for solving linear programs, which lack primal feasibility at the origin point and complicates computational procedures especially for beginners.
Therefore, an active research area of linear programming is on how to construct simple and less complex initial tableaus, to improve its pivoting selection strategies efficiently and reduced computation steps Vieira and Lins (2005).
1.3 JUSTIFICATION OF THE STUDY
It is beyond doubt from theoretical and practical experience that solving Linear Programming problems involve series of sophisticated steps and procedures that require a lot of time, focus and diligence to achieve the desired result manually. Sometimes the result may not still be correct and/or accurate.
Many researchers have proposed different algorithms to identify the redundancies and have removed them to get a reduced model for linear programming. In 1965, Zionts et al (1983), suggested some improvements upon the implementation of Boot method, but not to the point where it achieved practical value. In addition, a number of other methods were developed that dealt with redundancy, among which the geometric vertex enumeration method is the most well known. In geometric vertex enumeration method, the essential characteristic is the establishment of a number of situations in which redundancy can be recognized immediately without further computations.
According to Arsham et al, (2003), “LP problems, which lack feasibility at the origin point, have raised difficulties since the beginning of LP. For such problems, the ordinary Simplex algorithm requires additional variables (i.e., artificial variables) along with large penalty terms in the objective function. Unfortunately, adding these extraneous variables creates computational instability and increases the computational complexity”.
In the aspect of computerization, Frederick and Gerald (2001), stated that; a large amount of computation is usually required to deal most effectively with the complex problems typically considered by Operations Research (OR). Doing this by hand would often be out of the question. Therefore, the development of electronic digital computers, with their ability to perform arithmetic calculations thousands or even millions of times faster than a human being can and was a tremendous boon to OR.
Paparrizos (1990), introduced an algorithm which avoids the use of artificial variables through a tedious evaluation of a series of extra objective functions besides the original objective function. The algorithm checks both the optimality and feasibility conditions after completion of iterations. He indicates ’’We have not been able to construct such rules’’, for entering and exiting variables to and from the basic variable set. The pivot and probe type algorithm suggested in Sethi and Thompson (1984), is much complicated. Spivey and Thrall (1970) also made an attempt to come up with an algorithm; however it is not for general purpose. Arsham (2003), introduced an artificial-free algorithm for general linear programs and the classical network problems.
According to Keil and Jansson (2006), recent research shows that against intuition, bad condition numbers frequently occur in linear programming. To take this into account, reliability is required. Here we investigate rigorous results obtained by verification methods. We will examine different current techniques and software tools for varied linear programming and compare numerical results for existing implementations. Rounding errors inevitably introduced by floating point arithmetic can well deteriorate the result of numerical computations. This is especially true for problems being ill-posed, which 71% of the linear programs in the Netlib collection are, as observed by Ordonez and Freund (2003).
Moreover, classroom experience shows that some students, particularly non-mathematical majors, have difficulty in understanding the intuitive notion behind the computational procedure in performing linear programming operations (especially in minimization cases) (Arsham, 1997).
As information technology has undoubtedly become a more efficient, effective and an accurate means of carrying out computational jobs, an application program will be presented for this purpose which will accurately and with consistent output, solve linear programming problems with great speed compared to manual/traditional application. This will also show the computational differences between Push and Pull and Simplex method at the end of every execution of a problem.
1.4 SCOPE OF THE STUDY
This research focused on the design and implementation of an application software that will solve LP Problems using the Push and Pull and Simplex methods. Further, computational complexity of Push and Pull algorithm and Simplex methods for solving linear programming problems has been developed.
1.5 AIM OF THE STUDY
The overall aim of this study is to design, automated software for solving LP Problems using the Push and Pull algorithm and the Simplex algorithm, while comparing the computational complexity between the two algorithms.
1.6 OBJECIVES OF THE STUDY
The specific objectives of this research/study are to:
- design a computer application program to implement the Push and Pull algorithm and its computational comparison with Simplex method in solving linear programming problems.
- show that Push and Pull method, although a new and rarely used algorithm can be used as a preferable alternative to the Simplex method in solving linear programming problems in terms of reduced the computational steps and complexity of the Simplex tableau (especially in minimization cases).
- compare the computation steps involved in using Push and Pull method and Simplex method to solve linear programming problem.
1.7 DEFINITIONS AND TERMINOLOGIES IN LINEAR PROGRAMMING
Constraint: A constraint is a condition that must be satisfied by a solution.
Hyperplanes: The hyperplanes described by the equalities ai.x = bi.
Feasible set: A feasible set is the set of points that satisfy all the constraints.
Inequality form: Inequality form is the formulation of the linear programming problem where all the constraints are weak inequalities ai.x ≤ bi.
Infeasible problem: An infeasible problem is a problem with an empty feasible set.
Linear Equation: A Linear equation is a mathematical expression that has an equal sign and linear expressions.
Linear Expression: A Linear expression is a mathematical statement that performs functions of addition, subtraction, multiplication and division.
Linear Programming: Linear Programming is a method of solving problems associated to some situation with quantifiable entities (input and output values) by converting those values into a mathematical model that satisfies the requirement of a linear program in order to obtain the best value/outcome from the situation.
Nondegenerate problem: A non-degenerate problem is a problem where at each vertex precisely d constraints are tight.
Pivot rule: Pivot rule is the rule by which a neighboring vertex is chosen.
Polytope: A polytope is a geometric object with flat sides, and may exist in any general number of dimensions n as an n-dimensional polytope of n-polytope.
Random-Edge simplex algorithm: This is a randomized variant of the Simplex method where the neighboring vertex is chosen uniformly at random.
Simplex Method: Simplex method is a method that seeks an optimal vertex by iteratively moving from one vertex to a better neighboring vertex for a non-degenerate problem in inequality form
Strongly polynomial-time algorithm: A strong polynomial-time algorithm is an algorithm for which the total number of arithmetic operations and comparisons (on numbers whose size is polynomial in the input length) is bounded by a polynomial in n and d alone.
Tight constraint: A tight constrain is an inequality constraint is tight at a certain point if the point lies on the corresponding hyperplane.
Unbounded problem: An unbounded problem is a problem with no finite maximum.
Vertex: A vertex is a feasible point where at least the linearly independent constraints are tight.
DISCLAIMER: All project works, files and documents posted on this website, eProjectTopics.com are the property/copyright of their respective owners. They are for research reference/guidance purposes only and some of the works may be crowd-sourced. Please don’t submit someone’s work as your own to avoid plagiarism and its consequences. Use it as a reference/citation/guidance purpose only and not copy the work word for word (verbatim). The paper should be used as a guide or framework for your own paper. The contents of this paper should be able to help you in generating new ideas and thoughts for your own study. eProjectTopics.com is a repository of research works where works are uploaded for research guidance. Our aim of providing this work is to help you eradicate the stress of going from one school library to another in search of research materials. This is a legal service because all tertiary institutions permit their students to read previous works, projects, books, articles, journals or papers while developing their own works. This is where the need for literature review comes in. “What a good artist understands is that nothing comes from nowhere. The paid subscription on eProjectTopics.com is a means by which the website is maintained to support Open Education. If you see your work posted here by any means, and you want it to be removed/credited, please contact us with the web address link to the work. We will reply to and honour every request. Please notice it may take up to 24 – 48 hours to process your request.
