|
ф(т1)= m in ф(л:) ( 1 .1 ) яеР(71о^ (имеется в виду задача м инимизации). Если ф(л1) < ф(яо), то рассматриваем окрестность P(tei), определяем наилучшее решение лг и т.д. до тех пор пока не получим реш ение Лк, такое, что ф (Лк)= m in ф(л) яер(Лк) Это решение называется локально-оптимальным. Далее м ож но взять новое начальное решение и повторить процедуру до получения локально-оптимального решения и т.д. М о ж н о поступить по-другом у, расш ирив окрестность. Если локальнооптимальное решение, то определяем окрестность следую щ им образом Р Ю = U p W (1-2) псрСЛк) Д ругим и словами, Р(тСк) это объединение всех окрестностей реш ений, п р и надлежащих окрестности локально-оптимальным решения. Если Лк остается локально-оптимальным решением в новой окрестности, то производим дальнейшее расширение окрестности, либо останавливаемся на полученном реш ении. Достоинством методов локальной оптимизации является простота соответСТВ5ДОЩИХ алгоритмов. Н едостатком схемы является отсутствие оценок близости получаемого решения к оптимальному. В задачах календарного планирования метод локальной оптимизации реализуется, в основном, в так называемых алгоритмах «сглаживания» и в алгоритмах улучш ения решения путем изменения очередности работ критического пути. Рассмотрим два просты х примера, иллю стрирую щ их эти подходы. П р и м е р 2.1. Н а рис. 2.1 приведен сетевой граф ик проекта из 4 работ, ко то рым соответствую т верш ины сети. В ниж ней половине верш ин указаны объемы работ. Примем, что количество ресурсов на работах 1 и 2 не м ож ет превышать 4, а на работах 3 и 4 не м ож ет превышать 1. 51 |
Если < р ( л О < ф ( л о ) , то рассматриваем окрестность Р(Л), определяем наилучшее решение Я2и т.д. до тех пор пока не получим решение такое, что ф(яь)= min ф(я) Это решение называется локально-оптимальным. Далее можно взять новое начальное решение и повторить процедуру до получения локально-оптимального решения и т.д. Можно поступить по-другому, расширив окрестность. Если я* —локально-оптимальное решение, то определяем окрестность следующим образом = и Р (") (1-2) другими словами, Р(Як) это объединение всех окрестностей решений, принадлежащих окрестности локально-оптимальным решения. Если Як остается локально-оптимальным решением в новой окрестности, то производим дальнейшее расширение окрестности, либо останавливаемся на полученном решении. Достоинством методов локальной оптимизации является простота соответствующих алгоритмов. Недостатком схемы является отсутствие оценок близости получаемого решения к оптимальному. В задачах календарного планирования метод локальной оптимизации реализуется, в основном, в так называемых алгоритмах «сглаживания» и в алгоритмах улучшения решения путем изменения очередности работ критического пути. Рассмотрим два простых примера, иллюстрирующих эти подходы. Пример 1.1. На рис. 1.1 приведен сетевой график проекта из 4 работ, которым соответствуют вершины сети. В нижней половине вершин указаны объемы работ. Примем, что количество ресурсов на работах 1 и 2 не может превышать 4, а на работах 3 и 4 не может превышать 1. 44 |