Метод Фогеля применяется для построения опорного плана. В большинстве случаев этот способ дает опорный план, наиболее близкий к оптимальному. Использовать этот метод рекомендуется при расчетах вручную.
В основе метода лежит концепция штрафов, взимаемых за выбор не самого оптимального с точки зрения транспортных расходов маршрута.
Алгоритм метода включает следующие основные этапы.
Таблица 3.12
B1 | B2 | B3 | B4 | Ai | Столбцы разностей | |||||
A1 | 70 | 38 | 14 24 | 92 | 14 | 14 | — | — | — | — |
A2 | 58 | 20 18 | 56 | 72 | 20 | 38 | — | — | — | — |
A3 | 23 19 | 2 10 | 1 100 | 30 | 26 | 9 | 9 | 9 | 11 | 81 |
A4 | 7 3 | 36 | 121 | 34 8 | 41 | 5 | 5 | 5 | 5 | 118 |
Bj | 30 | 22 | 15 | 34 | ||||||
Строки разностей | 16 | 8 | 32 | 22 | ||||||
16 | 26 | 76 | 22 | |||||||
16 | 26 | 21 | 22 | |||||||
16 | — | 21 | 22 | |||||||
16 | — | 21 | — |
1. Вычисление разностей в каждой отроке и в каждом столбце
Матрицы между наименьшей стоимостью и ближайшей к ней по величине (табл.3.12). Разности по строкам записываются справа в столбце разностей, разности по столбцам — внизу в строке разностей. Например, для строки A1 разность равна A1B2- A1B3 =38-24=14 и т. д.
2. Поиск из всех разностей как по строкам, так и по столбцам максимальной. В примере эта разность равна 38.
3. Помещение в клетку, где находится наименьшая стоимость перевозки (A2B2 =18) в отроке о наибольшей разностью максимально возможного количества ресурсов (20). Поскольку при этом все ресурсы отправителя A2 исчерпаны эту отроку из дальнейшего рассмотрения исключаем.
4. Вычисление разностей по столбцам и отрокам, не принимая во внимание стоимости в клетках, имеющих ресурсы, и клетках исключенной строки, и определение максимальной разности в строке или столбце (B3=76).
5. Поиск минимального элемента в строке или столбце с максимальной разностью A1B3 =24 и размещение в данную клетку максимально возможного количества ресурса. Затем возвращаемся к этапу 4.
Окончательное значение целевой функции F=1546.