4
The Transportation Problem
4.1 INTRODUCTION
In the previous chapter we have used simplex method to solve any type of linear programming problems. However, there is another method, Allocation method which is applied to a lot of very practical problems generally called Transportation problems. The objective of the problem is to transport a commodity (single product) from more than one centre, called origins (or sources, or supply or capacity centres) to more than one places called destinations (sinks or demand or requirement centres) and the costs of transportation from each of the origins to each of the destinations being different and known. It is further assumed that
- The availability as well as requirements of the various centers are finite and contains the limited resources.
- The cost of transportations is linear.
The problem is to transport the goods from various origins to different destinations in such a manner that the cost of transportation is minimum.
The distinct feature of transportation problems is that sources and jobs must be expressed in terms of only one kind of unit.
4.2 MATHEMATICAL FORMULATION
Suppose that there are m sources and n destinations. Let a_{i} be the number of supply units available at source i(i = 1, 2, …, m) and let b_{j} be the number of demand units required at destination j(j = 1, 2, …, n). Let c_{ij} represents the costs of transporting one unit of commodity from source i to destination j. If x_{ij} (x_{ij} ≥ 0) is the number of units transported from source i to destinations j, then the equivalent linear programming model will be:
Determine non-negative values of x_{ij} satisfying both the availability constraints
as well as the requirement constraint:
and minimising the total cost of transportation
It is also assumed that total availabilities a_{i} satisfy the total requirement b_{j}. That is
Since the constraint equations (4.2.1), (4.2.2) and the objective function (4.2.3) are all linear in x_{ij}, so it may be viewed as a linear programming problem.
The above transportation problem can be represented by a table as:
TABLE 4.1
The matrix consists of squares called ‘cells’ which stacks terms, columns vertically and rows horizontally. Unit costs are placed in each cell. The unit transportation cost c_{ij} from the i^{th} source to the j^{th} destination is displayed in the lower right hand corner of (i, j)^{th} cell. The quantity x_{ij} transported from i^{th}_{} source to j^{th} destination is displayed in the upper left side of the (i, j)^{th} cell. Right and bottom sides of the transportation table point out the amounts of supplies a_{i} available at source i and the amount demanded b_{j} at destination j. The various a’s and b’s are called rim requirements.
4.2.1 Definitions
A feasible solution to a transportation problem is a set of non-negative allocations, x_{ij} that satisfies the rim (row and column) restrictions. A feasible solution is called a basic feasible solution if it contains no more than m + n − 1 non-negative allocations where m is the number of rows and n is the number of columns of the transportation problem. A feasible solution (not necessarily basic) is said to be optimal if it minimises (maximises) the transportation cost (profit). A basic feasible solution that contains less than m + n − 1 non-negative allocations is called degenerate basic feasible. A basic feasible solutions to a (m × n) transportation problem is said to be a non-degenerate basic feasible solution if it contains exactly m + n − 1 non-negative allocations in independent positions. The allocations are said to be in independent positions, if it is not possible to form a closed path. Closed path (loop) means by allowing horizontal and vertical lines and all the corner cells are occupied. Mathematically, an ordered set of at least four cells in a transportations table is said to form a loop provided:
- any two adjacent cells of the ordered set lie either in the same row or in the same column.
- no three or more adjacent cells in the ordered set lie in the same row or column.
For example,
TABLE 4.2
TABLE 4.3
TABLE 4.4
TABLE 4.5
4.2.2 Theorem (Existence of Feasible Solution)
A necessary and sufficient conditions for the existence of a feasible solutions to a transportation problem is that
Proof: The condition is necessary. Suppose there exist a feasible solution to the transportation problem. Then,
Hence the necessary part.
The condition is sufficient. Let us assume that (say). If λ_{i} ≠ 0 be any real number such that x_{ij} = λ_{i}b_{j} for all i and j, λ_{i} is given by
or,
Thus,
Since a_{i} > 0, b_{j} > 0, for all i and j, x_{ij} ≥ 0. Hence, a feasible solution exists.
4.2.3 Theorem (Basic Feasible Solution)
The number of basic variables in m × n transportation table are (m + n − 1).
Proof: Consider an m × n transportation problem with m-sources and n-destinations. According to Theorem 4.2.2, out of m + n constraints equations any of equations is redundant and it can be eliminated, so the remaining m + n − 1 form a linearly independent set.
To prove this, first add m row equations (4.2.1) and subtract from the sum the first n − 1 column equations (4.2 2), thereby getting the last column equation. That is,
Thus, we have proved that out of m + n constraint equations, only m + n − 1 equations are linearly independent. Hence, a basic feasible solution will consist of at most m + n − 1 positive variables, others being zero. In the degenerate case, some of the basic variables will be zero. By fundamental theorem of linear programming, one of the basic feasible solutions will be the optimal solutions.
Remarks:
- When the total capacity equals total requirement, the problem is called balanced.
- The allocated cells in the transportation table are called occupied cells and empty cells are called non-occupied cells.
4.2.4 Definition: Triangular Basis
The transportation problem has a triangular basis if the system of equations AX = b, is represented in terms of basic variables only, non-basic variables are set to zero in the system. In other words, the system has the property that there is at least one equation having exactly one basic variable; in a second equations not more than two basic variables occur, in a third equation not more than three basic variables occur, and so on.
4.2.5 Theorem
All the basic for a transportations problem are triangular
Proof: Let the set of constraints of a transportation problem be
Suppose that these constraints have been displayed in the transportation table having m rows and n columns. We prove,
- each row and column of the transportation table contains at least one basic variable, and
- it is not possible that all the rows and columns have two or more basic variables.
(i) follow from the fact that if any row or columns does not contain a basic variable, then the corresponding rim requirement cannot be satisfied (as a_{i}’s and b_{j}’s are all non-zero).
We prove (ii) by contradiction Suppose every equation has at least two basic variables. Then, there will be at least two basic variables in each row, and at least two basic variables in each column. So, the total number of basic variables will be at least 2(m + n) since there are m + n equations. Therefore, if N denotes the total number of basic variables, we must have N ≥ 2m and N ≥ 2n. Now, three cases may arise:
Case (i): If m > n, then N ≥ 2m ⇒N > m + n
Case (ii): If m < n, then N ≥ 2n ⇒N > n + m
Case (iii): If m = n, then N ≥ 2m ⇒N > m + n
We observe that in all cases N ≥ m + n. But we know N = m + n − 1, which is a contradiction.
Thus, assumption of existence of at least two basic variables in each row and each column is not possible. Therefore, combining (i) and (ii) we conclude that there is at least one constraint equation that contains exactly one basic variable.
Let x_{rc} be the only variable in the r^{th} row and c^{th} column. Then x_{rc} = a_{r}. The equations can be eliminated from the system by deleting the r^{th} row and substituting x_{rc} = a_{r}, in the c^{th} column equations. So r^{th} row gets cancelled, and b_{c} is replaced . The resulting system now consists of m − 1 row equations and n column equations of which m + n − 2 are linearly independent. Thus, there are m + n − 2 basic variables in the system. Repeating the process it is concluded that there is an equation in the reduced system which has only one basic variable. If this equations is suppose say c^{th} column equation, it contains two basic variables. Thus, the original system has an equation which has atmost two basic variables. Continuing the process, it can be shown that there is an equation which has atmost three basic variables, and so on.
4.3 METHODS FOR FINDING INITIAL BASIC FEASIBLE SOLUTION
Methods of finding an optimum solution to the transportation problem will consists of two steps:
- Find an Initial Basic Feasible Solution (IBFS).
- Find an optimal solution by making successive improvements to IBFS.
The triangularity of all basis in a transportation problem says that there is an IBFS to a transportation problem in such a manner that all the rim requirements are satisfied with exactly (m + n − 1) allocations in independent positions. We explain the different methods to find initial basic feasible solution of a transportation problem. In all the methods it is assumed at the beginning that the transportation table for x_{ij} is blank. That is, initially all x_{ij} = 0.
4.3.1 First Method—North-West Corner Rule
Step 1: Starting with the cell at the upper left (north-west) corner of the transportation matrix, we allocate as much as possible so that either the capacity of the first row is exhausted or the destination requirement of the first column is satisfied. That is, x_{11} = min (a_{1}, b_{1}).
Step 2:
- If min{a_{1}, b_{1}} = a_{1}, then put x_{11} = a_{1}, decrease b_{1} by a_{1} and move down vertically to the second row and make the second allocation of magnitude x_{21} = min(a_{2}, b_{1} − x_{11}) in the cell (2, 1). Cross out the first row.
- If min {a_{1}, b_{1}} = b_{1}, then put x_{11} = b_{1}, and decrease a_{1} by b_{1} and move horizontally to the second column and make the second allocation of magnitude x_{12} = min{a_{1} − x_{11} b_{2}} in the cell (1, 2). Cross out the first column.
- If a_{1} = b_{1}, then put x_{11} = a_{1} = b_{1}, and proceed diagonally. That, is make the second allocation of magnitude
x_{12} = min(a_{1} − a_{1}, b_{1}) = 0 in the cell (1, 2)
or
x_{21} = min(a_{2}, b_{1} − b_{1}) = 0 in the cell (2, 1)
cross out the first row and the first column.
Step 3: Repeat steps 1 and 2 moving down towards the lower right corner of the transportation table until all the rim requirements are satisfied.
4.3.2 Second Method—Least Cost or Matrix Minima Method
Step 1: Determine the smallest cost in the cost matrix of the transportation table and allocate
x_{ij} = min (a_{i}, b_{j}) in the cell (i, j)
Step 2: If x_{ij} = a_{i}, cross off the i^{th} row and decrease b_{j} by a_{i}. Go to step 3.
If x_{ij} = b_{j}, cross off the j^{th} column and decrease a_{j} by b_{j}. Go to step 3.
If x_{ij} = a_{i} = b_{j}, cross off the i^{th} row or the j^{th} column, but not both.
Step 3: Repeat steps 1 and 2 for the resulting reduced transportation table until all the rim requirements are satisfied. Whenever, the minimum cost is not unique, make an arbitrary choice among the minima.
4.3.3 Third Method—Vogel’s Approximation Method (VAM) or Unit Cost Penalty Method
Step 1: Calculate the penalties by taking the difference between the smallest and next smallest costs in each row (column) and write them in brackets against the corresponding row (column).
Step 2: Identify the largest row difference or column difference. In the case of a tie, choose either of them.
Step 3: Allocate as much as possible in the lowest cost cell of the row (or column) which are identified by step 2.
Step 4: In case the allocation is made fully to a row (or column), cross out the row (or column).
Step 5: Again, compute the column and row penalties for the reduced transportation table and then go to step 2. Continue the procedure until all rows and columns have been crossed out.
4.3.4 Fourth Method—Row Minima Method
Step 1: Allocate as much as possible in the lowest cost cell of the first row until the capacity of the source 1 (first row) is exhausted or the requirement at j^{th} distributions centre is satisfied or both.
Three cases arise:
- If the capacity of the source 1 is completely exhausted, cross off the first row and proceed to second row.
- If the requirement at j^{th} destination is satisfied, cross off the j^{th} column and reconsider the first row with the remaining capacity.
- If the capacity of the source 1 as well as the requirement at j^{th} destination are completely satisfied, make a zero allocation in the second lowest cost cell of the first row. Cross off the row as well as the j^{th} column and move down to the second row.
Step 2: Continue the process for the resulting reduced transportation table until the rim conditions are satisfied.
4.3.5 Fifth Method—Column Minima Method
Step 1: Allocate as much as possible in the lowest cost cell of the first column so that the demand of the first distribution centre is satisfied or the capacity of the i^{th} source is exhausted or both.
Three cases arise:
- If the requirement of the first distribution centre is satisfied, cross out the first column and move right to the second column.
- If the capacity of i^{th} source is satisfied, cross out i^{th} row and reconsider the first column with the remaining requirement.
- If the requirement of the first destination as well as the capacity of the ith source are completely satisfied, make a zero allocation in the second lowest cost cell of the first column. Cross out the column as well as the i^{th} row and move right to the second column.
Step 2: Continue the process for the resulting reduced transportation table until all the rim conditions are satisfied.
Example 1
Determine the basic feasible solution to the following transportation problem:
TABLE 4.6
Solution: Since total requirements = 7 + 5 + 3 + 2 = 17 = 6 + 1 + 10 = total supply, the given problem is balanced.
We find the initial basic feasible solution (IBFS) by all the five methods.
(a) North-West corner rule
Since a_{i} = b_{j} = 17, there exists a feasible solution to the problem. We find IBFS as follows.
Step 1: First, allocation is made in the cell (1, 1), with the magnitude of x_{11} = min(a_{1}, b_{1}) = min(6, 7) = 6. Cross out the first row, since this meet the supply position of S_{1}. No allocations are to be made to cells (1, 2), (1, 3), (1, 4). See Table 4.7.
TABLE 4.7
Step 2: Proceed to cell (2, 1). The magnitude of the allocation is given by
x_{21} = min(a_{2}, b_{1} − x_{11})
= min(1,7 − 6)
= 1Cross out first column and second row, since it meet the supply at S_{2} and requirements at D_{1}. See Table 4.8.
TABLE 4.8
Step 3 Proceed to cell (3, 2). The magnitude of third allocation in the cell (3, 2) is given by
x_{32} = min(10, 5) = 5
The supply from S_{3} is 10 units while the demand for D_{2} is 5 units. See Table 4.9. So, set x_{32} = 5. Since the demand for D_{2} is met, cross off the second column and proceed to the cell (3, 3). Allocate x_{33} = min(5, 3) = 3. See Table 4.10.
TABLE 4.9
TABLE 4.10
Step 4 Proceed to cell (3, 4) and allocate x_{34} = 2 there, see Table 4.11
TABLE 4.11
It can be seen that the proposed solution is a feasible solution, as all the supply and requirements constraints are fully satisfied. In this method allocations have been made to various cells without considering the cost of the transportation associated with them. Hence, the solution obtained may not be best, but it may be economical.
Note that any cell in which no allocation is made, the corresponding x_{ij} is equal to zero. A cell which gets allocation is called a basic cell. The transportations cost is
z = 2 × 6 + 1 × 1 + 8 × 5 + 15 × 3 + 9 × 2
= 116.
(b) Least cost method
This method consists of maximum possible allocation in the lower cost cell and then the next allocation is done in the cell with second lowest cost, and so on.
Consider Table 4.6. Here, the lowest cost cell is (2, 2) and maximum possible allocation (meeting supply and requirement positions) is made here.
So, maximum feasible allocation in cell (2, 2) is 1. That is, set x_{22} = 1. This meets the supply at S_{2} and therefore, we cross off the second row from the Table [see Table 4.12], indicating no further allocations to the cells (2, 1), (2, 3), (2, 4).
TABLE 4.12
TABLE 4.13
TABLE 4.14
The next lower cost cell (excluding the cells in row 2) is (1, 1). Maximum possible allocation for (1, 1) is 6, and row 1 is crossed out. Next lowest cost cell in row 3 is (3, 1) and allocation of (1) is made here.
Likewise, allocations are made in the cell (3, 2), (3, 4) and (3, 3) with x_{32} = 4, x_{34} = 2, x_{33} = 3, respectively.
All the rim requirements have been satisfied and hence an initial basic feasible solution has been determined. The solution is displayed in Table 4.15.
Since the solution does not form a loop, the solution is basic. The transportation cost is
z = [2 × 6 + 1 × 0 + 1 × 5 + 4 × 8 + 3 × 15 + 2 × 9]
= 112.
(c) Vogel’s approximation method
The difference between the smallest and next to the smallest costs in each row and column are first computed and displayed inside the parenthesis against the respective rows and columns. For example, in column 1, the two lowest elements are 1 and 2 and their difference is 1 which is entered as (1) below column 1. Similarly, the two smallest elements in row 2 are 0 and 1, their difference is 1, which is entered as (1) to the right of row 2. See Table 4.16.
TABLE 4.16
TABLE 4.17
Select the row or column with the greatest difference and allocate as much as possible within the restrictions of the rim conditions to the lowest cost cell in the row or column selected.
Since (6) is the greatest number in the parenthesis we choose column 4 and allocate as much as possible to the cell (2, 4) as it has lowest cost 1 in column 4. Since supply is 1, and requirements is 2, maximum possible allocation is 1. See Table 4.17. For the assignment made at (2, 4), supply of S_{2} is completely satisfied. So, row 2 is crossed out. The row and column differences are now computed for the reduced transportation Table (4.18), the largest of these is (5) which is allocated with the second column. So, we allocate 5 units to the cell (1, 2), since it has smallest transportation cost 3 in column 2. Since requirements of column 2 are completely satisfied, this column is crossed out and the reduced transportation table is Table 4.19.
TABLE 4.18
TABLE 4.19
Differences are calculated again. The maximum difference is (5). Therefore we allocate (1) to the cell (1, 1) since it has the lowest cost in row 1. Since requirements of row 1 are fully satisfied, it is crossed out and the reduced table is Table 4.20. As cell (3, 1) has the lowest cost 5, maximum allocation of (6) is made here. Likewise, for (3, 4), the allocation is (1) and for (3, 3) the allocation is (3). Eventually, the basic feasible solution in Table 4.21 is obtained.
TABLE 4.20
TABLE 4.21
z = [2 × 1 + 3 × 5 + 1 × 1 + 6 × 5 + 3 × 15 + 1 × 9]
= 102.
Note that the least of all the values of transportation cost found by three methods is VAM, which is having most economical initial feasible solution.
(d) Row minima method
Consider Table 4.6. We first allocate to cell (1, 1) in the first row as it contains the minimum cost 2. We allocate min (6, 7) = 6 in this cell. Since the supply at S_{1} is satisfied, the first row is crossed off. [See Table 4.22]. The next allocation, in the resulting matrix is made in cell (2, 2) of row 2 as it contains the minimum cost 0 in the row. We allocate min(1, 5) = 1 in this cell. The supply capacity of S_{2} is satisfied and hence the second row is crossed off. [See Table 4.23]. The next allocation, in the reduced table is made in the cell (3, 1) which contains the minimum cost as 5. We allocate min(1, 10) = 1 to this cell. Since the requirement conditions of D_{1} is satisfied, the first column is crossed off. [See Table 4.24]. Proceeding in this way we allocate (4), (2), (3) units to the cells (3, 2), (3, 4), (3, 3) till all the rim conditions are satisfied. The resulting transportation table is Table 4.25.
TABLE 4.22
TABLE 4.23
TABLE 4.24
TABLE 4.25
z = [2 × 6 + 1 × 0 + 1 × 5 + 4 × 8 + 3 × 15 + 2 × 9]
= 112.
(e) Column minima method
Consider Table 4.6. Allocate first to cell (2, 1) in the first column as it contains the minimum cost 1. We allocate min(1, 7) = 1 in this cell. Since the supply at S_{2} is satisfied the second row is crossed off. [See Table 4.26]
TABLE 4.26
The next allocation in the resulting table is made in cell (1, 1) of column 1 as it contains the second lowest cost 2 in that column. We allocate min (6, 6) = 6 in that cell. Since the supply S_{1} as well as the requirement at D_{1} are satisfied, we allocate zero in cell (3, 1) of first column and cross off first row and first column and move on to second column [See Table 4.27]
TABLE 4.27
TABLE 4.28
Proceeding in this way we allocate (5), (3), (2) to cells (3, 2), (3, 3) and (3, 4) till all the rim conditions are met with. The resulting table is shown in Table 4.28. The transportation cost associated with this solution is
z = [2 × 6 + 1 × 1 + 5 × 8 + 3 × 15 + 2 × 9]
= 116.
Note: Suppose the problem is unbalanced, a dummy origin or destination (as the case may be) is created to balance the supply and requirements.
4.4 OPTIMUM SOLUTION OF A TRANSPORTATION PROBLEM
Following the determination of an initial basic feasible solution to a transportation problem, we next obtain the optimum solution. An optimality test can be performed only on the feasible solution in which
- The number of allocations is m + n − 1, where m is the number of rows and n is the number of columns.
- These (m + n − 1) allocations should be in independent positions.
The technique is similar to that of simplex method. That is, determine the net evaluations for the non-basic variables (here, empty cells), then determine the entering variable, then leaving variable, compute a better feasible solution, and repeat the steps until an optimum solution has been reached.
The two methods are commonly used. They are,
- The Stepping-stone Method
- The Modified Distribution (MODI) Method or u-v Method.
First, we determine the net evaluations by making use of the properties of the primal and dual problems.
Let u_{1}, u_{2}, … u_{m} and v_{1}, v_{2}, … v_{m} be the dual variables associated with the origin and destination constraints, respectively.
The net evaluations for a transportation problem can be determined from the following theorem.
Theorem 2
If there is a feasible solution consisting of m + n − 1 independent allocations, and if u_{i} and v_{j} satisfies c_{rs} = u_{r} + v_{s} for each occupied cell (r, s), then the evaluation d_{ij} corresponding to each empty cell. (i, j) is given by
d_{ij} = c_{ij} − (u_{i} + v_{j})
Proof: The transportation problem is to find x_{ij} ≥ 0 in order to minimise
Subject to the restrictions
and,
The restrictions (4.4.2) and (4.4.3) has been written as
Any multiple of each of these restrictions (4.4.4) and (4.4.5) can be added to the objective function (4.4.1) to eliminate the basic variable. Now, multiply u_{i}(i = 1, 2, … m) and v_{j} (j = 1, 2, … n), respectively so that
or
For each basic cell (r, s), given c_{rs} = u_{r} + v_{s}. That is, the net evaluations must vanish for the basic variables. Since there are m + n − 1 dual equations in m + n dual unknowns, if we assign arbitrary value to one of these unknowns u_{i} or v_{j}, the rest of the m + n − 1 variables can be solved uniquely. After an arbitrary assignment, say u_{1} = 0 the rest of the values are obtained by simple addition and subtraction.
To prove d_{ij} = c_{ij} − (u_{i} + v_{j}), consider that the empty cell (i, j) which is connected to occupied cells by a closed loop. See Table 4.29.
TABLE 4.29
First, allocate + 1 unit to the empty cell (i, j) and in order to balance the total requirement of D_{j}, add −1 unit to occupied cell (r, j). Consequently, the total amount available from source S_{1} will be balanced by adding +1 unit to occupied cell (r, s), which cause the column D_{s} to become unbalanced. Balance the column D_{s} by adding − 1 unit to the occupied cell (i, s).
This process will give the cost difference d_{ij} [called the empty cell evaluation of (i, j)] between the new solution and the original solution. Thus,
d_{ij} = c_{ij} − c_{rj} + c_{rs} − c_{is}
Since c_{rs} = u_{r} + v_{s} for all occupied cells such as (r, j), (r, s) and (i, s)
d_{ij} = c_{ij} − (u_{r} + v_{j}) + (u_{r} + v_{s}) − (u_{i} + v_{s})
= c_{ij} − (u_{i} + v_{j})
Similarly, we generalize the result for all empty cell (i, j) to occupied cells. This completes the theorem.
Note that if the cost difference d_{ij} ≥ 0, then the basic feasible solution under test must be optimal. If d_{ij} < 0 (because negative difference implies decrease in cost) for one or more empty cells, then it is better to reduce the cost more by allocating as much possible to the cell with the largest negative values of d_{ij}.
4.4.1 The Stepping-Stone Method
Step 1: Find the initial basic feasible solution by any of the methods discussed above.
Step 2: Check the number of occupied cells. If there are less than m + n − 1, there exists degeneracy and introduce a very small positive assignment of ε (= 0) in suitable independent positions, so that the number of occupied cells is exactly equal to m + n − 1.
Step 3: Each empty (non-allocated) cell is now examined for a possible decrease in the transportation cost. One unit is allocated to an empty cell. A number of adjacent cells are balanced so that the row and the column constraints are not violated. If the net result of these changes is a decrease in the transportation cost we include as many units as possible in the selected empty cell and carry out the necessary change with other cells.
Step 4: Step 3 is performed with all the empty cells till no further reduction in the transportation cost is possible. If there is another with zero increase or decrease in the transportation cost, then the problem has multiple solutions.
4.4.2 MODI Method or the u-v Method
In the Stepping-stone method, a closed path is traced for each unoccupied cell. Cell evaluations are found and the cell with the most negative evaluation becomes the basic cell. In the modified method, cell evaluations of all the unoccupied cells are calculated simultaneously and only one closed path for the most negative cell is traced. So, it is a time saving method than the Stepping-stone method. This method consists of the following steps:
Step 1: Find the initial basic feasible solution by using any of the methods discussed above.
Step 2: Check for degeneracy. If the problem is a degenerate one it has to be properly modified.
Step 3: Introduce dual variables corresponding to the row constraints and the column constraints. If there are m origins and n destinations then there will be m + n dual variables. The dual variables corresponding to the row constraints are denoted by u_{i}(i = 1, 2, … m) while the dual variables corresponding to column constraints are denoted by v_{j} (j = 1, 2, … n). The values of the dual variables should be determined from the following equations:
u_{i} + v_{if} = c_{ij} if x_{ij} > 0
starting initially with same u_{i} = 0 or v_{j} = 0 and entering successively the values of u_{i} and v_{j} in the transportation table margins.
Step 4: Compute the cell evaluations d_{ij} = c_{ij} − (u_{i} + v_{j}) for each unoccupied cell (i, j) and enter them in the upper right corners of the corresponding cell (i, j).
Step 5: Examine the sign of each d_{ij}. If all d_{ij} > 0, then the solution under the test is optimal and unique. If all d_{ij} > 0 with at least one d_{ij} = 0, then the solution under the test is optimal and an alternative optimal solution exists. If at least one d_{ij} < 0, then the solution is not optimal. Go to the next step.
Step 6: From a new basis feasible solution by giving maximum allocation to the cell for which d_{ij} is most negative by making an occupied cell empty. For that draw a closed path consisting of horizontal and vertical lines beginning and ending at the cell for which d_{ij} is most negative and having its other corners at some allocated cells. Along this closed loop indicate +θ and −θ alternative at the corners. Choose minimum of θ from the cells having −θ. Add this minimum of θ to the cells with +θ and subtract this minimum of θ from the allocation to the cells with −θ.
Step 7: Repeat steps (2) to (6) to test the optimality of this new basic feasible solution.
Step 8: Continue the above procedure till an optimum solution is obtained.
Example 3
Using stepping-stone method find the optimum solution of the transportation problem.
TABLE 4.30
Solution: We compute an initial basic feasible solution of the problem by Vogel’s approximation method.
[see Example 4.3.6] which is given in Table 4.31.
TABLE 4.31
The solution is non-degenerate since the number of non-zero basic variables is m + n − 1 = 3 + 4 − 1 = 6
Let us start with any arbitrary empty cell (a cell without allocation), say (2, 3) and allocate +1 to this cell. In order to keep up the row 3 restriction, +1 must be allocated to cell (3, 4) and allocate −1 to this cell (3, 3), −1 to the cell (2, 4). This can be shown in Table 4.32.
TABLE 4.32
The increase in the transportation cost per unit quality of reallocation is 6 + 9 − 1 − 15 = −1.
The total number of empty cells will be mn − (m + n − 1) = (m − 1) (n −1) such number of cell evaluations must be calculated. In this problem (3 − 1) (4 − 1) = 6 cell evaluations must be calculated.
Table 4.33 shows the transportation table after reallocation for the cell (2, 1):
TABLE 4.33
The increase in the transportation cost after reallocation is 1 × 1 − 6 × 1 − 5 × 1 + 1 × 15 = 5. This cannot decrease the transportation cost. So, we choose the empty cell (2, 2), the transportation table after reallocation is
TABLE 4.34
The increase in the transportation cost per unit of reallocation is 1 × 0 + 1 × 2 − 1 × 1 − 3 × 1 = − 2.
This procedure was repeated with the remaining empty cells (1, 3), (1, 4), (3, 2). The reallocation tables are as follows:
TABLE 4.35
TABLE 4.36
TABLE 4.37
The increase in cost per unit of reallocation for the cells (1, 3), (1, 4), (3, 2) are 1 × 11 + 1 × 5 − 1 × 15 − 1 × 2 = − 1, 1 × 7 + 1 × 5 − 1 × 9 − 1 × 2 = 1, and 1 × 8 + 1 × 2 − 1 × 3 − 1 × 5 = 2, respectively. From all these reallocation to unoccupied cells, we can see for the cell (2, 2), the transportation cost per unit of reallocation is − 2. Thus, the new route would be beneficial to the company. Hence, the minimum transportation cost is
z = 2 × 2 + 4 × 3 + 1 × 0 + 5 × 5 + 3 × 15 + 2 × 9
= 104.
Example 4
Solve the transportation problem
TABLE 4.38
Solution: Since a_{i} = b_{j} = 43, the given transportation problem is balanced. Hence, there exists a basic feasible solution to this problem.
By VAM, the initial basic feasible solution, with all allocations made during the procedure in a single Table is
Initial transportation cost is 796.
To find optimum solution by MODI method
Since the number of basic cells = 6 = 3 + 4 − 1, the solution is non-degenerate.
We calculate u_{i} and v_{j} using u_{i} + v_{j} = c_{ij} for basic cells. Arbitrarily, start with some u_{i} or v_{j} as zero.
Here, start with u_{2} = 0 as the second row has maximum number of allocation.
c_{21} = u_{2} + v_{1} ⇒ 17 = 0 + v_{1} ⇒ v_{1} = 17
c_{22} = u_{2} + v_{2} ⇒ 18 = 0 + v_{2} ⇒ v_{2} = 18
c_{24} = u_{2} + v_{4} ⇒ 23 = 0 + v_{4} ⇒ v_{4} = 23
c_{14} = u_{1} + v_{4} ⇒ 13 = u_{1} + 23 ⇒ u_{1} = − 10
c_{32} = u_{3} + v_{2} ⇒ 27 = u_{3} + 18 ⇒ u_{3} = 9
c_{33} = u_{3} + v_{3} ⇒ 18 = 9 + v_{3} ⇒ v_{3} = 9
We find the net evaluations d_{ij} = c_{ij} − (u_{i} + v_{j}) for each non-basic cells and enter at the upper right corner of that cell. Complete Table is given as:
TABLE 4.40
Since all d_{ij} > 0, the solution under the test is optimal and unique.
Therefore, the optimum allocation schedule is given by
x_{14} = 11, x_{21} = 6, x_{22} = 3, x_{24} = 4, x_{32} = 7, x_{33} = 12, and minimum transportation cost = 796.
Example 5
The following table shows all the necessary information on the available supply to each warehouse, the requirement of each market and the unit transportation cost from each warehouse to each market.
TABLE 4.41
The shipping clerk has worked out the following schedule from experience: 12 units from A to II, I unit from A to III, 9 units from A to IV, 15 units from B to III, 7 units from C to I, and 1 unit from C to III.
- Check that the clerk has the optimal schedule.
- Find the optimal schedule and minimum total shipping cost.
- If the clerk is approached by a carrier of route C to II who offers to reduce his rate in the hope of getting some business, by how much must the rate be reduced before the clerk should give him an order.
Solution: The basic feasible solution is given as follows.
TABLE 4.42
(a) We calculate optimal schedule by MODI’s method. Starting iteration table is:
TABLE 4.43
Since d_{ij} < 0 for the cell (3, 4), the clerk does not have the optimal schedule.
Trace the path and assign +θ, −θ alternatively to each occupied cell at the corners of the path.
Here, θ = min (9, 1) = 1. Table 4.45 gives the result of second iteration.
TABLE 4.44
TABLE 4.45
Since all d_{ij} > 0, the current solution is optimal.
(b) The optimal schedule is
x_{12} = 12, x_{13} = 2, x_{14} = 8, x_{23} = 15, x_{31} = 7, x_{34} = 1.
Minimum total shipping cost is
z = 12 × 2 + 2 × 4 + 8 × 3 + 15 × 1 + 7 × 4 + 1 × 5 = 104.
(c) If the clerk decides to transport at the most 8 units from C to II (instead of 7 to I, and 1 to IV), then II may reduce his cost from C_{32} = 6 to at least 4 in order to have the improved cost. So, according to the given proposal, the total minimum transport cost will become 103.
Given the following data
TABLE 4.46
The cost of shipment from third source to the third destination is not known. How many units should be transported from the sources to the destinations so that the total cost of transporting all the units to their destinations is a minimum.
Solution: Since the cost c_{33} is unknown, assign a large cost, say M to this cell. Now, using VAM the initial basic feasible solution is obtained in Table 4.47.
By MODI’s method, we obtain Table 4.48.
TABLE 4.47
TABLE 4.48
Since all d_{ij} > 0, the current solution is optimum. But, it is to be noticed that cell (3, 3) also appears in the solution for which the cost of shipment is known. Hence there exists a pseudo optimum basic feasible solution:
x_{13} = 10, x_{23} = 15, x_{31} = 20, x_{32} = 15, x_{33} = 5.
4.5 DEGENERACY IN TRANSPORTATION PROBLEM
We have seen that for an m × n transportation table, the number of basic (or occupied) cell must be m + n − 1. The basic solution will degenerate whenever number of basic cells is less than m + n − 1.
Degeneracy occur in two ways,
- Degeneracy in the initial solution.
- Degeneracy at any intermediate stage.
4.5.1 Resolution of Degeneracy in the Initial Stage
To resolve degeneracy, allocate a very small quantity ε (close to zero) to one or more of the unoccupied cells so that a number of occupied cells becomes m + n − 1. In a minimisation transportation problem it is better to allocate ε to unoccupied cells that have lowest transportation costs. The quantity ε is considered to be so small that if it is transferred to an occupied cell it does not change the quantity of allocation. That is, x_{ij} + ε = x_{ij} − ε = x_{ij}, but ε − ε = 0. Also, ε does not affect the total transportation cost of the allocation. The quantity ε is used to evaluate unoccupied cells and if we get the optimum solution, it will be removed.
4.5.2 Resolution of Degeneracy during Solution Stages
To resolve degeneracy which occur during optimality test, allocate ε to one or more of recently vacated cells so that the number of occupied cells is m + n − 1 in the new solution. It may be removed, once we obtain the optimal solution.
Example 1 Degeneracy at Initial Stage
Find the non-degenerate basic feasible solution for the following transportation problem using (i) North west corner rule (ii) Vogel’s Approximation Method.
TABLE 4.49
Solution: Since a_{i} = b_{j} = 150, the given transportation problem is balanced. Hence, there exists a basic feasible solution to this problem.
(i) North-West corner rule
TABLE 4.50
Since the number of non-negative allocations is 7 which is less than (m + n − 1) = 5 + 4 − 1 = 8, the solution is degenerate.
Therefore, there is a need for making one infinitesimal allocation. Out of the unoccupied cells, cell (4, 4) has the least cost of 0. The infinitesimal allocation should be made in this cell. However, allocating ε to this cell forms a closed loop among the cells (4, 2), (5, 2), (5, 4) and (4, 4), such that allocations in these cells do no remain in independent positions. Therefore no allocation is made in cell (4, 4). Next higher cost cell is (4, 3) with cost 1. Allocation in this cell also form a loop, So, we choose next highest cost, namely, 3 in the cell (5, 1). Let us make the allocation in cell (5, 1).
TABLE 4.51
The initial transportation cost
= [10 × 10 + 20 × 13 + 30 × 4 + 40 × 7 + ε × 3 + 20 × 12 + 20 × 5 + 10 × 19]
= (1290 + 3ε)
= 1290 as ε → 0.
(ii) Vogel’s approximation method: The starting solution in the method is given as:
TABLE 4.52
Since the number of non-negative allocations is 7 which is less than m + n − 1 = 8, the basic solution is a degenerate one. To resolve this degeneracy, allocate a very small quantity ε to the unoccupied cell (3, 1) so that the number of occupied cells becomes (m + n − 1).
Hence, the non-degenerate basic feasible solution is as shown in the following Table:
TABLE 4.53
The initial transportation cost
= [10 × 10 + 20 × 9 + 30 × 5 + 10 × 7 + 20 × 1 + 10 × 0 + 50 × 3 + 4ε]
= 670 + 4ε
= 670 as ε → 0.
Note: It is not possible to add ε to any unoccupied cells. ε must be added to those empty cells which makes it possible to determine a unique set u_{i} and v_{j}. Applying MODI’s method to find the optimal solution, the dual variables u_{i} and v_{j} are obtained from the c_{ij} values of the basic variables. If we do not choose the empty cell for the allocation of ε properly, it would not be possible to locate one or more c_{ij} value which should be equated to the corresponding u_{i} + v_{j}.
Example 2 Degeneracy at Intermediate Stage
Find the basic feasible solution of the following transportation problem by north-west corner rule. Also find the optimal transportation plan.
TABLE 4.54
Solution: Since a_{i} = _{bj} = 200, the problem is balanced. By following the north west corner rule (like Example 1(a) of Section 4.3), we get the non-degenerate initial basic feasible solution shown in Table 4.55.
TABLE 4.55
Required number of allocations = m + n − 1 = 4 + 5 − 1 = 8. Actual number of allocations = 8. Hence, the problem is non-degenerate.
To obtain optimal solution, apply MODI’s method. The results of the iterations are displayed.
First iteration:
TABLE 4.56
Second iteration: θ = min (40, 10, 10) = 10
TABLE 4.57
In the second feasible solution, the number of allocations = 6 ≠ (m + n − 1) = 8. Hence, this is a degenerate solution. It can be removed by allocating ε to cell (D, 3) which has the next cell evaluation −4. This can be shown in the following Table.
The final iteration is
TABLE 4.59
4.6 UNBALANCED TRANSPORATION PROBLEMS
We solved the various transportation problems with the assumption that the total supply at the origins is equal to the total requirement at the destinations. If they are unequal the problem is known as an unbalanced transportation problem. If the total supply is more than the total demand we introduce an additional column with zero cost. The excess supply is entered as a rim requirement for the dummy destination. Likewise, if the total demand is more than the total supply an additional row is introduced with zero cost, the excess demand is entered as a rim requirement for this dummy source. Hence, the unbalanced transportation problem is converted into a balanced transportation problem.
Example 1
A company has three plants at locations A, B, C which supply to warehouse located at D, E, F, G, and H. Monthly plant capacities are 800, 500 and 900 units, respectively. Monthly warehouse requirements are 400, 400, 500,, 400 and 800 units, respectively. Unit transportation costs (in ) are given below. Determine an optimum distribution for the company in order to minimise the total transportation cost.
TABLE 4.60
Solution: In this problem, a_{i} = 2200units, whereas b_{i} = 2500. So, the problem is an unbalanced one.
TABLE 4.61
So, introduce a dummy plant P having all transportation costs equal to zero and having the plant availability equal to (2500 − 2200) = 300 units. The modified table is shown in Table 4.62.
Using VAM the following IBFS is obtained.
TABLE 4.62
Since the number of occupied cells = 7 which is less than (m + n − 1) = 8, the solution is degenerate. To make the number of allocations equal to 8 introduce an infinitesimal quantity ε in the independent cell (2, 5). Now, test the current solution for optimality, by MODI’s method.
Starting iteration:
TABLE 4.63
Here, θ = min (500, ε, 300) = ε. So, enter the non-basic cell (4, c) and leave the basic cell (2, 5).
First iteration:
TABLE 4.64
θ = min (500 − ε, 500 − ε, 300 − ε) = 300 − ε
TABLE 4.65
Here, θ = min (200, 200 − ε) = 200 − ε
The third iteration is:
TABLE 4.66
Since all the net evaluations are non-negative, the optimum solution is
x_{13} = 0, x_{15} = 800, x_{21} = 400, x_{24} = 100, x_{32} = 400, x_{33} = 200, x_{34} = 300, x_{43} = 300.
The optimum transportation cost is given by
z = 0 × 6 + 800 × 3 + 400 × 4 + 100 × 6 + 400 × 4 + 200 × 6 + 300 × 6 + 300 × 0 = 9200.
Example 2
Three warehouse supply five stores. The table indicates the cost of shipment per unit between warehouse and stores, warehouse capacities and requirements of the stores. However, a major bridge has been damaged preventing deliveries from warehouse A to store 5, from warehouse B to store 2, and from warehouse C to store 4. Within these limitations determine the optimum delivery scheme to minimise cost.
TABLE 4.67
Solution: Here, total supply = 1600 units, total requirements = 900 units.
Since demand is less than the supply, a dummy warehouse D is created to absorb the additional supply of 700 units. The associated cost element will be zero. Further, to avoid allocation in cells (A, 5), (B, 2), (C, 4), a very heavy penalty, + M is allocated to these cells. The modified transportation matrix is shown in Table 4.68.
TABLE 4.68
Find the initial basic feasible solution by VAM: This is shown in Table 4.69.
TABLE 4.69
Initial transportation cost is
z = [75 × 2 + 345 × 3 + 90 × 4 + 90 × 4 + 250 × 0 + 90 × 3 + 210 × 6 + 450 × 0]
= [150 + 1035 + 360 + 360 + 270 + 1260]
= 3435
To find optimal solution, we use MODI’s method.
Starting iteration:
TABLE 4.70
Here, θ = min (450, 90, 210) = 90.
First iteration:
TABLE 4.71
θ = min (360, 120) = 120.
Second iteration:
TABLE 4.72
Since d_{ij} > 0 for all non-basic cells, the current solution is optimum. Hence,
x_{11} = 75, x_{12} = 345, x_{14} = 90, x_{16} = 340, x_{23} = 180, x_{26} = 120, x_{35} = 210, x_{36} = 240.
The minimum transportation cost is
z = [75 × 2 + 345 × 3 + 90 × 4 + 340 × 0 + 180 × 3 + 120 × 0 + 210 × 5 + 240 × 0]
= [150 + 1035 + 360 + 540 + 1050]
= 3135.
Example 3
The unbalanced transportation problem is given in Table 4.73.
TABLE 4.73
Since there is not enough supply, some of the demand at the destinations may not be satisfied. Suppose there are penalty costs for every unsatisfied demand unit which are given by 5, 3, 2 for destinations 1, 2, 3, respectively. Find the optimal solution.
Solution: In this problem, the demand exceeds the supply. The problem is unbalanced. Introduce a ‘dummy source’ whose transportation costs are given as 5, 3, 2, respectively, and supply is given as (145 − 105) = 40. The modified transportation table is given by Table 4.74.
TABLE 4.74
TABLE 4.75
Using VAM an initial basic feasible solution having the transportation cost 595 is obtained in Table 4.75. The optimum table is given by Table 4.76. The optimum transportation cost is
z = 10 × 1 + 60 × 6 + 10 × 4 + 10 × 6 + 15 × 3 + 40 × 2.
= 595.
TABLE 4.76
Example 4
A product is produced by four factories F_{1}, F_{2}, F_{3} and F_{4}. Their unit production cost are 2, 3, 1 and 5, respectively. Production capacity of the factories are 50, 70, 30 and 50 units, respectively. The product is supplied to four stores S_{1}, S_{2}, S_{3} and S_{4} the requirements of which are 25, 35, 105 and 20, respectively. Unit cost of transportation are given in Table 4.77. Find the transportation plan such that the total production and transportation cost is minimum.
TABLE 4.77
TABLE 4.78
Solution: Form the transportation table which consists of both production and transportation costs (see Table 4.78). The total capacity = 200 and the total demand = 185. The problem is an unbalanced one which is converted into a balanced one by adding a dummy store S_{5} with cost 0 and supply in excess is given to this store.
TABLE 4.79
The initial basic feasible solution is obtained by least cost method. The solution is non-degenerate.
The total transportation cost is
z = [4 × 25 + 6 × 5 + 8 × 20 + 10 × 50 + 8 × 20 + 4 × 30 + 13 × 55 + 0 × 15] = 1525.
Optimum solution by MODI’s method is obtained. The final iteration now becomes:
TABLE 4.80
Since all d_{ij} ≥ 0, the solution is optimum but an alternative solution exists with transportation cost as 1465.
4.7 MAXIMISATION IN TRANSPORTATION PROBLEMS
There are certain types of transportation problems where the objective function is to be maximised instead of being minimised. These problems can be solved by converting the maximisation problem into a minimisation problem by multiplying all the entries by − 1 or by subtracting all the entries from the highest entry in the transportation table. The modified minimisation problem can be solved in the usual manner.
Example 1
A company has four factories F_{1}, F_{2}, F_{3} and F_{4} manufacturing the same product. The production and raw material costs differ from factory to factory and are given in the Table 4.81. In the first two rows the transportation costs from the factories to the sales depots S_{1}, S_{2}, S_{3} are also given. The last two columns in the Table gives the sales price and the total requirement at each depot. The production capacity of each factory is given in the last row.
TABLE 4.81
Determine the most profitable production and distribution schedule and the corresponding profit. The deficit production should be taken to yield zero profit.
Solution: First, we construct a profit table in which
Profit = [Sales price/unit] − [Production cost/unit] − [raw material cost/unit] − [transportation cost/unit]
Profit from F_{1} to S_{1} = 34 − 15 − 10 − 3 = 6
Profit from F_{2} to S_{1} = 34 − 18 − 9 − 9 = − 2
Profit from F_{3} to S_{1} = 34 − 14 − 12 − 5 = 3
Profit from F_{4} to S_{1} = 34 − 13 − 9 − 4 = 8
Profit from F_{1} to S_{2} = 32 − 15 − 10 − 1 = 6
Similarly, we can calculate the other profits and get the profit matrix as
TABLE 4.82
Note that the total supply = 310 units and total requirement =350 units. The given problem is of maximisation of profit. Convert this into minimisation type by subtracting all the profit values from the highest profit of 8. Now, in order to make the problem balanced, a dummy factory d is introduced to meet the extra requirements with zero profit coefficients. This is depicted in Table 4.83.
TABLE 4.83
The problem is balanced. So, we get the IBFS.
We can obtain the initial basic feasible solution by VAM.
TABLE 4.84
Since the number of allocations = m + n − 1 = 5 + 3 − 1 = 7 the optimality test can be performed. By MODI’s method we can perform the optimality test which is shown in Table 4.85. Then, Table 4.86 gives the optimal solution.
TABLE 4.86
Total profit = [6 × 10 − 2 × 90 − 4 × 60 + 2 × 50 + 8 × 80 + 5 × 20 + 0 × 40]
= 480.
Example 2
There are three factories A, B, and C which supply goods to four dealers D_{1}, D_{2}, D_{3}, D_{4}. The production capacities of these factories are 1000, 700, 900 units per month, respectively. The requirements from the dealers are 900, 800, 500 and 400 units per month, respectively. The per unit return (excluding transportation costs) are 8, 7, 9, at the three factories. Table 4.87 gives the unit transportation cost from the factories to the dealers. Determine the optimum solution to maximise the profit.
TABLE 4.87
TABLE 4.88
Solution: Profit = Return − Transportation cost. Hence,
Profit from A to D_{1} = 8 − 2 = 6
Profit from A to D_{2} = 8 − 2 = 6
Profit from A to D_{3} = 8 − 2 = 6
Profit from A to D_{4} = 8 − 4 = 4
Profit from B to D_{1} = 7 − 3 = 4
Profit from B to D_{2} = 7 − 5 = 2 and so on.
Table 4.88 gives the profit matrix. The problem is a balanced one. The problem is of maximisation type. Convert this into minimisation by subtracting all the cost entries in Table 4.88 by the highest cost entry 8. Hence, the new table is given in Table 4.89.
TABLE 4.89
TABLE 4.90
We can find the initial basic feasible solution by VAM, which is shown in Table 4.90. Since the number of allocated cells = 5 < m + n − 1 = 6, the solution is a degenerated one. To resolve the degeneracy, add ε to the empty cell (1, 3) which does not form a path, and which is least cost cell. Now, optimality test can be performed using MODI’s method.
TABLE 4.91
TABLE 4.92
Since d_{ij} ≥ 0, the initial solution is optimum. The optimum distribution is shown in Table 4.92.
Total profit or the maximum return
= [6 × 200 + 6 × 800 + 4 × 700 + 7 × 500 + 8 × 400]
= 15,500.
4.8 THE TRANS-SHIPMENT PROBLEM
The transportation problem assumes that direct routes exist from each source to each destination. There are situations in which units may be shipped from one source to another or to other destinations before reaching their final destination. This is called a trans-shipment problem and is solved using a similar algorithm with a little modification. The points to be noted are:
- The number of sources and destination are say m and n, respectively in a transportation problem. In trans−shipment study, we have m + n sources and m + n destinations.
- If S_{i} denotes the i^{th} source, D_{j} the j^{th} destination, then commodity can move along the routes:
S_{i} → D_{i} → D_{j}
S_{i} → S_{j} → D_{i} → D_{j}
S_{i} → D_{i} → S_{j} → D_{j}
and so on. The transportation cost from S_{i} to S_{j} is zero and the transportation costs from S_{i} to S_{j} is different from S_{j} to S_{i}. Similarly, D_{i} → D_{j} ≠ D_{j} → D_{i}.
- In solving the trans-shipment problem, we first find the optimum solution to the transportation problem.
- The basic feasible solution contains 2m + 2n − 1 basic variables, if we omit the variables appearing in the (m + n) diagonal cells, we have only m + n − 1 basic cells.
The formulation and solution of a trans-shipment can be illustrated in Example 1 below.
Example 1
Consider a transportation problem where the sources are plants and destinations are depots. The unit transportation cost, capacity at the plants and the requirement at the depots are given below.
TABLE 4.93
If each plant is also considered as a destination and each depot is also considered as a source, then there are five sources and five destinations. Some additional cost data are given in Table 4.94, Table 4.95 and Table 4.96.
TABLE 4.94
TABLE 4.95
TABLE 4.96
Table 4.97 is the formulation of trans-shipment problem. A buffer stock of 450 which is the total capacity and total requirements in the original transportation problem is added to each row and column of the trans-shipment problem. The resulting transportation problem has m + n = 5 sources and 5 destinations. Solving the transportation problem in Table 4.97 as usual we obtain.
x_{11} = 150, x_{13} = 300, x_{14} = 150, x_{21} = 300, x_{22} = 450, x_{33} = 300, x_{35} = 150, x_{44} = 450, x_{55} = 450.
The description of the trans-shipment problem is
- Transport x_{21} = 300 units from plant B to A. This increases the availability at plants A to 450 units including the 150 units originally available from A.
- From plant A to depot X, transport x_{13} = 300
From plant A to depot Y, transport x_{14} = 150
From depot X to depot Z, transport x_{35} = 150
The total shipment cost is
1 × 300 + 3 × 150 + 1 × 300 + 1 × 150 = 1200.
If, however, the commodities are transported from plants A, B to depots X, Y, Z, according to Table 4.97, the minimum transportation cost is x_{13} = 150, x_{21} = 150, x_{22} = 150 with a minimum cost of 3450. Thus, the trans-shipment reduces the cost of cargo movement.
4.9 SENSITIVITY ANALYSIS IN TRANSPORTATION PROBLEM
So far we have seen problems which are valid only for a limited period. The capacities of the sources and/or requirements at the destinations may vary with time. Similarly, there may be changes in the transportation cost. Such changes may affect the optimal allocation and the minimum transportation cost associated with it.
One way to study the effect of changes in these parameters is to get a new optimal solution by modifying the current optimal solution and by carrying out iterations on it if necessary.
Example 1
Consider Example 5 of section 4.4, and solve the following:
(d) Suppose the supply from warehouse B reduces to 12 units and simultaneously the requirement of market III reduces to 14 units. Find the optimal transportation schedule.
(e) Further, suppose the supply from warehouse A also reduces to 18 units and simultaneously the requirement of market III reduces to 10 units. Will the optimal solution of part (d) change?
(f) Suppose the supply of warehouse B is increased [with respect to optimal solution of part (b)] by 1 unit and simultaneously the demand of market III is also increased by 1 unit. Will the optimal solution change?
(g) Suppose the supply of warehouse B increases by 3 units [instead of 1 unit in part (f)] and demand of market IV also increases by 3 units. Will there be change in the optimal solution?
Solution: (d) The modified transportation table is shown below.
TABLE 4.98
As there is no change in the allocated cells, the above modification does not change the optimal schedule.
(e) As the allocation in the cell (A, III) is 2 units, the adjustment is not possible by considering the cell (A, III) alone. Even if this allocation is cancelled and the allocation in cell (B, III) is also reduced to 10 units to match the requirement of market III, this allocation can cause imbalance in the allocated cells of B and C. So, it is necessary to solve the problem a new.
(f) Making necessary changes in Table 4.45, we get the modified table as [see Table 4.99]. We can see that the modified solution does not change the optimal schedule.
(g) Table 4.45 shows that it will not be possible to confirm the changes to allocated cells only. The optimal solution, therefore, changes and the problem has to be solved a new.
4.10 APPLICATIONS
Transportation problem arises in many practical applications. In the beginning it was formulated for determining the optimal shipping pattern. The main aim is to find the shortest (least-cost) route in a network. Such network problems have two-fold importance. They pertain to problems of product distribution. Consequently, they are economically significant for many commercial enterprises that operate several plants and hold inventory in local warehouses. The mathematical characteristics of network models are so special that by exploiting these structural properties we obtain major efficiencies in finding optimal solutions. In actual industrial applications, network models contain thousands of activities and hundreds of constraints, so that using a streamlined algorithm, is not only worthwhile but sometimes a practical necessity.
We present a specific application here.
Example 1
A canning company operates two canning plants, A and B. Three growers are willing to supply the following amounts of fresh fruits:
Kumar | 200 tons at 100 per ton |
Raja | 300 tons at 90 per ton |
Vimal | 400 tons at 80 per ton |
Shipping costs in rupees per ton are as given in Table 4.100.
TABLE 4.100
From | To | |
---|---|---|
Plant A | Plant B | |
Kumar | 20 | 20.50 |
Raja | 10 | 10.50 |
Vimal | 50 | 30.00 |
Plant capacities and labour costs are as follows:
Plant A | Plant B | |
---|---|---|
Capacity | 450 tons | 550 tons |
Labour cost | 25/ton | 20/ton |
The canned fruits are sold at 250 per ton to the distributors. The company can sell at this price the entire quantity it produces. How should the company plan its operations at the two plants so as to maximise its profits?
Solution: First, we formulate this as an LPP.
x_{KA} = Quantity shipped from Kumar to plant A
x_{KB} = Quantity shipped from Kumar to plant B
x_{RA} = Quantity shipped from Raja to plant A
x_{RB} = Quantity shipped from Raja to plant B
x_{VA} = Quantity shipped from Vimal to plant A
x_{VB} = Quantity shipped from Vimal to plant B.
The supply constraints are given by
x_{KA} + x_{KB} ≤ 200
x_{RA} + x_{RB} ≤ 300
x_{VA} + x_{VB} ≤ 400
The constraints on plant capacities are
x_{KA} + x_{RA} + x_{VA} ≤ 450
x_{KB} + x_{RB} + x_{VB} ≤ 550.
All the variables are restricted to be non-negative.
To compute the net profit for each of the variables, we have to subtract from the selling price the cost of fresh fruits, shipping and labour costs. Hence, we get
P_{KA} = 250 − (100 + 20 + 25) = 105 per ton.
Similarly, the other profits can be calculated and the objective function is to maximise
Z = 105x_{KA} + (109.5)x_{KB} + 125x_{RA} + (129.50)x_{RB} + 95x_{VA} + 120x_{VB}.
The above LPP is an unbalanced TP where the total supply is less than the total demand; so, a dummy row is added with supply 100.
Now solve the problem as usual. Finding the optimal solution is left as an exercise.
EXERCISES
Sections 4.1 and 4.2
1. Describe the matrix form of the transportation problem. Illustrate with 2 origins and 3 destinations.
2. Show that all bases for transportation problem are triangular.
3. What do you mean by an unbalanced transportation problem and explain how to convert the unbalanced transportation problem into a balanced one.
4. Explain degeneracy in a transportation problem and how to resolve it.
Section 4.3
5. Solve the following transportation problem:
[Answer: x_{13} = 10, x_{23} = 15, x_{31} = 20, x_{32} = 15, x_{33} = 5. The transportation cost is 130.]
6. Determine an IFBS using (a) North-West Corner Rule, (b) VAM.
[Answer : (a) North-West Corner Rule: x_{11} = 3, x_{12} = 1, x_{22} = 2, x_{23} = 4, x_{24} = 2, x_{34} = 3, x_{35} = 6, with cost = 153.]
(b) Vogel’s Method: x_{14} = 4, x_{22} = 2, x_{25} = 6, x_{24} = 3, x_{32} = 1, x_{33} = 4, x_{34} = 1, cost = 68.]
7. Goods have to be transported from factories F_{1}, F_{2}, F_{3} to warehouses W_{1}, W_{2}, W_{3} and W_{4}. The transportation cost per unit, capacities and requirement of the warehouses are given in the Table.
Find the distribution with minimum cost. Obtain an IFBS to the following transportation problem.
[Answer: By least cost method IFBS is given below]
Section 4.4
8. Solve the transportation problem
[Answer: Optimal solution is given in the above table]
9. The following Table gives the cost for transportation material from supply points A, B, C, D to demand points E, F, G, H, J.
The present allocation is as follows.
A to E is 90; A to F is 10; B to F is 150; C to F is 10; C to G is 50, C to J is 120, D to H is 210; D to J is 70.
- Check whether this allocation is optimum. If not, find an optimum schedule.
- If in the above problem the transportation cost from A to G is reduced to 10, what will be the new optimum schedule?
[Answer: (a) No. The optimum schedule is: x_{12} = 100, x_{22} = 70, x_{25} = 80, x_{31} = 70, x_{33} = 50, x_{31} = 40, x_{44} = 210, x_{45} = 70, with minimum cost = 6810.]
(b) Same as part (a).
10. A company has three plants A, B, C, three warehouses X, Y, Z. The number of units available at the plants is 60, 70, 80 and the demand at X, Y, Z are 50, 80, 80, respectively. The unit cost of the transportation is given in the following Table.
Find the allocation so that the total transportation cost is minimum.
[Answer: By least cost method, the IBFS is
x_{13} = 50; x_{21} = 50; x_{23} = 20; x_{32} = 80 with cost 750.]
Optimal solution is same as IBFS.
11. Solve the following transportation problem
Section 4.5
12. A company has four warehouses and six stores, the cost of shipping one unit from warehouse i to store j is c_{ij}.
The requirements of six stores are 4, 4, 6, 2, 4, 2 and qualities at warehouse are 5, 6, 2, 9. Find the minimum cost solution.
[Answer: x_{13} = 5, x_{22} = 4, x_{26} = 2, x_{31} = 1, x_{32} = ε, x_{33} = 1, x_{41} = 3, x_{44} = 2, x_{45} = 4 and the optimal transportation cost = (68 + 3ε) = 68.]
13. Solve the following transportation problem,
[Answer: x_{11} = 1, x_{21} = 3, x_{31} = ε, x_{32} = 2, and x_{33} = 2, and minimum transportation cost = 743.]
14. Solve the following transportation table using Vogel’s approximation method.
[Answer: x_{13} = 5, x_{22} = 4, x_{26} = 2, x_{31} = 1, x_{32} = ε, x_{33} = 1, x_{41} = 3, x_{44} = 2, x_{45} = 4 and the minimum transportation cost is 112.]
Section 4.6
15. Solve the transportation problem
[Answer: x_{11} = 65, x_{12} = 5, x_{22} = 30, x_{23} = 25, x_{33} = 25, x_{34} = 45, x_{41} = 20, minimum cost = 1010.]
16. Solve the following transportation problem
[Answer: x_{13} = 35, x_{14} = 15, x_{24} = 10, x_{25} = 30, x_{31} = 30, x_{32} = 25, x_{34} = 15, minimum cost = 1130.]
17. Solve the transportation problem
[Answer: x_{11} = 140, x_{13} = 60, x_{22} = 50, x_{24} = 100, x_{34} = 120, x_{42} = 70, x_{43} = 20, the minimum cost is 2940.]
Section 4.7
18. Solve the following transportation problem to maximise the profit.
[Answer: x_{11} = 20, x_{14} = 30, x_{15} = 50, x_{21} = 20, x_{23} = 10, x_{32} = 20, x_{33} = 50, optimum profit = 5130.]
19. Consider four bases of operations B_{i} and three targets T_{j}. The tons of bombs per aircraft from any base that can be delivered to any target are given in the following Table.
The daily sortie capacity of each of the four bases is 150 sorties per day. The daily requirement in sorties over each individual target is 200. Find the allocation of sorties from each base to each target which maximises the total tonnage over all the three targets explaining each step.
[Answer: x_{11} = 50, x_{12} = 50, x_{23} = 150, x_{31} = 150, x_{42} = 150 maximum tonnage = 4250.]
Section 4.8
20. Consider the following trans-shipment problem with two sources and two destinations, the costs for shipment in rupees are given below. Determine the optimum shipping schedule.
21. Consider the following trans-shipment problem with two sources and three destinations. The costs per unit for shipment in rupees are also given. Find the optimum shipping schedule.
22. Given the following data, find the optimum transportation routes.