2) Вычислить сумму приводящих констант h(k) - это оценка для исходного множества маршрутов g0.
4) Выбрать для ветвления ту пару (I,j) из претендентов на ветвление, для которой θij получится максимальным.
1) Произвести приведение матрицы расстояний s по строкам и столбцам, получим приведенную матрицу s′.
Если при использовании метода ветвей и границ, полученная после вычеркивания строк, столбцов и наложения запретов матрица расстояний имеет размерность 2*2, то это может означать, что определяемые ею пары городов … маршрут.
завершают
Графическим решением задачи о коммивояжере является маршрут … .
Дана матрица расстояний
Претендент на ветвление в приведенной матрице находится на пересечении … .
строки 1 столбца 4
В задачах о размещениях затраты на производство продукции будут равны … .
(xi –объем продукции в единицах, который необходимо производить в пункте «i», xij – количество единиц продукции, поставляемой из пункта «i» в пункт «j», cij – затраты на транспортировку единицы продукции из производящего пункта «i» в потребляющий пункт «j», m – количество производящих пунктов, n – количество потребляющих пунктов)
В задаче о размещениях суммарные затраты по производству и транспортировке должны быть … .
минимальными
При использовании метода Гомори полученное решение задачи линейного программирования проверяется на … .
целочисленность
Если хотя бы одна координата решения задачи линейного программирования не удовлетворяет условию целочисленности при использовании метода Гомори, то … .
строим дополнительное линейное ограничение
При
использовании метода Гомори каждое
"k-ое" дополнительное ограничение
имеет вид:
,
где Nk
- это множество векторов … .
([xi0], [xij] – целая часть соответствующей величины; xi0 – нецелая координата оптимального плана задачи целочисленного программирования с наименьшим индексом; xij – координаты разложения векторов Aj)
не попавших в базис
Используя метод ветвей и границ оптимальное решение можно найти … .
анализируя все возможные варианты
Задача о размещениях заключается в таком … .
размещении предприятий, определении их производственных мощностей и организации перевозок, чтобы суммарные затраты по производству и транспортировке были минимальны
К необходимым условиям задачи о коммивояжере относят … .
возможность выезда коммивояжера из города только один раз
замкнутость маршрута
Дополнительное линейное ограничение в методе Гомори строится, если … .
хотя бы одна координата не является целым числом
Приведенная матрица расстояний в методе ветвей и границ получается в результате вычитания из элементов … .
каждой строки минимального элемента этой строки, а затем вычитания из элементов каждого столбца минимального элемента этого столбца
К необходимым условиям задачи о назначениях относят следующие условия … .
на каждое предприятие может выделяться только один вид оборудования
каждая единица оборудования может распределяться только на одно предприятие
К необходимым условиям задачи о размещениях относят следующие условия:
полное потребление производимой продукции
потребитель должен получить продукцию в объеме, не менее заданного значения
Численные методы безусловной оптимизации определяются для функций ... .
одной переменной
двух переменных
трех переменных
все ответы верны
Численные методы безусловной минимизации требуют, чтобы минимизируемая функция обладала свойством ... .
квазивыпуклости
К численным методам безусловной оптимизации функции одной переменной относится метод ... .
равномерного поиска
золотого сечения
Ньютона
все ответы верны
В методах безусловной оптимизации функций ε – это … .
длина интервала неопределенности
При нахождении минимума функции f(x) на отрезке [a, b] покрытие сеткой узлов с одинаковым шагом h производится в методе … .
равномерного поиска
В методе золотого сечения используются следующие константы … .
0,382 и 0,618;
К численным методам безусловной оптимизации функции многих переменных относится метод ... .
циклического покоординатного спуска
Хука - Дживса
наискорейшего спуска
все ответы верны
К методу, не требующему условия квазивыпуклости, относится метод … .
половинного деления
простых итераций
Ньютона
все ответы верны
Для сходимости метода циклического покоординатного спуска минимум функции f(x) вдоль любого направления должен быть ... .
единственен
Метод циклического покоординатного спуска может остановиться в неоптимальной точке, если функция f(x) ... .
не является дифференцируемой в некоторых точках
Метод Хука-Дживса осуществляет два типа поиска – это исследующий поиск и поиск по … .
образцу
В методе наискорейшего спуска поиск максимального значения функции f(x) осуществляется в направлении ... .
grad f(x)
В методе наискорейшего спуска поиск минимального значения функции f(x) осуществляется в направлении ... .
-grad f(x)
Согласно
теореме для строго квазивыпуклых функций
f(x) на отрезке [а, b]
при условиях, что любые две точки с и d
(с < d)
принадлежат [а, b]
и
следует, что точка минимума функции
f(x) может находиться только на отрезке
... .
Согласно
теореме для строго квазивыпуклых функций
f(x) на отрезке [а, b]
при условиях, что любые две точки с и d
(с < d)
принадлежат [а, b]
и
следует, что точка минимума функции
f(x) может находиться только на отрезке
... .
Новый
интервал неопределенности
в методе золотого сечения при условии,
что h
– шаг разбиения, будет сокращен до
размера... .
0,5·h
Для строго квазивыпуклых функций f(x) на отрезке [а, b] любые две точки с и d (с < d) этого отрезка [а, b] находятся из условия … .
Необходимым
условием нахождения
- точек локального минимума для дважды
дифференцируемой функции является …
.
определение таких точек x, в которых все первые частные производные 1-го порядка обращаются в нуль
Достаточным условием нахождения - точек локального минимума для дважды дифференцируемой функции является … .
проверка
положительной определенности матрицы
Гессе
в таких точках
Линиями
уровня функции
называют множество точек (x,
y),
удовлетворяющих уравнению … .
(ε – точность определения решения задачи, с – постоянная величина):
Необходимым условием методов многомерного прямого поиска является выбор ... .
допустимого направления поиска
Функция f(x) квазивыпукла на отрезке [a, b], если для всех x, принадлежащих [x1, x2] при любых x1, x2 [a, b] выполняется условие … .
Функция f(x) строго квазивогнута на отрезке [a, b], если для всех x, принадлежащих [x1, x2] при любых x1, x2 [a, b] выполняется условие … .
Хз…
Если ε – точность определения решения задачи, то метод циклического покоординатного спуска завершается при достижении следующего условия … .
(xk – предпоследняя точка; x(k+1) – последняя точка)
Нахождение минимума функции f многих переменных в направлениях параллельных осям координат происходит в методе … .
циклического покоординатного спуска
Нахождение минимума функции f многих переменных в направлении (– grad f(x0)) происходит в методе … .
наискорейшего спуска
Направлением наибольшего возрастания функции f многих переменных в точке x0 является … .
+grad f(x0)
Направлением наибольшего убывания функции f многих переменных в точке x0 является … .
–grad f(x0)
Если ε – точность определения решения задачи, xi – искомая точка, то метод наискорейшего спуска завершается при достижении следующего условия … .
Классический подход к задаче нахождения точек локального минимума для дважды дифференцируемой функции f(xi,xj) (i=1,…,n; j=1,…,n) состоит в … .
проверке
положительной определенности матрицы
Гессе
(необходимое условие)
в определении таких точек x, в которых все первые частные производные 1-го порядка обращаются в нуль (достаточно условие)
В методе наискорейшего спуска сходимость обеспечена, если ... .
функция f непрерывно дифференцируема
функция
f
имеет седловую точку
генерируемая последовательность принадлежит замкнутому ограниченному множеству
все ответы верны
Недостатком метода наискорейшего спуска для «овражных» функций является ... .
медленная сходимость в окрестности стационарной точки
«Овражная» функция – это функция … .
для которой поверхности уровня сильно вытянуты
Геометрически медленная сходимость метода наискорейшего спуска объясняется ... .
зигзагообразным продвижением к точке минимума
Недостатком метода Ньютона среди методов безусловной оптимизации является … .
необходимость многократного обращения матрицы Гессе
Суть метода Ньютона для функции f(x) состоит в том, что ... .
функция f(x) аппроксимируется многочленами второй степени, для которых находятся точки минимума
Требование квазивыпуклости минимизируемой функции является условием для применения метода … .
золотого сечения
равномерного поиска
К методам, требующим квазивыпуклости минимизируемой функции, относятся методы … .
золотого сечения и равномерного поиска
Методом не требующего условия квазивыпуклости функции, но необходимости дополнительного исследования в окрестности найденных корней на предмет наличия минимума (максимума) является метод … .
простых итераций
Ньютона
половинного деления
все ответы верны
Распределите пункты в порядке выполнения алгоритма метода наискорейшего спуска:
4
Найти
и проверить условие точности
,
положив i=i+1.
3
Проверить условие точности, если
,
положить
и решить задачу о минимуме
,
найти
>0.
1 Выбирать точку xi, i=1.