Суть метода аппроксимации Фогеля заключается в следующем. Для каждой строки и для каждого столбца находим разности между двумя записанными в них минимальными тарифами. Полученные разности записываем в специально отведенные для этого столбце и в строке в таблице условий задачи.
Среди указанных разностей выбираем максимальную. В строке (или в столбце), которой данная разность соответствует, определяем минимальный тариф. Клетку, в которой он записан заполняем на данной итерации.
Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбираем ту клетку, которая соответствует наибольшей разности между двумя минимальными тарифами в данном столбце (строке).
Применение метода аппроксимации Фогеля позволяет получить либо опорный план, близкий к оптимальному, либо сам оптимальный план.
Рассмотрим метод аппроксимации Фогеля на примере 2, рассмотренной выше.
Пример 3. Найти опорный план транспортной задачи, представленной в таблице условий ниже методом аппроксимации Фогеля:
 .
|
Число пунктов отправления m =3, а число пунктов назначения n =4. Следовательно опорный план задачи определяется числами, стоящими в m+n −1=3+4−1=6 заполненных клетках таблицы. Тарифы перевозок единицы груза из каждого пункта отправления во все пункты назначения задаются матрицей
 .
|
Наличие груза у поставщиков равно: 
.
Общая потребность в грузе в пунктах назначения равна: 
.
Модель транспортной задачи является закрытой. Следовательно, она разрешима.
Для каждой строки Ai найдем разности между двумя минимальными тарифами, записанными в данной строке и поместим их в соответствующем дополнительном столбце.
В строке 1 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1. В строке 2 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В строке 3 минимальный тариф равен 3, а следующий за ним равен 3, разность между ними 3−3=0.
Для каждого столбца Bj найдем разности между двумя минимальными тарифами, записанными в данном столбце и поместим их в соответствующей дополнительной строке.
В столбце 1 минимальный тариф равен 2, а следующий за ним равен 3, разность между ними 3−2=1. В столбце 2 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1. В столбце 3 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В столбце 4 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1.
Вычислив все разности выберем наибольшую из них. В данном случае наибольшая разница равна 2. В этом столбце минимальный тариф равен 1 и находится в пересечении строки A 1 и столбца B 3. Следовательно заполняем эту клетку.
A 1> B 3. Следовательно в клетку помещаем число 70. Потребности пункта B 3 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B 3 и будем считать запасы пункта A 1 равными 150−70=80.
 .
|
Для каждой строки Ai найдем разности между двумя минимальными тарифами, записанными в данной строке и поместим их в соответствующем дополнительном столбце.
В столбце 1 минимальный тариф равен 2, а следующий за ним равен 3, разность между ними 3−2=1. В столбце 2 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1. В столбце 3 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В столбце 4 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1. В строке 1 минимальный тариф равен 2, а следующий за ним равен 2, разность между ними 2−2=0. В строке 2 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В строке 3 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1.
Для каждого столбца Bj найдем разности между двумя минимальными тарифами, записанными в данном столбце и поместим их в соответствующей дополнительной строке.
В столбце 1 минимальный тариф равен 2, а следующий за ним равен 3, разность между ними 3−2=1. В столбце 2 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1. В столбце 4 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1.
Вычислив все разности выберем наибольшую из них. В данном случае наибольшая разница равна 2. В этой строке минимальный тариф равен 1 и находится в пересечении строки A 2 и столбца B 4. Следовательно заполняем эту клетку.
A 2> B 4. Следовательно в клетку помещаем число 40. Потребности пункта B 4 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B 4 и будем считать запасы пункта A 2 равными 100−40=60.
 .
|
Таким образом, продолжая процедуру в m+n−1-ом шаге получим:
 .
|
Запишем полученный опорный план:
 .
|
При этом плане стоимость перевозок вычисляется так:
F= 2·40+3·40+1·70+ 4·60+1·40+3·100=850.