Алгоритм Флетчера-Кларка

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

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

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

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

Предприятие Р₀ снабжает 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
	P1
	P2
	P3
	P4
	P5
	P6

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 определить параметр l_ij= d_i0 + d_0j - d_ij и занести его в таблицу.

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

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

g _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. Выбрать в таблице значений l_ij величину l_ij = maximum > 0 (если таких величин несколько, то выбрать любую). Если для выбранной величины l_ij склады P_i и P_j принадлежат разным классам, то объединить эти классы в один при выполнении условий:

а). g _i =g _j =1

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

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

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

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

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