5 мар 201456.3K0

Транспортная задача: метод аппроксимации Фогеля

Транспортная задача: метод аппроксимации Фогеля

Среди четырех, чаще всего применяющихся на практике, методов формирования опорного плана в транспортной задаче самый необычный – метод аппроксимации Фогеля. Последовательность действий при его использовании совершенно иная, чем при заполнении транспортной таблицы методом «Северо-Западного угла» или методом «Минимального элемента». На первый взгляд аппроксимация Фогеля сложнее, но это ложное впечатление. Метод простой и позволяет получить опорный план более приближенный к оптимальному решению, чем в случае применения других методов (за исключением разве что метода «Двойного предпочтения»).

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


ФОРМИРОВАНИЕ ОПОРНОГО ПЛАНА МЕТОДОМ АППРОКСИМАЦИИ ФОГЕЛЯ

Первым делом добавляем к транспортной таблице дополнительные строку и столбец. Далее находим для каждой строки и каждого столбца абсолютные разности (по модулю, т.е. без знака) между двумя минимальными тарифами. Если в строке/столбце две клетки с одинаковыми и минимальными значениями тарифов, то берем именно их. Тогда разность будет равна 0.
Найденные разности выписываем в добавочный столбец и добавочную строку.
Транспортная задача: метод аппроксимации Фогеля
Среди вычисленных разностей (и по строкам, и по столбцам!) выбираем наибольшую.

Транспортная задача: метод аппроксимации Фогеля
Затем в строке (или столбце), которой соответствует максимальная разность, ищем клетку с минимальным тарифом. Заполняем ее.
Если клеток с минимальным тарифом несколько, то заполняем ту из них, которой соответствует наибольшая разность.

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

Транспортная задача: метод аппроксимации Фогеля
В результате мы получаем опорный план:

Транспортная задача: метод аппроксимации Фогеля
Зачастую опорный план, полученный аппроксимацией Фогеля, оказывается либо сразу оптимальным (как в этом примере), либо очень близким к оптимальному. Но именно часто, а не всегда!


ИСТОЧНИКИ И ССЫЛКИ

Викиучебник. Аппроксимация Фогеля. - http://ru.wikibooks.org/wiki/Аппроксимация_Фогеля

© Копирование материала допустимо только при указании гиперссылки на источник: Галяутдинов Р.Р.


Орфография

Нашли опечатку? Помогите сделать статью лучше! Выделите орфографическую ошибку мышью и нажмите Ctrl+Enter.

Цитирование

Библиографическая запись для цитирования статьи по ГОСТ Р 7.0.5-2008:
Галяутдинов Р.Р. Транспортная задача: метод аппроксимации Фогеля // Сайт преподавателя экономики. [2014]. URL: http://galyautdinov.ru/post/approksimaciya-fogelya (дата обращения: 28.09.2020).

Еще можно почитать: