Solving Transportation Problem Using Linear Programming and Graph Theory by Proposed Model

Solving Transportation Problem Using Linear Programming and Graph Theory by Proposed Model

Sarla Raigar¹, Gurusharan Kaur², Kirti Kumar Jain³

Department of Applied Mathematics

Sagar Institute of Research and Technology, Bhopal,Madhya Pradesh India

sarla,raigar@yahoo.com¹, kdrgurusharan@gmail.com², k.jain1969@gmail.com³

ABSTRACT

This article describes how to use Graph Theory and LPP approaches to identify solutions to minimize transportation expenses. This paper's goal is to apply several strategies that have been created in the literature to address transportation-related issues and lower costs. This paper demonstrates the connection between the transportation problem and graph theory and starts the process of looking for different sorts of solutions. For this reason, we have employed a novel approach in conjunction with graph theory, LCM, VAM, NWCM, and Linear Programming Model. Which technique has a lower transportation cost is shown via comparison.

KEYWORD:

Transportation, Minimization costs, Sources supply, Demand, Bipartite graph, LINGO Software, Linear Programming.

1. INTRODUCTION:

The objective of the transportation problem, a unique type of linear programming challenge, is to reduce the expenses associated with shipping goods from multiple suppliers to various destinations, while meeting supply constraints and demand requirements. This work presents the development of a novel way for solving the transportation problem. One method finds an initial basic feasible solution, while the other uses a bipartite graph to discover the best answer. It first creates a graphical representation of the transportation problem, then a new graphical image, and last it creates new methods to solve bipartite graphs..

Mohamed H. Abdelati (2024), The goal of this research is to present a reported new approach “Avoiding the bigger cost” (ABC) to solving the IBFS for transportation problem. Excellent way is not always the most complicated and this is what distinguishes this method, which is simple in solution and effective in results. This method will be good for use in large transportation problems that are difficult to find an optimal solution by computational methods and in light of the difficulty of using software because of its high prices.

In this research study, Manish Jaiswal (2023) has developed a suggested approach for determining the first fundamentally workable answer to the transportation problems. After the researcher studied and contrasted the five numerical instances, the suggested approach is compared to the NWCM and LCM methods. The results from the suggested method are more accurate than those from the traditional method.

The goal of this study is to identify novel approaches for resolving transportation-related issues. The researcher creates a transport challenge and a linear programming problem using Lingo software in an effort to cut costs. The modified Vogel's approximation approach is used to solve this problem, and it is discovered that the outcomes of the two ways are identical.

The goal of this study is to used applied mathematics for optimum utilization of resources in cake production. A homemade cake becomes used as our case study. The choice variables in this study are 4 exclusive sizes (half of kg, 1 kg, 2kg and 3kg) of homemade cakes. Use LINGO software to solve linear equation.

Researchers Ekanayake et al. (2021) have developed a novel method for employing a bipartite graph to discover the unique result to a transportation troubles. The transportation troubles have been solved a variety of ways, but this strategy is crucial to the relationships between topology, transportation, and graphs.

Modi et al., (2017) the authors introduced an over technique for “Solving Transportation Problem by using Supply Demand Minima Method”, this method is very easy and gives you a minimum answer in a short time. Researcher have complied this method with NWCM and LCM.Top of ForBottom of Form

The primary aim of this effort is to find the most effective solutions for the transportation problem. That's why the present work focuses on Vogel's method. Many researchers have proposed different ways to solve the transportation problem. An improved Vogel approximation method was used for transportation problems.

1.1 LINEAR PROGRAMMING:

A mathematical technique called linear programming (LP) can be used to discover the optimal result in a given mathematical mould, typically in cases when there are multiple options and optimization is needed. It's a method for allocating scarce resources as effectively as possible.

In a linear programming problem, there are typically two main components:

1. Objective Function: This function defines the quantity that needs to be optimized, whether it's maximizing profit, minimizing cost, or achieving some other goal. The purpose function is a linear combination of decision variables.

2. Constraints: These are restrictions or limitations that must be adhered to. Constraints can represent physical limitations, such as limited resources, or other factors that restrict the decision-making process.

The decision variables are the values that must be set to achieve the best outcome for the objective function, while meeting the constraints.

Linear programming problems are characterized by having linear relationships among the variables, meaning that the purpose task and all constraints are linear equations or inequalities.

Linear programming has a wide used across in various fields, such that economics, engineering, operations research, and business management. It's used for tasks such as production planning, inventory management, transportation logistics, and financial portfolio optimization. Its versatility and efficiency make it a valuable tool for decision-making and problem-solving in many real-world scenarios.

1.2 GRAPH THEORY

One of the major and crucial fields of mathematics is graph theory. Its creation of novel algorithms with a wide range of applications is what is causing it to quickly enter the mainstream of mathematics. Paths, walks, and circuits from graph theory are applied in many different domains, such as resource networking, database design concepts, and the travelling salesman issue. We employed a bipartite graph in this paper, which is a graph whose vertices can be divide into two disjoint sets with all links connecting a node in one set to a node in the other[3][4].

3. Mathematical Formulation of Transportation Problem

The amount sent for origin (i) to the end (j) is denoted by x_ij≥ 0. The problem is expressed mathematically is given below.

Minimize Z =$\sum _{i-1}^m.\sum _{j=1}^{n}c$_ijx_ij

Subject to $\sum _{j=1}^{n}x$_ij = a_i

$\sum _{i=1}^{m}x$_ij = b_j

x_ij ≥ 0 for all i and j

Where,‘Z’ is total transportation cost that has to be reduced.

The cost per unit for moving products from the i-th origin to the j-thdestination is c_ij.
The amount carried from the i-th origin to the j-th destination is equal to x_ij.
a_i is the quantity on hand at the i-th origin.
b_j is the j-th destination's demand

1. Tabular form of Transportation Problem

Definitions

Transportation Model is balanced if Supply $\sum _{i=1}^m\mathrm{a}$_i = Demand $\sum _{j=1}^{n}b$_j

Otherwise unbalanced if Supply $\sum _{i=1}^m\mathrm{a}$_i≠ Demand $\sum _{j=1}^{n}b$_j

Given row and column limits, a set of non-negative allocations xij is a possible solution to a transportation problem.

If a transportation problem has a viable solution with no more than m+n-1 non-negative allocations, it is called a Basic viable Solution. In the transportation problem, m denotes the number of rows and n the number of columns[4].

5. Methodology

These techniques are present in many operations research textbooks and are always employed to solve transportation-related problems. Initial Basic Feasible Solution Methods[3]

1. North West Corner Method(NWCM)
2. Least Cost Method(LCM)
3. Vogel’s Approximation Method(VAM)

5. Algorithm of new Method

Step 1:- Look at whether the transportation issue is adjusted or not. On the off chance that it is adjusted at that point go to following step.

Step 2:- Discover the littlest taken a toll from each row and subtract the littlest taken a toll from each component of the row

Step 3 Discover the littlest taken a toll from each column and subtract the littlest taken a toll from each component of the column

Step 4: Determine which row or column has the least and another least (referred to as a row penalty and a column penalty), then construct it within the side and foot.

Step 5: Choose the highest value from there. We have to identify the least amount of supply or demand inside the least amount of the chosen row or column. Remove by deleting the lines or columns that correspond to the fulfilment of the request or supply.

Step 6:- Repeat steps 4 to 5 until all supplies and demand are met.

Step 7:-The sum of the current minimum tolls charged is calculated as the entire toll item and compared to the specified value of supply/demand.

1. Algorithm of Graph Method

Step 1: verify whether transportation issue is uniformly distributed. If it is, move onto the next step[4].

Step 2: Create a transportation problem graph based on the supply and demand scenarios for a visual depiction of the transportation issue.

Step 3: - Choose a bipartite graph that includes all the supply and demand elements.

Step 4: - Look for edges that have the lowest cost per unit starting from the first supply or demand listed in the table, and ensure they meet the minimum supply or demand requirement.

Step 5: - Continue applying step 4, until all supply and demand needs are fulfilled.

Step 6: - Repeat step 4 for the second supply or demand listed in the table, ensuring the edges meet the minimum supply or demand requirement.

Step 7: - Apply step 6 until all second supply or demand needs are met.

Step 8: - Now, repeat steps 4 to 7 for any unmet supply or demand needs.

Example 7.

Four rolling mills and three hearth furnaces are owned by a steel firm. The following table displays the transportation cost per ton for steel shipped from furnaces to rolling mills. Establish the lowest possible cost of transportation.

Solution:$\sum a$_i = $\sum b$_j = 150

The Transportation Cost is Z = 20*10+10*13+30*12+40*12+10*13+40*11 = 1740/-

Solution by LINGO Software

Minimum Transportation cost by LINGO software is 1740/-

Solution by Bipartite Graph

Graphical Representation for Problem[4]

Solution graph

Z= 10*20+13*10+12*40+13*10+12*30+11*40= 1740/-

8. Comparison of the numerical result

The following table displays a comparison of the numerical results obtained from the example.

9.CONCLUSION

The aim of this prominent operations research problem is to minimize the cost of transporting items from various suppliers to multiple destinations

Solving the transportation problem using linear programming provides an optimal solution in terms of cost (or other objective functions). The optimal cost in this case is mentioned as Rs. 1740/-.

Though not commonly used for larger problems due to complexity, the transportation problem can be represented graphically, especially for smaller instances, to visualize solutions[7].

The statement suggests the existence of a new method that is attractive due to its simplicity, ease of understanding, and efficiency in producing results similar to or better than the Vogel's Approximation Method (VAM). VAM is a well-known heuristic for solving transportation problems[6].

The new method is highlighted as:

• Easy to comprehend and implement.
• Provides results quickly.
• Achieves optimal or near-optimal solutions (Rs. 1740/- in this case).
• Can be utilized without extensive training or expertise.

These include being time-efficient

REFERENCES:

1. A. e. Anieting, V. O. Ezugwu and s. Ologun, “Aplication of liner programming Technique in the Determination of Optimum production Capacity”, IOSR Journal of Mathematics , Vol. 5, No. 06, (2023), PP. 62-65.
2. Akpan N. P. Iwok, I. A., “Application of programming for Optimal Use of Raw Materials in Bakery”, IJMSI Journal of Mathematics, Vol. 4, No. 08, (2013), PP 51-57.
3. Kaur Gurusharan, Tripathi Namrata and Verma Mona, “Application of Graph Theory in Science and Computer Science”, International Journal of Advance in Engineering and Management (IJAEM), Vol. 2 No. 06, PP 736-739.
4. Kaur Gurusharan, Tripathi Namrata, “Applying Graph Theory to Secure Data by Cryptography”, International Journal of Linguistics and Computational Applications (IJLCA) ISSN 2394-6385 (Print) Volume 8, Issue 1, January – March 2021 ISSN 2394-6393 (Online) 1 DOI: 10.30726/ijlca/v8.i1.2020.81001
5. Ekanayake E. M. U. S. B, Daundasekara W. B and perera S. P. C., “Solution of a Transportation Problem using Bipartite Graph”, Global Journal of Science Frontier Research: F Research, Vol. 21, No. 01, PP 59-68.
6. Modi Geeta, Duraphe Sushma and Raigar Sarla, “Solving Transportation by using Supply Demand Minima Method”, Journal of Ultra Scientist of Physical Science, Vol. 29,No. 08,(2017), PP 194-198.
7. Jain K. K., Raigar S and Sharma M, “Using Linear Programming to Use Resources to Make Cakes”, Journal of E- science Letters, Vol 03, No. 03, PP 29-33
8. Abiodum R. O. and CLEMENT A. O., “Application of Linear Programming Technique on Bread Production Optimization in Rufus Giwa Polytechnic Bakery Ondo State Nigeria”, American Journal of Operation Management and Information Systems, Vol. 2, No. 01, (2017), Pp 32-36.
9. Raigar S. and Jain K. K., “Transportation Problem Solve By Linear Programming and Modified Vogel’s approximation Method”, International Journal of Enhanced Research in Education Development, Vol. 11, No. 3,(2023), PP 448-453
10. Serder K. and Serkan B., “An Improved Vogel’s Approximation Method for the Transportation Problem”, Mathematics and Computation, Vol. 16, No. 02 (2011), Pp 370-381.