Проверяемый текст
Крюков, Сергей Вениаминович; Оптимизационные модели и механизмы корпоративного управления (Диссертация, апрель 2005)
[стр. 32]

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

Приложение 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ГК, такое, что

[Back]