Optimum solution of Transportation Problem with the help of Zero Point Method

Optimum solution of Transportation Problem with the help of Zero Point Method

International Journal of Engineering Research & Technology (IJERT)

ISSN: 2278-0181

Vol. 1 Issue 5, July – 2012

Gaurav Sharma

IES institute of technology and management, Bhopal (M.P.)

S. H. Abbas

Saifia Science College, Bhopal (M.P.)

V. K Gupta

UIT, RGPV Bhopal (M.P.)

Abstract

A Transportation model is special type of network model; deal with get minimum-cost plan to transport a commodity from sources to destination and also well known as a basic network problem for it could be extensively applied in many fields. For solving as such problem we are using zero point method to solve the Transportation Problem to get the optimal solution without using MODI method. The solution procedure is illustrated with numerical examples.

1. Introduction

   A special class of linear programming problem is Transportation Problem, where the objective is to minimize the cost of distributing a product from a number of sources (e.g. factories) to a number of destinations (e.g. warehouses) while satisfying both the supply limits and the demand requirement. Generally, the transportation model can be extended to areas other than the direct transportation of a commodity, including among others, inventory control, employment scheduling, and personal assignment. The objective of the transportation problem is to satisfy the required quantity of goods or services at each demand destination, within the limited quantity of goods or services available at each supply origin, at the m.

   There are different types of transportation problems and the simplest of them that is now standard in the literature was first presented by [5,11] published a paper on a continuous version of problem, [21] began to spearhead research on the potentialities of linear programming for the study of the problems in economics. His historic paper Optimum Utilization of the transportation problems in Systems was based on his war time experience. Because of this and the work done earlier by Hitchcock, the classical case is often referred as the Hitchcock Koopmans transportation problem. After both study many scholars have discussed transportation problems in uncertain environment.[8,9,10] introduced the solid transportation problem which also knows as multi commodity transportation problem;[1] put forward first the fuzzy transportation problem with fuzzy coefficients; Speranza and [12] focuses on a multiproduct production system on a single link;[6,14]proposed fuzzy objective programming methods for stochastic transportation problems;[03]are using standard and network linear programming method for transportation problem;[22] deals with an inbound material- collection problem so that decisions for both

   inventory and transportation functions are made simultaneously;[20] proposed a new heuristic approach for getting good starting solution for dual based approaches used for solving transportation problem; [17] used the dual matrix approach for transportation problem.[13] introduced the variant of vogels approximation method for transportation problem; [19]presented a modified economic ordering quantity for a single supplier-retailer system in which production, inventory and transportation costs are all considered;[4] studied the multi-objective transportation problem, in which the cost factors, the sizes of supply and demand are all fuzzy numbers;[23] used new particle swarm optimization algorithm (PSO) for the solution of linear transportation problem with its special structure; [7] established a mathematical model and solved it for transportation problem with uncertain cost;[15] obtained feasible solution and optimality bounds for optimization problems with probabilistic constraints; [02] gave a mathematical model for transportation problem with uncertain demand through describing the uncertainty by intervals; [16] represented the OR model for southern part of north region of Indian and solved this by Object Oriented Programming.

2. Mathematical Transportation Problem

   The general transportation problem is represented in the figure

   Suppose that are m origins and n destinations. The edges joining the origins and destinations represent the routes between the origins and destinations. In other words, (i, j) denotes the joining of the origin i and destination j. Let

   ai = quantity of product available at origin i, i = 1, 2,,m

   bj= quantity of product required at destination j, j = 1, 2,,n

   cij = The cost of transporting one unit of product from origin (i) to destination (j)

   xij = The quantity transported from origin i to destination j

   The objective is to determine the number of units to be transported from the origin i to destination j so that the total transportation cost is minimum, while, satisfying all the supply at origins and the demands requirement at the destinations.

   Mathematically, the problem can be stated as Minimize Subject to

   A transportation problem is said to be balanced if total supply from all sources equals to the total demand in all .

   Otherwise it is called unbalanced.

3. Zero Point Method

   The Zero Point Method proceeds as follows:

   Step 1. Construct the transportation table for the given transportation problem and then, convert into a balanced one if not.

   Step 2. Subtract each row entries of the transportation table from the row minimum

   Step 3. Subtract each column entries of the transportation table after using Step 2 from the column minimum.

   	W1	W2	W3	W4	Supply
   F1	21	16	25	13	11
   F2	17	18	14	23	13

   Step 4 Check if each column demand is less then to the sum of the supplies whose reduced costs in that column are zero. Also check if each row supply is less than to sum of the column demands whose reduced costs in that row are zero. If so, go to Step 7 ( Such reduced table is called the allotment table). If not go to Step 5

   Step 5. Draw the minimum number of horizontal lines and verticals line to cover all the Zeros of the reduced transportation table such that some entries of rows(s) or / column(s) which do not satisfy the condition of the step 4, are not covered.

   Step 6. Develop the new revised reduced transportation table as follows:

   1. Find the smallest entry of the reduced cost matrices not covered by any lines.

   2. Subtract this entry from all the uncovered entries and the same to all entries lying at the intersection of any two lines, and then , go to step 4.

      Step 7. Select a cell in the reduced transportation table whose reduced cost is the maximum cost. Say (, ). If there are more than one, then select anyone.

      Step 8. Select a cell in the row or / and – column of the reduced transportation table which is the only cell whose reduced coast is zero and then allot the maximum possible to that cell. If such a cell does not occur for the maximum value, find the next maximum so that such a cell occurs. If such cell does not occur for any value, we select any cell in the reduced transportation table whose reduced cost is fuzzy zero.

      Step 9. Reform the reduced transportation table after deleting the fully used supply point and the received demand points and also, modify it to include the no fully used supply point and not received demand points.

      Setp 10. Repeat Step 7 to Step 9 until all supply points are used and all demand points are fully received.

      Setp 11. This allotment yields a solution to the transportation problem.

4. Numerical Example

   1. Example 1: Consider the following balanced transportation problem

      F3	32	27	18	41	19
      Demand	6	10	12	15	43

      F3	32	07 27	12 18	41	19
      Demand	6	10	12	15	43

      Now, ai = bj = 43, the given transportation problem is balanced

      Now, using the step 2 to step 3 of the zero point method we have the following reduced transportation table

      	W1	W2	W3	W4	Supply
      F1	5	0	12	0	11
      F2	0	1	0	7	13
      F3	11	6	0	23	19
      Demand	6	10	12	15	43

      Now using the step 4 to the step 6 of the zero point method, we have the following allotment table

      	W1	W2	W3	W4	Supply
      F1	12	6	24	0	11
      F2	0	0	5	0	13
      F3	6	0	0	11	19
      Demand	6	10	12	15	43

      Now using the rules of the zero point method, we have the allotment

      Therefore the optimal solution for the given problem is x14 = 11, x21 = 06, x22 = 03, x32 = 07, and x33 = 12 and the optimum transportation cost for the problem, Z is 796

   2. Example 2: Consider the following unbalanced transportation problem

   	W1	W2	W3	W4	Supply
   F1	6	9	1	3	70
   F2	11	5	2	8	55
   F3	10	12	4	7	70
   Demand	85	35	50	45

   Now, ai = 195 and bj = 215, the given transportation problem is unbalanced. Therefore, an dummy row will be introduced with zero cost and having the plant availability = 215-195 = 20 units, The modified table is given

   	W1	W2	W3	W4	Supply
   F1	6	9	1	3	70
   F2	11	5	2	8	55
   F3	10	12	4	7	70
   F4	0	0	0	0	20
   Demand	85	35	50	45

   Now, using the step 2 to step 3 of the zero point method we have the following reduced transportation table

   	W1	W2	W3	W4	Supply
   F1	21	16	25	11 13	11
   F2	06 17	03 18	14	23	13

   	W1	W2	W3	W4	Supply
   F1	5	0	8	2	11
   F2	9	3	0	6	13
   F3	6	8	0	3	19

   F4	0	0	0	0	20
   Demand	6	10	12	15	43

   Now using the step 4 to the step 6 of the zero point method, we have the following allotment table

   	W1	W2	W3	W4	Supply
   F1	0	0	11	0	11
   F2	1	0	0	1	13
   F3	0	7	2	0	19
   F4	0	5	8	3	20
   Demand	6	10	12	15	43

   Now using the rules of the zero point method, we have the allotment

   	W1	W2	W3	W4	Supply
   F1	40 6	30 1	9	3	11
   F2	11	05 5	50 2	8	13
   F3	25 10	12	4	45 7	19
   F4	20 0	0	0	0	20
   Demand	6	10	12	15	43

   Therefore the optimal solution for the given problem is x11 = 40, x12 = 30, x22 = 05, x23 = 50,x31

   = 25, x34 = 45 and x41 = 20 and the optimum transportation cost for the problem, Z is 960.

5. Conclusion:

   The zero point method is a systematic procedure for transportation problem and easy to apply and can be utilized for all types of transportation problem whether maximize or minimize objective function, it conserve as an important tool for the decision makers when they are handling various types of logistic problems. And gives an optimal

   solution of transportation problem, other methods also gives an optimal solution but zero point method gives optimal solution without help of any other modified method.

6. References/Bibliography:

1. A. Kaufmann and M. Gupta (1991): Fuzzy mathematical models in engineering andmanagement science, 2nd edition, North-Holland, Amsterdam,

2. B. Jiang and Mingfu Sun (2008): The model and solution of transportation problem of uncertain demand, Mathematics teaching research,(1): 50-52

3. Bojan Srdjevic and Tihomir Zoranovic (1997): Transportation Problem- Standard Vs Network Linear programming; 2 the primer, 4thBalken conference on OR, Hellenic Operational Society, Thessalonica

4. E. E. Ammar and E. A. Youness (2005): Study on multi-objective transportation problem with fuzzy numbers, Applied Mathematics and Computation, 166: 241-253

5. F. L. Hitchcock (1941): The distribution of product from several source to numerous localities, J. Maths. Phy. , 20, 224-230

6. G. Chalam, Aruna (1994): Fuzzy goal programming approach to a stochastic transportation problem under budgetary constraint, Fuzzy Sets and Systems, 66: 293-299.

7. Guozhong Bai (2007): The transportation problem of uncertain freight, Journal of Foshan University (Natural Science Edition), 25(1): 6-10.

8. K.B. Haley (1962): The Solid Transportation Problem, Op. Res., Q.10, 448-463

9. K.B. Haley (1963): The multi- index Problem, Op. Res., Q.,11

10. K.B. Haley (1965): The existence of a solution to a multi- index Problem, Op.

    Res., Q.16, 471-474

11. L. V. Kantorovich (1942): On the translocation of masses, Compt. Rend.

    Akad.Sci., U.R.S.S., 37, 199-201

12. M.G. Speranza and W. Ukovich (1994): Minimizing Transportation and Inventory Costs for Several Products on a Single Link, Operations Research, 42(5):879-894

13. M. Mathirajan and B. Meenakshi (2004): Experimental Analysis of some variants of Vogels approximation method, Asia-Pacific Journal of OR, vol. 21, No. 4, 447-462

14. Mohammad Lotfy Hussein (1998): Complete solution of multiple objective transportation problem with possibilistic coefficients Fuzzy Sets and Systems, 93: 293-299

15. M. Sreenivas and T. Srinivas (2008): Probabilistic Transportation Problem, International Journal of Statistics and Systems, Vol. 3, No. 1, 83- 89

16. Nabendu Sen, Tanmoy Som and Banashri Sinha (2010): A Study of transportation problem for essential item of southern part of north region of India as an OR model and use of Object Oriented Programming, International Journal of Computer Science and Network Security, Vol. 10. No. 4, 78-86

17. P. Ji and K. F. Chu (2002): A dual simplex approach to the transportation problem, Asia pacific Journal of Operation Research, 19(1), 35-45

18. P. Pandian and G. Natrajan (2010): A New Algorithm for finding a Fuzzy Optimal solution for a Fuzzy Transportation Problem Applied Mathematical Science, Vol. 4, no. 2, 79-90

19. Q.H. Zhao, S.Y. Wang, K.K. Lai and G.P. Xia (2004): Model and algorithm of an inventory problem with the consideration of transportation cost, Computers and Industrial Engineering, 46(2): 398-397

20. R. R. K. Sharma and K. D. Sharma (2000): A new dual based procedure for the transportation problem, European Journal of Operation Research, 122, 611- 624

21. T.C. Koopman (1947): Optimum utilization of transportation system, Proc. Intern. Statics. Conf. Washington D.C.

22. W.W. Qu, J.H. Bookbinder and P. Iyogun (1999): An integrated inventory transportation system with modified periodic policy for multiple products, European Jour. of Operational Research, 115(2): 254-269

23. Zhi-Feng Hao, Han Huang and Xiao-Wei Yang (2006): A Novel Particle Swarm Optimization Algorithms For Solving Transportation Problem, Fifth International Conference on Machine Learning and Cybernetics, Dalian, August 13-16