Transportation problem: Iterative optimization method 1
Transportation Problem: Iterative optimization method
Introduction: A product is manufactured by three countries Mexico, Japan and France. Their daily production capacities are given with 90, 160 and 80. Four other countries demand the products USA, Netherlands, Germany and China. Their daily demand is given with 70, 60, 70, and 130. The transportation costs in Dollar from one country (i) to the other country (j) are given in the table below.
| Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
|
Determination of the optimal solution: Determine the extent deliveries from each of the supplying countries to each of the demanding countries, so that the total cost (production and transportation together) is minimal.
First step: develop initial solution by any of the five methods:
1) North West Corner Rule (NWCR) or South West Corner Rule (SWCR)
2) Row Minima Method (RMM)
3) Column Minima Method (CMM)
4) Matrix Minima Method (MMM)
5) Vogel’s Approximation Method (VAM)
In this Wiki, we will discuss two methods:
1) Vogel’s Approximation Method (VAM)
and
2) Matrix Minima Method (MMM)
Vogel’s Approximation Method is a more complex method to find a feasible initial solution, compared to the other methods. But this initial solution needs less iteration steps to find an optimal solution. Because of that, we use it in our first example. In our second example we want to show the solution process from the initial solution to the optimal solution based on the Matrix Minima Method, you’ll see that this method requires more steps to solve the same problem.
Digression: Steps of the Vogel’s Approximation Method to get the initial solution
1) Consider each row of the cost matrix individually and find the difference between two least cost cells in it. Then repeat this for each column. Identify the row or column with the largest difference (select any one in case of a tie).
2) Now consider the cell with minimum cost in that column (or row) and assign the maximal possible units to that cell.
3) Delete the row/column, if it is satisfied.
4) Again start with step 1 and calculate the differences, proceed in the same manner as stated in earlier paragraph and continue until all units have been assigned.
Feasible initial solution to the shown example (VAM):
| Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
|
But what is a feasible initial solution? In the following you will find some definitions for your understanding:
1) Feasible Solution: A set of non-negative allocations , which satisfies the row and column restrictions is known as feasible solution.
2) Basic Feasible Solution: feasible solution to a m-origin and n-destination problem is said to be basic feasible solution if the number of positive allocations are (m+n–1).
Explanation: If the number of allocations in a basic feasible solutions are less than (m+n–1), it is called degenerate basic feasible solution (otherwise non-degenerate).
3) Optimal Solution: A feasible solution (not necessarily basic) is said to be optimal if it minimizes the total transportation cost. (goal of our calculation)
Test for optimization:
In our example we have an initial feasible solution. This solution may be optimal or may not be optimal, so it’s essential to test for optimization.
At first we have to find the basic fields with the given formula:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): m+n-1 = number of required basic fields, where = number of rows (here: supply-countries) and = number of columns (here: demand-countries)
In our example 3+4-1=6 basic fields are required.
As basic fields you first declare the fields (cells) which already have an amount of (in our example we do have enough basic fields -> 6). If there were less than 6 fields, you have to choose an arbitrary field. In the basic fields the reduced costs () are equal 0, you mark them with a cross. Afterwards you choose an arbitrary multiplicator or and zero it (here: Japan). For a simple calculation you should choose a row or column with the most number of basic fields.
Now it’s possible to calculate the rest of the multiplicators with following formula:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*= c_{ij} - u_{i} - v_{j}
You can shift the formula as needed:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): u_{i} = c_{ij} - c_{ij}* - v_{j}
or
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): v_{j} = c_{ij} - c_{ij}* - u_{i}
| Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
|
1)
2) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): v_{USA} = 110 (c_{Japan-USA}) -0 (c_{Japan-USA}*) - 0 (u_{Japan}) = 110
3) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): v_{Germany} = 100 (c_{Japan-Germany}) -0 (c_{Japan-Germany}*) - 0 (u_{Japan}) = 100
4) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): v_{China} = 230 (c_{Japan-China}) -0 (c_{Japan-China}*) - 0 (u_{Japan}) = 230
5) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): u_{Mexico} = 140 (c_{Mexico-China}) -0 (c_{Mexico-China}*) - 230 (v_{China}) = -90
6) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): u_{France} = 30 (c_{France-USA}) -0 (c_{France-USA} *) - 110 (v_{USA}) = -80
7) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): v_{Netherlands} = 100 (c_{France-Netherlands}) -0 (c_{France-Netherlands} *) - (-80) (u_{France}) = 180
Our next step is to determine the missing reduced costs Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*
of the matrix with the formula above:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}* = c_{ij} - u_{i} - v_{j}
For example:
1) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{Mexico-USA}* = 100 (c_{Mexico-USA}) -(-120) (v_{USA}) - 140 (u_{Mexico}) = 80
2) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{France-USA}* = 30 (c_{France-USA}) -(-120) (v_{USA}) - 140 (u_{France}) = 10
... ... ...
| Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
|
As long as one Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}* < 0
, the solution is not optimal. Now you have to find the most negative cell in the matrix, it gives you the best chance to reduce costs (here: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{France-China}*
). Then allocate 0 to this empty cell in the final allocation table and afterwards subtract and add the amount of this allocation to other corners of the loop in order to restore feasibility, without breaking the rule: supply equal demand.
Again, apply the above test for optimality till you find all Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}* > 0
.
| Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
|
In our example the tableau after the 1.Iteration is optimal, because all Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}* > 0
. It minimizes the total transportation cost of the example.
Digression: Steps of the Matrix Minima Method (MMM) to get the initial solution
1. Allocate as much as possible to the feasible cell with the minimum transportation cost, and adjust the requirements, that demand equal supply
2. Repeat step 1 until all requirements have been met
In the following example, with the Matrix Minima Method, we want to show, that the amount of iteration steps is mostly connected with the initial solution of the method you have chosen.
| Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
|
Tip: Make sure how you redistribute your cells, otherwise you will make needless steps.
E.g. After the iteration and a new field with a maximum of negative reduced cost appear, try not to allocate the loop in your next step back to the cost cell you have taken it from in the previous step.
Conclusion: As you can see, Vogel’s Approximation method is the shortest way to get an optimal solution of the given example.
Summary:
1. determine a initial solution
2. determine m+n-1 basic fields an set Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}* = 0
3. set arbitrary or 4. determine the missing multiplicators 5. determine the missing reduced costs (Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*
) with the formula Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}* = c_{ij} - u_{i} - v_{j}
6. find the most negative cell in the matrix
7. add the amount of this allocation to other corners of the loop in order to restore
feasibility
8. set up the new matrix and start again with step 2 until all Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}* >= 0
Sources: https://www.pearsonschoolsandfecolleges.co.uk/FEAndVocational/Mathematics/ALevel/HeinemannModularMathematicsForEdexcelASAndALevel/Samples/Samplematerial/Chapter1.pdf http://shodhganga.inflibnet.ac.in/bitstream/10603/3970/8/08_chapter%203.pdf https://bisor.wiwi.uni-kl.de/orwiki/Transportproblem
Authors:
Christopher Einsfeld
Christian Kling
Julian Mirsanaye
