5.2 Метод подъема или метод локального поиска.

Примеры задач, решаемых этим методом:

1. Задача сетевого планирования.

2. Задача нахождения максимума функции нескольких переменных.

3. Задача поиска минимального остовного дерева в графе.

4. Задача коммивояжера.

5. Алгоритмы численных методов, дающие приближенные решения.

6. Задачи линейного программирования

и др.

Данный метод начинает работу с принятия начального предположения или вычисления начального решения задачи (1 этап).

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

3 этап – перебор всех решений из ограниченного множества до тех пор, пока не будет найдено решение, улучшить которое невозможно. Однако найденное решение может быть неоптимальным (приближенным).

Примечание: если рассматривать улучшение начального решения на множестве всех возможных решений, то получаем метод полного перебора вариантов, дающий оптимальное решение за время, которое может быть неприемлемым. Поэтому метод подъема рассчитан на ограниченное подмножество решений, перебор которых дает вычислительную сложность порядка O(n²) или O(n³).

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

Определим, как действует метод подъема для задачи сетевого планирования, рассмотренной в предыдущем пункте.

1 шаг – задается начальное решение Z₀ (начальная расстановка всех 10 рабочих по семи операциям).

2 шаг – свободное число рабочих размещается по следующей схеме:

1. Ставится один рабочий на работу с максимальной трудоемкостью. Эта работа может не принадлежать «критическому» пути.

2. Если есть свободные рабочие, то они размещаются на работы с максимальной трудоемкостью до тех пор, пока все рабочие не будут расставлены.

Пример:

Пусть К₀₁=1, К₀₂=2, К₁₃=1, К₂₄=2, К₃₄=2, К₁₄=1, К₄₅=1.

T(I₁)=t₀₁+ t₁₃+ t₃₅=1/1+2/1+4/2=5= I_кр

T(I₂)=t₀₁+ t₁₄+ t₄₅=1/1+2/1+1/1=4

T(I₃)=t₀₂+ t₂₄+ t₄₅=2/2+3/2+1/1=3,5

Берут рабочего с работы, не принадлежащей «критическому» пути, и ставят на другую работу, которая принадлежит «критическому» пути. Затем анализируют время выполнения всего комплекса работ. Если найдено улучшение, то процесс повторяют до тех пор, пока окажется, что любые перемещения не приводят к улучшению решения.

Условия перемещения рабочих:

1)

2) Нельзя снимать рабочих с работ, для которых K_i,j=1.

Для заданного примера (0, 2)(2, 4)

(1, 3)  max[(1/1 - 1/2); (2/1 - 2/2); (4/2 - 4/3)]

Затем проводят перестановку рабочего и пересчитывают длительность выполнения работ на пути.

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