|
Существует несколько схем решения задач дискретной оптимизации. Ниже дается их краткое описание [25]. Определим для каждого решения к множество Р(7с)так называемых соседних решений (окрестность решения л). При заданной процедуре получения соседних решений алгоритм локальной оптимизации работает следующим образом [9]. Берем какое-либо решение щ Рассматриваем окрестность Р(тсо) и в этой окрестности определяем наилучшее решение к\, такое что ф(я)= min ф(л) (1-4.1) «Ф(Яо> (имеется в виду задача минимизации). Если ф(л!) < ф(ло), то рассматриваем окрестность Р(Л]), определяем наилучшее решение лг и т.д. до тех пор пока не получим решение лК) такое, что фОО= m,in,ф(л)*€р(лк) Это решение называется локально-оптимальным. Далее можно взять новое начальное решение и повторить процедуру до получения локально-оптимального решения ит.д. Можно поступить по-другому, расширив окрестность. Если лк локально-оптимальное решение, то определяем окрестность следующим образом р (к.с)= U pW О-4-2) *€Р(7Ск> Другими словами, P(7ik) это объединение всех окрестностей решений, принадлежащих окрестности локально-оптимальным решения. Если лкостается локально-оптимальным решением в новой окрестности, то производим дальнейшее расширение окрестности, либо останавливаемся на полученном решении. 33 |
Приложение 1 Методы решения задач дискретной оптимизации Рассмотрим постановку задач дискретной оптимизации (экстремальных задач комбинаторного типа). Задано конечное множество Q допустимых реш ений (комбинаций). В качестве таких комбинаций могут выступать перестановки п чисел (число возможных решений п!), сочетания из п элементов то m (число решений С™) последовательность из п чисел, каждый член которой может принимать одно из m значений (число возможных решений mn) и т.д. Для каждой комбинации ttsQ определена функция ф(тг) в том смысле, что есть алгоритм вычисления функции ф(тг) для любого ttsQ . Требуется определить комбинацию X o g Q , д л я которой ф(ж) принимает максимальное или минимальное значение. Сложность решения задач дискретной оптимизации состоит в том, что число допустимых решений экспоненциально растет с ростом размерности задачи п. Поэтому простой перебор всех решений невозможен при больших п. В то же время, эти задачи относятся, как правило, к классу NP трудных задач, для которых доказано, что не существует методов их точного решения, отличных от перебора. Существует несколько схем решения задач дискретной оптимизации. Н иже дается их краткое описание [9 ,11,12,13,26, 28]. 1. Методы локальной оптимизации Определим для каждого решения тгмножество Р(тг) так называемых соседних решений (окрестность решения 7г). При заданной процедуре получения соседних решений алгоритм локальной оптимизации работает следующим образом [9]. Берем какое-либо решение тго Рассматриваем окрестность Р(тго) и в этой окрестности определяем наилучшее решение 7Гьтакое что (р(тс)= min ф(л) (1.1) (имеется в виду задача минимизации). Если < ф (7Го), то рассматриваем окрестность P(7Ti), определяем наилучшее решение тъ и т.д. до тех пор пока не получим решение 7ГК, такое, что Это решение называется локально-оптимальным. Далее можно взять новое начальное решение и повторить процедуру до получения локально-оптимального решения и т.д. Можно поступить по-другому, расширив окрестность. Если т клокальнооптимальное решение, то определяем окрестность следующим образом пч)= U p M с1-2) Другими словами, Р(тгк) это объединение всех окрестностей решений, принадлежащих окрестности локально-оптимальным решения. Если тгк остается локально-оптимальным решением в новой окрестности, то производим дальнейшее расширение окрестности, либо останавливаемся на полученном решении. Достоинством методов локальной оптимизации является простота соответствующих алгоритмов. Недостатком схемы является отсутствие оценок близости получаемого решения к оптимальному. В задачах календарного планирования метод локальной оптимизации реализуется, в основном, в так называемых алгоритмах «сглаживания» и в алгоритмах улучшения решения путем изменения очередности работ критического пути. Рассмотрим два простых примера, иллюстрирующих эти подходы. П ример 1.1. На рис. 1.1 приведен сетевой график проекта из 4 работ, которым соответствуют вершины сети. В нижней половине вершин указаны объемы работ. Примем, что количество ресурсов на работах 1 и 2 не может превышать 4, а на работах 3 и 4 не может превышать 1. Рис. 1.1. На рис. 1.2 приведен график использования ресурсов при выполнении всех работ с максимальной интенсивностью Заметим, что работы 1 и 3 критические, а работы 2 и 4 имеют полные резервы времени равные 4. Поэтому сдвигаем начало работы 2 на 3 единицы и выполняем ее в интервале (3, 7) тремя единицами ресурсов. При этом, естественно сдвигается работа 4 на 4 единицы. График использования ресурсов после локальной оптимизации на рис. 1.2 заштрихован. 79 |