Метод Фогеля

Материал из Циклопедии
Перейти к: навигация, поиск

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

Содержание

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

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

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

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

Потребитель B1,
потребность 20 кг
Потребитель B2,
потребность 30 кг
Потребитель B3,
потребность 30 кг
Потребитель B4,
потребность 10 кг
Поставщик A1,
запас 30 кг
[2 руб./кг] [3 руб./кг] [2 руб./кг] [4 руб./кг]
Поставщик A2,
запас 40 кг
[3 руб./кг] [2 руб./кг] [5 руб./кг] [1 руб./кг]
Поставщик A3,
запас 20 кг
[4 руб./кг] [3 руб./кг] [2 руб./кг] [6 руб./кг]

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

[править] Шаг 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. В нашем примере это ячейка X24 (2-й поставщик, 4-й потребитель), где цена доставки = 1 руб./кг. Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя (берем минимум между 40 и 10 кг, то есть 10 кг). Поскольку спрос потребителя полностью удовлетворен, закрашиваем соответствующий столбец в серый цвет.

Потребитель B1,
потребность 20 кг
Потребитель B2,
потребность 30 кг
Потребитель B3,
потребность 30 кг
Потребитель B4,
потребность 10-10=0 кг
Поставщик A1,
запас 30 кг
[2 руб./кг] [3 руб./кг] [2 руб./кг] [4 руб./кг]
Поставщик A2,
запас 40-10=30 кг
[3 руб./кг] [2 руб./кг] [5 руб./кг] [1 руб./кг] 10 кг
Поставщик A3,
запас 20 кг
[4 руб./кг] [3 руб./кг] [2 руб./кг] [6 руб./кг]

[править] Шаг 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, а в ней — выберем минимальный тариф, не учитывая (см. таблицу выше) закрашенные ячейки.

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

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

Потребитель B1,
потребность 20 кг
Потребитель B2,
потребность 30-30=0 кг
Потребитель B3,
потребность 30 кг
Потребитель B4,
потребность 10-10=0 кг
Поставщик A1,
запас 30 кг
[2 руб./кг] [3 руб./кг] [2 руб./кг] [4 руб./кг]
Поставщик A2,
запас 40-10-30=0 кг
[3 руб./кг] [2 руб./кг] 30 кг [5 руб./кг] [1 руб./кг] 10 кг
Поставщик A3,
запас 20 кг
[4 руб./кг] [3 руб./кг] [2 руб./кг] [6 руб./кг]

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

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

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

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

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

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

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

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

Потребитель B1,
потребность 20 кг
Потребитель B2,
потребность 30-30=0 кг
Потребитель B3,
потребность 30-20=10 кг
Потребитель B4,
потребность 10-10=0 кг
Поставщик A1,
запас 30 кг
[2 руб./кг] [3 руб./кг] [2 руб./кг] [4 руб./кг]
Поставщик A2,
запас 40-10-30=0 кг
[3 руб./кг] [2 руб./кг] 30 кг [5 руб./кг] [1 руб./кг] 10 кг
Поставщик A3,
запас 20-20=0 кг
[4 руб./кг] [3 руб./кг] [2 руб./кг] 20 кг [6 руб./кг]

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

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

Потребитель B1,
потребность 20 кг
Потребитель B2,
потребность 30-30=0 кг
Потребитель B3,
потребность 30-20-10=0 кг
Потребитель B4,
потребность 10-10=0 кг
Поставщик A1,
запас 30-20-10=0 кг
[2 руб./кг] 20 кг [3 руб./кг] [2 руб./кг] 10 кг [4 руб./кг]
Поставщик A2,
запас 40-10-30=0 кг
[3 руб./кг] [2 руб./кг] 30 кг [5 руб./кг] [1 руб./кг] 10 кг
Поставщик A3,
запас 20-20=0 кг
[4 руб./кг] [3 руб./кг] [2 руб./кг] 20 кг [6 руб./кг]

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

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

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

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

[править] Источники

  1. Рейнфельд, Фогель (Reinfeld N. V., Vogel W.) Математическое программирование. Методы решения производственных и транспортных задач, М., ИЛ., 1960, 303 стр.
  2. А. В. Кузнецов, Н. И. Холод, Л. С. Костевич. Руководство к решению задач по математическому программированию. Минск «Высшая школа», 1978 г.(djvu)
  3. Хазанова Л. Э. Математические методы в экономике: Учебное пособие. — 3-е изд.
  4. http://www.kb.mista.ru/article.php?id=859


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты