Алгоритм метода Фогеля

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

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

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

Вычислим штрафы для всех строк и столбцов. Максимальный штраф равен 7, поэтому выберем строку А₁, в ней клетку с минимальным тарифом с₁₅ и запишем в нее 1. Строка А₁ и столбец B₅ не рассматриваются далее.

Повторим итерационный процесс, вычислим штрафы. Максимальный штраф равен 5, поэтому выберем строку А₂, в ней клетку с минимальным тарифом с₂₄ и запишем в нее 1. Строка А₂ и столбец B₄ не рассматриваются далее.

На этом шаге не рассматриваются строки А₁, А₂ и столбцы B₄, B₅. Для оставшихся строк и столбцов снова вычислим штрафы. Максимальный штраф равен 4, поэтому выберем столбец B₂, в нем клетку с минимальным тарифом с₅₂ и запишем в нее 1. Строка А₅ и столбец B₂ не рассматриваются далее.

На этом шаге не рассматриваются строки А₁, А₂, А₅ и столбцы B₂ ,B₄, B₅. Строка А₃ и столбец B₁ имеют максимальный штраф – 3, поэтому из них можно выбрать любой. Выберем строку А_3, содержащую минимальный тариф с₃₃ = 4 и запишем в нее 1. Строка А₃ и столбец B₃ не рассматриваются далее.

В результате остались строка А₄ и столбец B₁. На их пересечении – клетка, содержащую минимальный тариф с₄₁ = 4, запишем в нее 1. В результате получим начальный опорный план, представленный в таблице 2.7.2.

В нашем случае число заполненных клеток должно быть

т + п – 1 = 5 + 5 – 1 = 9.

Заполненными являются только 5 клеток, т.е. опорный план транспортной задачи является вырожденным. Недостающие поставки заполним нулями. Применяя метод потенциалов, получим, что начальный опорный план, построенный по методу Фогеля, является оптимальным.

Таблица 2.7.2

места исполнители	B1	B2	B3	B4	B5	Штрафы	ui
А1	10 (-)	13 (-)	9 (-)	11 (-)	2 1	7 -	0
А2	9 (-)	12 (-)	8 (-)	3 1	4 0	1, 5 -	2
А3	7 (-)	5 (-)	2 1	5 (-)	8 (-)	1, 1, 1, 3-	2
А4	4 1	6 (-)	4 0	7 (-)	9 (-)	2, 2, 2, 0	2
А5	8 (-)	1 1	3 0	2 0	6 (-)	1, 1, 1 -	1
Штрафы	3,3,3,3	4,4,4-	1,1,1,0-	1,1 -	2 -
vj	2	0	2	1	2

Суммарные затраты при таких назначениях определяются исходными затратами:

z = 2 + 3 + 2 + 4 + 1 = 12.

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