Saturday, 10 May 2014

Transportation Model

Hungarian Assignment method

1. Subtract row elements from minimum of that row.
2. Subtract column elements from minimum of that column.
3. More than one zero either row-wise or column-wise are treated as one allocation.
For ex: If there are 3 zeros column wise...chk row-wise for 3 zeros and draw a straight line crossing all elements in that row.
After checking all rows.
chk column-wise for 3 zeros.
repear for all columns.
4. If the number of straight lines < row/columns ..indicates optimal solution has not been reached.
5. Find the minimum of remaining elements not crossed by straight lines.
6. subtract the remaining elements from this minimum and add the minimum to the intersection elements of straight lines.
7. repeat step 3.
8. start from first row until u find a row with one zero and assign that machine to that task
and cross off all other zeros for that machine
repeat it column-wise and row-wise.


Transportation Model

Always chk if total demand and total supply are equal.
else add a dummny column/row with zero transportation cost.
Question:  Find the feasible solution using Least Cost Method (LCM)
Ans:
1. Find the minimum transportation cost and allocate as much as possible until either supply=0 or demand=0;
Repeat until all the supply and demand becomes zero.

Question:  Find the feasible solution using North West Corner Method(NWCM)
1. Start with first row first column element and allocate units = supply/demand which ever is minimum
2. If the demand is fully met and supply is still there...move row-wise to next cell
3. else if supply is over and demand still there, move down column-wise
4.else if both supply and demand are zero, move diagonal wise to next row, next column element.

Question:  Find the feasible solution using Vogel's approximation method
Answer:
1. For each row and column, calculate the difference between minimum and next minimum
2. Find the column/ row with largest difference and
find the least transportation cost in that column/row and allocate as much as possible.
3. cross off all elements in row/column if supply=0 /demand=0;
4. repeat step 2 and 3.

For LCM, NWCM and Vogel's approximation method,
find the total cost by making a table as shown below
----------------------------------------------------------------------------------------------------------------------------------------
    Shipped               Units Shipped                  Cost/Unit(Rs. )              Total Cost (Rs. )
From     To                      (A)                                 (B)                                 (A*B)
-----------------------------------------------------------------------------------------------------------------------------------------

To check whether the solution from the above methods is optimal or not..
1. Do Acceptability test
    i. chk if number of allocations = number of rows * number of columns -1
        if not (degenrate solution case) put a dummy to one or more independent water square( in case of many, choose the one with minimum per unit transportation cost.
      
    ii. chk if all allocated squares/stone squares are independent or not.
        start from a stone cell and move either horizontally or verically and see if you can reach back to the stone cell from where u started without traversing  back.
        if not..then independent
        else degeneracy
2. If it passed Acceptability test, then perform optimality test.
    two methods
        Stepping stone
        Modified Distribution method (also known as MODI or U-V method)

Stepping stone method
1. For each water square,
by moving horizontally or vertically (rectilinear motion) to a stone square and making right angles at stone squares..traverse bact to the starting square.
2. Put a + and negative sign alternatively across the path
3. add all the transportation costs

4. if for all water squares, if all positive ...then optimal solution
else pick up the square with largest -ve value and repeat step 1 and step 2
find the minimum allocation of the -ve side and subtract from the -ve side allocation and
add the same to the +ve allocations
 5. Repeat all the above steps

Case: Multiple optimal solution
and each solution has same total cost.

No comments:

Post a Comment