Вопрос-ответ

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

последовательном

В задаче квадратичного программирования функция является

комбинацией линейной и квадратичной формы

В задаче линейного программирования введением дополнительных переменных можно

свести ограничения типа неравенств к равенствам

В методе дихотомии после N опытов, где N - четное и конечное число, интервал неопределенности запишется как

LNопт = 2- N/2 +N/2 ) e

В методе золотого сечения отрезок делится на две части так, что

отношение всего отрезка к большей его части равно отношению большей части к меньшей

В методе золотого сечения после N опытов длина интервала

LN = 1/tN-1

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

переходного процесса, заканчивающегося в кратчайшее время

В нелинейном программировании определить глобальный экстремум можно лишь методом

динамического программирования

В общем случае Лагранжа уравнение Эйлера является

нелинейным дифференциальным уравнением второго порядка

В общем случае линейная форма зависит от

всех переменных

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

dF/dxi = 0, i = 1, 2, ..., n )

В развернутой записи уравнение Эйлера имеет вид

Fy – Fxy, - Fyy, y, - Fy, y, y ² = 0

В симплекс методе все переменные делятся на базисные и небазисные, причем

все базисные переменные выражаются через небазисные

В симплекс-методе признаком движения вдаль грани является

положительность знака коэффициента линейной функции цели

В случае задачи с незакрепленными или подвижными концами

вариация функционала зависит от вариации искомой функции и ее концов

В случае пассивного поиска эффективность после добавления третьего эксперимента

не возрастает

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

A) М(х) (x) = 0

Вариационное исчисление – это

раздел математики

Вариационной исчисление можно рассматривать

как задачу нахождения экстремума функции бесконечного числа переменных

Величина интервала неопределенности Ln при параллельном поиске зависит

от распределения точек измерения xk и от номера точки, в которой достигается максимальное значение

Величина оптимального интервала неопределенности при пассивном поиске после N экспериментов задается формулой

LNопт = (1+e) / [N/2 +1]

Все методы решения задач целочисленного программирования можно разделить на группы

четыре

Второй вариацией функционала называют

A) 2 I = a2/2 (d2 I/da2)

Выпуклая функция f(x) на отрезке [x1, x2]

не может принимать значений больших, чем линейная функция интерполирующая значения f(x1), f(x2)

Выпуклое программирование, называют также

квадратичным

Глобальная оптимизация программирования - это

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

Глобальный экстремум - это экстремум, который достигается

сравнением всех кривых данного класса

Глобальный экстремум функции f(x) на отрезке [а, b] может достигаться

как во внутренних точках отрезка, так и на его границах

Двойственный симплекс-метод целесообразно применять

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

Динамическое программирование – это

метод оптимизации, основанный на принципе оптимальности Беллмана

Для решения задач оптимизации необходимо прежде всего уметь

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

Допустим, имеется m совместных уравнений: ji (x1, x2, ..., xn) = 0, i = 1,2, ..., m; требуется найти xj (j = 1,2, ..., n), удовлетворяющие им. Очевидно, что

значения хj будут нулями функций ji

Если L и L/ линейные формы соответственно прямой и двойственной задачи линейного программирования то:

min L/ = max L

Если допустимые дискретные значения, входящие в множество, состоят всего из двух значений: 0 и 1, то в этом случае имеет место программирование

целочисленное с булевыми переменными

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

последовательном поиске

Если подинтегральная функция F (x, y, y,) не зависит от x, то уравнение Эйлера сводится к уравнению

yFy, – F =const

Если подинтегральная функция F (x, y, y,) не зависит от y, то уравнение Эйлера сводится к уравнению

Fy = const

Если подинтегральная функция F (x, y, y,) не зависит от y,, то уравнение Эйлера сводится к уравнению

Fy = 0

Задача о кратчайшем питии является примером

дискретной оптимизационной задачи

Задача о рациональном питании относится к задаче

линейного программирования

Задача оптимизации программирования - это задача

создания программы, которая оптимально использует ресурсы ЭВМ

Задача распределения ресурсов является задачей

динамического программирования

Задачи отыскания экстремума и нуля функции

сводятся друг к другу

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

неравенства имеют вид строгих равенств

Задачу линейного программирования можно сформулировать так:

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

Из двух методов Фибоначчи и золотого сечения не требует априорного знания числа опытов

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

Из перечисленного: 1) ввод слабых переменных, 2) оптимальный (направленный) перебор, 3) переход по вершинам допустимых значений – к симплекс-методу в линейном программировании можно отнести

2 и 3

Из перечисленного: 1) градиентный; 2) дихотомии; 3) овражный, - к методам многомерного поиска можно отнести

1 и 3

Из перечисленного: 1) динамическое программирование; 2) вариационное исчисление; 3) линейное программирование, к классическим методам оптимизации можно отнести

только 2

Из перечисленного: 1) квадратичное программирование, 2) решение задач с сепарабельными функциями, 3) прямые методы, – требованиям теоретически разработанного метода удовлетворяет (ют)

только 1

Из перечисленного: 1) классические, 2) алгоритмы, использующие симплекс-метод, 3) градиентные, 4) специальные – к методам квадратичного программирования можно отнести

2, 3, 4

Из перечисленного: 1) логическое программирование; 2) функциональное программирование; 3) динамическое программирование, к методам оптимизации можно отнести виды программирования

только 3

Из перечисленного: 1) нелинейное дифференциальное уравнение; 2) линейное дифференциальное уравнение; 3) присутствие в уравнении операции минимизации - к дифференциальному уравнению Беллмана можно отнести

1, 3

Из перечисленного: 1) оптимальная траектория в фазовом пространстве; 2) независимость от вида траектории прохода системы в конечную точку; 3) неголономные связи - к динамическому программированию можно отнести

1, 2

Из перечисленного: 1) пассивный, 2)производный, 3) параллельный, 4) активный – к прямым методам отыскания экстремума можно отнести

1, 3, 4

Из перечисленного: 1) покоординатный спуск (подъем), 2) рандомизации, 3) наискорейшего спуска, – к методу градиента можно отнести

1 и 3

Из перечисленного: 1) поэтапное определение оптимального управления; 2) рекуррентные соотношения для решения оптимальных задач численным методом; 3) преобразованная функция Лагранжа - к функциональному уравнению Беллману можно отнести

1, 2

Из перечисленного: 1) прагматические; 2) математические; 3) функциональные - к критериям оптимизации можно отнести

1,2

Из перечисленного: 1) преобразованная функция Лагранжа; 2) динамическая система, изменяющая состояние во времени; 3) прямой метод вариационного исчисления - к принципу максимума Понтрягина можно отнести

1, 2

Из перечисленного: 1) прямой метод отыскания экстремума функции; 2) метод Стильтьеса; 3) принцип максимума; 4) динамическое программирование - к методам оптимизации можно отнести

1, 3, 4

Из перечисленного: 1) соотношения, являющиеся необходимыми и достаточными условиями оптимума, 2) алгоритмы поиска экстремума с доказательством их сходимости, 3) аналитические алгоритмы существования – к понятию теоретически разработанного метода можно отнести

1 и 2

Из перечисленного: 1)градиентные, 2)отсечения, 3) комбинаторные, 4) приближенные – к целочисленному программированию можно отнести методы

2, 3, 4

Из перечисленного: 1)метод ветвей и границ, 2) метод последовательного конструирования, 3) симплекс-метод, 4) метод анализа и отсева вариантов – к комбинаторным методам можно отнести

1, 2, 4

Из перечисленного1) движение поперек области, 2) движение по периметру контура двумерной области, 3) движение по ребрам многомерного многогранника, – к симплекс-методу в линейном программировании можно отнести

2 и 3

Из перечисленных методов оптимизации: 1) градиентный; 2) лингвистический; 3) вариационный, могут использоваться как аналитические и как численные

только 1

Из перечисленных методов оптимизации: 1) динамическое программирование; 2) лингвистические методы; 3) прямые методы, к эвристическим методам можно отнести

только 2

Из перечисленных методов: 1) Лебега; 2) Лагранжа; 3) принципа максимума; 4) динамического программирования, к методам оптимизации можно отнести

2, 3, 4

Из перечисленных последовательностей чисел: 1) F2 = 2, F3 = 3, F4 = 5, F5 = 8; 2) F2 = 2, F3 = 3, F4 = 4, F5 = 8; 3) F1 = 2, F3 = 3, F5 = 5, F7 = 7 – к числам Фибоначчи можно отнести

только 1

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

Фибоначчи

Интегральный критерий используется для определения параметров

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

Интервала неопределенности Ln после N экспериментов при параллельном поиске выражается следующим образом

L n = xk+1 – xk-1 1£ k £ N

Использование нечетного числа опытов целесообразно только при

большой погрешности измерений e

Исходная формулировка задачи при симплекс-методе должна содержать

только положительные переменные и ограничения типа равенств

Исходным функционалом для получения уравнения Эйлера является

A)

Итерационная формула в методе градиента записывается следующим образом

xk+1 = - xk - l grad [F(xk)] x = {x1, х2,…хn}

Итерационный процесс в методе Ньютона записывается в виде

Xk+1 = xk – F(xk)/ F/ (xk)

К числу релаксационных итерационных методов относится метод

овражный

Каноническая форма дифференциальных уравнений Эйлера основана на

вариационной механике Гамильтона – Лагранжа

Канонической формой уравнений Эйлера являются уравнения вида

- H / y = dp /dx, H / p = dy /dx

Классификация методов оптимизации

носит условный характер

Классический метод градиента может быть описан следующим дифференциальным уравнением

dx/dt = - l grad [F(x)] x = {x1, х2,…хn}

Классическое вариационное исчисление - исчисление, основанное на

методе вариаций и дифференциальном уравнение Эйлера

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

исключать подмножества вариантов, не содержащие оптимальной точки

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

переходного процесса, заканчивающегося в кратчайшее время

Критерий минимума критического времени выполнения работы используется при минимизации

критического пути по графу при ограниченных ресурсах

Критерий минимума стоимости в единицу времени определяет стоимость функционирования

систем массового обслуживания

Критерий оптимальности это:

количественная оценка оптимизирующего качества объекта

Критерий среднего квадрата ошибки - это

величина дисперсии разности опорного и выходного сигнала системы

Критерий среднего квадрата ошибки - это

работы автоматизированных систем регулирования

Локальная оптимизация программирования – это

адаптация программы к конкретной архитектуре ЭВМ

Локальный экстремум - это экстремум, который достигается

сравнением только близких кривых

Математическая формулировка задач целочисленного программирования

аналогична задачам нелинейного программирования

Метод неопределенных множителей Лангранжа в вариационном исчеслении используется

когда на функцию наложены дополнительные условия

Метод Ньютона более близок к методу

градиента

Метод Ньютона широко используется для

отыскания нулей функции

Метод поиска экстремума путем последовательного деления отрезка пополам называется

методом дихотомии

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

рандомизации

Метод поиска, при котором предполагается движение по нормали к линиям уровней, называется методом

градиента

Методы квадратичного программирования можно разделить на группы

три

Методы оптимизации широко используются при

проектировании сложных инженерных сооружений и систем

Методы отыскания экстремума функционала ведут свое начало от

классических методов Эйлера — Лагранжа — Гамильтона

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

замене нелинейных функций ломаными кривыми

Методы целочисленного программирования

представляют собой набор частных приемов, пригодных для решения частных задач

Минимаксный критерий используется для определения

оптимальной стратегии при наличии конфликтной ситуации

Минимаксный критерий оптимизации используется в теории игр, при этом задается матрица || aij ||, где: i= 1, 2, ..., m; j= 1, 2, ..., n, которая называется матрицей

платежей

Минимаксный критерий оптимизации используется в теории игр, при этом задается матрица || aij ||, где: i= 1, 2, ..., m; j= 1, 2, ..., n, каждый элемент этой матрицы означает

платеж противнику в случае, когда он применяет стратегию j, а наша сторона - стратегию i

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

выпуклого нелинейного

Наглядная геометрическая интерпретация процесса нахождения оптимального решения симплекс-методом получится, если

от исходной прямоугольной системы координат перейти к косоугольной

Наглядная геометрическая интерпретация процесса нахождения оптимального решения симплекс-методом удобна при

малом числе переменных

Наиболее распространенные методы оптимизации используют понятие

минимума (или максимума) функции или функционала

Наилучший выбор стратегии при пассивном поиске получается при

разделении экспериментальных точек на равноотстоящие пары

Наихудший интервал при параллельном поиске при заданном числе точек поиска , где хк стратегия и K – номер точки, в которой достигается максимальное значение, зависит хк

только от стратегии поиска

Не очень строго функционал можно определить как

функцию от функции

Необходимым условием существования локального экстремума функции одной переменной является

обращение в ноль ее первой производной

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

Беллмана, Понтрягина, Кротова

Общее решение уравнения Эйлера Fy - d F y’/dx = 0 содержит две неопределенные постоянные, для определения которых требуется удовлетворение некоторого условия. Как правило, в качестве такого условия задается

значение функции у(х) в начале и конце интервала у (а) и y(b)

Одна из основных задач автоматизированных информационных систем (АИС) управления - оперативно-календарное планирование, относится к задачам

целочисленного программирования

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

на заданном интервале имеется одно экстремальное значение

Одновременный параллельный замер параметров для поиска экстремума производится, когда

нет времени на последовательный анализ

Оптимальная система управления может быть реализована в виде

стратегии или способа управления объектом

Оптимальная стратегия при параллельном поиске экстремума хkопт существует

в единственном варианте

Оптимальный интервал после N опытов в методе Фибоначчи записывается как

LNопт = 1/FN - (FN-2 / FN ) e

Оптимизация – это

процесс нахождения наилучшего решения задачи

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

найти глобальный экстремум при наличии нескольких локальных экстремумов

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

отсутствие ограничений на изменениях переменных

Пассивная стратегия поиска экстремума ничем не отличается от активной для случая

двух экспериментов

Первой вариацией функционала называется выражение

A) I = a dI/da

Переход от исходной прямоугольной системы координат к косоугольной в симплекс-методе производится введением

свободных переменных

Переходный процесс в теории регулирования - это

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

Поиск бывает активный или последовательный, когда

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

Поиск бывает пассивный или параллельный, когда

стратегия известна до получения результатов эксперимента

Поиск экстремума может быть детерминированным при

отсутствии шумов

Поиск экстремума может быть стохастическим при

наличии ошибки замеров значений функции

Последовательный поиск является

активным

Постановка задачи оптимизации предполагает существование следующих условий

наличие объекта оптимизации и цели оптимизации

Прагматические критерии оптимизации - это

выработанные практикой количественные характеристики оптимальности некоторой системы

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

приближенные

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

равно числу ребер, исходящих из данной вершины

При определении условного экстремума функции, когда требуется определить максимум (или минимум) функции F(х) при ограничивающих условиях, используется метод

неопределенных множителей Лагранжа

Примером функционала может служить

определенный интеграл

Принцип Гамильтона в механике формулируется как

фазовая траектория системы является экстремалью функционала

Принцип оптимальности Беллмана можно сформулировать так

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

Принцип оптимальности Беллмана является основой

динамического программирования

Принцип оптимальности динамического программирования утверждает, что

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

Принцип оптимальности справедлив для

дискретных, и стохастических процессов управления

Процедура пассивного поиска носит название поиска однородными парами, если экспериментальные точки делятся на

равноотстоящие пары

Пусть на некоторой гладкой кривой, проходящей через точки a и b, достигается экстремум функционала. Надо определить необходимые условия, которым должна удовлетворять функция y(x), чтобы на ней достигался минимум. Для этого сравниваем значения функционала для близких к y(x) функций, придавая y(x) вариацию

A)

Решение задач линейного программирования дает

один экстремум

Решение задач нелинейного программирования может давать

два или более экстремума

Решение прямой и двойственной задачи линейного программирования называют соответственно

планом и псевдо планом

Симплекс – метод в задаче линейного программирования реализуется в виде

симплекс таблиц

Симплекс-метод в линейном программировании - это специальный метод

оптимального (направленного) перебора

Симплекс-метод обеспечивает сходимость к экстремальной точке за

конечное число шагов

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

регулярностью

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

только дискретные

Стоимость функционирования системы массового обслуживания в единицу времени можно записать как

C = c1 pср + c2 wср, где pср - среднее число простаивающих точек, wср – среднее число заявок, ожидающих своей очереди, c1 – стоимость простоя, c2 – стоимость ожидания в очереди

Стратегия носит наименование e-минимаксной, когда

вводится величина e, определяемая погрешностью измерительной аппаратуры

Стратегия поиска в методе рандомизации совпадает с(со)

процедурами проверки статистических гипотез

Стратегия хkопт при параллельном поиске может быть названа минимаксной, если

LNопт =

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

не может выполнить своего основного назначения

Теорема Куна - Таккера в выпуклом программировании обобщает

теорему Лагранжа для классических задач

Теоретически в нелинейное программировании наиболее детально разработан раздел

выпуклого или квадратичного программирования

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

стационарными

Требованием минимума функционала I = min, при использовании интегрального критерия, можно обеспечить в системе

переходный процесс с малыми отклонениями

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

динамическое программирование

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

большему значению у соответствует более близкое к максимуму значение х

Уравнение Эйлера – это

Fy - d F y’/dx = 0

Уравнение Эйлера для функционала имеет вид

y² = 0

Уравнение Эйлера для функционала имеет вид

(y¢ )2 – 2 yy² = 0

Уравнение Эйлера для функционала имеет вид

y¢ + xy² = 0

Условие Лежандра позволяет

отличать минимум от максимума

Условиями трансверсальности возникают в задаче

когда концы искомой функции могут перемещаться по заданным кривым

Условный экстремум - это экстремум функции при условии, когда

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

Фундаментом теории целочисленного программирования является(ются)

первый алгоритм Гомори

Функциональное уравнение Беллмана представляет собой

формальную запись принципа оптимальности

Функция f(x) имеет на отрезке [а, b] может минимум в точке , если

для всех х Î [ а, b] f ( ) £ f (x)

Функция f(x) ограниченная на отрезке [а, b] может иметь на этом отрезке

один глобальный максимум и несколько локальных максимумов

Функция f(x1, х2,... xn), с которыми имеют дело в квадратичном программировании имеют вид

Функция f(х) = f(x1, ..., xn) называется сепарабельной, если она представлена в виде

f (x1,х2 ..., xn) = å cjfj (xj)

Функция f(х) n переменных ||x1, ..., xn|| = x Ì G называется выпуклой функцией в выпуклой области G, если для любых двух точек из G выполняется соотношение

f{lx1 + (1 - l)x2}£ lf(x1) + (1 - l) f(x2)

Частным случаем функционала является

функция

Числа Фибоначчи вычисляются на основании следующих рекуррентных соотношений

F0 = F1 = 1; Fk = Fk-1+Fk-2 k = 2,3…

Чтобы решить минимаксную задачу min max aij = ?, требуется найти

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

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

изменение начальных условий

Экстремальная задача называется обобщенной задачей Лагранжа, когда

ограничивающее условие содержит производные

Экстремум в задачах линейного программирования

единственный, т. е. локальный и глобальный одновременно

Эффективность поиска при методе дихотомии с ростом числа опытов N

растет экспоненциально

Эффективность поиска при методе однородными парами с ростом числа опытов N

растет прямо пропорционально