Comparative Study of Efficiency of Integer Programming, Simplex Method and Transportation Method in Linear Programming Problem (LPP)
Ayansola Olufemi Aderemi, Oyenuga Iyabode Favour, Abimbola Latifat Adebisi
To cite this article:
Ayansola Olufemi Aderemi, Oyenuga Iyabode Favour, Abimbola Latifat Adebisi. Comparative Study of Efficiency of Integer Programming, Simplex Method and Transportation Method in Linear Programming Problem (LPP). American Journal of Theoretical and Applied Statistics. Vol. 4, No. 3, 2015, pp. 85-88. doi: 10.11648/j.ajtas.20150403.13
Abstract: In this paper, we present a Linear Programming Problem (LPP) to minimize the cost of transportation of NBC, PLC products from three distribution centres to ten depots. Three methods of analysis were considered namely: Integer Programming, simplex method and transportation method via computer packages. The result of the analysis revealed that, the cost of transportation from these distribution centres to all the 10 depots are the same. That is, the optimal cost is
N9, 127, 776.
Keywords: Constraints, Algorithm, Simplex Methods, Objective Function, Minimizes
The purpose of this paper is to give the brief introduction of Linear Programming Problem (LPP) and to look at the three methods say; Integer Linear Programming, Simplex method and Transportation method in solving Linear Programming Problem and find out the method(s) that will gives the minimum cost of transportation. Linear programming (LP) is a tool for solving optimization problems. It is a mathematical modeling "System" which has found widespread uses in providing decision maker with an efficient means for resolving complex operational alternatives. It is applicable to the general category of problems that require the optimization of a linear objective function subject to linear constraints.
In general, Linear Programming is a technique used to determine the best utilization of limited resources to reach a desired objective of either maximizing the benefit (Profit) or minimizing the costs. (Aminu, 1998).
Aremu, M.A (2007) in his paper, titles; A Linear Programming Approach to Profit optimization in a production mixed system, revealed the resources that will maximizes profit to Nigeria Bottling Company, PLC Ilorin Plant in 2003 production.
However, Integer programming techniques have gained a lot of interest recently as they provided state-of-the art methods for predicting RNA secondary structures with Pseudoknops (Poolsap et.al; 2009; Sato et.al; 2011). In our practical life, we come across many business and production industries which have to usually face problems of economics optimization such as cost minimization of non- economic items that are most vital to the existence of their firms. The transportation models are one of these economic optimizations which have their roots in operational management and industrial mathematics as well as since long back 1941. However, the transportation models have applications not only in limited areas of production industries but also worldwide applications in communication networks, planning and scheduling, we refer Ford, L.R and Fulkerson, D.R (1957), Fulkerson, D.R (1961), Garvin, W.W (1960) and Herderson, A and Schlaifer, R (1954).
In various problems of economic optimization, the transportation problem is a logistical problem for organizations especially for manufacturing and transport companies. The difference methods used in solving different versions of transportation models pay a key role in decision-making and process of allocating problem in these organizations, Kirca and Stair (1990).
Furthermore, since the simplex method is an iterative algebraic procedure for solving linear programming problems-transportation models, therefore, keeping in view this feature of the simplest method a few noteworthy previous researchers e.g Arsham, H and Khan, A.B (1989), Arsham, H (1992), Balinski, M.L and Gomory, R.E (1963) among others confined their attention in this direction and developed optimal solution for deterministic transportation models.
2. General Overview of linear Programming Formulation
The general Linear Programming Problem (GLPP) is of the standard form of
In linear systems of equations, we have
Where are called decision variables, are called the cost of variable considered and are the quantity of materials used.
In this paper, we want to solve the LPP above using the following methods.
Method 1: Integer Programming Method.
The general integer programming problem can be written as
and integer, j I
where b, c and d are vectors, A and B are matrices of conformable dimensions, and the index set I denotes the variables required to be integer. The reason for distinguishing two types of constraints is that the second of these, is supposed to have special structure.
Integer programming is a valuable tool in operations research, having tremendous potential for applications. Such problems occur quite frequently in business and industry. All assignment and transportation problems are Integer Programming Problem (IPP), the decision variables are either zero or one i.e or 1.
Method 2: Simplex Method
The simplex method is the computational technique used to solve linear programming problem (LPP) involving several number of variables and constraints.
This simplex method is an algorithm for starting at feasible point and by sequence of exchange to other points until a solution point called optimal solution is found.
Method 3: Formulation of Transportation Model
The transportation algorithm is a special designed linear programming for minimizing the total cost of distributing goods from ‘n’ dispatch points to ‘n’ receiving points, provided (i) the number of items to be dispatched from, and the number to be received at, each point is known and (ii) the cost of transportation between each pair of points is known.
In formulation of transportation model, we have;
with the assumption that
3. Data Analysis
The data used for numerical illustration were collected from Nigeria Bottling Company: Asejire, Benin and Ikeja Distribution Centres. The products collected from these three Distribution Centres were distributed to ten (10) depots Viz: Ibadan, Saki, Akure, Sapele, Onitsha, Warri, Ikorodu, Enugu, Abeokuta and Abuja. The above mentioned Distribution Centres and depots were used as a case study for this paper. A computer package was applied for the analysis of the collected data.
From the analysis, it is observed that using the three methods: Integer Linear Programming, Simplex Method and Transportation Method; the result obtained using Microsoft Excel Solver is the same as shown in the table below:
4. Results of Analysis
The values for the decision variables show the optimal quantities to transport over each route. The table above also shows the minimum cost transportation schedule.
|FROM||TO||UNITS TRANSPORTED||COST PER UNIT||TOTAL COST|
The results of our analysis revealed that using any of the three methods of obtaining the optimal solution in transportation problem, i.e Simplex Method, Integer Linear Programming Method and Transportation Method yield the same optimal cost. This means that any of the three methods could be used to give optimal cost which would minimizes the total shipping cost with satisfying both demand and supply limits.
Whenever, there is a physical movement of goods from the point of manufacturer to the final consumers through a variety of channels of distribution, there is a need to minimize the cost of transportation so as to increase profit on sales.