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

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

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

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

В соответствии с выше указанным алгоритмом выполняется загрузка клеток с учетом имеющихся ограничений по спросу и предложению. Оставшиеся разницы столбцов или строк перечеркиваются и ставиться знак "К", т.е. окончание проверки, означающей, что перераспределение груза закончено. Определяются новые разницы для всех строк и столбцов таблицы, при этом загруженные и свободные клетки, расположенные в строках или столбцах, в которых исчерпаны ограничения по спросу или предложению во внимание не принимаются. Если вновь полученная разница отличается от полученной ранее, то последняя зачеркивается и пишутся новые. Действие повторяется до тех пор, пока весь груз не будет распределен. Последнюю одну или две клетки загружают без определения разностей, полученный по методу аппроксимации Фогеля план перевозки проверяется на оптимальность по методу Моди, если полученное распределение груза окажется не оптимальным, то дальнейшее решение производится по алгоритму метода Моди.

Таблица № 6