Метод Фогеля

Метод Фогеля часто позволяет найти более оптимальное начальное допустимое решение, чем метод северо-западного угла и метод минимального элемента.

Алгоритм метода.

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

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

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

Таблица 24

Условие задачи

Пункты назначения Пункты отправления	B1	B2	B3	B4	Запасы груза
A1				8
А2
A3		4
A4		5
A5		6
Потребности в грузе

Решим задачу из табл. 24 методом Фогеля. Вычислим штрафы для всех строк и столбцов. Несколько строк и столбцов имеют макси­мальный штраф — единицу, поэтому из них можно выбрать любую строку или столбец. Выберем, например, строку A₃, содержащую минимальный тариф с₃₂ = 4. Предпочтение отдано строке A₃, а не строке A₄ так как перевозка х₃₂ = а₃ = 30 сразу же позволяет вывезти большее количество груза. Запасы пункта A₃ исчерпаны полностью, и строка A₃ исключается из дальнейшего рассмотрения (табл. 25). В пункт В₂ следует перевезти еще b₂ - х₃₂ = 5 единиц груза.

Повторим итерационный процесс, но без строки A₃. Вычислим штрафы. Максимальный штраф равен 1, поэтому выберем строку A₄, так как в ней находится клетка с минимальным тарифом с₄₄ = 4, и запишем в нее перевозку х₄₄ = а₄ = b₄= 15. Строка A₄ и столбец В₄ не рассматриваются далее.

Таблица 25

Метод Фогеля

Пункты назначения Пункты отправления

B1

B2

B3

B4

Запасы груза

A1

–

8 –

1,1,1,1,–

А2

–

–

1,1,1,1,1

A3

–

4

–

–

1,–

A4

–

5 –

–

1,1,–

A5

–

6 –

–

1,1,1,0,0

Потребности в грузе

0,0,0,–

1,1,1,1,1

0,0,0,0,2

1,1,–

Третий шаг итерации. На этом шаге не рассматриваются строки A₃, A₄ и столбец В₄. Для оставшихся строк и столбцов снова вычисля­ются штрафы. Строки A₁ и A₅ соответствуют максимальному штрафу и содержат клетки с минимальным тарифом 5. Выберем строку A₁ и внесем в клетку A₁В₁ перевозку x₁₁= b₁= 15. Столбец В₁ далее не учитываем. Отметим, что из пункта A₁ следует еще вывезти b₁- х₁₁ = 5 единиц груза.

Следующий шаг итерации. Строки A₃, A₄ и столбцы В₁, В₄ исключе­ны из расчетов. Столбец В₂ и строка A₁ характеризуются штра­фом 1 и содержат минимальный тариф 6. Выберем строку A₁ так как ей соответствует максимально возможная перевозка х₁₃ = а₁ – х₁₁= 5. Строку A₁ исключаем. В пункт В₃ следует довезти b₃ – х₁₃ = 15 единиц груза.

Пятый шаг итерации. На этом шаге итерации остались строки A₂, A₅ и столбцы В₂, В₃, для которых вычисляется штраф. Столбцу В₃ приписывается максимальный штраф 2. Наименьший тариф с₁₅ = 6 име­ет перевозка, соответствующая клетке A₅В₃, для которой х₅₃ = а₅ = 10. В итоге из рассмотрения исключается строка A₅.

В результате осталось рассмотреть только строку A₂ (столбцы В₂ и В₃ содержат по одной незаполненной клетке). Из пункта A₂ выво­зится 25 единиц груза, который доставляется в пункт В₂ в количест­ве х₂₂ = b₂ - x₃₂ = 5 и в пункт В₃ - х₂₃ = b₃ - х₅₃ - х₁₃ = 20.

Стоимость полученного допустимого плана

Сравним план, полученный методом Фогеля с планами, получаемыми методами северо-западного угла и минимального элемента.

Таблица 26

Метод северо-западного угла

Пункты назначения Пункты отправления	B1	B2	B3	B4	Запасы груза
A1			–	8 –
А2	–		–	–
A3	–	4		–
A4	–	5 –
A5	–	6 –	–
Потребности в грузе

Таблица 27

Метод минимального элемента

Пункты назначения Пункты отправления	B1	B2	B3	B4	Запасы груза
A1		–		8 –
А2	–	–		–
A3	–	4	–	–
A4	–	5 –	–
A5	–	6		–
Потребности в грузе

В результате проведенных вычислений видно, что допустимый план, найденный методом Фогеля, дает наиболее оптимальный результат. Это объясняется тем, что при поиске анализируются не только тарифы, но и потери, которые могут получиться, если не воспользоваться минимальным тарифом в строке или столбце.