Задачей линейного программирования называется задача, в которой целевая функция … .

и ограничения являются линейными

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

допустимым планом задачи

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

оптимальное

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

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

Допустимое множество - это множество всех точек плоскости, координаты которых … .

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

Выпуклым многоугольником может быть … .

неограниченный многоугольник

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

многоугольник, вырождающийся в точку

Линиями уровня функции f(х) называется множество точек х, удовлетворяющих уравнению f(x) = … .

a, a=const

Если с₁,с₂ являются коэффициентами при х₁ и x₂ в уравнении целевой функции f(x₁,x₂)=c₁x₁+c₂x₂, то вектор, соединяющий точку (0,0) и точку (с₁,с₂), называется … .

нормалью

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

точек максимума

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

минимума

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

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

Если допустимая область задачи линейного программирования не ограничена снизу, то целевая функция … .

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

Отметьте верные утверждения … .

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

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

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

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

ограничена

Если векторы А_j, соответствующие отличным от нуля координатам вектора х, линейно-независимы, то ненулевое допустимое решение х = (х₁, …, х_n)^Т называется … .

опорным

Ненулевое опорное решение называется невырожденным, если оно имеет … .

(А - матрица коэффициентов при неизвестных переменных левой части ограничений, m - ранг матрицы А)

«m» положительных координат

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

(А - матрица коэффициентов при неизвестных переменных левой части ограничений)

вырожденным

Ненулевое опорное решение называется …, если оно имеет точно «m» положительных координат.

(А - матрица коэффициентов при неизвестных переменных левой части ограничений, m - ранг матрицы А)

невырожденным

Упорядоченный набор из «m» линейно-независимых векторов А_i, соответствующих положительным координатам опорного решения называется … .

(А - матрица коэффициентов при неизвестных переменных левой части ограничений, m - ранг матрицы А)

базисом

Если ранг матрицы А равен 2, то допустимое решение х = (1, 0, 0, 0) называется … .

(А - матрица коэффициентов при неизвестных переменных левой части ограничений)

вырожденным

Если ранг матрицы А равен 2, то допустимое решение х = (0, 7, 0, 11) называется … .

(А - матрица коэффициентов при неизвестных переменных левой части ограничений)

невырожденным

Вектор х = (х₁, …, х_n) тогда и только тогда является опорным решением задачи линейного программирования, когда … .

(А - матрица коэффициентов при неизвестных переменных левой части ограничений)

все компоненты точки х отличны от нуля

Если среди компонентов вектора оценок а_j в алгоритме решения задачи линейного программирования существуют такие, для которых все х_ij ≤ 0, то … .

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

При решении задачи линейного программирования в форме симплекс-таблиц значение целевой функции вычисляется как сумма … .

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

В симплекс-таблице ведущим будет столбец, в котором значение α_j … .

(α_j – компонент вектора оценок)

минимально

Ведущей строкой симплекс-таблицы при решении задачи линейного программирования будет строка, для которой отношение координат вектора b к соответствующим положительным координатам вектора … .

(b – вектор свободных членов ограничений, правых частей ограничений, А - матрица коэффициентов при неизвестных переменных левых частей ограничений)

А ведущего столбца минимально

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

ведущим

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

(А - матрица коэффициентов при неизвестных переменных левых частей ограничений)

изменение базиса, путем замены вектора А ведущей строки на вектор А ведущего столбца

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

ведущий элемент

При решении задачи линейного программирования с помощью симплекс-таблиц построение симплекс-таблиц происходит до тех пор, пока все … .

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

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

теневой

Оптимальной теневой ценой ресурса называется такая, которая … .

минимизирует общую теневую стоимость ресурсов

Выберите верные утверждения … .

Целевая функция исходной задачи задается на максимум, а целевая функция двойственной задачи – на минимум

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

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

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

пустой

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

чувствительности

Линейными функциями являются функции … .

x₁+4x₂ = 0

f = 11x₁-11x₂

Линейными функциями являются функции … .

f = 15x₁+8x₂-14x₃

f = x₁

-2x₁+9x₃ = 0

Ограничения в каноническом виде для задачи линейного программирования представлены выражениями … .

13x₂-4*(x₁-x₃)=11

Ограничения в каноническом виде для задачи линейного программирования представлены выражениями … .

2x₁+3x₂-4x₃=3

5x₁-6x₄=8

Задача, состоящая в нахождении наибольшего/наименьшего значения функции f(x)=c₁x₁+c₂x₂+…+ c_nx_n на множестве точек х^т=(х₁,…,х_n), удовлетворяющие системе ограничений вида

называется … .

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

Задачей линейного программирования, записанной в векторной форме, является … .

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

Вектор А₄ равен … .

(А_i - базис)

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

Вектор b равен … .

(b – опорное решение задачи, свободные члены ограничений)

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

Допустимым решением будет значение х = … .

(0, 2, 0, 1)

(2, 1, 1, 0)

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

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

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

Формулой определяется значение … .

целевой функции

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

Двойственной задачей по отношению к прямой задаче будет … .

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

(f – целевая функция прямой задачи, f* – целевая функция двойственной задачи)

будет иметь оптимальное решение, причем max f = min f^*

Допустимой точкой или допустимым решением (планом) задачи линейного программирования, называется … .

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

Множество всех точек плоскости, координаты которых удовлетворяют всем ограничениям системы задачи линейного программирования – это …

допустимое множество

Вектор градиента (grad) для функции f = -5x₁ + 7x₂ будет соединять в пространстве координат точки (0,0) и … .

(-5, 7)

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

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

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

она не пуста

Необходимым и достаточным условием существования максимального (минимального) решения задачи линейного программирования является … .

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

Если векторы A_j, соответствующие отличным от нуля координатам вектора х, линейно-независимы, то ненулевое допустимое решение x = (x₁, …, x_n)^Т называется … .

опорным

Опорное решение называется вырожденным, если … .

( - матрица коэффициентов перед переменными x₁, …, x_n в ограничениях задачи линейного программирования, m – количество ограничений)

число положительных координат опорного решения меньше ранга матрицы А

Если ранг матрицы A равен m, то ненулевое опорное решение называется невырожденным, если оно имеет …

( - матрица коэффициентов перед переменными x₁, …, x_n в ограничениях задачи линейного программирования, m – количество ограничений)

«m» положительных координат

Базис – это … .

( - матрица коэффициентов перед переменными x₁, …, x_n в ограничениях задачи линейного программирования, A_j = (a_1j, a_2j, …, a_mn)^T, m – количество ограничений, n – количество переменных)

упорядоченный набор из «m» линейно-независимых векторов A_i , соответствующих положительным координатам опорного решения

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

ведущий элемент

При решении задачи линейного программирования с помощью метода симплекс таблиц ведущая строка в симплекс-таблице выбирается следующим образом: находится отношение координат вектора b к соответствующим … .

( - матрица коэффициентов перед переменными x₁, …, x_n в ограничениях задачи линейного программирования, A_j = (a_1j, a_2j, …, a_mn)^T, m – количество ограничений, n – количество переменных, b –опорное решение)

положительным координатам вектора A и выбирается минимальное из них

Каждый вид ресурса на предприятии обладает «теневой» ценой, которая определяет … .

ценность данного ресурса для предприятия

Объективно-обусловленными или оптимальными оценками при решении двойственных задач линейного программирования называют … .

оптимальные теневые цены

Число переменных двойственной задачи … .

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

К задачам линейного программирования относят следующие виды задач … .

планирования выпуска продукции

планирования капитальных вложений

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

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

каждое из ограничений графически задает … .

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

Множество решений задачи линейного программирования … .

выпукло

Вектор х = (x₁, …, x_n) тогда и только тогда является опорным решением задачи, когда точка х … .

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

В формуле пересчета для метода симплекс таблиц , x_rs представляет собой … .

ведущий элемент

Условием нахождения оптимального опорного решения задачи линейного программирования с помощью симплекс-таблиц является выполнение соотношения для вектора оценок … .

α_j > 0

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

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

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

переменные y_m обозначают … .

теневую цену ресурса

Коэффициентами при неизвестных в целевой функции двойственной задачи являются … .

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

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

Матрица системы сильных ограничений двойственной задачи будет равна … .

Если при решении двойственной задачи условные двойственные оценки единицы сырья y_i=0, это означает, что вид сырья … .

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

При анализе чувствительности двойственной задачи изучается … .

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

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

воздействие изменений в коэффициентах целевой функции

Общая постановка транспортной задачи состоит … .

в определении оптимального плана перевозок однородного груза из N пунктов отправления в М пунктов потребления

В качестве критерия оптимальности берётся … стоимость перевозок всего груза.

минимальная

Термин «транспортная задача» возник в … годах.

30-х

Транспортная задача относится к классу задач … программирования.

линейного

К способам нахождения опорного плана транспортной задачи можно отнести метод … .

минимального элемента

северо-западного угла

К способам нахождения оптимального опорного плана транспортной задачи можно отнести метод … .

потенциалов

Транспортная задача может быть … .

открытой

закрытой

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

закрытой

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

открытой

Необходимым и достаточным условием разрешимости транспортной задачи является ее … .

закрытость

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

2. Проверка на оптимальность.

1. Поиск опорного плана.

3. Переход к новому опорному плану, улучшающему целевую функцию в сторону ее оптимальности.

Опорный план транспортной задачи может быть … .

вырожденным

невырожденным

Для нахождения опорного плана транспортной задачи существуют методы … .

минимального элемента

северо-западного угла

аппроксимации Фогеля

Расставьте приоритеты в алгоритме нахождения начального опорного плана методом минимального элемента:

4Если наименьший тариф соответствует более чем одной клетке, выбор осуществляется случайным выбором.

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

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

2Производится корректировка оставшихся запасов и потребностей.

Метод потенциалов решения транспортной задачи реализуется для … опорных решений.

невырожденных

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

циклом

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

чувствительность

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

оптимальности

В транспортных задачах в таблицу поставок для каждой пары «поставщик-потребитель» сводятся … .

мощности поставщиков, запросы потребителей и затраты на перевозку единицы груза

Мощности поставщиков, запросы потребителей и затраты на перевозку единицы груза записываются в таблицу … .

поставок

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

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

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

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

все перечисленные варианты

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

перевозок

Общая стоимость перевозки между M пунктами отправления и N пунктами потребления в транспортных задачах равна … .

(x_ij – количество тонн сырья, c_ij – стоимость перевозки одной тонны сырья, x_i – пункт отправления, y_i – пункт потребления)

Методом линейного программирования одними из первых стали решать задачи … .

транспортные

Транспортная задача – одна из самых первых задач, которую стали решать с помощью методов … программирования.

линейного

В закрытой транспортной задаче сумма запасов … .

равна сумме потребностей

В открытой транспортной задаче … .

сумма потребностей не равна сумме запасов

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

открытой

Если транспортная задача является открытой, то в задачу вводим … .

одного потребителя

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

в таблицу поставок вводим одного поставщика

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

в таблицу поставок вводим одного поставщика

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

поставщика

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

потребителя

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

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

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

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

Транспортная задача является разрешимой, если она является … .

закрытой

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

нахождение начального базиса

построение дополнительного линейного ограничения

Опорный план называется невырожденным, если он содержит … .

(M - количество пунктов потребления, N – количество пунктов отправления)

M+N-1 отличных от нуля значений неизвестных

Опорный план, содержащий (M+N-1) отличных от нуля значений неизвестных, называется … планом.

(M - количество пунктов потребления, N – количество пунктов отправления)

невырожденным

Для нахождения опорного плана транспортной задачи не используют методы … .

метод Гомори

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

Расставьте приоритеты в алгоритме нахождения начального опорного плана методом северо-западного угла:

3Находим следующий северо-западный угол, заполняем эту клетку, вычеркиваем, вычеркиваем строку или столбец.

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

1В верхнюю левую клетку таблицы поставок записываем наименьшее число из запасов и потребностей.

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

северо-западного угла

Важнейшим условием построения опорного плана является назначение в выбранной клетке … .

наибольшего возможного плана перевозки

При использовании метода северо-западного угла выбирают клетку, которая соответствует северо-западному углу, такой клеткой в таблице поставок является … клетка.

верхняя левая

Число заполненных клеток в таблице поставок в методе северо-западного угла … .

(M - количество пунктов потребления, N – количество пунктов отправления)

меньше или равно (M+N-1)

Метод потенциалов используется для решения транспортной задачи в следующих случаях … .

после применения метода северо-западного угла

после применения метода минимального элемента

Величина, которая характеризует затраты на поставку от i-го поставщика j-ому потребителю в транспортных задачах равна … .

(v_j – потенциал j-го потребителя, u_i – потенциал i-го поставщика)

v_j-u_i

При решении транспортной задачи величина v_j-u_i-c_ij называется … .

(v_j – потенциал j-го потребителя, u_i – потенциал i-го поставщика, с_ij – стоимость перевозки одной тонны груза от i-го поставщика j-му потребителю)

теневой ценой по перемещению единицы груза от i-го поставщика j-му потребителю

Если при решении транспортной задачи теневая цена для свободной клетки меньше нуля, то перемещение по маршруту i→j может привести к … .

увеличению затрат

Если при решении транспортной задачи теневая цена для свободной клетки больше нуля, то перемещение по маршруту i→j может привести к … .

уменьшению затрат

Для определения потенциалов для заполненных клеток составляются выражения … .

(v_j – потенциал j-го потребителя, u_i – потенциал i-го поставщика, с_ij – стоимость перевозки одной тонны груза от i-го поставщика j-му потребителю)

v_j-u_i-c_ij=0

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

(v_j – потенциал j-го потребителя, u_i – потенциал i-го поставщика, с_ij – стоимость перевозки одной тонны груза от i-го поставщика j-му потребителю)

v_j-u_i-c_ij≤0

Опорный план в транспортной задаче является оптимальным при условиях … .

(v_j – потенциал j-го потребителя, u_i – потенциал i-го поставщика, с_ij – стоимость перевозки одной тонны груза от i-го поставщика j-му потребителю, x_ij – количество тонн сырья, которое i-го поставщика j-му потребителю)

v_j-u_i-c_ij=0 для клеток с x_ij>0 и v_j-u_i-c_ij≤0 для клеток с x_ij=0

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

(v_j – потенциал j-го потребителя, u_i – потенциал i-го поставщика, с_ij – стоимость перевозки одной тонны груза от i-го поставщика j-му потребителю)

наибольшая разность v_j-u_i-c_ij>0

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

в клетке пересчета

Клетка в таблице поставок, которая не удовлетворяет условию оптимальности плана, называется клеткой … .

пересчета

Цикл пересчета в таблице поставок транспортной задаче начинается с … клетки.

«плюсовой»

Цикл пересчета в таблице поставок транспортной задачи начинается с … клетки.

плюсовой

Цикл пересчета в таблице поставок транспортной задаче строится … .

по часовой стрелке

В клетку пересчета при перераспределении груза в транспортной задаче записывается … .

(x_ij – количество тонн сырья, которое i-го поставщика j-му потребителю)

наименьшее из чисел x_ij,стоящих в «минусовых» клетках

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

«минусовых»

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

«плюсовым»

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

северо-западного угла

Если минимальное значение среди чисел x_ij в «минусовых» клетках цикла пересчета равно нулю, то … .

(x_ij – количество тонн сырья, которое i-го поставщика j-му потребителю)

задача не имеет решение

необходимо добавить еще одного потребителя

преобразование таблицы перевозок сведется к перестановке этого нуля в свободную клетку

найдено оптимальное решение задачи

ХУЙ ЗНАЕТ!

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

снижаются

При анализе чувствительности можно указать промежутки устойчивости оптимального плана по изменению тарифов для … клеток.

свободных и занятых

К задачам целочисленного линейного программирования относятся задачи … .

о размещениях

о коммивояжёре

о назначениях

Задача, в которой требуется найти минимальный замкнутый и безпетельный маршрут с условием, что из каждого города необходимо въезжать и выезжать только один раз, называется задачей … .

о коммивояжёре

К методам решения задач целочисленного программирования относятся…

метод ветвей и границ

метод отсечения Гомори

Матрица, которая получается из матрицы расстояний вычитанием из элементов каждой строки …, называется приведённой.

минимального элемента этой строки, а затем вычитанием из элементов каждого столбца минимального элемента этого столбца

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

о назначениях

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

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

Задача о назначениях заключается в нахождении такого распределения оборудования … .

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

Задача о коммиявожёре заключается в нахождении…

минимального замкнутого и безпетельного маршрута, при условии, что из каждого города коммиявожёр въезжает и выезжает только один раз

Распределите пункты в порядке выполнения алгоритма метода отсечения Гомори:

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

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

2Полученное оптимальное решение задачи, если оно существует, проверяем на целочисленность.

Набор из «n» упорядоченных пар городов, образующих маршрут, который проходит через каждый город только один раз, называется … .

циклом

Задача, состоящая в таком расположении предприятий, определении их производственных мощностей и организации перевозок, чтобы суммарные затраты по производству и транспортировке были минимальны, называется задачей … .

о размещениях

Задача о размещениях формулируется следующим образом: найти такие значения … .

(x_i –объем продукции в единицах, который необходимо производить в пункте «i», x_ij – количество единиц продукции, поставляемой из пункта «i» в пункт «j», c_ij – затраты на транспортировку единицы продукции из производящего пункта «i» в потребляющий пункт «j», m – количество производящих пунктов, n – количество потребляющих пунктов)

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

В задачах о размещениях условие означает следующее … .

(x_i –объем продукции в единицах, который необходимо производить в пункте «i», x_ij – количество единиц продукции, поставляемой из пункта «i» в пункт «j», m – количество производящих пунктов, n – количество потребляющих пунктов)

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

Задача о назначениях формулируется следующим образом: найти такие значения … .

(x_ij – распределение оборудования, c_ij – производительность «i»-го типа оборудования на «j»-ом предприятии, n – количество оборудования различных типов, m – количество предприятий, имеющих различный уровень оснащенности)

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

В задачах о назначениях условие, которое устанавливает, что каждое предприятие получает по одному виду оборудования, записывается следующим образом … .

(x_ij – распределение оборудования, c_ij – производительность «i»-го типа оборудования на «j»-ом предприятии, n – количество оборудования различных типов, m – количество предприятий, имеющих различный уровень оснащенности)

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

(x_ij – распределение оборудования, c_ij – производительность «i»-го типа оборудования на «j»-ом предприятии, n – количество оборудования различных типов, m – количество предприятий, имеющих различный уровень оснащенности)

При решении задач целочисленного программирования методом Гомори "k-ое" дополнительное ограничение имеет вид … .

([x_i0], [x_ij] – целая часть соответствующей величины; x_i0 – нецелая координата оптимального плана задачи целочисленного программирования с наименьшим индексом; x_ij – координаты разложения векторов A_j, не попавших в базис; N_k – множество векторов, не попавших в базис)

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

комбинации (перестановки) одного и того же набора чисел

В методе ветвей и границ для решения задач целочисленного программирования для ветвления выбирается … .

подмножество с меньшей оценкой

В методе ветвей и границ длина замкнутого маршрута, образованного циклом t (набор из «n» упорядоченных пар городов, образующих маршрут, который проходит через каждый город только один раз) называется … .

издержками

В методе ветвей и границ условие S_ii = ∞, i=1,…,n говорит о том, что … .

(S_ij – элемент матрицы расстояний, который определяет расстояние при переходе из пункта «i» в пункт «j»)

переезд из пункта «i» в пункт «i» запрещен

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

приводящей константой

В методе ветвей и границ издержки цикла t вычисляются по формуле Z(t)=Z'(t)+h, где h – это … .

(Z(t) – издержки цикла t для исходной матрицы расстояний, Z'(t) – издержки цикла t после приведения)

сумма минимальных элементов строк исходной матрицы

Пара городов (i, j) для ветвления в задаче о коммивояжере выбирается среди тех пар, которым в приведенной матрице расстояний соответствуют … элементы.

нулевые

В методе ветвей и границ на вершине дерева ветвей располагается … .

подмножество, содержащее две пары городов, завершающих маршрут

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

3) Выбрать претендентов для ветвления, т.е. те пары (i, j) i=l,2,..., j = l, 2, ..., i ≠ j, для которых S_ij(k)=0.

2) Вычислить сумму приводящих констант h(k) - это оценка для исходного множества маршрутов G₀.

4) Выбрать для ветвления ту пару (i,j) из претендентов на ветвление, для которой θ_ij получится максимальным.

1) Произвести приведение матрицы расстояний S по строкам и столбцам, получим приведенную матрицу S′.

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

завершают

Графическим решением задачи о коммивояжере является маршрут … .

Дана матрица расстояний

Претендент на ветвление в приведенной матрице находится на пересечении … .

строки 1 столбца 4

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

(x_i –объем продукции в единицах, который необходимо производить в пункте «i», x_ij – количество единиц продукции, поставляемой из пункта «i» в пункт «j», c_ij – затраты на транспортировку единицы продукции из производящего пункта «i» в потребляющий пункт «j», m – количество производящих пунктов, n – количество потребляющих пунктов)

В задаче о размещениях суммарные затраты по производству и транспортировке должны быть … .

минимальными

При использовании метода Гомори полученное решение задачи линейного программирования проверяется на … .

целочисленность

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

строим дополнительное линейное ограничение

При использовании метода Гомори каждое "k-ое" дополнительное ограничение имеет вид: , где N_k - это множество векторов … .

([x_i0], [x_ij] – целая часть соответствующей величины; x_i0 – нецелая координата оптимального плана задачи целочисленного программирования с наименьшим индексом; x_ij – координаты разложения векторов A_j)

не попавших в базис

Используя метод ветвей и границ оптимальное решение можно найти … .

анализируя все возможные варианты

Задача о размещениях заключается в таком … .

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

К необходимым условиям задачи о коммивояжере относят … .

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

замкнутость маршрута

Дополнительное линейное ограничение в методе Гомори строится, если … .

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

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

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

К необходимым условиям задачи о назначениях относят следующие условия … .

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

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

К необходимым условиям задачи о размещениях относят следующие условия:

полное потребление производимой продукции

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

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

одной переменной

двух переменных

трех переменных

все ответы верны

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

квазивыпуклости

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

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

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

Ньютона

все ответы верны

В методах безусловной оптимизации функций ε – это … .

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

При нахождении минимума функции 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, принадлежащих [x₁, x₂] при любых x₁, x₂ Î [a, b] выполняется условие … .

Функция f(x) строго квазивогнута на отрезке [a, b], если для всех x, принадлежащих [x₁, x₂] при любых x₁, x₂ Î [a, b] выполняется условие … .

Хз…

Если ε – точность определения решения задачи, то метод циклического покоординатного спуска завершается при достижении следующего условия … .

(x^k – предпоследняя точка; x^(k+1) – последняя точка)

Нахождение минимума функции f многих переменных в направлениях параллельных осям координат происходит в методе … .

циклического покоординатного спуска

Нахождение минимума функции f многих переменных в направлении (– grad f(x₀)) происходит в методе … .

наискорейшего спуска

Направлением наибольшего возрастания функции f многих переменных в точке x₀ является … .

+grad f(x₀)

Направлением наибольшего убывания функции f многих переменных в точке x₀ является … .

–grad f(x₀)

Если ε – точность определения решения задачи, x_i – искомая точка, то метод наискорейшего спуска завершается при достижении следующего условия … .

Классический подход к задаче нахождения точек локального минимума для дважды дифференцируемой функции f(x_i,x_j) (i=1,…,n; j=1,…,n) состоит в … .

проверке положительной определенности матрицы Гессе (необходимое условие)

в определении таких точек x, в которых все первые частные производные 1-го порядка обращаются в нуль (достаточно условие)

В методе наискорейшего спуска сходимость обеспечена, если ... .

функция f непрерывно дифференцируема

функция f имеет седловую точку

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

все ответы верны

Недостатком метода наискорейшего спуска для «овражных» функций является ... .

медленная сходимость в окрестности стационарной точки

«Овражная» функция – это функция … .

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

Геометрически медленная сходимость метода наискорейшего спуска объясняется ... .

зигзагообразным продвижением к точке минимума

Недостатком метода Ньютона среди методов безусловной оптимизации является … .

необходимость многократного обращения матрицы Гессе

Суть метода Ньютона для функции f(x) состоит в том, что ... .

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

Требование квазивыпуклости минимизируемой функции является условием для применения метода … .

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

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

К методам, требующим квазивыпуклости минимизируемой функции, относятся методы … .

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

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

простых итераций

Ньютона

половинного деления

все ответы верны

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

4 Найти и проверить условие точности , положив i=i+1.

3 Проверить условие точности, если , положить и решить задачу о минимуме , найти >0.

1 Выбирать точку x_i, i=1.

2 Проверить условие точности, если , то x_i – искомая точка.

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

([а₁, b₁] – начальный отрезок, точки с₁ и d₁ принадлежат начальному отрезку)

3) Если , то определяем отрезок , вычислим .

1 Разделить начальный отрезок и выбрать точки , k = 1.

2 Если то оптимальная точка – это любая точка отрезка [ak,bk].

Если , то определяем отрезок , вычислим .

Требуемая точность в методах безусловной оптимизации обознается буквой … .

ε

На рисунке представлена … функция.

квазивыпуклая

На рисунке представлена … функция.

неквазивыпуклая

Неравенство f(c)>f(d) на отрезке [а, b] выполняется для функции, представленной на рисунке … .

([а, b] – начальный отрезок, точки с и d принадлежат начальному отрезку)

A

Неравенство f(c)≤f(d) на отрезке [а, b] выполняется для функции, представленной на рисунке … .

([а, b] – начальный отрезок, точки с и d принадлежат начальному отрезку)

Г

Метод Хука-Дживса осуществляет два типа поиска: … поиск и поиск по образцу.

исследующий

При нахождении минимума функции методом золотого сечения правильное изображение деления отрезка при условии f(c₁)>f(d₁) изображено на рисунке … .

([а₁, b₁] – начальный отрезок, точки с₁ и d₁ принадлежат начальному отрезку)

Г

Сходимость метода Хука-Дживса обеспечивается при тех же условиях, что и метод … .

покоординатного спуска

При нахождении минимума функции методом золотого сечения правильное изображение деления отрезка при условии f(c₁)≤f(d₁) изображено на рисунке … .

([а₁, b₁] – начальный отрезок, точки с₁ и d₁ принадлежат начальному отрезку)

Б

Множество точек (x,y), удовлетворяющих уравнению f(x,y)=c называют … .

линиями уровня

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

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

На рисунке представлена иллюстрация метода … .

циклического покоординатного спуска

На рисунке точка x₂ представляет собой ... точку.

неоптимальную

На рисунке представлена иллюстрация метода … .

Хука-Дживса

На рисунке представлена … функция.

овражная

Избежать появления так называемого «оврага» функции можно с помощью метода … .

Хука-Дживса

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

оптимальное управление

электрических цепей

проектирования строительных конструкций

все ответы верны

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

выпуклой

Нелинейными функциями являются … .

Линейными функциями являются … .

Геометрический способ решения задач нелинейного программирования подходит для решения задач с числом переменных равным … .

двум

Непустое множество, в котором отрезок прямой, соединяющий две любые точки данного множества также принадлежит этому множеству, называется … .

выпуклым

Непустое множество, в котором отрезок прямой, соединяющий две любые точки данного множества не весь принадлежит этому множеству, называется … .

невыпуклым

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

глобальным

Теорема Куна – Таккера справедлива для задач … .

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

Если f(x)>0 для всех значений переменных x = (x₁, x₂, …, x_n) кроме x=0, то квадратичная форма f называется … .

положительно-определённой

Если f(x)<0 для всех значений переменных x = (x₁, x₂, …, x_n) кроме x=0, то квадратичная форма f называется …

отрицательно-определённой

Квадратичной формой относительно переменных x₁, x₂, …, x_n называется скалярная функция от этих переменных, имеющая вид … .

Квадратичная форма является выпуклой функцией, если она … .

положительно-полуопределённая

Квадратичная форма является вогнутой функцией, если она … .

отрицательно-полуопределённая

Решение задачи квадратичного программирования можно найти с помощью метода … .

искусственного базиса

Градиентные методы позволяют находить … .

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

К градиентным методам относятся методы … .

приведённого градиента Вулфа

штрафных функций

Эрроу - Гурвица

все ответы верны

Градиентный метод решения задач нелинейного программирования состоит в последовательном переходе от начальной точки к другим, пока в очередной точке градиент не станет равным нулю или не будет выполнено условие (ε – точность полученного решения) … .

В уравнении F(x₁,x₂,…,x_n) = f(x₁,x₂,…,x_n) + H(x₁,x₂,…,x_n), где F(x₁,x₂,…,x_n) - максимальное значение функции, f(x₁,x₂,…,x_n) - целевая функция, H(x₁,x₂,…,x_n) – это … .

штрафная функция

Точка x_k будет является максимумом целевой функции f в методе штрафных функций, если градиенты целевой функции f и ограничительной функции … .

коллинеарны

Расставьте в правильном порядке этапы нахождения решения задачи нелинейного программирования геометрическим способом:

3 Определение гиперповерхности наинизшего (наивысшего) уровня или установление неразрешимости задачи из-за неограниченности целевой функции снизу (сверху) на множестве допустимых решений.

1 Нахождение области допустимых решений задачи, определяемой ограничениями (если она пуста, то задача не имеет решения).

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

2 Построение гиперповерхности .

Целевая функция и ограничения имеют вид:

.

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

А

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

глобальными

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

4 Записывать оптимальное решение исходной задачи и найти значение целевой функции в оптимальной точке.

2 Записывать в виде системы необходимые и достаточные условия существования седловой точки для функции Лагранжа.

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

1 Составить функцию Лагранжа.