Vogel's approximation method

from Wikipedia, the free encyclopedia

The Vogelsche approximation method is a heuristic method in the field of operations research for solving a transport problem . This method is characterized by the fact that it comes very close to the optimum . However, the effort is compared to other methods, such as B. the north-west corner method or the matrix minimum method , comparatively high.

algorithm

  1. First, an auxiliary matrix with the opportunity costs , which consist of the difference between the two smallest values of each row and column created.
  2. Then the row or column with the highest opportunity costs is found in the auxiliary matrix.
  3. The lowest value is then found from this row or column. The maximum possible capacities are assigned to this field in the original matrix.
  4. If the supply or demand quantity is exhausted, the relevant column or row in the original matrix is ​​padded with zeros and deleted in the auxiliary matrix.
  5. After each pass, the opportunity costs are recalculated and the assignment starts all over again.
  6. This method ends when all capacities are allocated.

Web links