Таким образом, стоимость ремонта участка дороги будет зависеть от выбранной технологии, используемых материалов и техники. Причем зависимость будет носить дискретный характер, то есть определенному сочетанию технологии, материалов и оборудования будет соответствовать конкретная величина затрат и конкретные параметры потребительских свойств, приобретаемых данным участком дороги после ремонта, а также величина межремонтного срока. Следовательно, выбор оптимальных вариантов производства работ будет производиться в пространстве дискретных состояний, то есть относиться к ЫР—трудным задачам оптимизации (задачи комбинаторной оптимизации). Рассмотрим основные методы решения задач дискретной оптимизации. 1.4. Методы решения задач дискретной оптимизации Рассмотрим постановку задач дискретной оптимизации (экстремальных задач комбинаторного типа) [25]. Задано конечное множество С>допустимых решений (комбинаций). В качестве таких комбинаций могут выступать перестановки п чисел (число возможных решений п!), сочетания из п элементов то т (число решений С™) последовательность из п чисел, каждый член которой может принимать одно из т значений (число возможных решений т п) и т.д. Для каждой комбинации яе(3 определена функция ф(л) в том смысле, что есть алгоритм вычисления функции ф(я) для любого л€(). Требуется определить комбинацию для которой ф(л) принимает максимальное или минимальное значение. Сложность решения задач дискретной оптимизации состоит в том, что число допустимых решений экспоненциально растет с ростом размерности задачи п. Поэтому простой перебор всех решений невозможен при больших п. В то же время, эти задачи относятся, как правило, к классу ЫРтрудных задач, для которых доказано, что не существует методов ихточного решения, отличных от перебора. 32 |
Приложение 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ГК, такое, что |