Метод Фогеля
Метод Фогеля (англ. Vogel’s approximation method)[1] — один из методов получения начального решения транспортной задачи. В отличие от метода северо-западного угла или метода минимальных тарифов, генерирует наиболее приближенное к оптимальному начальное решение. Это решение, однако, также может потребовать окончательной оптимизации при помощи метода потенциалов.
Суть метода[править]
Метод Фогеля состоит в вычислении для каждой строки транспортной таблицы разницы между двумя наименьшими тарифами. Аналогичное действие выполняют для каждого столбца этой таблицы. Наибольшая разница между двумя минимальными тарифами соответствует наиболее предпочтительной строке или столбцу (если есть несколько строк или столбцов с одинаковой разницей, то выбор между ними произволен). В пределах этой строки или столбца отыскивают ячейку с минимальным тарифом, куда пишут отгрузку.[2] Строки поставщиков или столбцы потребителей, которые полностью исчерпали свои возможности по отгрузке или потребности которых в товаре были удовлетворены, вычеркиваются из таблицы (в примерах ниже они закрашиваются серым цветом), и вычисление повторяются до полного удовлетворения спроса и исчерпания отгрузок без учета вычеркнутых («серых») ячеек.[3]
Числовой пример[править]
В этом примере стоимость доставки в рублях за кг записана в ячейках в квадратных скобках.
| Потребитель 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]
Источники[править]
- ↑ Рейнфельд, Фогель (Reinfeld N. V., Vogel W.) Математическое программирование. Методы решения производственных и транспортных задач, М., ИЛ., 1960, 303 стр.
- ↑ А. В. Кузнецов, Н. И. Холод, Л. С. Костевич. Руководство к решению задач по математическому программированию. Минск «Высшая школа», 1978 г.(djvu)
- ↑ Хазанова Л. Э. Математические методы в экономике: Учебное пособие. — 3-е изд.
- ↑ http://www.kb.mista.ru/article.php?id=859
 ↑ [+] | |
|---|---|
| Транспортная задача |
Транспортная задача (классическая) • Решение симплекс-методом • Решение в Excel • Транспортная задача с промежуточными пунктами (и ограничением по транзиту, с запретами) • Трёхиндексная транспортная задача (алгоритм минимального элемента) |
| Начальное решение |
Метод северо-западного угла • Метод минимальных тарифов • Метод Фогеля |
| Вырожденные случаи | |