Какой из перечисленных ниже методов не является методом исключения интервалов

Итоговый тест с эталонами ответов по дисциплине «Методы оптимизации» , страница 4

17. Метод, используемый при решении задач оптимизации, в которых управление и координаты объекта могут иметь разрывы, – _________ _________.

(Эталон: принцип максимума)

1. Схема метода Эйлера…

2. Метод Эйлера предназначен для решения обыкновенных дифференциальных уравнений _________ порядка

(Эталон: первого; первый)

4. Динамическое программирование позволяет одну задачу со многими переменными заменить…

а) рядом последовательно решаемых задач с меньшим числом переменных

б) группой различных задач, с одинаковым числом переменных

в) рядом произвольно решаемых задач, с одинаковым числом переменных

г) группой последовательно решаемых задач с большим числом переменных

5. Основной принцип оптимизации многошагового процесса и особенность вычислительного метода динамического программирования, принцип оптимальности _________

(Эталон: Беллмана; Беллман)

21. Множество X, на котором оптимизируется f(x), …

5. Функция, имеющая более одного экстремума, называется …

23. Точка х * ÎХ – решение задачи условной оптимизации при …

24. Точка х * ÎХ является глобальным решением задачи оптимизации, если выполняются условия:

26. Верно утверждение – …

а) метод наискорейшего спуска относится к алгоритмам нулевого порядка

б) методы исключения интервалов являются алгоритмами нулевого порядка

в) метод дихотомии является алгоритмом первого порядка

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

27. Верны утверждения:

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

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

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

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

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

45. Точка х 0 , не лежащая на отрезке между двумя любыми точкам выпуклого многогранного множества М отличными от x 0 , называется …

46. Вершины многогранника – это … точки.

47. Если решение задачи линейного программирования существует, то оно обязательно достигается на _________ допустимой области.

13.2.1. Методы исключения интервалов

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

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

Правило исключения интервалов. Пусть W(x) унимодальна на отрезке [a,b], а ее минимум достигается в точке x * . Рассмотрим x₁ и x₂, расположенные a<x₁<x₂<b.

Если W(x₁)>W(x₂), то точка минимума W(x) не лежит в интервале (a,x₁), т.е. x * (x₁,b).

Если W(x₁)<W(x₂), то точка минимума W(x) не лежит в интервале (x₂,b), т.е. x * (a,x₂).

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

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

Процесс применения методов поиска на основе исключения интервалов включает два этапа:

этап установления границ интервала;

этап уменьшения интервала.

Этап установления границ интервала

Выбирается исходная точка, а затем на основе правила исключения строится относительно широкий интервал, содержащий точку оптимума. Обычно используется эвристический метод, например, Свенна, в котором (k+1) -пробная точка, которая определяется по рекуррентной формуле

x_o — произвольно выбранная начальная точка;

 — подбираемая величина шага.

Знак  определяется путем сравнения значений W(x), W(x_o + ), W(x_o -):

если W(x_o -) W(x) W(x_o + ), то  имеет положительное значение;

если W(x_o -) W(x) W(x_o + ), то  имеет отрицательное значение;

если W(x_o -) W(x) W(x_o + ), то точка минимума лежит между x_o - и x_o +  и поиск граничных точек завершен;

если W(x_o -) W(x) W(x_o + ), то имеем противоречие предположению об унимодальности.

Пример 13.3. Приложение метода Свенна к задаче оптимального раскроя бревна на брус.

Выполняется условие W(l_o-)W(x)W(l_o+), следовательно,  имеет отрицательное значение; l * =12.

Искомый интервал 5<l * <9.

Этап уменьшения интервала

Метод деления пополам

Найти W(x) на отрезке [a,b].

Шаг 1. x_m=(a+b)/2; L=b-a; вычислить W(x_m).

Если W(x₁)W(x_m), то перейти к шагу 4.

Шаг 5. L=b-a. Если L<, то закончить поиск. В противном случае вернуться к шагу 2.

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

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

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

Тест МО. Тест по дисциплине методы оптимизации

A. Постепенное сужение области допустимых значений целевой функции.

B. Последовательное уменьшение интервала поиска. +

C. Последовательное превращение интервалов неопределенности в зону поиска оптимума целевой функции.

D. Последовательное увеличение интервала поиска.

5. Какие из ниже перечисленных методов относятся к методам одномерной оптимизации?

A. Методы Розенброка, Хука-Дживса, Нелдера-Мида, случайного поиска.

B. Методы быстрого спуска, сопряженных градиентов, переменной метрики.

C. Методы быстрого спуска, Розенброка, Хука-Дживса, метод золотого сечения.

D. Метод дихотомического деления, метод золотого сечения, метод чисел Фибоначчи, метод полиномиальной аппроксимации. +

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

A. базовой задачи структурного синтеза.

B. задачи прийняттякаркаснийишень. [Каркасный]

C. базовой задачи оптимизации. +

D. задачи принятия пт минимального решения.

7. Что называют параметрическим синтезом?

A. Задачу оптимизации на базе многовариантного анализа.

B. проектировочные процедуру, суть которой заключается в разработке [или выборе] структуры объекта.

C. Задачу оптимизации на базе двовариантного анализа.

D. проектировочные процедуру, суть которой заключается в расчете [или выборе] значений параметров элементов объекта. +

8. Что такое градиент функции многих переменных?

A. Матрица перестановок.

B. Матрица Якоби

C. Матрица множества альтернатив.

D. Матрица Гессе. +

9. В зависимости от количества управляемых параметров методы оптимизации делятся на методы …

A. одномерной и многомерной оптимизации. +

B. двумерной и многомерной оптимизации.

C. одномерной и n + к-мерной оптимизации.

D. одномерной, двумерной и трехмерной.

10. Какое из перечисленных определений касается понятия «параметрический синтез»?

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

B. Проектировочная процедура, суть которой заключается в разработке или выборе структуры объекта.

Нули функции. Интервалы знакопостоянства функции.
Метод интервалов

Значительная доля материала, касающегося производных и исследования функций, традиционно относится к школьной программе, и данная статья не является исключением из правила. Сегодня мы потренируемся в нахождении нулей и интервалов знакопостоянства функции, а также подробно разберём метод интервалов, который можно сравнить с надёжной арматурой в стенах рассматриваемой темы. Если же проект вашего здания находится на стадии котлована, пожалуйста, начните с вводного урока о графиках функций. Кроме того, желательно ознакомиться со статьями Область определения функции, Асимптоты графика, и, по существу, информация этой странички – логическое продолжение. Материал, естественно, будет полезен и старшеклассникам.

Что такое нули функции и что такое интервалы знакопостоянства функции?

Рассмотрим некоторую функцию .

1) Точки, в которых график пересекает ось , называют нулями функции. Чтобы найти нули функции нужно решить уравнение , то есть найти те значения «икс», при которых функция обращается в ноль. В следующем условном примере нули функции обозначены красными точками:

Очевидно, что . Заметьте, что точка не является нулём функции, поскольку не входит в её область определения.

2) Интервал знакопостоянства – это интервал, в каждой точке которого функция положительна либо отрицательна.

В нашем случае функция положительна на интервалах , то есть для любого значения «икс» любого из перечисленных интервалов справедливо строгое неравенство . Или совсем просто – график функции на таких интервалах расположен ВЫШЕ оси абсцисс.

На интервалах функция отрицательна, то есть любому значению «икс», принадлежащему этим интервалам соответствует строгое неравенство , и график функции расположен НИЖЕ оси .

Компактная запись перечисленных фактов выглядит так:
, если ;
, если .
Строки можно переставить местами, это не имеет принципиального значения, лично я привык сначала указывать интервалы, на которых функция положительна.

Что можно сказать об интервале ? Только то, что функция не определена на данном интервале, и, разумеется, о знакопостоянстве речи не идёт вообще.

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

Как найти интервалы знакопостоянства функции?

Алгоритм метода интервалов прост и бесхитростен:

2) Находим нули функции (точки пересечения графика с осью абсцисс).

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

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

Начнём с распространённой квадратичной функции:

Найти интервалы знакопостоянства функции.

Решение:

1) Функция определена и непрерывна на всей числовой прямой. Таким образом, точки разрыва и «нехорошие» промежутки отсутствуют.

2) Найдём нули функции. Для этого нужно решить уравнение . В данном случае:

Дискриминант положителен, значит, уравнение имеет два действительных корня:

3) Откладываем все найденные точки на числовой оси:

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

Хорошо, параболу многие читатели представляют. Но что делать, если функция более сложная? Например, . Заметная часть аудитории уже затруднится сказать, как принципиально выглядит график данной функции. И это, так скажем, ещё только минимальное усложнение.

Однако и в простых и в сложных случаях работает универсальный способ:

Рассмотрим функцию непрерывную на некотором интервале , график которой не пересекает ось на этом интервале. Тогда:

– если функция положительна в какой-либо точке интервала , то она положительна и ВО ВСЕХ точках данного интервала;

– если функция отрицательна в какой-либо точке интервала , то она отрицательна и ВО ВСЕХ точках данного интервала.

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

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

1) Берём произвольную точку интервала . С вычислительной точки зрения проще всего взять . Подставляем её в нашу функцию:

Следовательно, функция положительна и в каждой точке интервала .

2) Берём произвольную точку интервала , здесь по удобству вне конкуренции ноль. Снова выполняем подстановку:

А, значит, функция отрицательна и в каждой точке интервала .

3) И, наконец, обрабатываем наиболее простую точку интервала :

Поэтому функция положительна в каждой точке интервала .

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

Фиксируем полученные результаты на числовой оси:

Да, вы не имеете никаких представлений о параболе, но совершенно точно можете сказать, что на интервалах график функции расположен ВЫШЕ оси , а на интервале – НИЖЕ данной оси.

Ответ:
, если ;
, если .

Точно так же решается целый спектр задач-«сателлитов», вот некоторые из них:

Решить квадратичное неравенство .

Проводим аналогичные действия и даём ответ .

Решить квадратичное неравенство .

Проводим аналогичные действия и даём ответ .

Проводим аналогичные действия, даём ответ .

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

Может ли функция быть положительно или отрицательной на всей числовой прямой? Конечно, в статье Область определения функции мы рассмотрели типовые примеры. В частности выяснили, что (парабола, полностью лежащая в верхней полуплоскости). Метод интервалов проходит и тут! Рассматриваем единственный интервал , берём из него самую удобную точку и выполняем подстановку: . А значит, функция положительна и в каждой точке интервала .

Перейдём к кубическим многочленам:

Найти интервалы знакопостоянства функции.

Решение: снова придерживаемся алгоритма:

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

2) Найдём нули функции, то есть решим уравнение . Для этого выполним разложение на множители:

Таким образом, нули функции: .

3) Откладываем найденные значения на числовой прямой:

Теперь в каждом из четырёх полученных интервалов берём наиболее простую точку и находим значения функции в данных точках:

Таким образом:

Ответ:
, если ;
, если .

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

Кубическая функция настолько распространена, что не удержусь от полного чертежа «молнии»:

Казалось бы, решение можно упростить: взять левый интервал , выяснить, что на нём функция отрицательна, а дальше знаки будут чередоваться – «плюс», «минус», «плюс». Знакочередование бывает часто, но…

ЗНАКИ ЧЕРЕДУЮТСЯ ДАЛЕКО НЕ ВСЕГДА

Поэтому не ленимся – ТЕРПЕЛИВО рассматриваем КАЖДЫЙ интервал: из КАЖДОГО интервала берём наиболее выгодную точку и выясняем знак функции в данной точке.

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

Но формально можно использовать метод интервалов, который приведёт нас к такому же результату:

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

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

Следует отметить, что ситуация касания графика оси не единственна, в ряде случаев функция не меняет знак при переходе через точку разрыва. Хороший пример встретился в статье Непрерывность функции: .

Найти интервалы знакопостоянства функции.

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

Функции с многочленами встречаются очень часто, поэтому имеет смысл рассмотреть ещё пару экземпляров:

Найти интервалы знакопостоянства функции.

Решение:

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

2) Находим нули функции:

Таким образом, нули функции: .

3) Откладываем данные значения на оси абсцисс:

Определим знаки функции на полученных интервалах:

Таким образом:

Ответ:
, если ;
, если .

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

Функция-многочлен 4-й степени тоже достойна полного графика:

Собрат для самостоятельного решения:

Найти интервалы знакопостоянства функции.

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

Перейдём к обширной группе функций, у которых есть точки разрыва:

Найти интервалы знакопостоянства функции.

Решение: вот здесь начинает в полную силу работать пункт № 1 алгоритма:

1) Функция определена на всей числовой прямой, кроме точки , которая обращает знаменатель в ноль.

2) Находим точки пресечения графика с осью (нули функции):

Знаменатель нулевым быть не может, поэтому приравниваем к нулю числитель и решаем уравнение счастливого первоклассника:

3) Откладываем на оси абсцисс ВСЕ найденные точки, при этом выкалываем точку , так как она не входит в область определения функции:

Определим знаки функции на полученных интервалах:

В результате:

Ответ:
, если ;
, если .

Чем отличается данный пример от всех предыдущих? Да ничем особенным.

Напоминаю, что практически так же решается ряд смежных задач, например:

Решить неравенство
Ответ:

Решить неравенство
Ответ:

Найти область определения функции
Ответ:

Короткое разминочное задание для самостоятельного решения:

Найти интервалы знакопостоянства функции.

Кстати, подобные вещи вполне реально решить мысленно! Попытайтесь найти интервалы знакопостоянства «в уме», тем более, вы ничем не рискуете – в конце урока есть готовый образец.

Рассмотрим более навороченные дробно-рациональные функции:

Найти интервалы знакопостоянства функции.

Решение: далее пункты алгоритма нумеровать не будем.

Находим область определения функции. Проверим, обращается ли знаменатель в ноль:

Перепишем квадратное уравнение в привычном виде:

И для удобства сменим знаки у каждого слагаемого:

. Внимание: в САМОЙ ФУНКЦИИ так делать НЕЛЬЗЯ! В ней знак «минус» не пропадает: .

Дискриминант больше нуля, значит, уравнение имеет два действительных корня и в область определения не войдут две точки:

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

Таким образом, функция обращается в ноль в единственной точке:

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

Ответ:
, если ;
, если .

Как выглядит график функции, знают немногие, но совершенно точно можно сказать, что на интервалах он расположен ВЫШЕ оси , а на интервалах – НИЖЕ данной оси. В точке график, кстати, только касается её.

Найти интервалы знакопостоянства функции.

Это пример для самостоятельного решения.

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

Найти интервалы знакопостоянства функции.

Просто и со вкусом.

Решение: функция определена и непрерывна на интервале . Найдём точки пересечения графика с осью абсцисс:

Нулю может быть равен только числитель:

Согласно определению логарифма (которое нужно бы уже хорошо усвоить):

Отметим найденные точки на числовой прямой:

На промежутке функция не определена вообще. Об этом можно сделать пометку на чертеже либо просто оставить полуинтервал без внимания. Я обычно не ставлю никаких знаков.

Определим знаки на интервалах, которые входят в область определения функции:

Таким образом:

Ответ:
, если ;
, если .

На практике под логарифмом часто находится квадратный дву- или трёхчлен. Пожалуйста, ВНИМАТЕЛЬНО изучите оставшиеся примеры, в которых метод интервалов используется ДВАЖДЫ: первый раз для нахождения области определения, а второй раз для нахождения интервалов знакопостоянства.

Найти интервалы знакопостоянства функции.

Решение: сначала найдём область определения функции. Выражение под знаком логарифма должно быть положительным:

Квадратичное неравенство решим методом интервалов. Проверим, существуют ли действительные корни соответствующего уравнения:

Да, уравнение имеет два действительных перца. Не нужно удивляться, что дискриминант получился «плохой», это довольно распространённый инцидент в ходе исследовании функций. Невозмутимо находим корни:

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

Таким образом, область определения:

Что теперь? Теперь ЗАБЫВАЕМ про найденные знаки и интервалы знакопостоянства. Самый важный факт состоит в том, что отрезок не входит в область определения функции .

На втором шаге находим точки пересечения графика с осью абсцисс (нули функции):

Решаем ещё одно квадратное уравнение:

Снова используем метод интервалов. Откладываем на числовой прямой ВСЕ найдённые ранее точки:

Тесновато получилось, но что делать, зато масштаб выдержан.

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

Таким образом:

Ответ:
, если ;
, если .

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

Найти интервалы знакопостоянства функции.

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

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

Решения и ответы:

Пример 3: Решение:
1) Функция определена на всей числовой прямой.
2) Найдём нули функции:

Таким образом: .
3) Определим знаки функции методом интервалов:

Ответ:
, если ;
, если .

Пример 5: Решение:
1) Функция определена на всей числовой прямой
2) Найдём нули функции:

Проведём замену:

3) Выполним чертёж и определим знаки функции на найденных интервалах:

Ответ:
, если ;
, если .

Пример 7: Решение:
1) Функция определена на всей числовой прямой, кроме точки .
2) Найдём нули функции:

3) Определим знаки функции на полученных интервалах:

Ответ:
, если ;
, если .

Пример 9: Решение: точки не входят в область определения функции.
График функции не пересекает ось , т.к.
Методом интервалов определим знаки функции:

Ответ:
, если ;
, если .

Пример 12: Решение: найдём область определения:

Таким образом,
Найдём точки пересечения графика с осью абсцисс:

Определим знаки функции на полученных интервалах:

Ответ:
, если ;
, если .