Метод фогеля

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

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

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

Таблица 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.