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

Уравнение нахождения точки экстремума
характерно для:

• метода Фибоначчи
• метода дихотомии
• (Правильный ответ) метода Ньютона

Функция f(x) достигает глобального (абсолютного) максимума в
точке x0, если для всех точек x є R справедливо:

• f(x0) = f(x)
• (Правильный ответ) f(x0) ? f(x)
• f(x0) ? f(x)

Выберите из представленного ряда записей задач
линейного программирования запись задачи в стандартной форме:

• (Правильный ответ)
  

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

• ни одного ограничения не удовлетворяются
• (Правильный ответ) одни ограничений удовлетворяются, а другие — нет
• все ограничения удовлетворяются

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

• неотрицательны
• положительны
• (Правильный ответ) неположительны

Если для всех точек x, лежащих в малой окрестности точки
имеет место неравенство
, то:

• функция достигает локального минимума в точке
  
• (Правильный ответ) функция достигает локального максимума в точке
  
• функция не имеет экстремумов в точке
  

Метод градиентного спуска предполагает движение:

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

Если в двойственной задаче имеется такое допустимое решение y0, что
cTx0=bTy0, то допустимый вектор x0:

• (Правильный ответ) является оптимальным
• не является оптимальным
• является двойственным

Задача линейного программирования имеет вид: максимизировать
?сixi, i=1,…,n при условиях
A1x1+A2x2+…+Anxn?b;
Данная форма записи является:

• канонической формой
• матричной формой
• (Правильный ответ) векторной формой

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

• (Правильный ответ) cTx0=bTy0
• cTx0>bTy0
• cTx0=-bTy0

Пусть f(x) и все gi(x) выпуклы и все функции
gi(x) удовлетворяют условию регулярности Слейтера. Вектор x*
решением задачи нелинейного программирования: минимизировать f(x) при условиях
gi(x) ? 0, i = 1,…,m тогда и только тогда, когда существует такой вектор
?* ? 0, для которого выполняются условия:

• (Правильный ответ) L(x*,?) ? L(x*,?*) ? L(x,?*) и
  
• L(x*,?) > L(x*,?*) > L(x,?*) и
  
• L(x*,?) ? L(x*,?*) ? L(x,?*) и
  

В каком из методов происходит сравнение значений функции в (n + 1)
вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры?

• метод покоординатного спуска
• метод Хука – Дживса
• (Правильный ответ) метод Нелдера – Мида
• метод градиентного спуска

Пара векторов x*, ?* для которых
выполняется условие: для всех
? ? 0, x є Rn L(x*, ?) ? L(x*,
?*) ? L(x, ?*), называется:

• условием регулярности Слейтера
• (Правильный ответ) седловой точкой функции Лагранжа
• условием дополняющей нежесткости

Если вторая производная функции у = f(х) в данном промежутке положительна,
то кривая…?

• параллельна
• выпукла
• (Правильный ответ) вогнута

Каноническая форма задачи линейного программирования имеет вид:

• (Правильный ответ)
  

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

• (Правильный ответ)

Если при проверке сходимости а < ?, то это означает?

• все значения функции очень далеки друг от друга
• все значения функции одинаковы
• (Правильный ответ) все значения функции очень близки друг к другу
• все значения функции различны

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

• на границе допустимой области
• за допустимой областью
• (Правильный ответ) внутри допустимой области

Пусть уравнение определяет базисное решение . Предположим,
что это решение допустимо, т.е. . Если Аr
не входит в базис, то:

• (Правильный ответ) A1x1r+A2x2r+…+Amxmr = Ar
• A1x1r+A2x2r+…+Amxmr ? Ar
• A1x1r+A2x2r+…+Amxmr ? Ar

Метод Дэвидона-Флетчера-Пауэлла также называют

• (Правильный ответ) методом переменной метрики
• метод покоординатного спуска
• метод Ньютона

Пусть функция f(x) является строго квазивыпуклой и выполняется неравенство
f(?x1 + (1–?)x1) < max{f(x1),f(x2)}.
При этом для всех действительных x1, x2 выполняется условие:

• f(x1) > f(x2)
• f(x1) = f(x2)
• (Правильный ответ) f(x1) ? f(x2)

Комплексный метод является?

• процедурным
• равномерным
• (Правильный ответ) итерационным
• последовательным

Если вторая производная функции у = f(х) в данном промежутке отрицательна, то кривая…?

• (Правильный ответ) выпукла
• параллельна
• вогнута

Функция f(x) достигает локального максимума в точке
и при этом имеет место равенство
. Это справедливо:

• для всех действительных x
• (Правильный ответ) для всех x, принадлежащих малой окрестности
  
• для всех положительных x

Пусть f(x1,…,xn) дифференцируема в некоторой
допустимой области R. Если в некоторой внутренней точке
области R функция достигает относительного
максимума, то:

• ?f(x0)/?xj ? 0, j=1,…,n
• (Правильный ответ) ?f(x0)/?xj = 0, j=1,…,n
• ?f(x0)/?xj ? 0, j=1,…,n

Пусть новое решение уравнения
A1x1+A2x2+…+Amxm+Arxr = А0
имеет вид ,
и при этом выполняется соотношение , т.е. данное решение
является допустимым. Чтобы данное решение являлось базисным, необходимо:

• вывести переменную xi из базисного решения, и ввести дополнительный вектор в базис
• (Правильный ответ) вывести переменную xi из базисного решения, а соответствующий вектор – из базиса
• ввести дополнительную переменную xi в базисное решение, а соответствующий вектор – в базис

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

• оптимальное решение имеет двойственная задача
• оптимальное решение имеет прямая задача
• (Правильный ответ) оптимальные решения имеют и прямая, и двойственная задачи

Пусть известен некоторый сопряженный базис ,
которому соответствует псевдоплан x. Базисные компоненты псевдоплана удовлетворяют условиям
xi = xi0?0 для всех i є I?. При этом псевдоплан
x является оптимальным решением. Тогда справедливы соотношения:

• Aj??Aixij; A0??Aixi, i є I?;
• (Правильный ответ) Aj=?Aixij; A0=?Aixi, i є I?.
• Aj??Aixij; A0??Aixi, i є I?;

Пусть имеется начальный интервал (a; b), который имеет длину
L = b – a. Согласно метода Фибоначчи:

• Ln = L1/Fn — ?(Fn–2/Fn)
• (Правильный ответ) Ln = L1/Fn + ?(Fn–2/Fn)
• Ln = ?(Fn–2/Fn) — L1/Fn

Чему будет равно общее число сетки, если область G является двумерным кубом,
каждую сторону которого при построении сетки мы делим на 10 частей?

• 100
• 1024
• (Правильный ответ) 121
• 2048

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

• не определена
• (Правильный ответ) строго вогнутая
• строго выпуклая

Чему будет равняться коэффициент растяжения ?, если известно,
что x0 = 5, xe = 3, xr = 6?

• 6
• 2
• (Правильный ответ) -2
• 8

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

• (Правильный ответ) от многоэкстремальности
• нахождения максимальной функции
• от оврагов

Если некоторая точка x0 функции является стационарной, а сама
функция в окрестности точки x0 является строго выпуклой,
то в точке x0:

• достигается внутренний относительный максимум
• (Правильный ответ) достигается внутренний относительный минимум
• достигается внутренний абсолютный максимум

Множество R(x) всех векторов x, которые удовлетворяют условиям:

a11x1 + a12x2+…+a1nxn ? b1 a21x1 + a22x2+…+a2nxn ? b2 ……………………. am1x1 + am2x2+…+amnxn ? bn, x1?0,×1?0,…,xn?0,

является:

• (Правильный ответ) допустимым множеством решений задачи (1)
• оптимальным множеством решений задачи (1)
• эквивалентным множеством решений задачи (1)

Псевдоплан x={xi0} является оптимальным решением
прямой задачи, если среди его базисных компонентов:

• нет положительных
• имеются отрицательные
• (Правильный ответ) нет отрицательных

Рассмотрим задачу нелинейного программирования:
минимизировать f(x) при
.
Известно, что существует множество неотрицательных скаляров {?i} ? 0,
для которых справедливо соотношение
?f(x*)=??i?i(x) = -??i?gi(x*), i є I.
Тогда для входящего вектора справедливо условие:

• ?f(x*)(x – x*) = 0 для всех x є S
• (Правильный ответ) ?f(x*)(x – x*) ? 0 для всех x є S
• ?f(x*)(x – x*) > 0 для всех x є S

Пусть задача линейного программирования имеет вид:
максимизировать ?сixi, i=1,…,n при условиях

a11x1 + a12x2+…+a1nxn ? b1 a21x1 + a22x2+…+a2nxn ? b2 (1) ……………………. am1x1 + am2x2+…+amnxn ? bn, x1?0,×1?0,…,xn?0.

Тогда множество R(x) является допустимым множеством решений данной задачи, если оно удовлетворяет условиям:

• (Правильный ответ)
  a11x1 + a12x2+…+a1nxn ? b1 a21x1 + a22x2+…+a2nxn ? b2 ……………………. am1x1 + am2x2+…+amnxn ? bn, x1?0,×1?0,…,xn?0,
• a11x1 + a12x2+…+a1nxn > b1 a21x1 + a22x2+…+a2nxn > b2 ……………………. am1x1 + am2x2+…+amnxn > bn, x1?0,×1?0,…,xn?0,
• a11x1 + a12x2+…+a1nxn < b1 a21x1 + a22x2+…+a2nxn < b2 ……………………. am1x1 + am2x2+…+amnxn < bn, x1?0,×1?0,…,xn?0,

Чему будет равняться функция в точке образа, если базисная точка
b1 = 1, а b2 = 7?

• 115
• (Правильный ответ) 13
• 8
• 12

Пусть задана задача нелинейного программирования:
минимизировать f(x1,…,xn) при условиях

h1(x1,…,xn) = 0;h2(x1,…,xn) = 0;……………hm(x1,…,xn) = 0.

Допустим, что существует такая точка x*, в которой достигается относительный экстремум данной задачи.
Если ранг матрицы
I = [?hj(x)/?xj], i = 1,…,m; j = 1,…,n
в точке x* равен m, то существуют m чисел
?1,…,?n, не все из которых равны нулю одновременно, и при которых:

• ?f(x*) + ??i?hi(x) < 0, i = 1,…,m.
• (Правильный ответ) ?f(x*) + ??i?hi(x) = 0, i = 1,…,m
• ?f(x*) + ??i?hi(x) ? 0, i = 1,…,m

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

представляет собой:

• (Правильный ответ) общую форму
• стандартную форму
• каноническую форму

Задана целевая функция Z=20×1+10×2 ?? max и ряд ограничений
10х1+2х2?200, 2х1+4х2?110, 2х1+3х2?140, х1,х2?0.
Найти решение задачи.

• х1=14, х2=19
• (Правильный ответ) х1=16, х2=19
• х1=18, х2=13

Пусть R – выпуклое множество точек n – мерного пространства.
Функция f, определенная на R, удовлетворяет условиям: для любых
x1, x2 є R и 0 ? k ? 1
f[kx1+(1–k)x2] ? kf(x1)+(1–k)f(x2).
Тогда функция f называется:

• выпуклой вниз
• выпуклой
• (Правильный ответ) вогнутой

Если для всех точек x є R некоторой функции f(x)
справедливо неравенство f(x0) ? f(x), то в точке x0
функция f(x):

• экстремумов не имеет
• (Правильный ответ) достигает глобального (абсолютного) максимума
• достигает глобального (абсолютного) минимума

Пусть функция F(x) вогнута (выпукла), что соответствует монотонности ее первой
производной. Если в некоторой точке градиент функции F(x) равен нулю, то функция F(x)
в этой точке:

• (Правильный ответ) имеет локальный минимум (максимум)
• имеет глобальный минимум (максимум)
• не определена

Чему будет равняться функция в точке образа, если базисная точка
b1 = 2, а b2 = 5?

• 3
• 6
• (Правильный ответ) 8
• 2

Согласно симплекс – метода, верное базисное решение
при ограничениях задачи линейного программирования
A1x1+A2x2+…+Anxn+An+1xn+1+…+An+mxn+m=A0
имеет вид:

• A1x1-A2x2-…-Anxn-An+1xn+1-…-An+mxn+m=A0;
• (Правильный ответ)
• A1x1-A2x2+…+Anxn-An+1xn+1+…+An+mxn+m=A0.

Пусть .
Тогда присоединенная функция

построена в виде:

• квадратичной параболы
• (Правильный ответ) барьера
• оврага

Кривая у = f(х) называется вогнутой в промежутке a<x<b, если она лежит

• перпендикулярно касательной в любой точке этого промежутка
• параллельно касательной в любой точке этого промежутка
• (Правильный ответ) ниже касательной в любой точке этого промежутка
• выше касательной в любой точке этого промежутка

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

• обратной
• прямой
• (Правильный ответ) двойственной

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

• меняет знак с положительного на отрицательный
• (Правильный ответ) меняет знак с отрицательного на положительный
• знак не меняет

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

• методы внутренней точки
• (Правильный ответ) методами барьеров
• методы внешней точки
• комбинированные методы

Задана целевая функция Z=25×1+20×2 ?? max и ряд ограничений
8х1+3х2?400, 3х1+2х2?80, 5х1+7х2?200, х1,х2?0.
Найти решение задачи.

• (Правильный ответ) х1=16, х2=16
• х1=18, х2=16
• х1=12, х2=14

Пусть функция F(x) вогнута (выпукла), что соответствует монотонности ее первой
производной. Известно, что если функция F(x) имеет локальный минимум (максимум) в точке
x’, то в этой точке градиент функции F(x):

• (Правильный ответ) равен нулю
• положителен
• отрицателен

Пусть уравнение определяет базисное решение , которое является
допустимым, т.е. . При этом справедливо равенство:
A1x1r+A2x2r+…+Amxmr = Ar.
Это значит, что:

• Ar выражается через этот базис
• Ar входит в базис
• (Правильный ответ) Ar не входит в базис

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

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

• (Правильный ответ) линейно – независимыми
• ортонормированными
• линейно – зависимыми

Пусть f(x1,…,xn) дифференцируема в некоторой
допустимой области R. Если в некоторой внутренней точке
области R функция достигает относительного
максимума, то:

• ?f(x0)/?xj ? 0, j=1,…,n
• (Правильный ответ) ?f(x0)/?xj = 0, j=1,…,n
• ?f(x0)/?xj ? 0, j=1,…,n

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

• метод покоординатного спуска
• (Правильный ответ) метод градиентного спуска
• метод Нелдера – Мида

Пусть функция f(x) определена на непустом и выпуклом множестве R.
Функция f(x) квазивыпукла, есл