Турчак Л.И. Основы численных методов. Под ред. В.В.Щенникова (1987) (1095857), страница 29
Текст из файла (страница 29)
В результате решения задачи будут найдены значения проектных параметров х„х„а затем и х,. В приведенном примере фактически получилась задача безусловной оптимизации для целевой функции (6.5), поскольку ограничение-равенство оыло использовано для исключения параметра х,. Вместе с тем можно рассматриваемую задачу усложнить и поставить дополнительные условия. Например, потребуем, чтобьг данный контейнер имел „длину не менее 2 м. Это условие запишется в виде ограничения-неравенства на один из параметров, например х, ~ 2. (6.6) 'Хаким образом, мы получили следующую условную задачу оптимизации: минимизируя функцию (6.5) и учитывая ограничение-неравенство (6.6), найти оптимальные значения параметров плана хг, х, (хг ~ О, х, > 0).
5 2. ОдноыеРнхя оптимиЗАпия Эта теорема не доказывает единственности решения. Не исключена возможность, когда равные экстремальные значения достигаются сразу в нескольких точках данного отрезка, В частности, такая ситуация имеет место для периодической функции, рассматриваемой на отрезке, содержащем несколько периодов, Будем рассматривать методы оптимизации для разных классов целевых функций, Простейшим из них является случай дифференцируемой функции /(х) на отрезке [а, Ь], причем функция задана в виде аналитической зависимости у =/(х), и может быть найдено явное выражение для ее производной / (х). Нахожденпе экстремумов таких функций можно проводить известными из курса высшей математики методами дифференциального исчисления.
Напомним вкратце этот путь. Функция ~(х) может достигать своего наименьшего и наибольшего значений либо в граничных точках отрезка [а, Ь1, лпоо в точках минимума и максимума. Последние точки обязательно должны быть критическими, т. е. производная /'(х) в этих точках обращается в нуль,— это необходимое условие экстремума. Следовательно, для определения наименыпего или наибольшего значений функции ~(х) па отрезке [а, Ь1 нужно вычислить ее значения во всех критических точках данного отрезка и в его граничных точках и сравнить полученные значения; наименьшее или.
наибольшее из них и будет искомым значением. П р и и е р. Найти наименьшее и наибольшее значения функции /(х) = т'/3 — ж на отрезке [1, 31. Р еш ение. Вычислим производную этой функции: ~' (х) = х' — 2х. Приравнивая ее нулю, найдем критические точки а' — 2х=О, х,=О, х,=2. Точка х О лежит вне рассматриваемого отрезка, поэтому для анализа оставляем три точки: а 1, т~=2, Ь=3. Вычисляем значения функции в этих точках~ ~(1) = -2/3, ~(2) = -4/3, ~(3) О. Сравнивая полученные величины, находим, что наименьшего значения функция /'(х) достигает в точке ж = 2, наибольшего — в точке х= 3, т.
е. ~ш~ ~(2) = -4/3, ~щы = ~(3) О. $74 гл. 6. мнтоды оптггмизлппи В рассмотренном примере уравнение / (х) = О для отыскания критических точек удалось решить непосредственно. Для более сложных видов производной функции ~'(х) неооходпмо использовать численные методы решения нелинейных уравнений. Как уже отмечалось, используемый здесь метод, основанный на вычислении производной целевой функции, требует ее аналитического представления.
В других случаях, когда целевая функция задана в таоличном виде пли может быть вычислена прп некоторых дискретных значениях аргумента, используются различные методы поиска. Они основаны на вычислении целевой функции в отдельных точках и выборе среди них наибольшего или наименьшего значений. Существует ряд алгоритмов решения. данной задачи. Рассмотрим некоторые из них.
2. Методы поиска. Численные методы поиска экстремальных значений функции рассмотрим на примере нахождения минимума функции ~(х) на отрезке [а, Ь]. Будем предполагать, что целевая функция унил~одальна., т. е. на данном отрезке опа имеет только один минимум. Отметим, что в инженерной практике обычно встречаются именно такие целевые функции. Процесс решения задачи методом поиска состоит в последовательном сужении пптервала изменения проектного параметра, называемого интервалом неопределенности, В начале процесса оптимизации его длина равна Ь вЂ” а, а к концу она должна стать менее заданного допустимого значения е, т.
е. оптимальное значение проектного параметра должно находиться в интервале неопределенности — отрезке [х„, х„+,~, причем х„+, — х. ~ е. Наиболее простым спосооом сужения интервала неопределенности является деление его на некоторое число равных частей с последующим вычислением значений целевой функции. в точках разбиения. Пусть и — число элементарных отрезков, Ь =(6 — а)/и — шаг разбиения. Вычислим значения целевой функции у~ = /~(х) в узлах х, = а+ Иг - (и = О, 1, ..., и). Сравнивая полученные значения ~(х„), 'найдем среди них наименьшее у~ = ~(х;).
Число иг„= у; можно приближенно принять за наименьшее значение целевой функции ~(х) на отрезке [а, Ь~. Очевидно, что близость т„к минимуму т зависит от числа точек, н для непрерывной функции ~(х) 11гп гии = иг~ гг~ яд я 2. Од110мггнля оптимпзАцня 175 т. е. с увеличением числа точек разбиения погрешность в определении минимума стремится к нулю. В данном методе, которьш можно назвать методом перебори, основная трудность состоит в выборе и и оценке погрешности. Можно, например, провести оптимизацию с разными шагами и исследовать сходимость такого итерационного процесса.
Но это трудоемкий путь. Более экономичным спосооом уточнения оптимального параметра является использование свойства унимодаль- ности целевои функции, которое позволяет построать процесс сужения интервалаа неопределенности. Пусть, как и ранее, среди всех значений уннмодальыой функции у = 1(х), вычисленных в узлах х„(Й = = О, 1, ..., и), наименьшим оказалось у,. Это озна- 7 1 1 1 чает, что оптимальное зна- " х~ -~.-~ ~; х.'.
х,- Ь х чение проектного парамет- Рвс. 29 ра находится на отрезке [х; „х.;+,1 (рис. 29), т. е. интервал неопределенпости сузился до длины двух шагов. Если размер интервала недостаточен для удовлетворения заданной погрешности, т. е. х;+, — х;, ) е, то его снова можно уменьшить путем нового разбиения. Получится интервал, равный двум длинам нового шага разопенпя, п т. д. Процесс оптимизации продолжается до достижения заданного размера интервала неопределенности, В описанном методе общего поиска можно с помощью некоторой изобретательности, а также разумного выбора шага разоиенпя дооиться эффективного поиска.
Например, пусть начальная длина интервала неопределенности равна Ь вЂ” а= 1. Нужно добиться его уменьшения в 100 раз. Этого легко достичь разбиением интервала на 200 частей. Вычислив значения целевой функции ~(х,) (й'= О, 1, ..., 200); найдем ее минимальное значение ~(х;), Тогда искомым интервалом неопределенности будет отрезок [х, „х;+,~. Однако можно поступить и иначе, Сначала разооьем отрезок [а, Ъ1 на 20 частей и найдем интервал неопределенности длиной 0.1, при этом ыы вычислим значения целевой функции в точках хам=и+0.051 (й=О, 1, гл.
6. методт>1 оптпмпз гнпп ! ~ Г(х~» ~(~,) Ф ! ~((,) ~ ~~(~~ а4 а 'а~=~~а ~Ъ ~'1 Ь1- хъ Рис. ЗО Поясним сначала идею метода геометрически, а затем выведем необходимые соотношения, На первом шаге процесса оптимизации внутри отрезка [а„Ь,~ (рис. 30, а) выбираем две внутренние точки х~ и х2 и вычисляем значения целевой функции ~(х~) и ~(х2). Поскольку в данном случае ~(х~)(~(х~), очевидно, что минимум расположен на одном из прилегающих к х~ отрезков [а„х,] или ..., 20). Теперь отрезок [х; ~, х,+~~ снова разобъем на 20 частей; получим искомый интервал длиной 0.01, причем значения целевой функции вычисляем в точках х„= =х;, +0.005Уа (1=1, 2, ..., 19) (в точках х;, и х,+, значения ~(х) уже найдены). Таким образом, во втором случае в процессе оптимизации произведено 40 вычислений значений целевой функции против 201 в первом случае, т.
е. способ разбиения позволяет получить существенную э <спомню вычислений. Существует ряд специальных методов поиска оптимальных решений с разными способамп выбора узлов и сужения интервала неопределенности: метод деления отрезка пополам, метод золотого сечения и др.
Рассмотрим одпп из них. 3. Метод золотого сечения. При построении процесса оптимизации стараются сократить объем вычислений и время поиска. Этого достигают ооычно путем сокращения ко:шчества вычислении (или измерений — при проведении эксперимента) значений целевой функции ((х) . Одним пз наиоолее эффективных методов, в которых прп ограниченном количество вычислений ~(х) достигается наилучшая точность, является метод золотого сечения. Он состоит в построении последовательности отрезков [а~, Ь,], [ао ЬД, ..., стягивающихся к точке минимума функции ~(х). На каждом шаге, за исключением первого, вычисление значения функции ~(х) проводится лишь один раз. дта точка, называемая голатыл сечением, выбирается специальным ооразом.
5 2. ОдномнРнля оптпмпзАцпя 177 анхо хг]. ПоэтомУ ОтРезок [хг1 Ьо] и01кпО ОтОРОсить, СУЗНВ тем самым первоначальный интервал неопределенности. Второй шаг проводим на отрезке ~а1, Ь~] (рис. 30, б), где а, =а„Ь, = х,. Нужно снова выбрать две внутренние точки, но одна из них (х,) осталась из предыдущего шага, поэтому достаточно выбрать лишь одну точку х„вычислить значение Е(хг) и пронести сравнение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
