Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Transportation problem

  1. May 11, 2006 #1
    Suppose we are asked to find the basic feasible solution for maximizing transportation cost using Vogel approximation method (VAM). We then convert it into minimization type by changing the sign of values in the cost matrix. We then write the row penalty and column penalty. Suppose there is tie between 2 penalty values, which should be taken first? I have this doubt because I get 2 different solutions in each case.
    If the question was minimization type and if there is a tie we would take that penalty corresponding to which there is minimum cost. If I apply the same rule in maximization type question, I get a solution which is less than the other solution (i.e. suppose solution obtained by applying the rule is 1000 and the other solution is 1200, this solution(1000) is not appropriate as the question is to obtain maximum cost).
  2. jcsd
  3. May 11, 2006 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If you are working on a maximization problem, you can either :

    (i) Change the sign of the costs and apply the minimization method; or

    (ii) Determine the row/column with largest penalty (calculated as highest cost - next highest cost) and apply the maximum allowed amount to the cell with the highest cost in that row/column.

    Either of these two methods should give you a basic feasible solution.

    Now, you say you did the first thing and got a less optimal solution by breaking the tie by choosing the cell with the lower cost. This is possible.

    Remember that VAM is only a heuristic for determining a starting point. There is no reason to expect it to produce the best starting solution either. It is unlikely to produce the result that happened in your case, but it is not impossible.

    So, don't worry about it. If I were you, I'd simply pick the assignment that produced the larger transportation cost, and move on to the optimixation from there. It wouldn't bother me so much that I had to deviate from the method suggested by Vogel.

    Alternatively you can start with the other BSF (the lower one, that is got by strictly following Vogel), but it might take a couple more steps of iteration before you get to the optimal solution.

    Mostly, my choice would depend on whether my grader/prof was a person that encouraged or discouraged improvization.

    PS : There's also the small chance that you made a numerical mistake. If you supply the cost matrix and the constraints, someone can double-check your result.

    PPS : Why do you begin your post with "Sir" ? Do you not think there are any women trained in Operations Research ?
    Last edited: May 11, 2006
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook