Сложность задач оптимизации

МИНОБРНАУКИ РОССИИ

Федеральное государственное  бюджетное образовательное учреждение

высшего профессионального  образования

"Московский  государственный технический университет

радиотехники, электроники и автоматики"

МГТУ МИРЭА

ФАКУЛЬТЕТ КИБЕРНЕТИКИ

Специальность 090102 «Компьютерная безопасность»

 

 

КУРСОВАЯ  РАБОТА

по  учебной дисциплине “Математическая  логика”

на  тему

“Сложность  задач оптимизации”

 

 

 

 

 

 

 

 

Выполнил

 студент гр. Кс-41-10

Укропов Л.А.

 

 

 

 

 

 

 

МОСКВА

2012 год

Содержание: 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

В данной курсовой работе будет рассмотрен вопрос о различных решениях задач по оптимизации, показано использование данного параметра в методах оптимизации. Также будут рассмотрены основные понятия и определения оптимизации.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Основные понятия

1. Определения.

 

Под оптимизацией понимают процесс выбора наилучшего варианта из всех возможных. С точки зрения инженерных расчетов методы оптимизации позволяют выбрать наилучший вариант конструкции, наилучшее распределение ресурсов и т.д.

В процессе решения задачи оптимизации  обычно необходимо найти оптимальные значения некоторых параметров, определяющих данную задачу. При решении инженерных задач их принято называть проектными параметрами, а в экономических задачах их обычно называют параметрами плана. В качестве проектных параметров могут быть, в частности, значения линейных размеров объекта, массы, температуры и т.п. число n проектных параметров x₁,x₂,…,x_n характеризует размерность ( и степень сложности) задачи оптимизации.

Выбор оптимального решения или  сравнение двух альтернативных решений проводится с помощью некоторой зависимой величины (функции), определяемой проектными параметрами. Эта величина называется целевой функцией (или критерием качества). В процессе решения задачи оптимизации должны быть найдены такие значения проектных параметров, при которых целевая функция имеет минимум (или максимум). Таким образом, целевая функция – это глобальный критерий оптимальности в математических моделях, с помощью которых описываются инженерные или экономические задачи.

Целевую функцию можно записать в виде

U=F(x₁, x₂,…,x_n).                              (1.1)

Примерами целевой функции, встречающимися в  инженерных и экономических расчетах, являются прочность и масса конструкции, мощность установки, объем  выпуска продукции, стоимость перевозок груза и т.п.

В случае одного проектного параметра  целевая функция (1.1) является функцией одной переменной, и се график - некоторая кривая на плоскости. При целевая функция является функцией двух переменных, и ее график — поверхность в трехмерном пространстве.

 

 

Следует отметить, что целевая функция  не всегда может  быть представлена в виде формулы. Иногда она может  принимать только некоторые значения, задаваться в виде таблицы и т. п. Во всех случаях она должна быть однозначной функцией проектных параметров.

Целевых функций может быть несколько. Например, при проектировании изделий машиностроения одновременно требуется обеспечить, максимальную надежность, минимальную материалоемкость, максимальный полезный объем (или грузоподъемность). Некоторые целевые функции могут оказаться несовместимыми. В таких случаях необходимо вводить приоритет той или иной целевой функции.

2. Задачи оптимизации.

 

Можно выделить два типа задач оптимизации  — безусловные и  условные. Безусловная задача оптимизации состоит в отыскании максимума или минимума действительной функции (1.1) при действительных переменных и определении соответствующих значений аргументов на некотором множестве σ  n-мерного пространства. Обычно рассматриваются задачи минимизации; к ним легко сводятся и задачи на поиск максимума путем замены знака целевой функции на противоположный.

Условные задачи оптимизации, или задачи с ограничениями, это такие, при формулировке которых задаются некоторые условия (ограничения) на множестве . Эти ограничения задаются совокупностью некоторых функций, удовлетворяющих уравнениям или неравенствам.

Ограничения-равенства выражают зависимость между, проектными параметрами, которая должна учитываться при нахождении решения. Эти ограничения отражают законы природы, наличие ресурсов т. п.

в результате ограничений область проектирования , определяемая всеми проектными параметрами, может быть существенно уменьшена в соответствии с физической сущностью задачи.

При наличие ограничений оптимальное  решение может соответствовать  либо локальному экстремуму в нутрии области проектирования, либо значению целевой функции на границе области. Если ограничения отсутствуют то ищется оптимальное решение на всей области проектирования, то есть глобальный экстремум.

 2. Одномерная оптимизация

2.1 Задачи па экстремум.

 

Одномерная задача оптимизации в общем случае формулируется следующим образом. Найти наименьшее (или наибольшее) значение целевой функции y=х, заданной на множестве σ, и определить значение проектного параметра х Є σ, при котором целевая функция принимает экстремальное значение. Существование решения поставленной задачи вытекает из следующей теоремы.

Теорема Вейерштрасса. Всякая функция F(х), непрерывная на отрезке [а, b], принимает на этом отрезке наименьшее и наибольшее значения, т.е. на отрезке [а, b] существуют такие точки х₁ в х₂, что для любого х Є [а, b] имеют место неравенства

                                            

Эта теорема не доказывает единственности решения. Не исключена возможность достижения равных экстремальных значений сразу в нескольких точках данного отрезка. В частности, такая ситуация имеет место для периодической функции, рассматриваемой на отрезке, содержащем несколько периодов.

Будем рассматривать методы оптимизации  для разных классов целевых функций. Простейшим из них является случай дифференцируемой функции F(х) на отрезке [а, b], причем функция задана в виде аналитической зависимости у = F(х), и может быть найдено явное выражение для ее производной ‚ . Нахождение экстремумов таких функций можно проводить известными из курса высшей математики методами дифференциального исчисления. Напомним вкратце этот путь.

Функция ‚ может достигать своего наименьшего и наибольшего значений либо в граничных точках отрезка [а, b], либо в точках минимума и максимума. Последние точки обязательно должны быть критическими, т. е. производная в этих точках обращается в нуль, — это необходимое условие экстремума. Следовательно, для определения наименьшего или наибольшего значений функции ‚ на отрезке [а, b] нужно вычислить ее значения во всех критических точках данного отрезка и в его граничных точках и сравнить полученные значения; наименьшее или наибольшее из них и будет искомым значением.

Случай, когда целевая функция задана в табличном виде или может быть вычислена при некоторых дискретных значениях аргумента, используются различные методы поиска. Они основаны на вычислении целевой функции в отдельных точках и выборе среди них наибольшего или наименьшего значений. Существует ряд алгоритмов решения данной задачи. Рассмотрим некоторые из них.

2.2 Методы поиска.

 

Численные методы поиска экстремальных значений функции рассмотрим на примере нахождения минимума функции на отрезке [а., b]. Будем предполагать, что целевая функция унимодальна, т.е. на данном отрезке она имеет только один минимум. Отметим, что в инженерной практике обычно встречаются именно такие целевые функции.

Погрешность приближенного решения задачи определяется разностью между оптимальным значением x проектного параметра и приближение к  нему х. Потребуем, чтобы эта погрешность была по модулю меньше заданного допустимого значения а:

                  (2.1)

Процесс решения задачи методом поиска состоит в последовательном сужении интервала изменения проектного параметра, называемого интервалом неопределенности. В начале процесса оптимизации его длина равна , а к концу она должна стать меньше , т. е. оптимальное значение проектного параметра должно находиться в интервале неопределенности – на отрезке , причем . Тогда для выполнения (2.1) в качестве приближения к оптимальному значению можно принять любое .

Наиболее  простым способом сужения интервала  является деление его на некоторое число равных частей с последующим вычислением значений целевой функции в точках разбиения. Пусть - число элементарных отрезков, - шаг разбиения. Вычислим значения целевой функции в узлах . Сравнивая полученные значения , найдем среди них наименьшее .

Число можно приближенно принять за наименьшее значение целевой функции на отрезке . Очевидно, что близость к минимуму зависит от числа точек, и для непрерывной функции

т. е. с увеличением числа точек разбиения погрешность минимума стремится к нулю.

В данном методе, который можно  назвать методом перебора, главная трудность состоит в выборе и оценке погрешности. Можно, например, провести оптимизацию с разными шагами и исследовать сходимость такого итерационного процесса. Но это трудоемкий путь.

Более экономичным способом уточнения  оптимального параметра является использование свойства унимодальности целевой функции, это позволяет построить процесс сужения интервала неопределенности. Пусть, как и ранее, среди всех значений унимодальной функции , вычисленных в узлах наименьшим оказалось . Это означает, что оптимальное значение проектного параметра находится на отрезке , т. е. интервал неопределенности сузился до длины двух шагов. Если размер интервала недостаточен для удовлетворения заданной погрешности, т. е. ,

то его снова можно уменьшить путем нового разбиения. Получится интервал, равный двум длинам нового шага разбиения и т. д. Процесс оптимизации продолжается до достижения заданного размера интервала неопределенности.

Существует  ряд специальных методов поиска оптимальных решений разными способами выбора узлов и сужения интервала неопределенности - метод деления отрезка пополам, метод золотого сечения и др. Рассмотрим один из них.

2.3 Метод золотого сечения.

 

При построении процесса оптимизации  стараются сократить объем вычислений и время поиска. Этого достигают  обычно путем сокращения количества вычислений (или измерений — при проведении эксперимента) значений целевой функции . Одним из наиболее эффективных методов, в которых при ограниченном количестве вычислений   достигается наилучшая точность, является метод золотого сечения. Он состоит в построении последовательности отрезков , ,... , стягивающихся к точке минимума функции . На каждом шаге, за исключением первого, вычисление значения функции проводится лишь в одной точке. Эта точка, называемая золотым сечением, выбирается специальным образом.

Поясним сначала идею метода геометрически, а затем выведем необходимые  соотношения. Па первом шаге процесса оптимизации внутри отрезка  выбираем некоторые внутренние точки и и вычисляем значения целевой функции и . Поскольку в данном случае , очевидно, что минимум расположен на одном из прилегающих к отрезков: или . Поэтому отрезок можно отбросить, сузив тем самым первоначальный интервал неопределенности.

Второй шаг проводим на отрезке , где . Нужно снова выбрать две внутренние точки, но одна из них осталась из предыдущего шага, поэтому достаточно выбрать лишь одну точку , вычислить значение и провести сравнение. Поскольку здесь , ясно, что минимум находится на отрезке . Обозначим этот отрезок , снова выберем одну внутреннюю точку и повторим процедуру сужения интервала неопределенности. Процесс оптимизации повторяется до тех пор, пока длина очередного отрезка не станет меньше заданной величины .

Теперь рассмотрим способ размещения внутренних точек на каждом отрезке . Пусть длина интервала неопределенности равна l, а точка деления разбивает его на части . Золотое сечение интервала неопределенности выбирается так, чтобы отношение длины большего отрезка к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка:

                          (2.2)

Из этого соотношения можно  найти точку деления, вычислив отношения

Преобразуем, выражение (2.2) и найдем значения ,

Поскольку пас интересует только положительное  решение, то

Очевидно, что интервал неопределенности можно разделить в соотношении золотого сечения двояко: в пропорциях и . Точки деления и выбираются с учетом этих пропорций. В данном случае имеем