Embedded Files
Transportation and Assignment Problems.
Transportation and Assignment Problems.
Transportation Problems.
Transportation Problems.
A transportation problem involves supply, demand, and transportation costs. A supplier makes enough of a product to meet the demands of other companies. The supply must be delivered to the different companies, and the supplier wishes to minimize the shipping cost, while satisfying demand.
The amount of product available and the requirements are shown on the right side and the bottom of a table. These numbers are called rim conditions. A table showing costs (in the upper right-hand corner of a cell) and rim conditions form a tableau.
Each cell is indicated by its row and column. For example, the cell with a cost of 3 is cell (I, 2).
The northwest corner rule (NCR) involves the following.
● Locate the cell in the far top left (initially that will be cell (I,1) ).
● Cross out the row or column that has the smallest rim value for that cell.
● Place that rim value in that cell and reduce the other rim value by that smaller value.
● Continue that process until you get down to a single cell.
● Calculate the cost of this solution.
Example 1:
Apply the Northwest Corner Rule to the following tableau and determine the cost associated with the solution.
The Cost is 5(6) + 1(5) + 2(1) + 5 (2) = 30 + 5 + 2 + 10 = 37
The indicator value of a cell C (not currently a circled cell) is the cost change associated with increasing or decreasing the amount shipped in a circuit of cells starting at C. It is computed with alternating signs and the costs of the cells in the circuit.
Example 2:
Determine the indicator value of the non-circled cells in the last example.
Solution:
The indicator value for cell ( ) I,3 is 1− 6 + 5 - 2 = -2
The indicator value for cell ( ) I,2 is 4 − 6 + 5 - 1 = 2.
Improving on the Northwest Corner Rule.
If some indicator cells are positive and some are zero, there are multiple solutions for an optimal value.
The stepping stone method improves on some non-optimal feasible solution to a transportation problem. This is done by shipping additional amounts using a cell with a negative indicator value.
Example
Apply the stepping stone algorithm to determine an optimal solution. Consider both cells with negative indicator values, determine the new cost for each consideration and compare to the solution found using the Northwest Corner Rule.
Solution:
Increasing the amount shipped through cell ( ) I,3 , we have the following.
The cost is 5(1) + 0(2) + 2(1) + 6(5) = 5 + 0 + 2 + 30 = 37
The cost can be reduced to 37 (compared to 47) when increasing the amount shipped through cell ( 1,3).
Exercises for Further Understanding!
Exercises for Further Understanding!
Problem 1:
Apply the Northwest Corner Rule to the following tableau to determine the cost associated with the solution.
Assignment Problems.
Assignment Problems.
An assignment problem is a particular case of transportation problem. The objective is to assign a number of resources to an equal number of activities . So as to minimize total cost or maximize total profit of allocation. The problem of assignment arises because available resources such as men, machines etc. have varying degrees of efficiency for performing different activities, therefore, cost, profit or loss of performing the different activities is different.
Hungarian Method (Assignment Algorithm)
First check whether the number of rows is equal to number of columns, if it is so, the assignment problem is said to be balanced. Then proceed to step 1. If it is not balanced, then it should be balanced before applying the algorithm.
Step 1: Subtract the smallest cost element of each row from all the elements in the row of the given cost matrix. See that each row contains at least one zero.
Step 2: Subtract the smallest cost element of each column from all the elements in the column of the resulting cost matrix obtained by step 1 and make sure each column contains at least one zero.
Step 3: (Assigning the zeros)
(a) Examine the rows successively until a row with exactly one unmarked zero is found. Make an assignment to this single unmarked zero by encircling it. Cross all other zeros in the column of this encircled zero, as these will not be considered for any future assignment. Continue in this way until all the rows have been examined.
(b) Examine the columns successively until a column with exactly one unmarked zero is found. Make an assignment to this single unmarked zero by encircling it and cross any other zero in its row. Continue until all the columns have been examined.
Step 4: (Apply Optimal Test)
(a) If each row and each column contain exactly one encircled zero, then the current assignment is optimal.
(b) If atleast one row or column is without an assignment (i.e., if there is at least one row or column is without one encircled zero), then the current assignment is not optimal. Go to step 5. Subtract the smallest cost element of each column from all the elements in the column of the resulting cost matrix obtained by step 1 and make sure each column contains at least one zero.
Step 5: Cover all the zeros by drawing a minimum number of straight lines as follows:
(a) Mark the rows that do not have assignment.
(b) Mark the columns (not already marked) that have zeros in marked rows.
(c) Mark the rows (not already marked) that have assignments in marked columns.
(d) Repeat (b) and (c) until no more marking is required.
(e) Draw lines through all unmarked rows and marked columns. If the number of these lines is equal to the order of the matrix then it is an optimum solution otherwise not.
Step 6: Determine the smallest cost element not covered by the straight lines. Subtract this smallest cost element from all the uncovered elements and add this to all those elements which are lying in the intersection of these straight lines and do not change the remaining elements which lie on the straight lines.
Step 7: Repeat steps (1) to (6), until an optimum assignment is obtained.
EXAMPLE 1:
Solve the following assignment problem shown in Table using Hungarian method. The matrix entries are processing time of each man in hours.
Solution:
The given problem is balanced with 5 job and 5 men.
Subtract the smallest cost element of each row from all the elements in the row of the given cost matrix. See that each row contains atleast one zero.
Subtract the smallest cost element of each Column from all the elements in the Column of the given cost matrix. See that each Column contains atleast one zero.
Assigning the zeros, we have the following A =
Since each row and each column contain exactly one encircled zero, then the current assignment is optimal.
Where the optimal assignment is as 1 to II , 2 to IV , 3 to I , 4 to V and 5 to III.
The optimal z = 15 + 14 + 21 + 20 + 16 = 86 hours.
Exercises For Further Understanding!
Exercises For Further Understanding!
Problem 1:
Solve the following assignment problem shown in Table using Hungarian method. The matrix entries are processing time of each Job to each machine in hours.
Page updated
Report abuse