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;
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
f (x 1 2 n
………………. (1.1)
n
j = 1
a ij ij i
….…………… (1.2)
x j
The problem is usually expressed in matrix form, and then becomes:
Max{c T
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.
2
, 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:
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).
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.
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.
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:
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.