Эвристические методы оптимизации. Алгоритм Флетчера-Кларка.

На практике иногда нужно найти оптимальное решение задачи, для которой метод оптимизации неизвестен.

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

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

Общая постановка задачи:

Предприятие Р₀ снабжает n складов: Р₁, Р₂, Р₃, ....Р_n. Количество машин, используемых для перевозки, не ограничено. Все машины имеют одинаковую грузоподъёмность, для каждой машины она равна С .

Стоимость перевозки между P_i и P_j равна d_ijd_ji.

Каждая отправляемая с предприятия Р₀ машина должна вернуться обратно.

Вместимость склада P_i равна С_i.

При какой минимальной общей стоимости перевозок можно заполнить все склады при условии, что маршруты перевозок представляют собой контуры, попарно пересекающиеся только в точке Р₀?

Примечание: можно рассматривать различные обобщения этой задачи, вводя дополнительные ограничения на грузоподъёмность, проходимость дорог, количество заездов на один склад.

Работу метода рассмотрим на примере: задача о перевозках задана таблицами вместимости складов С_i и стоимости перевозок d_ij. Для удобства на рисунке они совмещены.

Ci		P0	P1	P2	P3	P4	P5	P6
	P0	0	4	6	8	2	4	5
4	P1	4	0	3	3	2	1	5
6	P2	6	3	0	5	6	7	1
3	P3	8	3	5	0	8	2	1
1	P4	2	2	6	8	0	3	2
8	P5	4	1	7	2	3	0	4
2	P6	5	5	1	1	2	4	0

C=10 - вместимость одной машины.

В каждой клетке на пересечении P_i и P_j указана стоимость перевозки d_ij .

На рисунке приведено одно из возможных решений:

С₆=2 С₂=6

С₅=8 С₁=4

С₄=1 С₃=3

Такие перевозки возможны, так как вместимость складов в контурах не превышает 10.

Значение стоимости перевозок по каждому из контуров рисунка:

(Р₀,Р₂,Р₁,Р₀)= d₀₂ + d₂₁ + d₁₀ =6+3+4=13;

(Р₀,Р₃,Р₄,Р₀)= d₀₃ + d₃₄ + d₄₀ =8+8+2=18;

(Р₀,Р₅,Р₆,Р₀)= d₀₅ + d₅₆ + d₆₀ =4+4+5=13;

Общая стоимость перевозок: 13+18+13=44.

Рассмотрим теперь метод Флетчера-Кларка.

Алгоритм:

1. Для каждой пары вершин (P_i,P_j) , таких, что ij, i0, j0 определить параметр _ij= d_i0 + d_0j - d_ij и занести его в таблицу.

2. В качестве начального решения выбрать тривиальное решение S вида S={(P₀,P₁,P₀,), (P₀,P₂,P₀,),........, (P₀,P_п,P₀,)}.

3. Для каждого маршрута в найденном решении S вычислить значение параметров _i , i0 по формуле:

_i= 0, если (P_i,P₀)  S

1, если (P_i,P₀)  S

4. Все вершины P_m1 , P_m2 ,......., P_mk каждого маршрута из S (исключая P₀) объединяются в класс {P_m1 , P_m2 ,......., P_mk} и вычисляется объёмность перевозки

Q{P_m1 , P_m2 ,......., P_mk}=C_m1 + C_m2 +.......+ C_mk ,

где C_mi вместимость склада P_mi .

5. Выбрать в таблице значений _ij величину _ij = maximum > 0 (если таких величин несколько, то выбрать любую). Если для выбранной величины _ij склады P_i и P_j принадлежат разным классам, то объединить эти классы в один при выполнении условий:

а). _i=_j=1

б). Q{P_i , P_l , P_k.,......... } + Q{P_j , P_m ,. P_v. ,.....}  C,

выделив _ij в таблице меткой

Если одно из условий а) или б) не выполняется, то зачеркнуть клетку _ij в таблице

6. Найти новое значение _i , i0.

7. Повторять пункты 4 и 5 до тех пор, пока есть возможность выбора величины _ij > 0

Пример работы алгоритма.

Составляем таблицу значений _ij . Таблица будет заполнена ниже главной диагонали, т.к. матрица стоимости перевозок симметрична.

Первая сверху строка и первый слева столбец и клетки главной диагонали не заполняются, т.к. параметр _ij вычисляется при ij0.

_ij= d_i0 + d_0j - d_ij

₂₁= d₂₀ + d₀₁ - d₂₁=6+4-3=7

	P1	P2	P3	P4	P5	P6
P1	-	-	-	-	-	-
P2	7	-	-	-	-	-
P3	9	9	-	-	-	-
P4	4	2	2	-	-	-
P5	7	3	10	3	-	-
P6	4	10	12	5	5	-

Выбираем начальное тривиальное решение S .

Составляем таблицу для _i и объёмности перевозок по контурам решения S .

	i	Q{ Pi}
P0,P1,P0	1=1	Q{P1}=C1=4
P0,P2,P0	2=1	Q{P2}=C2=6
P0,P3,P0	3=1	Q{P3}=C3=3
P0,P4,P0	4=1	Q{P4}=C4=1
P0,P5,P0	5=1	Q{P5}=C5=8
P0,P6,P0	6=1	Q{P6}=C6=2

1). ₆₃=12=maximum

₆=₃=1 и Q{P₆}+ Q{P₃}=C₆+C₃=2+3=5<C =10

Образуем класс {P_6,P₃} и выделяем ₆₃ кружком в таблице. Значения _i не изменяются.

2). ₆₂=10 > 0

Пробуем объединить классы {P_6,P₃} и {P₂}:

₆=₂=1 и Q{P₆}+ Q{P₃}+ Q{P₂}=C₆+C₃+C₂=2+3+6=11 > C =10

Вычёркиваем ₆₂ в таблице. Значения _i не изменяются.

3). ₅₃=10 > 0

Пробуем объединить классы {P_6,P₃} и {P₅}:

₅=₃=1 и Q{P₅}+ Q{P₆}+ Q{P₃}=C₅+C₆+C₃=8+2+3=13 > C =10

Вычёркиваем ₅₃ в таблице. Значения _i не изменяются.

4). ₃₁=9 > 0

Пробуем объединить классы {P_6,P₃} и {P₁}:

₁=₃=1 и Q{P₃}+ Q{P₆}+ Q{P₁}=C₃+C₆+C₁=3+2+4=9 < C =10

Образуем класс{P_6,P₃,P₁}. Отмечаем клетку ₃₁ в таблице.

Находим новые значения _i : ₆=₁=1; ₃=0

5). ₃₂=9 > 0

₃=0 , ₂=1 Условие а) не выполняется. Поэтому вычеркиваем клетку ₃₂ .

6). ₅₁=7 > 0

₅=₁=1 и Q{P₅}+ Q{P₁}+ Q{P₆}+ Q{P₃}=C₅+C₁+C₆+C₃=8+4+2+3=17 > C =10

Вычёркиваем ₅₁ в таблице. Значения _i не изменяются.

7). ₂₁=7 > 0

₂=₁=1 и Q{P₂}+ Q{P₁}+ Q{P₆}+ Q{P₃}=C₂+C₁+C₆+C₃=6+4+2+3=15 > C =10

Вычёркиваем ₂₁ в таблице. Значения _i не изменяются.

8). ₆₄=5 > 0

₆=₄=1 и Q{P₆}+ Q{P₃}+ Q{P₁}+ Q{P₄}=C₆+C₃+C₁+C₄=2+3+4+1=10 = C =10

Образуем класс{P_4,P₆,P₃,P₁}. Отмечаем клетку ₆₄ в таблице.

Находим новые значения _i : ₁=₄=1; ₃=₆=0

9). ₆₅=5 > 0

₆=0 , ₅=1 Условие а) не выполняется. Поэтому вычеркиваем клетку ₆₅ .

10). ₆₁=4 > 0

Но {P₆} и {P₁} уже в одном классе! Поэтому вычеркиваем клетку ₆₁ .

11). ₄₁=4 > 0

Но {P₄} и {P₁} тоже уже в одном классе! Поэтому вычеркиваем клетку ₄₁ .

12). ₅₂=3 > 0

Пробуем объединить классы {P₅} и {P₂}:

₅=₂=1 и Q{P₅}+ Q{P₂}=C₅+C₂=8+6=14 > C =10. Условие не выполнено.

Вычеркиваем клетку ₅₂ в таблице.

13). ₅₄=3 > 0

Пробуем объединить классы {P₄, P₆, P₃, P₁,} и {P₅}:

₅=₄=1. Очевидно, что Q{P} будет > C =10. Условие не выполнено.

Вычеркиваем клетку ₅₄ в таблице.

14). ₄₂=2 > 0

Пробуем объединить классы {P₄, P₆, P₃, P₁,} и {P₂}:

₂=₄=1. Очевидно, что Q{P} будет > C =10. Условие не выполнено.

Вычеркиваем клетку ₄₂ в таблице.

15). ₄₃=2 > 0

Но {P₄} и {P₃} уже в одном классе! Поэтому вычеркиваем клетку ₄₁ .

Все элементы ₄₃ мы рассмотрели. У нас получились такие маршруты, являющиеся решением задачи:

(Р₀,Р₄,Р₆,Р₃,Р₁,Р₀)= d₀₄ + d₄₆ + d₆₃ +d₃₁ + d₁₀=2+2+1+3+4=12;

(Р₀,Р₂,Р₀)= d₀₂ + d₂₀ =6+6=12;

(Р₀,Р₅,Р₀)= d₀₅ + d₅₀ =4+4=8;

Общая стоимость перевозок: 12+12+8=32.

Полученная ранее стоимость перевозок без учёта метода Флетчера-Кларка была равна 44, что больше 32.