В чем состоит особенность метода фогеля

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

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

Метод аппроксимации Фогеля лишен выше указанных недостатков, однако довольно сложен для исполнения по сравнению двумя предыдущими методами.

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

На каждой итерации вычисляют по всем столбцам и строкам разность между двумя записанными в них минимальными тарифами,

Среди указанных разностей выбирают максимальную.

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

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

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

Рассмотрим процесс составления опорного плана по методу Фогеля. На первом шаге разности между двумя соседними минимальными тарифами равны для строк (2-1=1. 5-4=1, 3-2=1), для столбцов (7-4=3, 5-2=3, 3-1=2, 6-2=4). Максимальная разность имеет место для четвертого столбца (4). Заполняем клетку А₁B₄, удовлетворив всю потребность четвертого предприятия, в результате чего у первого поставщика останется 50 единиц сырья, а четвертый столбец исключается из дальнейшего рассмотрения (вместо разностей ставится прочерк).

На втором шаге итерации вычислим разности между соседними минимальными тарифами оставшихся клеток для строк (7-1=6, 5-4=1, 3-2=1) и для столбцов (7-4=3, 5-2=3, 3-1=2). Максимальная разность будет для первой строки (6). Заполняем клетку А₁B₃, исчерпав оставшееся сырье первого поставщика, при этом третьему потребителю нужно еще 190-50=140 единиц сырья. В итоге из рассмотрения исключаем первую строку.

На следующем этапе разности равны для строк (5-4=1, 3-2=1) и для столбцов (9-4=5, 5-2=3, 9-3=6). Максимальная разность у третьего столбца (6). Заполняем клетку А₃B₃, полностью удовлетворив потребности третьего предприятия, в результате чего у третьего производителя останется 170-140=30 единиц сырья. Из дальнейшего рассмотрения исключаем третий столбец.

Далее разности равны для строк (5-4=1, 9-2=7) и для столбцов (9-4=5, 5-2=3). Разность максимальной будет для третьей строки. Следовательно, заполняем клетку А₃B₂, исключив из последующих шагов третью строку.

На последнем шаге остается только одна разность для второй строки (5-4=1). Поэтому заполняем оставшиеся клетки данной строки в порядке возрастания тарифов, сначала клетку А₂B₁, затем А₂B₂.

В результате опорный план будет задаваться следующей матрицей: , при этом общая стоимость перевозок составит: Q=1*50+2*110+4*120+5*20+2*30+3*140=1330 условных единиц.

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

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

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

Процедура расчетов состоит в следующем. Для каждой строки и для каждого столбца рабочей транспортной таблицы находим абсолютную разность двух наименьших тарифов. Эти разности заносятся в специально отведенные для этого «строку разностей» и «столбец разностей».

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

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

Рассчитываем абсолютную разность строк и столбцов:

• 1- я строка 15-3|=2 1-й столбец |6-3|=3
• 2- я строка 13-21=1 2-й столбец |5-3|=2
• 3- я строка |3-4|=1 3-й столбец |3-4|=1
• 4-й столбец |2-7|=5

Наибольшая разность 5 соответствует 4-му столбцу, который будет приоритетным. В этом столбце находится клетка с наименьшим тарифом: это с₂4 = 2, отсюдах₂₄ = 20.

Метод Фогеля

Метод Фогеля (англ. Vogel’s approximation method) [1]  — один из методов получения начального решения транспортной задачи. В отличие от метода северо-западного угла или метода минимальных тарифов, генерирует наиболее приближенное к оптимальному начальное решение. Это решение, однако, также может потребовать окончательной оптимизации при помощи метода потенциалов.

Содержание

Суть метода [ править ]

Метод Фогеля состоит в вычислении для каждой строки транспортной таблицы разницы между двумя наименьшими тарифами. Аналогичное действие выполняют для каждого столбца этой таблицы. Наибольшая разница между двумя минимальными тарифами соответствует наиболее предпочтительной строке или столбцу (если есть несколько строк или столбцов с одинаковой разницей, то выбор между ними произволен). В пределах этой строки или столбца отыскивают ячейку с минимальным тарифом, куда пишут отгрузку. [2] :115 Строки поставщиков или столбцы потребителей, которые полностью исчерпали свои возможности по отгрузке или потребности которых в товаре были удовлетворены, вычеркиваются из таблицы (в примерах ниже они закрашиваются серым цветом), и вычисление повторяются до полного удовлетворения спроса и исчерпания отгрузок без учета вычеркнутых («серых») ячеек. [3] :55

Числовой пример [ править ]

В этом примере стоимость доставки в рублях за кг записана в ячейках в квадратных скобках.

В эти же ячейки транспортной таблицы следует вписать объемы перевозки, чтобы распределить запасы поставщиков по потребителям.

Шаг 1 [ править ]

Вычислим разницы между двумя минимальными тарифами по строкам.

• Строка 1: 2-2=0
• Строка 2: 2-1=1
• Строка 3: 3-2=1

И затем по столбцам.

• Столбец 1: 3-2=1
• Столбец 2: 3-2=1
• Столбец 3: 2-2=0
• Столбец 4: 4-1=3

Наиболее предпочтителен столбец 4, поскольку разница для него максимальна.

В столбце 4 найдем минимальную цену — 1 руб/кг в строке 2. В нашем примере это ячейка X₂₄ (2-й поставщик, 4-й потребитель), где цена доставки = 1 руб./кг. Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя (берем минимум между 40 и 10 кг, то есть 10 кг). Поскольку спрос потребителя полностью удовлетворен, закрашиваем соответствующий столбец в серый цвет.

Шаг 2 [ править ]

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

• Строка 1: 2-2=0
• Строка 2: 3-2=1
• Строка 3: 3-2=1

И затем по столбцам.

• Столбец 1: 3-2=1
• Столбец 2: 3-2=1
• Столбец 3: 2-2=0

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

В нашем примере это ячейка X₂₂ (2-й поставщик, 2-й потребитель), где цена доставки = 2 руб./кг.

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

Шаг 3 [ править ]

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

• Строка 1: 2-2=0
• Строка 3: 4-2=2

И затем по столбцам.

• Столбец 1: 4-2=2
• Столбец 3: 2-2=0

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

В нашем примере это ячейка X₃₃ (3-й поставщик, 3-й потребитель), где цена доставки = 2 руб./кг.

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

Шаг 4 [ править ]

Заполнение оставшихся ячеек (см. таблицу выше) безальтернативно, алгоритмически (если мы пишем программу для ЭВМ) присваиваем разницы = 0, если число нераспределенных ячеек в строке или столбце меньше двух.

Дальнейшая оптимизация решения [ править ]

Полученный результат распределения составляет 2*20+2*10+2*30+1*10+2*20 = 170 рублей. Метод минимальных тарифов на этом же примере дал результат стоимостью 210 рублей, а метод северо-западного угла — 290 руб., то есть — наименее оптимальный. Проверить этот результат на оптимальность и, при необходимости, окончательно его оптимизировать можно при помощи метода потенциалов (который в этом примере показывает, что это распределение оптимально).

Программная реализация [ править ]

В коде для 1С:Предприятие 8.2 по ссылке метод представлен функцией РаспределениеМетодомФогеля и шестью функциями, имя которых начинается подстрокой «Фогель». [4]

Метод Фогеля

Таким образом, основной целью метода Фогеля является минимизация этих затрат. Когда мы говорим, что это эвристический подход, мы имеем в виду, что он использует простые критерии для решения сложных проблем. Кроме того, у него есть преимущество перед другими, потому что, хотя он требует большего количества итераций, его первоначальные результаты — не фиктивные — лучше. Он похож на другие методы, например, венгерский.

Происхождение метода Фогеля

С приходом промышленной революции проблемы в бизнесе росли. Среди них — постановка задач и затрат. По этой причине появились методы, позволяющие сделать это эффективно. Так, в 1955 г. Гарольд В. Кун предложил венгерский метод, в то время как аналогичные методы начали развиваться в области управления операциями.

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

Шаги, которым необходимо следовать при использовании метода Фогеля

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

Но, сказав это, давайте рассмотрим шаги, которые мы должны предпринять для этого; хотя мы увидим это более подробно на примере:

• Сначала мы должны рассчитать штраф, который мы добавим к исходной матрице. Для выполнения этого шага вычитаются две наименьшие затраты в каждой строке и столбце. Затем используется строка или столбец с наибольшим штрафом. Если есть два равных максимальных значения, выбор остается за лицом, выполняющим анализ.
• Затем мы должны взглянуть на ту строку или столбец, которые мы выбрали. Мы выбираем ячейку с наименьшей стоимостью и назначаем ей наибольшее количество единиц спроса, которое мы можем, с учетом доступного предложения. Таким образом, остальная часть этой строки или столбца будет равна нулю, и мы сможем удалить ее.
• Наконец, следует помнить о некоторых заключительных правилах. Если осталась только одна строка, алгоритм останавливается. Если это положительные значения, вы должны определить основные переменные решения. В противном случае он возвращается к первой точке и процесс перезапускается.

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

Чтобы лучше понять эту концепцию, ниже представлен ее пример.

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

На первом этапе вычисляются штрафы (Pe1), как объяснялось ранее, и выбирается самый высокий из них — тройка (темно-синий) из поля (Pe1, D3). Мы выбираем наименьшее значение в этом столбце, которым будет четыре (средний синий) прямоугольник (P2, D3). В таблице справа в той же позиции вставляется максимально возможное значение в соответствии с требованием этого столбца, которое составляет 30 (серый). Следовательно, в предложении останется 10, так как его максимум — 40.

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

Как мы видим, на рисунке 2 отображается только столбец D2, и все значения положительные. В этом смысле мы подошли к концу. Теперь, занимая эти две позиции (P2D2; P3D2) в таблице спроса и предложения, мы видим, какие значения будут отсутствовать, чтобы все было равно нулю. В данном случае недостающие числа — десять и пятнадцать.

Наконец, мы можем видеть, что метод Фогеля предлагает общую стоимость, которая рассчитывается путем умножения этих данных справа на ее удельные затраты слева. Мы вставили исходную таблицу с самого начала, чтобы облегчить расчет. Общая стоимость составит 650 и, в свою очередь, мы можем наблюдать частичку каждого варианта.