86223 (612688)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Министерство образования и науки Республики Казахстан

Карагандинский Государственный Технический Университет

Кафедра САПР

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе

по дисциплине "Теория принятия решений"

Тема: "Сравнительный анализ методов оптимизации"

Руководитель:

(подпись) (дата)

Студент:

(группа)

_____________________

(подпись) (дата)

Караганда 2009

Содержание

Введение

1. Формулировка математической задачи оптимизации. Основные понятия

1.1 Формулировка математической задачи оптимизации

1.2 Минимум функции одной переменной

1.3 Минимум функции многих переменных

1.4 Унимодальные функции

1.5 Выпуклые функции

2. Прямые методы безусловной оптимизации

2.1 Прямые методы одномерной безусловной оптимизации

2.1.1 Метод деления отрезка пополам (дихотомии)

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

2.1.3 Практическое применение прямых методов одномерной безусловной оптимизации

2.2 Методы безусловной минимизации функций многих переменных

2.2.1 Метод циклического покоординатного спуска

2.2.2 Алгоритм Хука-Дживса

2.2.3 Практическое применение прямых методов безусловной многомерной оптимизации

2.2.4 Минимизация по правильному симплексу

2.2.5 Поиск точки минимума по деформируемому симплексу

2.2.6 Практическая реализация симплексных методов

3. Условная оптимизация

4. Линейное программирование

Заключение

Список использованной литературы

Введение

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

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

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

1. Формулировка математической задачи оптимизации. Основные понятия

1.1 Формулировка математической задачи оптимизации

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

Под минимизацией (максимизацией) функции n переменных f (x) = (x₁,.., x_n) на заданном множестве U n-мерного векторного пространства Е_n понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на множестве U значения f (x). При записи математических задач оптимизации в общем виде обычно используется следующая символика:

f (x) min (max),

х U

где f (x) - целевая функция, а U - допустимое множество, заданное ограничениями на управляемые переменные.

Если функция f (x) - скалярная, то задача ее оптимизации носит название задачи математического программирования. В этом случае критерий оптимизации один, и, следовательно, речь идет об однокритериальной (одномерной) оптимизации. Если же критериев несколько, то такая задача называется многокритериальной (задачей векторного программирования).

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

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

1.2 Минимум функции одной переменной

Пусть функция f (x) определена на множестве U вещественной оси R.

1. Число х* U называется точкой глобального (абсолютного) минимума или просто точкой минимума функции f (x) на множестве U, если f (x*) f (x) для всех х U.

Значение f * = f (x*) = называют глобальным (абсолютным) минимумом или просто минимумом функции f (x) на множестве U.

Множество всех точек минимума f (x) на U в дальнейшем будет обозначено через U*.

2. Число U называется точкой локального минимума функции f (x), если для всех xU, достаточно близких к , т.е. если существует > 0 такое, что это неравенство выполняется для любого .

Глобальный минимум f (x) является и локальным минимумом, а обратное неверно.

1.3 Минимум функции многих переменных

Будем рассматривать функции многих переменных f =f (x₁, …, x_n) как функции, заданные в точках х n-мерного евклидова пространства Е_n: f =f (х).

1. Точка х^*Е_n, называется точкой глобального минимума функции f (х), если для всех х^*Е_n выполняется неравенство f (x^*) f (х). Значение f (x^*) = = называется минимумом функции. Множество всех точек глобального минимума функции f (х) будем обозначать через U^*.

2. Точка называется точкой локального минимума функции f (х), если существует -окрестность точки : U_n ( ) ={x | (x, ) < } такая, что для всех х^*U_n ( ) выполняется неравенство f ( ) f (х).

3. Если допустимое множество U в задаче минимизации (максимизации) функции n переменных совпадает со всем пространством E_n, то говорят о задаче безусловной оптимизации

, x E_n.

1.4 Унимодальные функции

Если функция f (x) на множестве U имеет, кроме глобального, локальные минимумы, отличные от него, то минимизация f (x), как правило, сильно затрудняется. В частности, многие методы поиска точки минимума f (x) приспособлены только для функций, у которых каждый локальный минимум является одновременно и глобальным. Этим свойством обладают унимодальные функции.

Функция f (x) называется унимодальной на отрезке [а; b], если она непрерывна на [а; b] и существуют числа и , , такие, что:

1) если а < , то на отрезке [a; ] функция f (x) монотонно убывает;

2) если < b, то на отрезке [; b] функция f (x) монотонно возрастает;

3) при х [; ] f (x) =f ^* = .

Множество унимодальных на отрезке [а; b] функций мы будем обозначать через Q [а; b]. Отметим, что возможно вырождение в точку одного или двух отрезков из [a; ], [; ] и [; b]. Некоторые варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции показаны на рисунке 1.

Рисунок 1 - Некоторые варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции

Основные свойства унимодальных функций:

1. Любая из точек локального минимума унимодальной функции является и точкой ее глобального минимума на отрезке [а; b].

2. Функция, унимодальная на отрезке [а; b], является унимодальной и на любом меньшем отрезке [с; d] [а; b].

3. Пусть f (x) Q [а; b] и . Тогда:

если , то x^* [a; x₂] ;

если , то x^* [x₁; b],

где х* - одна из точек минимума f (x) на отрезке [a; b].

1.5 Выпуклые функции

Функция f (x), заданная на отрезке [a; b], называется выпуклой на этом отрезке, если для всех х', х" [а; b] и произвольного числа [0; 1] выполняется неравенство

f [x'+ (1- ) x"] f (x') + (l - ) f (x"). (1)

Перечислим основные свойства выпуклых функций.

Если функция f (x) выпукла на [a; b], то на любом отрезке [х'; х"] [a; b] ее график расположен не выше хорды, проведенной через точки графика с абсциссами х' и х" (рисунок 2).

Рисунок 2 - Взаимное расположение

Пусть х' и х" - произвольные точки отрезка [a; b], причем х' < х". Легко проверить, что при любом [0; 1] точка x = x^’ + (1-) x" лежит на отрезке [x’; х"] и при непрерывном изменении от 0 до 1 пробегает этот отрезок от точки х" (при = 0) до точки x' (при = 1).

Рассмотрим хорду графика f (x), проходящую через точки (х',f (х')) и (х",f (х")). Ордината y точки этой хорды, соответствующая абсциссе c, равна. Поэтому неравенство (1) графика выпуклой функции и хорды означает, что f (x) y, т.е. при любом расположении x_, на отрезке [х'; х"] точка графика функции f (x) лежит не выше соответствующей точки хорды.

2. Из курса математического анализа известны следующие условия выпуклости функции:

а) для того чтобы дифференцируемая на отрезке [а; b] функция f (x) была выпуклой на этом отрезке, необходимо и достаточно, чтобы производная f ' (x) не убывала на [а; b] ;

б) для того чтобы дважды дифференцируемая на отрезке [а; b] функция f (x) была выпуклой на этом отрезке, необходимо и достаточно, чтобы при всех х [а; b] выполнялось неравенство f " (x) 0.

3 Условие выпуклости для дифференцируемой на отрезке [а; b] функции f (x) означает, что на этом отрезке любая касательная к графику f (x) лежит не выше этого графика (рисунок 3).

Рисунок 3 - условие выпуклости

Уравнение касательной к графику f (х) в точке (x_0, f (x₀)), x₀ [а; b] имеет вид: у (х) =f (x₀) +f ’ (x₀) (x-x₀). По формуле конечных приращений для любого х [а; b] имеем: f (х) =f (x₀) +f ’ () (x-x₀), где точка лежит между x и x₀. Поэтому

f (х) - у (х) = [f ’ () - f ’ (x₀)] (x-x₀), х [а; b],

откуда с учетом того, что производная f ’ (x) выпуклой функции не убывает, получаем:

f (x) -y (x) 0 (2)

для всех х [а; b].

4. Если f (x) - выпуклая дифференцируемая на отрезке [а; b] функция и в точке х* [а; b] выполняется равенство

f ’ (x^*) = 0 (3)

то х* является точкой глобального минимума f (х) на [а; b].

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов курсовой работы