|
3 Построение, исследование и апробация оптимизационных алгоритмов решения системы моделей ЗД Выбор методов оптимизации В предыдущем разделе задача оптимизации инвестиционного портфеля предприятия формализована нами как «задача о ранце» с булевыми переменными. В нашей постановке рассматриваехмая задача сводится к задаче псевдобулевой оптимизации [2] с, в общем случае, алгоритмически заданными ограничениями. Поскольку множество допустимых решений дискретной экстремальной задачи есть конечное множество, то для ее решения может быть использован метод полного перебора [14]. Перебрав все возможные варианты решений, мы гарантированно получаем оптимальное решение. Таким образом, полный перебор является универсальным методом решения задач дискретной оптимизации. При этом реальные задачи, аналогичные решаемой нами, не решаются полным перебором на современных ЭВМ (исключая суперЭВМ из-за их недоступности и дороговизны) за приемлемое время уже на размерностях выше 40 [13]. Однако метод чрезвычайно удобен в качестве оценки сверху количества вычислений целевого функционала, необходимых для достижения оптимума. Применение регулярных методов [85-91] целочисленного линейного программирования (например метода ветвей и границ) для решения данной задачи также вызывает определенные трудности из-за характера ограничений. Для решения задач данного класса и такой размерности, как решаемая здесь задача, наиболее приемлемыми являются эвристические алгоритмы. Кроме того, эвристический алгоритм определяется как алгоритм со следующими “удобными” для нас свойствами. -63 |
3. i=i+l. Если /2, иначе к п. 4. 4. Конец. 3.4 Построение и апробация методов решения системы моделей на примере ФГУП ЦКБ “Геофизика” Задача оптимизации инновационного портфеля предприятия формализована нами как «задача о ранце» с булевыми переменными, которая может быть сведена к задаче псевдобулевой оптимизации [82] вида: f ( X ) -> opt, Л'еО где D {X е R n :х} = 0 v 1}9a f ( X ) принимает значения из R x. Поскольку множество допустимых решений дискретной экстремальной задачи есть конечное множество, то для ее решения может быть использован метод полного перебора [83]. Перебрав все возможные варианты решений, мы гарантированно получаем оптимальное решение. Таким образом, полный перебор является универсальным методом решения задач дискретной оптимизации. При этом реальные задачи, аналогичные решаемой нами, не решаются полным перебором на современных ЭВМ (исключая суперЭВМ) за приемлемое время уже при размерностях порядка 40 [84]. Однако метод чрезвычайно удобен в качестве оценки сверху количества вычислений целевого функционала, необходимых для достижения оптимума. Применение регулярных методов целочисленного линейного программирования (например, метода ветвей и границ) для решения данной задачи также вызывает определенные трудности из-за характера имеющихся в задаче ограничений. Для решения задач данного класса и такой размерности наиболее приемлемыми являются эвристические алгоритмы. Кроме того, эвристический 124 |