Метод аппроксимации Фогеля

Еще более близкий к оптимальному план может быть получен с использованием метода аппроксимации Фогеля.

Этот метод принято сокращенно обозначать МАФ.

Метод является эвристическим, т.е. интуитивным, не обоснованным строго. Следует отметить, что во многих случаях план, полученный с его помощью, совпадает с тем, который получается при использовании метода наименьшей стоимости.

Алгоритм метода состоит в следующем:

1). Рассматривая матрицу затрат на перевозки, вычисляют штрафы для строк и столбцов, вычитая наименьший элемент строки (столбца) из следующего за ним по величине элемента этой же строки (столбца).

2). Выбирают столбец (строку) с наибольшим штрафом (если их несколько, то любой(-ую) из них). В нем (ней) выбирают клетку с наименьшим коэффициентом целевой функции и заполняют ее (алгоритм заполнения, пересчета свободных членов и исключения строки (столбца) такой же, как и в ранее рассмотренных двух методах).

3). Для оставшихся столбцов (строк) с ненулевыми свободными членами снова вычисляют штрафы и возвращаются к пункту 2, и так пока все клетки не будут исключены из рассмотрения.

4). Если из рассмотрения не исключены только столбцы (строки) с нулевыми свободными членами, к ним применяют метод наименьшей стоимости.

Для рассматриваемого примера наибольшим штрафом будет 14 – для Стокгольма. Из этого центра производства дешевле всего поставлять продукцию в дополнительный центр сбыта (не поставлять никуда) - с₁₃ = 0. Поэтому примем x₁₃ = 10:

При пересчете штрафов оказывается, что наибольший снова соответствует Стокгольму. Теперь из него дешевле всего поставлять продукцию в Лион, и эти поставки следует принять равными 90 (x₁₂ = 90):

	Лейпциг	Лион	дополнительный центр сбыта	ai	штраф
				120	25-14=
Стокгольм				110 20	=11
Триест					18-8=10
Руан					12-6=6
bj	150
штраф	18-12=6	8-6=2

Наибольший штраф (25) по-прежнему в первой строке. Следовательно, оставшиеся в Стокгольме 20 установок будут перевезены в Лейпциг (x₁₁ = 20). После этого наибольший штраф будет соответствовать Триесту, откуда следует перевезти 40 установок в Лейпциг (x₂₁ = 40). Недостающие после этого в Лейпциге 90 установок будут поставлены из Руана (x₃₁ = 90):

	Лейпциг	Лион	дополнительный центр сбыта	ai	штраф
				120
Стокгольм				110 20
Триест
Руан
bj	150 130 90
штраф	18-12=6

Подставив полученный план в целевую функцию, легко убедиться, что он еще дешевле – 3560 ф.ст. Более того, как будет показано в дальнейшем, этот план является и оптимальным, т.е. в данном случае методом аппроксимации Фогеля сразу получено решение задачи, что для задач небольшой размерности случается очень часто. Однако, в общем случае это не так, и оптимальное решение следует искать методом потенциалов.

Можно доказать, что план, построенный любым из трех перечисленных методов, будет действительно опорным (т.е. что систему ограничений можно привести к такому виду, что столбцы коэффициентов при ненулевых переменных будут линейно независимы) [1, 14].