|
2. М О ДЕЛИ УП РАВ ЛЕНИ Я П РО Д О ЛЖ И ТЕЛ Ь Н О С ТЬ Ю ВЫ П О ЛНЕН ИЯ РАБОТ В С ТР О И ТЕЛ Ь Н О М П РО ЕКТЕ 2.1. М е то д ы реш ения задач д и с кр е тн о й о п ти м и за ц и и Рассмотрим постановку задач дискретной оптим изации (экстремальных задач комбинаторного типа). Задано конечное множество Q допустим ы х решений (ком бинаций). В качестве та ки х ком бинаций м о гут вы ступать перестановки п чисел (число возм ож ны х реш ений п !), сочетания из п элементов то m (число решений СЦ*) последовательность из п чисел, каж ды й член которой м ож ет принимать одно из m значений (число возм ож ны х реш ений ш ") и т.д. Для каисдой комбинации n e Q определена ф ункция ф(д) в том смысле, что есть алгоритм вычисления ф ункции ф(тс) для лю бого jte Q . Требуется определить ком бинацию для которой ф(д) принимает максимальное или минимальное значение. С ложность решения задач дискретной оптимизации состоит в том, что число допустимы х решений экспоненциально растет с ростом размерности задачи п. П оэтому простой перебор всех реш ений невозможен при больш их п. В то же время, эти задачи относятся, ка к правило, к классу N P труд ны х задач, для ко торы х доказано, что не сущ ествует методов и х точного реш ения, отличны х от перебора. Сущ ествует несколько схем решения задач дискретной оптимизации. Н и же дается их краткое описание [9 ,1 1 ,1 2 ,1 3 ,2 6 , 28]. М е т о д ы л о к а л ь н о й о п т и м и з а ц и и Определим для каж д ого решения я множество Р (я) та к называемых соседних решений (о кр е стн о сть решения я). П р и заданной процедуре получения соседних реш ений алгоритм локальной оптимизации работает следую щ им образом [9]. Берем какое-либо реш ение Яо Рассматриваем окрестность Р(яо) и в этой окрестности определяем паилучшее решение Яь такое что 50 |
2. МЕТОД ДИХОТОМИЧЕСКОГО ПРОГРАММИРОВАНИЯ 2.1. Методы решения задач дискретной оптимизации Рассмотрим постановку задач дискретной оптимизации (экстремальных задач комбинаторного типа). Задано конечное множество Q допустимых решений (комбинаций). В качестве таких комбинаций могут выступать перестановки п чисел (число возможных решений п!), сочетания из п элементов то m (число решений С®) последовательность из п чисел, каждый член которой может принимать одно из m значений (число возможных решений ш") и т.д. Для каждой комбинации reeQ определена функция ф(я:) в том смысле, что есть алгоритм вычисления функции (>(л) для любого TxeQ. Требуется определить комбинацию tco^Q, д л я которой (р(я) принимает максимальное или минимальное значение. Сложность решения задач дискретной оптимизации состоит в том, что число допустимых решений экспоненциально растет с ростом размерности задачи п. Поэтому простой перебор всех решений невозможен при больших п. В то же время, эти задачи относятся, как правило, к классу NP —трудных задач, для которых доказано, что не существует методов их точного решения, отличных от перебора. Существует несколько схем решения задач дискретной оптимизации. Ниже дается их краткое описание [9, 11, 12, 13,26,28]. Методы локальной оптимизации Определим для каждого решения я множество Р(я) так называемых соседних решений (окрестность решения л). При заданной процедуре получения соседних решений алгоритм локальной оптимизации работает следующим образом [9]. Берем какое-либо решение щ Рассматриваем окрестность Р(яо) и в этой окрестности определяем наилучшее решение яц такое что ф(я)= ш т ф(я) (1.1) л«Р(Яо> (имеется в виду задача минимизации). 43 |