Реферат: Сравнительный анализ методов оптимизации
Министерство образования и наукиРеспублики Казахстан
Карагандинский Государственный Технический Университет
Кафедра САПР
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовой работе
по дисциплине «Теория принятия решений»
Тема: «Сравнительный анализ методов оптимизации»
Руководитель:
(подпись) (дата)
Студент:
(группа)
_____________________
(подпись) (дата)
Караганда 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) = (x1,.., xn) на заданном множестве 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), если />для всех xÎU,достаточно близких к />, т.е. еслисуществует e > 0 такое, что это неравенство выполняетсядля любого/>/>.
Глобальный минимум f (x) является и локальным минимумом, а обратноеневерно.
1.3 Минимум функции многих переменныхБудем рассматриватьфункции многих переменных f =f (x1, …, xn) как функции,заданные в точках х n-мерного евклидовапространства Еn: f =f (х).
1. Точка х*ÎЕn,называется точкой глобального минимума функции f (х),если для всех х*ÎЕn выполняется неравенство f (x*) £ f (х). Значение f (x*) = =/> называется минимумом функции. Множество всех точек глобального минимумафункции f (х) будем обозначать через U*.
2. Точка /> называется точкойлокального минимума функции f (х), если существует e-окрестность точки />:Un (/>) ={x | r (x, />) < e} такая, что для всех х*ÎUn(/>) выполняется неравенство f (/>) £ f (х).
3. Если допустимоемножество U в задаче минимизации (максимизации) функции n переменных совпадает со всем пространством En,то говорят о задаче безусловной оптимизации
/>, x ÎEn.
/>1.4 Унимодальныефункции
Если функция f (x) на множестве U имеет, кроме глобального,локальные минимумы, отличные от него, то минимизация f (x), как правило, сильно затрудняется. В частности, многие методы поискаточки минимума f (x) приспособлены только дляфункций, у которых каждый локальный минимум является одновременно и глобальным.Этим свойством обладают унимодальные функции.
Функция f (x) называется унимодальной на отрезке [а; b], еслиона непрерывна на [а; b] и существуют числа a и b, />, такие, что:
1) если а < a, то на отрезке [a; a] функция f (x) монотонно убывает;
2) если b < b, то на отрезке [b; b] функция f (x) монотонно возрастает;
3) при х Î [a; b] f (x) =f * = />.
Множество унимодальныхна отрезке [а; b] функций мы будем обозначать через Q[а; b]. Отметим, что возможно вырождение в точку одного или двух отрезков из [a; a], [a; b] и [b; b]. Некоторые варианты расположения и вырождения в точку отрезковмонотонности и постоянства унимодальной функции показаны на рисунке 1.
/>
Рисунок 1 — Некоторые варианты расположения и вырождения вточку отрезков монотонности и постоянства унимодальной функции
Основные свойстваунимодальных функций:
1. Любая из точеклокального минимума унимодальной функции является и точкой ее глобальногоминимума на отрезке [а; b].
2. Функция, унимодальнаяна отрезке [а; b], является унимодальной и на любом меньшем отрезке [с; d] /> [а; b].
3. Пусть f (x) />Q[а; b] и />. Тогда:
если />, то x*/> [a; x2] ;
если />, то x*/> [x1; b],
где х* — одна из точекминимума f (x) на отрезке [a; b].
1.5 Выпуклые функции
Функция f (x), заданная на отрезке [a; b], называется выпуклой на этом отрезке, если для всех х', х" /> [а; b] и произвольногочисла /> [0; 1] выполняетсянеравенство
f [ax'+ (1- a) x"] £ af (x') + (l — a) f (x"). (1)
Перечислим основныесвойства выпуклых функций.
Если функция f (x) выпукла на [a; b], то на любом отрезке [х'; х"] Ì [a; b] ее график расположен невыше хорды, проведенной через точки графика с абсциссами х' и х" (рисунок2).
/>
Рисунок 2 — Взаимноерасположение/>
Пусть х' и х" — произвольные точки отрезка [a; b],причем х' < х". Легко проверить, что при любом a Î [0; 1]точка xa = ax’+ (1-a) x" лежит на отрезке [x’; х"] и при непрерывном изменении a от 0до 1 пробегает этот отрезок от точки х" (при a = 0) до точки x' (приa = 1).
Рассмотрим хорду графикаf (x), проходящую через точки (х',f(х')) и (х",f (х")). Ордината yaточки этой хорды, соответствующая абсциссе c,равна. Поэтому неравенство (1) графика выпуклой функции и хорды означает, что f (xa) £ ya, т.е. при любом расположении xa, на отрезке [х'; х"] точка графика функции 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 (х) в точке (x0, f (x0)), x0Î [а; b] имеет вид: у (х) =f (x0) +f ’ (x0) (x-x0). По формуле конечных приращений для любогохÎ [а; b] имеем: f (х) =f (x0) +f ’ (x) (x-x0),где точка x лежит междуx и x0. Поэтому
f (х) — у (х) = [f ’ (x) — f ’ (x0)] (x-x0), хÎ [а; b],
откуда с учетом того,что производная f ’ (x) выпуклой функции не убывает, получаем:
f (x) -y (x) ³ 0 (2)
для всех хÎ [а; b].
4. Если f (x) — выпуклая дифференцируемая на отрезке [а; b] функция и в точке х* Î [а; b] выполняется равенство
f ’ (x*)= 0 (3)
то х* является точкойглобального минимума f (х) на [а; b].
С учетом (3) уравнениекасательной у (х) =f (х0) +f ’ (х0) (х-х0) к графику f (x) для точки x0=х*принимает вид у (х) =f (x*). Поэтому из (2) следует,что f (x) />f (x*) для всех хÎ [а; b], т.е. х* — точка глобального минимума f (x).
Благодаря свойству 3выпуклых функций данное свойство приобретает простой геометрический смысл: посколькукасательная к графику f (x) в точке с абсциссой х*горизонтальна, а этот график расположен не ниже касательной, то х* есть точкаминимума f (x) (рисунок 3).
Таким образом, равенство(3) для выпуклой дифференцируемой функции является не только необходимымусловием глобального минимума (как для всякой дифференцируемой функции), но иего достаточным условием.
5. Можно показать, чтовсякая выпуклая непрерывная на отрезке [а; b] функцияявляется и унимодальной на этом отрезке. Обратное, вообще говоря, неверно (рисунок4).
/>
Рисунок 4 — график унимодальной, но не выпуклой функции
Таким образом, кромеперечисленных свойств, выпуклые функции обладают также и всеми свойствамиунимодальных функций.
2. Прямые методы безусловной оптимизации
Для решения задачиминимизации функции f (х) на отрезке [а; b] напрактике, как правило, применяют приближенные методы. Они позволяют найтирешение этой задачи с необходимой точностью в результате определения конечногочисла значений функции f (х) и ее производных в некоторых точках отрезка[а; b]. Методы, использующие только значения функции ине требующие вычисления ее производных, называются прямыми методами минимизации.
Большим достоинствомпрямых методов является то, что от целевой функции не требуетсядифференцируемости и, более того, она может быть не задана в аналитическом виде.Единственное, на чем основаны алгоритмы прямых методов минимизации, этовозможность определения значений f (х) в заданных точках.
Рассмотрим наиболеераспространенные на практике прямые методы поиска точки минимума. Самым слабымтребованием на функцию f (х), позволяющим использовать эти методы,является ее унимодальность. Поэтому далее будем считать функцию f (х) унимодальной на отрезке [а; b].
Рассмотрим конкретныевычислительные алгоритмы решения задачи безусловной минимизации f (х) ® min, xÎ En, которые опираются только на вычисление значенийфункции f (х), т.е. прямые методы минимизации. Важно отметить, что для ихприменения не требуется дифференцируемость целевой функции и даже ееаналитическое задание. Нужно лишь иметь возможность вычислять или измерять значенияf (х) в произвольных точках. Такие ситуации часто встречаются в практическиважных задачах оптимизации.
2.1 Прямыеметоды одномерной безусловной оптимизации
Методы исключения отрезков
Пусть а < x1<х2<b. Сравнив значения f (x) в точках x1 и х2 (пробныхточках), можно сократить отрезок поиска точки х *, перейдя к отрезку [а; х2],если /> или к отрезку m [x1; b] если /> (рисунок 5). Описанную процедуру можно повторить необходимое число раз,последовательно уменьшая отрезок, содержащий точку минимума. Когда длинапоследнего из найденных отрезков станет достаточно малой, следует положить />, где /> - однаиз точек этого отрезка, например, его середина. Методы минимизации, основанныена этом принципе, называются методами исключения отрезков.
Чтобы относительноеуменьшение отрезка на каждой итерации не зависело от того, какая из его частейисключается из дальнейшего рассмотрения, пробные точки следует располагатьсимметрично относительно середины исходного отрезка. В зависимости от способавыбора пробных точек получаются различные методы исключения отрезков. Далеепроводится рассмотрение двух наиболее часто встречаемых.
/>
Рисунок 5 — Уменьшение отрезка поиска точки минимумаметодами исключения отрезков
2.1.1 Методделения отрезка пополам (дихотомии)
Суть метода заключаетсяв том, что заданный отрезок [а; b] делится пополам:
/>.
Затем в каждой изполовин отрезка [а; с] и [с; b] выбираются по одной точке x1 и х2, в нихвычисляются значения функций, производится сравнение полученных значений, и врезультате сравнения устанавливается отрезок, в котором минимума быть не может.Откинув его, продолжаем ту же процедуру с полученным отрезком до тех пор, покавновь полученный отрезок не станет меньше по длине некоторой наперед заданнойвеличины:
/>.
Скорость достижения /> очевидно зависит отвеличины откидываемого отрезка. Поэтому x1и х2 выбираютсясимметрично на расстоянии />:
/> (4)
где d > 0 — малое число.
В конце вычислений пометоду дихотомии в качестве приближенного значения х* берут середину последнегоиз найденных отрезков [а; b], убедившись предварительно, что достигнутонеравенство />.
Опишем алгоритм методаделения отрезка пополам.
Шаг 1. Определить середину отрезка и значения x1 и х2 поформулам (4). Вычислить f (x1) и f (x2).
Шаг 2. Сравнить f (x1) и f (x2).Если />, то перейти к отрезку [а; x2], положив b = x2, иначе — к отрезку [x1;b], положив а = x1.
Шаг 3. Найти достигнутую точность />. Если /> то перейти к следующей итерации, вернувшись к шагу 1. Если />, то завершить поиск х*, перейдя к шагу 4.
Шаг 4. Положить
/>.
Замечания:
1. Число d из (4) выбирают на интервале (0; 2e) с учетом следующих соображений:
а) чем меньше d, тем больше относительное уменьшение длиныотрезка на каждой итерации, т.е. при уменьшении dдостигается более высокая скорость сходимости метода дихотомии;
б) при чрезмерно малом d сравнение значений f (x) в точках x1 и х2, отличающихся на величину d,становится затруднительным. Поэтому выбор d должен бытьсогласован с точностью определения f (x) и сколичеством верных десятичных знаков при задании аргумента х.
Пусть /> - погрешность счета. Тогдаследует учитывать следующее условие:
/>.
2.1.2 Методзолотого сечения
Рассмотрим такоесимметричное расположение точек x1 и х2 на отрезке [а; b], при которомодна из них становится пробной точкой и на новом отрезке, полученном послеисключения части исходного отрезка. Использование таких точек позволяет накаждой итерации метода исключения отрезков, кроме первой, ограничитьсяопределением только одного значения f (x),так как другое значение уже найдено на одной из предыдущих итераций.
Найдем точки x1 и х2,обладающие указанным свойством.
Рассмотрим сначалаотрезок [0; 1] и для определенности предположим, что при его уменьшенииисключается правая часть этого отрезка. Пусть х2 = t, тогда симметрично расположенная точка х1 =1-t (рисунок 6).
/>
Рисунок 6 — Определение пробныхточек в методе золотого сечения
Пробная точка х1 отрезка[0; 1] перейдет в пробную точку х2¢ = 1-tнового отрезка [0; t]. Чтобыточки х2 = t, и х2¢ = 1-tделили отрезки [0; 1] и [0; t] в одном и том же отношении,должно выполняться равенство /> или />, откуда находим положительное значение
/>…
Таким образом,
х1 = 1-t = />, />.
Для произвольногоотрезка [а; b] выражения для пробных точек примут вид
/>; />. (5)
Замечания:
1. Точки x1 и х2 из (5) обладают следующимсвойством: каждая из них делит отрезок [а; b] надве неравные части так, что отношение длины всего отрезка к длине его большейчасти равно отношению длин большей и меньшей частей отрезка. Точки с такимсвойством называются точками золотого сечения отрезка [а; b]. Это и объясняет название рассматриваемого метода.
2. На каждой итерации исключения отрезков с пробнымиточками (5) одна из них /> переходит на следующий отрезок и значение f (x) в этой точке вычислять не следует. Если новым отрезком становится [а; х2],то на него переходит пробная точка/> исходного отрезка, становясь его второй пробнойточкой (х2’= х1) (рисунок 6). В случаеперехода к отрезку [х1; b] пробная точка /> исходного отрезка становится первой пробнойточкой отрезка [х1; b].
3. Легко проверить, что х1=а+b-х2, и x2=а+b-х1. Поэтому на каждой итерации метода золотого сечения недостающуюпробную точку нового отрезка можно найти по перешедшей на него пробной точке спомощью сложения и вычитания, не используя формул (5).
4. В конце вычислений пометоду золотого сечения в качестве приближенного значения х* можно взятьсередину последнего из полученных отрезков
/>.
Опишем алгоритм методазолотого сечения.
Шаг 1. Найти х1 и х2 по формулам (5).Вычислить f (x1) и f (x2).
Шаг 2. Определить />. Проверка на окончание поиска: если en> e, то перейти к шагу 3, иначе — к шагу 4.
Шаг 3. Переход к новому отрезку и новым пробным точкам. Если f (x1) £ f (x2) то положить b=x2, x2=x1, f (x2)£ f (x1), x1=b-t (b-a) ивычислить f (x1), иначе — положить a=x1, x1= x2, f (x1)= f (x2), x2=b+t (b-a) ивычислить f (x2). Перейти к шагу 2.
Шаг 4. Окончание поиска: положить
/>, />.
Сравнение методовисключения отрезков. Присравнении прямых методов минимизации обычно учитывают количество Nзначений f (x), гарантирующее заданнуюточность определения точки х* тем или иным методом. Чем меньше N, тем эффективнее считается метод. При этом вспомогательные операциитакие, как выбор пробных точек, сравнение значений f (x) и т.п., не учитываются. Во многих практических случаях определениезначений целевой функции требует больших затрат (например, времени ЭВМ илисредств для проведения экспериментов) и вспомогательными вычислениями можнопренебречь. А эффективность метода минимизации особенно важна именно в такихслучаях, поскольку позволяет сократить указанные затраты.
Эффективность методовминимизации можно также сравнивать, на основании гарантированной точности e (N) нахождения точки х*,которую они обеспечивают в результате определения N значений f (x). Метод золотого сечения считают более точным,чем метод дихотомии, однако разница в точности в данном случае незначительна.
2.1.3Практическое применение прямых методов одномерной безусловной оптимизации
Пусть заданы следующиепараметры:
/>
Примем /> и />. Тогда /> (рисунок 7).
/>
Рисунок 7 — Поведениеисходной функции на заданном отрезке
Проведем несколькоитерации методом дихотомии:
/>
Поскольку f (x1)< f (x2), то b: =x2, a оставляем прежним. Тогда дляследующей итерации:
/>
Так как f (x1)> f (x2), то a: =x1, b оставляем прежним. Тогда натретьем шаге:
/>
Результаты полногорешения данной задачи представлены на рисунке 8. Листинг программы представленв приложении А.
/>
Рисунок 8 — Получение решенияметодом дихотомии
Для метода золотого сечения:
/>
Так как f (x1) < f (x2), то b: =x2, a оставляем прежним. Тогда дляследующей итерации:
/>
Поскольку f (x1)< f (x2), то b: =x2, a оставляем прежним. Тогда натретьем шаге:
/>
И так далее до тех пор, пока не достигнем указанной точности.Полный расчет представлен на рисунке 9. Листингпрограммы представлен в приложении А.
/>
Рисунок 9 — Получение решения методом золотого сечения
2.2 Методы безусловной минимизации функций многихпеременных
Теперь рассмотрим задачи оптимизации, сводящиеся к поискуточек минимума функции многих переменных на всем пространстве. В большинствеслучаев такая задача бывает сложнее задачи минимизации функции одной переменной, так как с ростом размерности пространствапеременных, как правило, возрастают объем вычислений и сложность алгоритмов, атакже затрудняется анализ поведения целевой функции.
2.2.1 Метод циклического покоординатного спускаЭтот метод заключается впоследовательной минимизации целевой функции f (x) понаправлениям x1 и x2.
/>
Рисунок 10 — Циклический покоординатный спуск.
Опишем этот алгоритм.
Шаг 0. Выбрать х Î En,критерий достижения точности e и шаг />. Найти f (x1(0),x2(0)).
Шаг 1. Принять x1(1) = x1(0) +/>.Определить f (x1(1),x2(0)). Сравнить полученное значение с значением начальной функции. Если f (x1(1),x2(0)) < f (x1(0),x2(0)), то перейти к шагу 5, если же f (x1(1),x2(0)) > f (x1(0),x2(0)), то перейти к шагу 2.
Шаг 2. Принять x1(1) = x1(0) — />.Определить f (x1(1),x2(0)). Сравнить полученное значение с значением начальной функции. Если f (x1(1),x2(0)) < f (x1(0),x2(0)), то перейти к шагу 5, если же f (x1(1),x2(0)) > f (x1(0),x2(0)), то перейти к шагу 3.
Шаг 3. Принять x2(1) = x2(0) +/>.Определить f (x1(0),x2(1)). Сравнить полученное значение с значением начальной функции. Если f (x1(0),x2(1)) < f (x1(0),x2(0)), то перейти к шагу 5, если же f (x1(0),x2(1)) > f (x1(0),x2(0)), то перейти к шагу 4.
Шаг 4. Принять x2(1) = x2(0) — />.Определить f (x1(0),x2(1)). Сравнить полученное значение с значением начальной функции. Если f (x1(0),x2(1)) < f (x1(0),x2(0)), то перейти к шагу 4, если же f (x1(0),x2(1)) > f (x1(0),x2(0)), то принять исходную точку заминимум.
Шаг 5. Проверить условие достижения точности />.
Если в процессе решенияс шагом /> не получено решения, топринять />
/>2.2.2 АлгоритмХука-ДживсаЭтот алгоритм содержитдве основные процедуры:
а) исследующийпокоординатный поиск в окрестности данной точки, предназначенный дляопределения направления убывания f (х);
б) перемещение внаправлении убывания.
/>
Рисунок 11 — Метод Хука-Дживса
Трактовать данный метод можно по-разному. Рассмотрим один измногочисленных вариантов.
Опишем один из алгоритмов данного метода.
Шаг 1. Выбираем начальную точку и находим в нейзначение функции.
Шаг 2. Обозначимкоординаты начального вектора: />.
Тогда, соответственно, угол направления движения
/>.
Рассчитываем координаты4-х точек в окрестности начальной по следующим формулам:
/>
/>
/>
/>
Находим в указанныхточках значения функции. Если какое-нибудь из них оказалось меньше значенияфункции в точке x0, то принимаем его за исходное.
Шаг 3. Сравниваем полученные значения с f (x1(0),x2(0)). Если какое-нибудь из нихоказалось меньше значения функции в 0-й точке точке, то принимаем его заисходное и переходим к шагу 5.
Шаг 4. Если же все полученные значения функции оказалисьбольше исходного, то уменьшаем шаг /> ипереходим к шагу5.
Шаг 5. Проверить условие достижения точности
/>.
Если данное условие невыполнено, возвращаемся к шагу 2.
2.2.3 Практическое применение прямых методовбезусловной многомерной оптимизации
Пусть заданы следующиеусловия:
/>
Тогда по методуциклического покоординатного спуска будет выполнен счет следующего вида:
/>
/>
Т. к. />, будемдвигаться в противоположную сторону по оси абсцисс с тем же шагом:
/>
/>,
поэтому продолжаем двигаться дальше с тем же шагом в данномнаправлении до достижения указанной точности, в противном случае уменьшаем шаг(/>):
/>
Результаты работыданного алгоритма представлены на рисунке 12. Листинг программы приведен вприложении Б.
/>
Рисунок 12 — Решениепоставленной задачи методом спуска
Перейдем к методуХука-Дживса. Обозначим координаты начального вектора: />.
Тогда, соответственно, угол направления движения
/>.
Найдем значения функции 4-х точек в окрестности начальной:
/>
/>
/>
/>
Минимальное значение функция принимает в точке2, поэтомудвижемся в заданном направлении 2 пока идет уменьшение функциидо достижения указанной точности, в противном случае уменьшаем шаг
(/>):
/>
Конечный результат получен на ЭВМ за 36итераций. Результат представлен на рисунке 13. Листинг программы приведен в приложении Б.
/>
Рисунок 12 — Решениепоставленной задачи методом спуска
2.2.4 Минимизацияпо правильному симплексуПравильным симплексом впространстве En называется множество из n + 1равноудаленных друг от друга точек (вершин симплекса). Отрезок, соединяющий двевершины, называется ребром симплекса.
В пространстве E2правильным симплексом является совокупность вершин равностороннеготреугольника, в E3 — правильного тетраэдра.
Если х0-одна из вершин правильного симплекса в Enто координаты остальных п вершин х1,. ., хn можно найти, например, по формулам:
/> (6), где
d1/>, d2/>,
a- длина ребра. Вершину х0симплекса,построенного по формулам (6), будем называть бaзовой.В алгоритме симплексного метода используется следующее важное свойствоправильного симплекса. По известному симплексу можно построить новый симплексотрaжением какой-либо вершины, например, хk симметрично относительно центра тяжести хcостальных вершин симплекса. Новая и старая вершины/>и хk связаны соотношением:
/>, где xc/>.
В результате получаетсяновый правильный симплекс с тем же ребром и вершинами />=2xc — хk, хi, i= 0,. ., n, i¹ k. Такимобразом, происходит перемещение симплекса в пространстве Еn. На рисунке 13 представлена иллюстрация этого свойства симплекса впространстве Е2.
/>
Рисунок 13 — Построениенового симплексa в E2отрaжением точки х: a — нaчaльныйсимплекс х0, х1, />;б — новый симплекс х0, х1, />;центр отрaжения — точкa xc = (х0+ х1) /2
Поиск точки минимумафункции f (x) с помощью правильных симплексов производят следующим образом. Накаждой итерации сравниваются значения f (х) в вершинах симплекса. Затемпроводят описанную выше процедуру отражения для той вершины, в которой f (х) принимаетнаибольшее значение. Если в отраженной вершине получается меньшее значениефункции, то переходят к новому симплексу. В противном случае выполняют еще однупопытку отражения для вершины со следующим по величине значением f (х). Если иона не приводит к уменьшению функции, то сокращают длину ребра симплекса,например, вдвое и строят новый симплекс с этим ребром. В качестве базовойвыбирают ту вершину х0старого симплекса, в которой функцияпринимает минимальное значение. Поиск точки минимума f (x) заканчивают,когда либо ребро симплекса, либо разность между значении функции в вершинахсимплекса становятся достаточно малыми. Опишем один из вариантов алгоритмаэтого метода.
Шаг 0. Выбрать параметр точности e, базовую точку х0, ребро /> и построить начальныйсимплекс по формулам:
/>
Вычислить f (х1(0),x2(0)).
Шаг 1. Вычислить значения f (х) ввершинах симплекса х1,. ., xn.
Шаг 2. Упорядочить вершины симплекса х0,. .,хn так, что бы f (х1(0),x2<sup/>
(0)) £ …£ £f (х1) £ f (хn-1) £ f (хn).
Шаг 3. Найти среднее значение функции:
/>.
Проверить условие /> из учета того, что:
/> (3.38)
Если оно выполнено, товычисления прекратить, полагая х* » х0,f * » f (x0).В противном случае перейти к шагу 4.
Шаг 4. Найти
/>
и выполнить отражениевершины хn. К примеру, для отражения вершины А следуетнайти точку
/>.
Тогда отраженная вершинабудет иметь вид:
/>.
Если f (Е) <f (xn),то перейти к построению нового симплекса, иначе — перейти к шагу 5.
Шаг 5. Перейти к новому правильному симплексу с вдвоеменьшим ребром (редуцирование), считая базовой вершиной х0. Остальныеn вершин симплекса найти по формуле хi = (хi + х0) /2, i=1,. .,n. Перейти к шагу 1.
Геометрическаяиллюстрация работы алгоритма в пространстве показана на рисунке 14, где точких0,х1,х2 — вершиныначального симплекса, а пунктиром указаны процедуры отражения.
/>/>
Рисунок 14 — Поиск точки минимума функции />с помощью правильныхсимплексов в пространстве />
Замечания:
1. Следует иметь в виду,что если функция f (х) многомодальна, то описанным методом может быть найденаточка локального, а не глобального минимума f (х).
2. Если ограниченностьснизу целевой функции не очевидна, то в алгоритм метода следует включитьдополнительную процедуру останова.
2.2.5 Поискточки минимума по деформируемому симплексу
Алгоритм, описанный вразд.2.2.4, можно модифицировать, добавив к процедуре отражения при построениинового симплекса процедуры сжатия и растяжения. А именно, положение новойвершины вместо вершины хn, соответствующейнаибольшему значению функции, находится сравнением и выбором наименьшего средизначений целевой функции в точках;
/> (7)
Геометрическаяиллюстрация этих процедур для пространства E2приведена на рисунках 15 и 16.
/>
Рисунок 15 — Пробныеточки z1,z2,z3,z4 для перехода к новомусимплексу
/>
Рисунок 16 — Новыесимлексы, полученные в результате процедур сжатия (а, б); отражения (в); растяжения(г).
Так как величина a Î (0;
1), то выбор точек z1и z2 соответствует сжатию симплекса; b » 1, поэтому выбор точки z3 соответствует отражению, а g > 1 и выбор точки z4 приводит крастяжению симплекса. Численные эксперименты показывают, что этот алгоритмхорошо работает в пространстве En для n £ 6. Отметим,что при деформациях утрачивается свойство правильности исходного симплекса. Поэтому,не стремясь к правильности начального симплекса, его строят из произвольнойбазовой точки х0Î En, по формулам
/>, (8)
где e i — i-й базисный вектор; a- параметр симплекса. На практике хорошозарекомендовал себя следующий набор параметров a, b и g для выборапробных точек zi в формулах (9): a =1/2, b = 1 и g =2.
Опишем алгоритм методапоиска точки минимума функции по деформируемому симплексу.
Шаг 0. Выбрать параметр точности e, параметры a, b и g, базовуюточку х0, параметр a и построитьначальный симплекс. Вычислить f (х0).
Шаг 1. Вычислить значения функции в вершинах симплекса х1,...,xn.
Шаг 2. Упорядочить вершины х0,..., xn так, чтобы f (х0) £ … £ f (хn).
Шаг 3. Проверить достижение заданной точности. Если оновыполняется, то вычисления завершить, полагая х * » х0, f * » f (х0). Иначе — перейти к шагу 4.
Шаг 4. Найти />ипробные точки zk, k=1, …, 4 пo формулам (9). Найти f (z*) = min f (zk). Если f (z*) < f (zn). то положить xn=z*и перейти к шагу 2. Иначе — перейти к шагу 5.
Шаг 5. Уменьшить симплекс, полагая хi = (хi + х0) /2, i = 1,.., n и перейти к шагу 1.
Замечание. Для того чтобы избежать сильной деформациисимплекса, алгоритм иногда дополняют процедурой обновления. Например, после Nшагов алгоритма из точки х0снова строят симплекс, полагая а = ||x0-xn||.
С теоретической точкизрения описанные методы минимизации слабо исследованы, однако практикапоказывает их работоспособность.
2.2.6 Практическая реализация симплексных методов
Пусть заданы следующиеусловия:
/>
Для первой вершины:
/>
Для второй вершины:
/>
Для третьей вершины:
/>
Наибольшее значение функция принимает в точке2, ее и будемотражать. Для этого найдем точку С, лежащую между 1-й и 3-й точками:
/>
Рассмотрим метод симплекса.
Находим координаты отраженной вершины Е и значение в нейфункции:
/>
Т. к. />, тостроим новый симплекс на вершинах Е,1 и 3 и повторяем эту операцию до тех пор,пока среднеквадратичное отклонение не примет указанной величины, в противномслучае приступаем к редуцированию — уменьшению размеров симплекса.
Результат рабочей программы представлен на рисунке 17. Листингприведен в приложении В.
/>
Рисунок 17 — Практическая реализация симплекс-метода
Перейдем к методу деформируемого симплекса.
Введем коэффициенты уменьшения и увеличения: />.
Найдем значения функции 4-х точек в окрестности начальной:
/>
/>
/>
/>
Минимальное значение функция принимает в точке1, поэтомустроим новый симплекс на вершинах Е,1 и 3 и повторяем выше указанную операциюдо тех пор, пока среднеквадратичное отклонение не примет указанной величины, впротивном случае приступаем к редуцированию — уменьшению размеров симплекса. Результатрабочей программы представлен на рисунке 18. Листинг приведен в приложении В.
/>
Рисунок 18 — Практическая реализация метода деформируемого симплекса
3. Условная оптимизация
До сих пор рассматривались методы безусловной оптимизации, т.е.на параметры оптимизации не накладывались никакие ограничения, поэтомудопустимая область определения определялась только лишь условием существованияцелевой функции.
Но в реальных задачах обязательно присутствуют ограничениятипа равенств или неравенств и ограничения по пределам изменения:
/>
Наличие ограничений приводит к изменению точки минимума,тогда как в задаче без ограничений данная точка может оказаться вне допустимойобласти.
Рассмотрим 2 метода решения задачи условной оптимизации:
Если наложены ограничения типа равенства, то из этогоограничения выразим одну переменную через другую (двумерный случай). Подставивполученную зависимость в целевую функцию, получим преобразованную целевую функциюбез ограничений.
Целевая функция преобразуется так, чтобы эта преобразованнаяфункция в допустимой области была бы близка к исходной, а в недопустимыхобластях имела бы значения, существенно большие, чем допустимые. Такие функцииносят название штрафных, так как к исходной функции добавляются штрафы приприближении к недопустимым областям.
Например:
/>
где R — параметр штрафа (некое число).
Существуют многочисленные штрафные функции для неравенств, адля равенств на практике применяется один вид, т.е. если имеем задачу />, тогда формируем штрафнуюфункцию
/>
В данном курсовом проекте необходимо было максимизироватьобъемное тело, представленное на рисунке 19.
/>
Рисунок 19 — Объем, который необходимо максимизировать
Указанное тело состоит из цилиндра и стоящего на немсегмента сферы. Определим изменяемые параметры для данного случая (рисунок 20):r — радиус цилиндра (равенрадиусу сферы), h — высота сегментасферы и h2 — высота цилиндра.
/>/>
Рисунок 20 — Изменяемые параметры
Для цилиндра: />.
Для сегмента: />
Тогда для всей фигуры: />
Пусть площадь всего объема равна 200: />
Выразим из формулы общей площади параметр h2:
/>.
Подставим полученное выражение в формулу объема, получим:
/>
Обозначим r=3 и h=1.Затем следует провести двумерную оптимизацию. Ниже на рисунке 21приведена рабочая форма программы, реализующая двумерную оптимизацию дляпервого случая и трехмерную — для штрафных функций по методу координатногоспуска.
Для указанного случая V=260.799603505204при r*=4.06250000000002 и h*=0.975.
Случай со штрафными функциями в общем виде можно записатькак:
/>
где с -площадь.
Таким образом, следует провести трехмерную оптимизацию дляследующей функции:
/>
Изменяемыми параметрами в данном случае являлись r — радиус цилиндра и сферы, h — высота сегмента и h2 — высота цилиндра.
Для второго случая V=260.778443852174при r*=4.44999999999999, h*=1.025и h2*=4.05.
Таким образом, к предложенному объему были применены обаметода решения задачи условной оптимизации. Результат рабочей программыпредставлен на рисунке 21, а листинг — в приложении Г.
/>
Рисунок 21 — Условная оптимизация
4. Линейное программирование
Если целевая функция и все ограничения в задаче оптимизацииявляются линейными функциями, то такая задача носит название линейногопрограммирования. В общем случае она имеет вид:
/>
Если в общей модели присутствуют ограничения 3-х видов, тозадачи, в которых есть только ограничения первого вида, не считая ограниченийна знаки переменных, называются задачами распределительного типа.
Они широко распространены, поэтому будут подробнорассматриваться в рамках данного курсового проекта.
Понятно, что ограничения определяют область допустимыхзначений переменных, поэтому любое x из этой области являютсядопустимым решением, а x* — оптимальное решение, если:
/>
Те ограничения, которые принимают вид равенства, называютсяактивными ограничениями; соответствующий этому ограничению ресурс называетсядефицитным.
Стандартная форма записи задачи линейного программированияимеет вид:
/>
Система уравнений является базисной, то есть ранг матрицы равняетсяL-числу строк. Понятно, что L <N, где N- число переменных. Если же L =N,то при условии базисности допустимая область превращается в точку.
Исходная задача линейного программирования млжет бытьсформулирована так, что ограничения имеют вид равенств. Можно показать, что отформы записи в виде равенств можно перейти к форме записи в виде неравенств.
Рассмотрим ограничения:
/>.
В базисной системе число неизвестных больше, чем числопеременных. Следовательно, любые L переменных могутбыть выражены через оставшиеся N — Lсвободные переменные. При этом такая система имеет единственное решение из-забазисности системы. Выбор свободных и базисных переменных произволен.
Запишем базисную систему в виде:
/>
Поскольку Rang (AБ) = L, то можно сказать, чтоматрица /> существует.
Тогда
/>, а />
является решением матричного уравнения /> при любых />.
Если />, где /> - N-мерныйноль, то полученное решение называется допустимым. Если при этом />, т.е. />, то решение называетсябазисным. Если, к тому же, />, торешение называется допустимым базисным.
Если множество /> непусто, то область допустимых значений выпукла, и базисные решения существуют.
Также можно показать, что допустимое базисное решениеявляется крайней точкой />.
Если /> замкнута,то число крайних точек ограничено.
Оно не превышает
/>.
Целевая функция достигает своего максимума в крайней точке.
Если же max достигаетсяв нескольких крайних точках, то значение функции в этих точках одинаково. Такоеже значение функция принимает во всех точках выпуклой и линейной комбинацииэтих крайних точек.
То, что целевая функция достигает max в крайней точке, а число таковых ограничено, в принципе,позволяет решить задачу оптимизации простым перебором значений функции вкрайних точках.
Однако, число крайних точек растет как N!..Поэтому разработан симплекс-метод, заключающийся в том, что, начиная сбазисного решения, осуществляется переход к другим базисам при условии ростазначений целевой функции. Симплекс-метод при известном допустимом базисном решении.Для задач распределительного типа, в которых присутствуют ограничения типа /> несложно убедиться в том,что после записи задачи в стандартной форме легко можно найти допустимыебазисные решения, которые можно использовать в качестве начального базиса.
Если в задаче N переменных и L ограничений (/>), тоцелевая функция имеет вид:
/>
Разделим Г на 2 части: Г (ГБГS). Тогда целевая функция будет выглядеть как:
/>
В начальной допустимой базисной точке, как известно, YS=0. Следовательно,
/>
Идея симплекс-метода заключается в том, что при переходе кновому допустимому базисному решению второе слагаемое должно быть положительным.Среди положительных выбирается наибольшее. В скалярном виде:
/>.
Метод выбора столбца, вводимого в базис и выбора строкипеременной, выводимой из базиса, сведем в так называемую симплекс-таблицу.
Рассмотрим следующую задачу:
/>
Параметр k в этом случае — подбираемый коэффициент, величина которого оказалась: k=7.
Рассмотрим геометрический способ решения задачи линейногопрограммирования. Запишем для данного случая:
/>
Тогда на рисунке можно увидеть, что область допустимыхзначений, ограниченная указанными прямыми, принимает вид пятиугольника:
/>
Оптимальное решение соответствует прямой, параллельной fнач. и проходящей через самую дальнюю от fнач. точку допустимого множества. Из графикавидно, что оптимальная точка x* (1.8, 1.14375) находитсяна пересечении g1 (x1) и g2 (x2). Значение функции в этойточке: f (x*) =15.375.
Для решения данной задачи с помощью симплекс-таблицперепишем исходную систему в следующем виде:
/>
Тогда симплекс-таблица на 0-й итерации примет вид:
Значение y1 y2 y3 y4 y5 y3 8 1 4 1 y412
6
1 1 y5 7 2 3 1 -f 6 4Суть симплекс-метода в том, что происходит замена однойпеременной в базисе так, чтобы значение целевой функции возрастало. Поэтому вкачестве переменной для ввода в базис выбирается та из yS,которой соответствует наибольшее положительное значение симплекс-разности.
Под симплекс-разностью понимаются элементы, стоящие в строке-f на пересечении с соответствующей переменной yi. В данном случае наибольшую положительнуюсимплекс-разность, равную 6, имеет переменная y1.
Далее выбираем ту переменную, которая выводится из базиса. Выбираетсята переменная из базиса, у которой элемент на пересечении строки базисной переменнойили столбца вводимой в базис переменной (y1) положителен.
Для данного случая это переменные y3,y4,y5.
Проведем сравнение отношений элемента столбца y1 ксоответствующему элементу столбца значений: /> -наибольшее отношение.
Следовательно, из базиса выводится переменная y4.
Перейдем к первой итерации. Элемент, стоящий на пересечениивыводимой строки и столбца вводимой переменной, называется ведущим элементом.
На месте ведущего элемента на текущей итерации запишем 1, авсе остальные элементы равны 0:
Значение y1 y2 y3 y4 y5 y3 0.0000 y1 1.0000 y5 0.0000 -f 0.0000Заполним строку y1. Для этого строкуy4 0-й итерации разделим на 6:
Значение y1 y2 y3 y4 y5 y3 0.0000 y1 2.0000 1.0000 0.1667 0.0000 0.1667 0.0000 y5 0.0000 -f 0.0000Для того, чтобы заполнить строки итерации 1, используемстроку y1 итерации 1 и соответствующие строки итерации0.
Таким образом, симплекс-таблица на первой итерации будетиметь вид:
Значение y1 y2 y3 y4 y5 y3 6.0000 0.0000 3.8333 1.0000 -0.1667 0.0000 y1 2.0000 1.0000 0.1667 0.0000 0.1667 0.0000 y5 3.0000 0.0000 2.6667 0.0000 -0.3333 1.0000 -f -12.0000 0.0000 3.0000 0.0000 -1.0000 0.0000Аналогичные операции проделаем и с полученной таблицей. Тогдадля второй итерации:
Значение y1 y2 y3 y4 y5 y3 1.6875 0.0000 0.0000 1.0000 0.3125 -1.4375 y1 1.8125 1.0000 0.0000 0.0000 0.1875 -0.0625 y21.1250
0.0000
1.0000
0.0000
-0.1250
0.3750
-f-15.3750
0.0000 0.0000 0.0000 -0.6250 -1.1250Так как во второй итерации среди симплекс-разностей нетположительных элементов, то дальнейшего улучшения невозможно. Полученныйрезультат является оптимальным: />
Заключение
В ходе выполнения данного курсового проекта были исследованыразличные численные методы, применяемые при решении различного рода уравнений иих систем. В частности, были исследованы метод хорд, касательных, метод простыхитераций для решения нелинейных уравнений, методы простых итераций и Зейделядля решения систем линейных алгебраических уравнений, метод интерполирования,численного интегрирования и дифференцирования.
На основе данных нашего исследования были разработаныпрограммы для применения соответствующих методов.
В данном курсовом проекте был также проведен сравнительныйанализ всех методов, в результате чего все поставленные задачи были выполнены,цели достигнуты. Мы приобрели навыки в применении различных численных методовна практике. Теперь перед нами стоит задача в применении приобретенных знаний всвоей будущей профессиональной деятельности.
Списокиспользованной литературы
1. Турчак Л.И. Основы численныхметодов: Учеб. пособие. — М.: Наука, Гл. ред. физ. — мат. лит., 1978. — 320 с.
2. Щетинин Е.Ю. Математическиеметоды оптимизации. Конспект лекций
3. Гилл Ф., Мюррей У., Райт М. Практическаяоптимизация. Пер. с англ. — М.: Мир, 1985 -509с.
4. Дегтярев Ю.И., «Исследованиеопераций», Москва 1986.