Метод Фогеля

Метод Фогеля применяется для построения опорного плана. В большинстве случаев этот способ дает опорный план, наиболее близ­кий к оптимальному. Использовать этот метод рекомендуется при расчетах вручную

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

Алгоритм метода включает следующие основные этапы.

Таблица 3.12

1. Вычисление разностей в каждой отроке и в каждом столбце
матрицы между наименьшей стоимостью и ближайшей к ней по величи­не (табл.3.12). Разности по строкам записываются справа в столбце
разностей, разности по столбцам - внизу в строке разностей. Напри­мер, для строки A₁ разность равна A₁B₂- A₁B₃ =38-24=14 и т.д.

2. Поиск из всех разностей, как по строкам, так и по столбцам максимальной. В примере эта разность равна 38.

3. Помещение в клетку, где находится наименьшая стоимость пе­ревозки (A₂B₂ =18) в отроке о наибольшей разностью максимально возможного количества ресурсов (20). Поскольку при этом все ресур­сы отправителя A₂ исчерпаны эту отроку из дальнейшего рассмотре­ния исключаем.

4. Вычисление разностей по столбцам и отрокам, не принимая во внимание стоимости в клетках, имеющих ресурсы, и клетках исклю­ченной строки, и определение максимальной разности в строке или столбце (B₃=76).

5. Поиск минимального элемента в строке или столбце с максимальной разностью A₁B₃ =24 и размещение в данную клетку максимально возможного количества ресурса. Затем возвращаемся к этапу 4.

Окончательное значение целевой функции F=1546.