Метод Фогеля

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

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

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

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

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

Таблица 24

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

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

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

Таблица 25

Метод Фогеля

Третий шаг итерации. На этом шаге не рассматриваются строки 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

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

Таблица 27

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

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