PDA

Просмотр полной версии : ПОМОГИТЕ: ТЕОРИЯ АЛГОРИТМОВ


KITINA
23.03.2017, 17:56
Какую функцию, определённую при всех х ϵ En и у ≥ 0, называют функцией Лагранжа?
Выберите один ответ:
L(x,y) = \phi (x) - (y,f(x))
L(x, y) = cx - y(b + Ax)
L(x, y) =f(x) + y(b – g(x))
L(x, y) = cx + y(b – Ax)

Вопрос 2

Частично-рекурсивные функции – это…
Выберите один ответ:
функции, условием неактивности ограничивающих функций в точке y*
функции, определяемые особым образом с достаточной математической строгостью
функции, с условием активности ограничивающих функций в точке x*
Вопрос 3

Дайте название теоремы, условия которой звучат следующим образом: «Пусть допустимое множество не пусто и является компактным и выпуклым, а непрерывная функция F(x) вогнута на Х. Тогда локальный максимум является глобальным, а множество точек, на котором достигается максимум, выпукло.
Выберите один ответ:
Теорема Вейерштрасса
Теорема двойственности
Теорема достаточного условия глобального максимума
Теорема Куна-Таккера
Вопрос 4

Какие понятия являются основными при ормальной постановке задачи?
Выберите один или несколько ответов:
Допустимое множество
«инструментальные» переменные
Константы
Целевая функция
Вопрос 5

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

ввод вектор-строки из m новых переменных y = (y1, y2, …, ym);
определение функции Лагранжа как суммы целевой функции и скалярного произведения вектора множителей Лагранжа и вектора разности между постоянными ограничениями и функциями ограничений L (x, y) = F(x) + y(b – g(x));
отыскание точки (x*, y*), в которой все частные производные первого порядка функции Лагранжа обращаются в нуль.
Определите порядок этих этапов:

Выберите один ответ:
1, 2, 3
3, 2, 1
3, 1, 2
2, 1, 3
Вопрос 6

Как в соответствии с методом множителей Лагранжа задача f(x)→ min, xϵ Rn, h1(x) = 0 преобразуется в задачу безусловной минимизации?

Выберите один ответ:
L = L(x, y) =f(x) + y(b – g(x))
L(x;λ) = f(x) = λh1(x) → min, xϵ Rn
L(x, y) = cx + y(b – Ax) = cx + yb – yAx
L(x*,y*) = F(x*) + y*(b – g(x*)) = F(x*)
Вопрос 7

Если вектор инструментальных переменных x* принадлежит допустимому множеству и целевая функция принимает на этом векторе значение не меньшее, чем в любой другой допустимой точке, то он является:
Выберите один ответ:
Точкой глобального максимума
Точкой локального минимума
Точкой глобального минимума
Точкой локального максимума
Вопрос 8

Как называют точку х* = argmin { \phi (x): x ϵ X}? Выберите несколько вариантов ответов.
Выберите один или несколько ответов:
Допустимой точкой
Оптимальной точкой
Точкой глобального минимума
Решением
Вопрос 9

Сколько основных видов общей задачи математического программирования выделяют?
Выберите один ответ:
2
4
5
3
Вопрос 10

Как называется вектор-строка из m новых переменных y = (y1, y2, …, ym)?
Выберите один ответ:
Вектором функции Лагранжа
Вектором переменной Лагранжа
Вектором градиента функции
Вектором множителей Лагранжа
Вопрос 11

Массовость – это …
Выберите один ответ:
Свойство алгоритма служить для решения одного типа задач
Специальным образом определяемое устройство, работа которого обладает свойствами алгоритмического процесса
Свойство алгоритма служить для решения класса задач
свойство алгоритма, характеризующее однозначность преобразований
Вопрос 12

Задачу называют задачей выпуклого программирования, когда:
Выберите один ответ:
Множество X вогнуто и вогнуто функция \phi (х)
Множество X выпукло и выпукла функция \phi (х)
Множество X выпукло и вогнута функция \phi (х)
Множество X вогнуто и выпукла функция \phi (х)
Вопрос 13

Характерные свойства алгоритма (укажите неверный ответ):

Выберите один ответ:
Формальность
Определенность
Результативность
Вопрос 14

Как называют точку х, в которой выполняются необходимые условия локального минимума функции \phi (х) на множестве Х?
Выберите один ответ:
Оптимальной
Стационарной
Допустимой
Точкой глобального минимума
Вопрос 15

Какие задачи можно рассматривать как частный случай задач выпуклого программирования?
Выберите один ответ:
Задачи нелинейного программирования
Задачи линейного программирования
Задачи параметрического программирования
Задачи динамического программирования
Вопрос 16
Дана задача: f(x) = x12 + x22, при ограничении h1(x) = 2x1 + x2 – 2 = 0. Найдите минимальное значение f(x0; λ0).
Выберите один ответ:
2
4/5
2/5
1/2
Вопрос 17

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

Что из перечисленного характеризует метод множителей Лагранжа?
Выберите один или несколько ответов:
Является одним из наиболее эффективных методов решения классических задач программирования
С его помощью можно получить ценную информацию о том, в какой степени оптимальное значение целевой функции чувствительно к изменениям констант ограничений
Используется в качестве основного подхода к решению почти всех видов задач оптимизации
Решаемая этим методом задача «погружается» в более широкий класс задач, описываемых рядом параметров, и вслед за этим с помощью принципа оптимальности определяется основное рекуррентное соотношение
Вопрос 19

Что принято понимать под целевой функцией? Выберите несколько правильных ответов.
Выберите один или несколько ответов:
Функция, экстремальное значение которой ищется вне пределов обозначенного допустимого множества
Функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными и допустимым множеством в задаче оптимизации
Краткое математическое изложение цели данной задачи
Она представляет собой действительную непрерывно дифференцируемую функцию вектора инструментальных переменных F = F(x) = F(x, x, …, xn).
Вопрос 20

Что представляют собой все ограничения в классической задаче математического программирования?
Выберите один ответ:
Неравенства
Равенства
Условия неотрицательности
Условия константности
Вопрос 21

В нелинейном программировании система ограничений состоит из:
Выберите один или несколько ответов:
Условий неотрицательности
Ограничений в виде неравенств
Ограничений в виде равенств
Условий константности
Вопрос 22


Машина Тьюринга – это
Выберите один ответ:
Специально определяемый вид формул алгебры
Специальным образом определяемое устройство, работа которого обладает свойствами алгоритмического процесса
Функциональная диаграмма
Специальные преобразования функций в теории рекурсивных функций: оператор-подстановки, оператор примитивной рекурсии, оператор минимизации
Вопрос 23


Какая теорема формулирует условия существования глобального максимума?
Выберите один ответ:
Теорема двойственности
Теорема о магистрали
Теорема Вейерштрасса
Теорема Куна-Таккера
Вопрос 24


Для решения задач выпуклого программирования разработаны многочисленные численные методы, приспособленные для решения на ЭВМ, в основном связанные с:
Выберите один или несколько ответов:
Основной идеей того, что функция наиболее быстро убывает, если двигаться в направлении, противоположном градиенту
Основной идеей того, что функция наиболее быстро возрастает, если двигаться в направлении, противоположном градиенту
Основной идеей того, что функция стабильна, если двигаться в направлении, противоположном градиенту
Понятием градиента целевой функции
Вопрос 25


Основные свойства алгоритма:
Выберите один или несколько ответов:
Определенность
Массовость
Дискретность
Неопределённость

Добавлено через 2 минуты
У кого есть ответа, пожалуйста помогите, можете прислать на почту - [email protected]
Тестирование. Раздел 1. «Основы математического программирования»
Тренинг
Контроль

Тестирование. Раздел 2. «Симплекс-метод»
Тренинг
Контроль

Тестирование. Раздел 3. «Динамическое программирование»
Тренинг
Контроль

Итоговое тестирование
Контроль -/100
Интегральная оценка

ZAZAZA
14.04.2017, 19:23
Кто может помочь? [email protected]

klimaster
19.04.2017, 22:20
Теорема. Класс функций, вычислимых на машинах Тьюринга, ….
совпадает с классом частично-рекурсивных функций.

Какие понятия являются основными при ормальной постановке задачи?
«инструментальные» переменные
Целевая функция
Допустимое множество

Что представляют собой все ограничения в классической задаче математического программирования?
Равенства

В линейном программировании система ограничений состоит из:
Условий неотрицательности
Ограничений в виде неравенств

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

Какая теорема даёт условие существования решения задачи выпуклого программирования?
Пусть функция F(X) выпукла на выпуклом множестве D Rnи дифференцируема в точке Х*ϵ D. Тогда для того чтобы эта точка была точкой минимума функции F(X) , необходимо и достаточно, чтобы для любой точки Х ϵ D выполнялось неравенство (∇ F(X*), (X-X*))≥0.

Решение по методу Лагранжа классической задачи математического программирования подразумевает следующие этапы:
1. ввод вектор-строки из m новых переменных y = (y1, y2, …, ym);
2. определение функции Лагранжа как суммы целевой функции и скалярного произведения вектора множителей Лагранжа и вектора разности между постоянными ограничениями и функциями ограничений L (x, y) = F(x) + y(b – g(x));
3. отыскание точки (x*, y*), в которой все частные производные первого порядка функции Лагранжа обращаются в нуль.
Определите порядок этих этапов:
123

Что характеризует симплексный алгоритм?
Выбор начальной точки осуществляется с учётом ограничений

Основные свойства алгоритма:
Выберите один или несколько ответов:
Дискретность
Массовость
Определенность

Какая теорема формулирует условия существования глобального максимума?
Выберите один ответ:
Теорема Вейерштрасса

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

Как в соответствии с методом множителей Лагранжа задача f(x)→ min, xϵ Rn, h1(x) = 0 преобразуется в задачу безусловной минимизации?
Выберите один ответ:
L(x;λ) = f(x) = λh1(x) → min, xϵ Rn

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

Raptor
17.05.2017, 13:10
Для решения задач выпуклого программирования разработаны многочисленные численные методы, приспособленные для решения на ЭВМ, в основном связанные с:
Выберите один или несколько ответов:
Основной идеей того, что функция наиболее быстро убывает, если двигаться в направлении, противоположном градиенту
Понятием градиента целевой функции

Как называются ограничения первого вида?
Выберите один ответ:
Активными ограничениями

В каком из видов общей задачи математического программирования целевая функция является линейной формой?
Выберите один ответ:
В задаче линейного программирования

Какие задачи можно рассматривать как частный случай задач выпуклого программирования?
Выберите один ответ:
Задачи линейного программирования

Алгебра высказываний – это…
Выберите один ответ:
Логическая функция
Простейшая из формальных логических теорий

Выберите определения: «Задача математического программирования состоит:…»
Выберите один или несколько ответов:
В выборе вектора инструментальных переменных из множества возможностей, максимизирующего значение целевой функции
В нахождении значений переменных, максимизирующих заданную функцию и удовлетворяющих системе ограничений
(или минимизирующих — этот вариант можно включить как частный а можно и нет, тут зависит от строгости вопроса и преподавателя)

Характерные свойства алгоритма (укажите неверный ответ):
Выберите один ответ:
Формальность

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

Основные свойства алгоритма:
Выберите один или несколько ответов:
Дискретность
Определенность
Массовость5

Дайте название теоремы, условия которой звучат следующим образом: «Пусть допустимое множество не пусто и является компактным и выпуклым, а непрерывная функция F(x) вогнута на Х. Тогда локальный максимум является глобальным, а множество точек, на котором достигается максимум, выпукло.
Выберите один ответ:
Теорема достаточного условия глобального максимума

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

Что характерно для задач выпуклого программирования?
Выберите один или несколько ответов:
Любой локальный минимум является глобальным
Все действия сводятся к нахождению единственного минимума

В нелинейном программировании система ограничений состоит из:
Выберите один или несколько ответов:
Ограничений в виде неравенств
Ограничений в виде равенств
Условий неотрицательности

Система ограничений может включать также условия неотрицательности переменных, если такие условия имеются.
Задачу выпуклого программирования называют основной, если:
Выберите один ответ:
Все функции fi(x) выпуклы, а \phi (х) вогнуто

Частично-рекурсивные функции – это…
Выберите один ответ:
функции, определяемые особым образом с достаточной математической строгостью
функции называются частично рекурсивными, то есть они не полностью определенные

Что из перечисленного характеризует метод множителей Лагранжа?
Выберите один или несколько ответов:
Используется в качестве основного подхода к решению почти всех видов задач оптимизации
Решаемая этим методом задача «погружается» в более широкий класс задач, описываемых рядом параметров, и вслед за этим с помощью принципа оптимальности определяется основное рекуррентное соотношение
С его помощью можно получить ценную информацию о том, в какой степени оптимальное значение целевой функции чувствительно к изменениям констант ограничений

Задачу называют задачей выпуклого программирования, когда:
Выберите один ответ:
Множество X выпукло и вогнута функция \phi (х)
Задачей выпуклого программирования называется частный случай общей задачи математического программирования, когда целевая функция и функции ограничений являются вогнутыми на выпуклом множестве R.
Честно говоря, я не понимаю, что здесь понимается под функцией \phi(x), если это не обозначение целевой функции, то тогда какой?
Множество X выпукло и выпукла функция \phi (х)
Теорема. Класс функций, вычислимых на машинах Тьюринга, ….
совпадает с классом частично-рекурсивных функций.

Какие понятия являются основными при ормальной постановке задачи?
«инструментальные» переменные
Целевая функция
Допустимое множество

Что представляют собой все ограничения в классической задаче математического программирования?
Равенства

В линейном программировании система ограничений состоит из:
Условий неотрицательности
Ограничений в виде неравенств

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

Какая теорема даёт условие существования решения задачи выпуклого программирования?
Пусть функция F(X) выпукла на выпуклом множестве D Rnи дифференцируема в точке Х*ϵ D. Тогда для того чтобы эта точка была точкой минимума функции F(X) , необходимо и достаточно, чтобы для любой точки Х ϵ D выполнялось неравенство (∇ F(X*), (X-X*))≥0.

Решение по методу Лагранжа классической задачи математического программирования подразумевает следующие этапы:
1. ввод вектор-строки из m новых переменных y = (y1, y2, …, ym);
2. определение функции Лагранжа как суммы целевой функции и скалярного произведения вектора множителей Лагранжа и вектора разности между постоянными ограничениями и функциями ограничений L (x, y) = F(x) + y(b – g(x));
3. отыскание точки (x*, y*), в которой все частные производные первого порядка функции Лагранжа обращаются в нуль.
Определите порядок этих этапов:
123

Что характеризует симплексный алгоритм?
Выбор начальной точки осуществляется с учётом ограничений

Основные свойства алгоритма:
Выберите один или несколько ответов:
Дискретность
Массовость
Определенность

Какая теорема формулирует условия существования глобального максимума?
Выберите один ответ:
Теорема Вейерштрасса

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

Как в соответствии с методом множителей Лагранжа задача f(x)→ min, xϵ Rn, h1(x) = 0 преобразуется в задачу безусловной минимизации?
Выберите один ответ:
L(x;λ) = f(x) = λh1(x) → min, xϵ Rn

Сколько основных видов общей задачи математического программирования выделяют?
3
Дайте название теоремы, условия которой звучат следующим образом: «Пусть допустимое множество не пусто и является компактным и выпуклым, а непрерывная функция F(x) вогнута на Х. Тогда локальный максимум является глобальным, а множество точек, на котором достигается максимум, выпукло.

Raptor
03.06.2017, 18:18
ПОМОГИТЕ

Симплекс-таблица образуется из (выберите один ответ):
Выберите один ответ:
Свободных членов в ограничениях
Базисных переменных
Небазисных переменных
Матрицы коэффициентов системы уравнений линейного программирования, приведенной к “канонической форме”

Кем была переформулирована и решена транспортная задача?
Выберите один ответ:
Л. Фордом
Л. Канторовичем
А. Н. Тихоновым
Г. Монжа

Новая базисная переменная в симплекс-таблице, это:
Выберите один ответ:
Элемент, находящийся на пересечении последних строки и столбца
Минимальный элемент в ведущем столбце
Элемент, находящийся на пересечении ведущих строки и столбца
Минимальный элемент в ведущей строке

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

В чем заключаются условия новой транспортной задачи?
Выберите один ответ:
Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы минимальных временных затрат.
Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы минимальных финансовых затрат.
Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы рациональных затрат.
Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы минимальных затрат.

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

Какие взаимно-обратные зависимости характеризуют прямую и двойственную задачи?
Выберите один или несколько ответов:
Определяются значения n переменных – компонент вектора-строки х/ значения m переменных – компонент вектора-столбца y
Определяется максимум/минимум
Различны знаки неравенств
Константы ограничений одной из задач являются коэффициентами целевой функции другой

Как первоначально выглядела формулировка транспортной задачи?
Выберите один ответ:
Имеется куча песка и яма разных объёмов. Как рационально засыпать песком яму, потратив наименьшие усилия на перевозку?
Имеется куча песка и яма разных объёмов. Как рационально засыпать песком яму, потратив наименьшее время на перевозку?
Имеется куча песка и яма одинаковых объёмов. Как засыпать песком яму, потратив наименьшее время на перевозку?
Имеется куча песка и яма одинаковых объёмов. Как засыпать песком яму, потратив наименьшие усилия на перевозку?

Какая теорема трактует понятие базисного плана в терминах первой геометрической интерпретации задач линейного программирования?
Выберите один ответ:
Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.
Если система векторов содержит m линейно независимых векторов, то допустимый план является крайней точкой многогранника планов.
Каждый допустимый базисный план является угловой точкой множества допустимых планов D.
Если задача имеет решение, то целевая функция достигает экстремального значения хотя бы в одной из крайних точек многогранника решений. Если же целевая функция достигает экстремального значения более чем в одной крайней точке, то она достигает того же значения в любой точке, являющейся их выпуклой линейной комбинацией.

Выберите из перечисленных характеристик те, что относятся к прямой задаче:
Выберите один или несколько ответов:
Определяются значения m переменных – компонент вектора-строки y
Определяются значения n переменных – компонент вектора-столбца х
Определяется максимум
Определяется минимум

В каких годах 20-го века была переформулирована на язык современной математики и решена транспортная задача?
Выберите один ответ:
В 20-х годах
В 60-х годах
В 40-х годах
В 50-х годах

Какие переменные называют базисными?
Выберите один ответ:
Любые переменные, входящие в систему ограничений
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Это переменные, встречающиеся в системе ограничений только 1 раз
Это переменные, которые встречаются только в левой части системы ограничений

К логической операции относя:
Выберите один или несколько ответов:
Фильтрация
Дизъюнкция
Двойная импликация
Импликация

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

Что привело к осознанию вырожденности как самостоятельной проблемы в линейном программировании и необходимости разработки и внедрения специальных методов борьбы с вырожденностью?
Выберите один ответ:
"Застревание"симплекс-метода
Невозможность применения симплекс-метода
Зацикливание симплекс-метода

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


Какой алгоритм позволяет найти решение задач линейного программирования с помощью итеративной процедуры?
Выберите один ответ:
Дробный алгоритм
Первый алгоритм Гомори
Симплексный алгоритм
Алгоритм Флойда

Матрицей перехода к новому базису называется:
Выберите один ответ:
Матрица, которая содержит строк и у которой первые r <- m диагональных элементов ненулевые, а элементы, лежащие ниже главной диагонали и элементы последних m-r строк равны нулю.
Матрица, столбцами которой являются координаты векторов нового базиса в их разложении по векторам старого.
Скалярная матрица порядка n , диагональные элементы которой равны 1.
Диагональная матрица S , у которой все диагональные элементы равны между собой.

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

Как называется исходная задача линейного программирования, являющаяся задачей на максимум?
Выберите один ответ:
Прямой задачей
Основной задачей
Косвенной задачей
Двойственной задачей

Выберите из перечисленных характеристик те, что относятся к двойственной задаче:
Выберите один или несколько ответов:
Определяется максимум
Определяется минимум
Определяются значения m переменных – компонент вектора-строки y
Определяются значения n переменных – компонент вектора-столбца х

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

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

Raptor
06.06.2017, 15:59
ПОМОГИТЕ

Какое предположение в динамическом программировании играет существенную роль?
Выберите один или несколько ответов:
Функция оптимального поведения J*(x, t) представляет собой однозначную и непрерывно дифференцируемую функцию от n переменных.
Функция оптимального поведения J*(x, t) представляет собой однозначную и непрерывно дифференцируемую функцию от n + 1 переменных.
Решения задач более широкого класса являются однозначными и непрерывно дифференцируемыми функциями относительно изменений начальных параметров.
Решения задач более широкого класса являются однозначными и непрерывными функциями относительно изменений начальных параметров.

Что является непременным условием и единственным смыслом задачи коммивояжёра?
Выберите один ответ:
Поиск корневой вершины
Поиск самого короткого пути
Поиск самого длинного пути
Поиск самого выгодного пути

Какое ограничение связано с уравнением Беллмана, в качестве граничного условия, налагаемого на конечное состояние?
Выберите один ответ:
J*(x(t1), t1) = F(x2, t2).
J*(x(t1), t1) = F(x1, t1).
J*(x(t1), t1) =max F(x, t1).
J*(x(t1),u1, t1) = F(x1, u1, t1).

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

Как называют кружки схемы?
Выберите один ответ:
Вершинами (узлами) графа
Листьями графа
Ребрами графа
Корнями графа

Различают следующие частные случаи общей постановки задачи:
Выберите один или несколько ответов:
Симметричная задача коммивояжёра
Линейная задача коммивояжера
Геометрическая задача коммивояжёра
Треугольная задача коммивояжёра

Какой характер могут иметь зависимости между критериальной функцией и переменными?
Выберите один или несколько ответов:
Линейный
Произвольный
Экспоненциальный
Нелинейный

Каким условиям должна удовлетворять задача, чтобы для ее решения мог быть применен алгоритм динамического программирования?
Выберите один или несколько ответов:
Задача должна зависеть от количества шагов и быть определенной на каждом из них
Задача должна позволять интерпретацию как многошаговый процесс, каждый шаг которого состоит из принятия решения о выборе одного из допустимых управлений, приводящих к изменению состояния системы
Состояние системы на каждом шаге должно описываться одинаковым (по составу) набором параметров
Объектом исследования должна служить управляемая система (объект) с заданными допустимыми состояниями и допустимыми управлениями

Как называется максимальное значение целевого функционала задачи с начальным состоянием х и начальным временем t?
Выберите один ответ:
Оптимальным решением
Точкой бифуркации
Функцией оптимального поведения
Функцией оптимального решения

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

Что отображают узлы (вершины) дерева?
Выберите один ответ:
Варианты решения
Состояния, в которых возникает необходимость выбора
Различные состояния задачи
Различные события, которые могут иметь место

Какие трудности связаны с вычислительными алгоритмами динамического программирования?
Выберите один ответ:
При наличии нескольких ограничений состояние управляемого объекта на каждом шаге характеризуется набором параметров и табулировать значения функций необходимо для многократно большего количества точек.
Не достаточно мощности современных процессоров
Требуется много оперативной памяти
Большие погрешности приближения

Уравнение Беллмана имеет вид:
Выберите один ответ:
((dJ*)/(dt)) = max[I(x, u, t) +
{u(t)}
((dJ*)/(dx))f(x, u, t)].
-((dJ*)/(dt)) = max[I(x, u, t) +
{u(t)}
((dJ*)/(dx))f(x, u, t)].
((dJ*)/(dt)) = min[I(x, u, t) +
{u(t)}
((dJ*)/(dx))f(x, u, t)].
-((dJ*)/(dt)) = min[I(x, u, t) +
{u(t)}
((dJ*)/(dx))f(x, u, t)].

Как называются две вершины графа, соединенные ребром?
Выберите один ответ:
Изолированными вершинами
Смежными вершинами
Висячими вершинами
Связанными вершинами

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

Что можно отнести к достоинствам комплекса методов динамического программирования?
Выберите один ответ:
Уменьшение времени, затраченного на вычисление.
Единый универсальный метод решения.
Сокращение объема используемой памяти.
Возможность упрощения процесса решения, за счет ограничения области и количества исследуемых при переходе к очередному этапу вариантов.

Задача коммивояжёра это:
Выберите один ответ:
Задача на поиск Гамильтонова пути в графе
Задача на поиск ребра с наибольшим весом в графе
Задача, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные пункты хотя бы по одному разу с последующим возвратом в исходный пункт
Задача на поиск кратчайшего пути между двумя вершинами в графе

Что представляет собой динамическое программирование в широком смысле?
Выберите один ответ:
Математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах N-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Раздел математического программирования, в котором на все или некоторые переменные дополнительно накладывается ограничение целочисленности.
Способ решения сложных задач путём разбиения их на более простые подзадачи.
Случай математического программирования, в котором целевой функцией или ограничением является нелинейная функция.

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

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

Как называется основное дифференциальное уравнение в частных производных, вытекающее из главного рекуррентного соотношения?
Выберите один ответ:
Обобщенное рекуррентное соотношение
Уравнение Беллмана
Динамическое уравнение
Уравнение Гельмгольца

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

Как называются линии, соединяющие кружки схемы?
Выберите один ответ:
Ветвями графа
Ребрами графа
Узлами графа
Вершинами графа

Кто сформулировал данный принцип оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения.
Выберите один ответ:
Д. Гильберт
А. Эйнштейн
А. Н. Колмогоров
Р.Э. Беллман

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

22.07.2017, 10:33
куплю теорию алгоритмов с 2 модуля по 3 с итоговым

metalset
31.08.2017, 10:31
куплю ответы на тест по данной теме. в лс.

sinij_
11.09.2017, 14:20
модуль на 3

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

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

функция F(X) достигает глобального минимума.

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

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

Для решения задач выпуклого программирования разработаны многочисленные численные методы, приспособленные для решения на ЭВМ, в

основном связанные с

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

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

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

1, 2, 3

Как называют точку х* = argmin { \phi (x): x ϵ X}? Выберите несколько вариантов ответов

Оптимальной точкой
Допустимой точкой
Точкой глобального минимума

Основные свойства алгоритма

Определенность
Дискретность
Массовость
Неопределённость

Что принято понимать под целевой функцией? Выберите несколько правильных ответов

Функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными и допустимым множеством в задаче оптимизации
Краткое математическое изложение цели данной задачи

Алгебра высказываний – это…

Логическая функция
Простейшая из формальных логических теорий

Какая теорема формулирует условия существования глобального максимума

Теорема Вейерштрасса

Что из перечисленного характеризует метод множителей Лагранжа?

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

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

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

Характерные свойства алгоритма (укажите неверный ответ):

Формальность

Что представляют собой все ограничения в классической задаче математического программирования?

Равенства

Определённость алгоритма – это …

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

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

Ограничений в виде неравенств
Ограничений в виде равенств
Условий неотрицательности

Если вектор инструментальных переменных x* принадлежит допустимому множеству и целевая функция принимает на этом векторе значение не

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

Точкой глобального максимума

Частично-рекурсивные функции – это…

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

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

Любой локальный минимум является глобальным
Все действия сводятся к нахождению единственного минимума

Как называется вектор-строка из m новых переменных y = (y1, y2, …, ym)?

Вектором функции Лагранжа

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

выпуклым, а непрерывная функция F(x) вогнута на Х. Тогда локальный максимум является глобальным, а множество точек, на котором

достигается максимум, выпукло

Теорема достаточного условия глобального максимума

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

Целевая функция
Допустимое множество

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

Все функции fi(x) выпуклы, а \phi (х) вогнуто

Как называют точку х, в которой выполняются необходимые условия локального минимума функции \phi (х) на множестве Х?

Массовость – это …

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

Назовите основные виды общей задачи математического программирования

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

Gens
05.10.2017, 12:44
Ответы на первый модуль. оценка-4

Вопрос 1
Дайте название теоремы, условия которой звучат следующим образом: «Пусть допустимое множество не пусто и является компактным и выпуклым, а непрерывная функция F(x) вогнута на Х. Тогда локальный максимум является глобальным, а множество точек, на котором достигается максимум, выпукло.
Выберите один ответ:
Теорема достаточного условия глобального максимума

Вопрос 2
Определённость алгоритма – это …
Выберите один ответ:
Свойство алгоритма, характеризующее однозначность преобразований

Вопрос 3
Дана задача: f(x) = x12 + x22, при ограничении h1(x) = 2x1 + x2 – 2 = 0. Найдите минимальное значение f(x0; λ0).
Выберите один ответ:
4/5

Вопрос 4
Глобальный максимум является строгим (сильным), если:
Выберите один ответ
Значение целевой функции при Х = Х* строго больше любого другого значения функции на допустимом множестве

Вопрос 5
В каком из видов общей задачи математического программирования целевая функция является линейной формой?
Выберите один ответ:
В задаче линейного программирования

Вопрос 6
Машина Тьюринга – это
Выберите один ответ:
Специальным образом определяемое устройство, работа которого обладает свойствами алгоритмического процесса

Вопрос 7
Как в соответствии с методом множителей Лагранжа задача f(x)→ min, xϵ Rn, h1(x) = 0 преобразуется в задачу безусловной минимизации?
L(x;λ) = f(x) = λh1(x) → min, xϵ Rn

Вопрос 8
Какие задачи можно рассматривать как частный случай задач выпуклого программирования?
Выберите один ответ:
Задачи нелинейного программирования

Вопрос 9
Выберите определения: «Задача математического программирования состоит:…»
Выберите один или несколько ответов:
В выборе вектора инструментальных переменных из множества возможностей, максимизирующего значение целевой функции
В нахождении значений переменных, максимизирующих заданную функцию и удовлетворяющих системе ограничений

Вопрос 10
Какие понятия являются основными при ормальной постановке задачи?
Выберите один или несколько ответов:
«инструментальные» переменные
Допустимое множество
Целевая функция

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

Вопрос 12
Какая теорема даёт условие существования решения задачи выпуклого программирования?
Выберите один ответ:
Пусть функция F(X) выпукла на выпуклом множестве D Rnи дифференцируема в точке Х*ϵ D. Тогда для того чтобы эта точка была точкой минимума функции F(X) , необходимо и достаточно, чтобы для любой точки Х ϵ D выполнялось неравенство (∇ F(X*), (X-X*))≥0.

Вопрос 13
Какую функцию, определённую при всех х ϵ En и у ≥ 0, называют функцией Лагранжа?
Выберите один ответ:
L(x,y) = Ф(x) - (y,f(x))

Вопрос 14
Пока нет ответа
Балл: 1,00
В нелинейном программировании система ограничений состоит из:
Выберите один или несколько ответов:
Ограничений в виде неравенств
Ограничений в виде равенств
Условий неотрицательности

Вопрос 15
Задачу выпуклого программирования называют основной, если:
Выберите один ответ:
Все функции fi(x) выпуклы, а ф(х) вогнуто

Вопрос 16
В линейном программировании система ограничений состоит из:
Выберите один или несколько ответов:
Условий неотрицательности
Ограничений в виде неравенств

Вопрос 17
Назовите основные виды общей задачи математического программирования
Выберите один или несколько ответов:
Задача нелинейного программирования
Задача линейного программирования
Задача динамического программирования

Вопрос 18
Частично-рекурсивные функции – это…
Выберите один ответ:
функции, определяемые особым образом с достаточной математической строгостью

Вопрос 19
Что представляют собой все ограничения в классической задаче математического программирования?
Выберите один ответ:
Равенства

Вопрос 20
Решение по методу Лагранжа классической задачи математического программирования подразумевает следующие этапы:
1. ввод вектор-строки из m новых переменных y = (y1, y2, …, ym);
2. определение функции Лагранжа как суммы целевой функции и скалярного произведения вектора множителей Лагранжа и вектора разности между постоянными ограничениями и функциями ограничений L (x, y) = F(x) + y(b – g(x));
3. отыскание точки (x*, y*), в которой все частные производные первого порядка функции Лагранжа обращаются в нуль.
Определите порядок этих этапов:
Выберите один ответ:
1, 2, 3

Вопрос 21
Какая теорема формулирует условия существования глобального максимума?
Выберите один ответ:
Теорема Вейерштрасса

Вопрос 22
Характерные свойства алгоритма (укажите неверный ответ):
Выберите один ответ:
Формальность

Вопрос 23
Алгоритм – совокупность правил….
Выберите один ответ:
определяющих данный вычислительный процесс (точное предписание, определяющее вычислительный процесс, ведущий от варьируемых исходных данных)

Вопрос 24
Что характеризует симплексный алгоритм?
Выберите один ответ:
Выбор начальной точки осуществляется с учётом ограничений

Вопрос 25
Что принято понимать под целевой функцией? Выберите несколько правильных ответов.
Выберите один или несколько ответов:
Краткое математическое изложение цели данной задачи
Функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными и допустимым множеством в задаче оптимизации


Очень хотелось бы увидеть ответы на 2-3 модули.

xolodno
11.10.2017, 14:08
Теория алгоритмов. Раздел 2. «Симплекс-метод».zip (http://mti.prioz.ru/krfilesmanager.php?do=downloadfile&dlfileid=1447)
На 4 вышло, если кто сможет улучшить - тому будет плюс к карме.

Добавлено через 10 часов 40 минут
Теория алгоритмов. Раздел 3. Динамическое программирование (http://mti.prioz.ru/krfilesmanager.php?do=downloadfile&dlfileid=1448)
На 4. Правки и дополнения приветствуются.

Добавляю вопросы из итогового экзамена, второпях решён один из трёх
Теория алгоритмов. Дополнение (http://mti.prioz.ru/krfilesmanager.php?do=downloadfile&dlfileid=1449)

Gens
24.10.2017, 16:49
Теория алгоритмов. Раздел 2. «Симплекс-метод».zip (http://mti.prioz.ru/krfilesmanager.php?do=downloadfile&dlfileid=1447)
На 4 вышло, если кто сможет улучшить - тому будет плюс к карме.

Добавлено через 10 часов 40 минут
Теория алгоритмов. Раздел 3. Динамическое программирование (http://mti.prioz.ru/krfilesmanager.php?do=downloadfile&dlfileid=1448)
На 4. Правки и дополнения приветствуются.

Добавляю вопросы из итогового экзамена, второпях решён один из трёх
Теория алгоритмов. Дополнение (http://mti.prioz.ru/krfilesmanager.php?do=downloadfile&dlfileid=1449)


многое есть но многого и нет, видимо старые тесты(((

Askarbek99
29.10.2017, 08:47
куплю теорию алгоритмов с 2 модуля [email protected]

Алексей-it
05.11.2017, 20:56
Привет!
А есть варианты ответа на 2-3 раздел?
Поделитесь пожалуйста [email protected]

Sergg
03.02.2018, 13:08
Кто сдавал недавно, подскажите итоговые тесты совпадают с промежуточными?!!!!

Jack91
06.03.2018, 23:10
Итоговые тесты совпадают с промежуточными.

Вот результаты моих запар, ребят, пришлось применять теорию алгоритмов к тестам по теории алгоритмов(:)) чтобы отобрать правильные ответы, и ещё погуглить. К сожалению, мне дико не хватило ответов на вопросы, когда я их искал, и эта ветка - единственная во всём интернете (хотя бы с частичными вариантами ответов); поэтому я решил, что если получится сдать, то выложу и выручу тех, кто будет искать так же, как и я ;)
Сдал на отлично.

P.S. К слову сказать, учебный курс я, будучи ответственным студентом, прошёл и рекомендуемую литературу перечитал.

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

Вот, второй раздел, "Симпликс-метод":
(плюсы - верно, минусы - точно не подходит)

Какие переменные называют базисными?

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



Назовите методы, позволяющие эффективно преодолевать вырожденность:

+++Метод А.Чарнса

+++ Метод П.Вольфа

+++Метод Б.Ц.Бахшияна



Что характеризует симплексный алгоритм?

+++Выбор начальной точки осуществляется с учётом ограничений



Кем была переформулирована и решена транспортная задача?

+++Л. Канторовичем



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


+++Прямой задачей



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

+++Различны знаки неравенств



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

+++Каждый опорный план содержит ровно m положительных компонент, где m – число ограничений в задаче



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

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



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

+++Симплексный алгоритм



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

+++Двойственной задачей



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

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



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

+++Еа<Еб



Матрицей перехода к новому базису называется:

+++Матрицей которая из старой, тыры-пыры



Операторы – это …

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



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

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



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

+++Через некоторую угло*вую точку многогранного множества допустимых планов зада*чи, соответствующую текущему базисному плану, проходит более чем m гиперплоскостей ограничений задачи.

+++«попадание» линии, проходящей через вершину вектора b параллельно оси аппликат, в ребро кону*са, натянутого на систему расширенных векторов текущего базиса.

+++Одно или несколько ограничений в некоторой угло*вой точке многогранного множества допустимых планов зада*чи являют*ся избыточными.



Если смещение в некоторую другую вершину не уменьшает целевую функцию, то:

+++Все вершины являются решениями, а также все точки между этими вершинами



Если перемещение в любую соседнюю вершину уменьшает целевую функцию, то:

+++Найденное решение единственное



В чём заключается борьба с выраженностью?

+++В преобразовании задачи путём «незначительного» изменения вектора правых частей системы ограничений на величины ?i таким образом, чтобы это изменение не повлияло реально на оптимальный план задачи.

Симплекс-таблица образуется из (выберите один ответ):

+++Матрицы коэффициентов системы уравнений линейного программирования, приведенной к “канонической форме”


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

+++Г. Монжа


Какая транспортная задача называется открытой?

+++Еа>Еб

+++Еа<Еб



Какая транспортная задача называется закрытой?

+++Еа=Еб


Какие варианты реализации симплекс-метода возможны (принять во внимание тот факт, что число вершин допустимого множества конечно)?

+++Приведёт к решению задачи

+++Через конечное число шагов покажет, что целевая функция не ограничена


В каких годах 20-го века была переформулирована на язык современной математики и решена транспортная задача?

+++В 40-х годах


Базисный план х называется невырожденным, если:
+++Все его базисные компоненты строго положительны


Композиция машин – это …

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



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


+++В одной вершине многогранника условий пересекается более двух прямых, описываемых уравнениями вида xi = 0.

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


Что привело к осознанию вырожденности как самостоятельной проблемы в линейном программировании и необходимости разработки и внедрения специальных методов борьбы с вырожденностью?

+++"Застревание"симплекс-метода


Процесс поиска глобального оптимума состоит из таких этапов:

Берётся любая соседняя вершина по такому направлению, в котором целевая функция возрастает

Берётся любая вершина допустимого множества

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

Берётся очередная соседняя вершина по такому направлению, в котором целевая функция возрастает

Определите порядок осуществления данных этапов.

+++2, 1, 4, 3



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

+++Определяются значения m переменных – компонент вектора-строки y

+++Определяется минимум



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

+++Определяются значения n переменных – компонент вектора-столбца х

+++Определяется максимум



Дана таблица двойственных задач: Как следует читать эту таблицу, чтобы получить задачу минимизации?

+++Сверху вниз



Дана таблица двойственных задач: Как следует читать эту таблицу, чтобы получить задачу максимизации?

+++Слева Направо



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

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



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

+++Оно неотрицательно



Задача, двойственная к двойственной задаче, представляет собой:

+++Исходную задачу



К логической операции относя:

+++Импликация

+++Дизъюнкция

+++Двойная Импликация



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

+++Макс Ф, А<б, х>0



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

+++Имеется куча песка и яма одинаковых объёмов. Как засыпать песком яму, потратив наименьшие усилия на перевозку?



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

+++За ограниченное количество шагов (итераций) получить искомый результат — план, обеспечивающий экстремальное значение целевой функции.



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

+++Каждый допустимый базисный план является угловой точкой множества допустимых планов D.



Важным шагом в работах Канторовича было:

+++Применение метода двойственности

+++Формулировка транспортной задачи на языке теории меры

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



Новая базисная переменная в симплекс-таблице, это:

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

Выберите правильное утверждение:

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



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

+++Симплексной таблицей



Для чего используется симплекс-таблица?

+++За ограниченное количество шагов (итераций) получают искомый результат — план, обеспечивающий экстремальное значение целевой функции.



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

+++Ведущим преобразованием

_______________________________________________________
Раздел третий, "Динамическое программирование":

Задача коммивояжёра это:

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



Что является непременным условием и единственным смыслом задачи коммивояжёра?

+++Поиск самого выгодного пути



Как называются две вершины графа, соединенные ребром?

+++Смежными вершинами



Путь, содержащий каждую вершину графа ровно один раз, называется:

+++Гамильтонов путь

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

+++Способ решения сложных задач путём разбиения их на более простые подзадачи.


Укажите примеры задач динамического программирования, в которых поиск оптимума возможен при поэтапном подходе:

---Разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию.

---Вычисление корней квадратного уравнения



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

---Каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения.

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



Какой характер могут иметь зависимости между критериальной функцией и переменными?


+++Линейный
+++Нелинейный

Какова логика анализа методом «Дерева решений»?


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

Различают следующие частные случаи общей постановки задачи:

+++Треугольная задача коммивояжёра

+++Симметричная задача коммивояжёра

+++Геометрическая задача коммивояжёра


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

Описать строение оптимальных решений.

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

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

Пользуясь полученной информацией, построить оптимальное решение.

---3,4,1,2
---2,1,4,3
---2,4,3,1

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

+++Объектом исследования должна служить управляемая система (объект) с заданными допустимыми состояниями и допустимыми управлениями
+++Состояние системы на каждом шаге должно описываться одинаковым (по составу) набором параметров
+++Задача должна позволять интерпретацию как многошаговый процесс, каждый шаг которого состоит из принятия решения о выборе одного из допустимых управлений, приводящих к изменению состояния системы

Что является особенностью задач последовательного принятия решений?

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

Как называются линии, соединяющие кружки схемы?

+++Ребрами графа



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

+++Необходимо найти и описать все возможные пути при любом из вариантов способов поиска решения



В каком направлении решается задача при использовании алгоритмов динамического программирования, если задано конечное состояние управляемой системы?
+++В ПРЯМОМ

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

+++В ОБРАТНОМ

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

+++Особенности решения задач: по этапам, через фиксированные интервалы, промежутки времени.



Какое ограничение связано с уравнением Беллмана, в качестве граничного условия, налагаемого на конечное состояние?

+++J*(x(t1), t1) = F(x1, t1).

Как называют кружки схемы?

+++Вершинами (узлами) графа



Задача коммивояжёра называется геометрической, когда:

+++Матрица расстояний отражает расстояния между точками на плоскости



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

+++Арис



Что отображают ветви дерева?

+++Различные события, которые могут иметь место


К числу каких задач относится задача коммивояжёра?

+++Трансвычислительных

Когда применяется дерево решений?

+++Когда количество альтернатив и количество шагов принятия решений ограниченно (конечно)



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

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

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

Какое свойство является основным с точки зрения идеологии динамического программирования?
+++Последующее состояние, в котором оказывается система после выбора решения на k-м шаге, зависит только от данного решения и исходного состояния к началу k-го шага

Как называется основное дифференциальное уравнение в частных производных, вытекающее из главного рекуррентного соотношения?
+++Уравнение Беллмана

Как называется максимальное значение целевого функционала задачи с начальным состоянием х и начальным временем t?
+++Функцией оптимального поведения

Какие трудности связаны с вычислительными алгоритмами динамического программирования?
+++При наличии нескольких ограничений состояние управляемого объекта на каждом шаге характеризуется набором параметров и табулировать значения функций необходимо для многократно большего количества точек.

Основное рекуррентное соотношение в математической форме имеет следующий вид:

+++ J*(x, t) = max[I(x, u, t)Δt + {u(t)}
J*(x + Δx, t + Δt)].

С чем связаны трудности решения уравнения Беллмана на цифровых электронно-вычислительных машинах с большим быстродействием?
+++Недостаточная машинная память

Одним из разделов какого программирования является динамическое программирование?
+++Оптимального программирования

Известно, что проверка решения задачи коммивояжёра:
+++Равна или больше самого решения

В каких задачах успешно применяются методы динамического программирования?
+++В задачах без учёта фактора времени

Для чего применяется дерево решений?
+++Для структуризации проблем

Что можно отнести к достоинствам комплекса методов динамического программирования?
+++Возможность упрощения процесса решения, за счет ограничения области и количества исследуемых при переходе к очередному этапу вариантов.

В каком случае при использовании алгоритмов динамического программирования иногда прибегают к компромиссу: отказываются от оптимизации на первом или последнем этапе?
+++Если заданы начальное и конечное состояния

Какое предположение в динамическом программировании играет существенную роль?
+++Решения задач более широкого класса являются однозначными и непрерывными функциями относительно изменений начальных параметров.
+++Функция оптимального поведения J*(x, t) представляет собой однозначную и непрерывно дифференцируемую функцию от n + 1 переменных.

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

Что отображают узлы (вершины) дерева?
+++Состояния, в которых возникает необходимость выбора

Гамильтонов цикл – это:
+++Гамильтонов путь, начальная и конечная вершины которого совпадают

Задача коммивояжёра называется треугольной, когда:
+++На матрице стоимостей выполняется неравенство треугольника

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

Какое свойство называют «отсутствием последействия»?
+++Последующее состояние, в котором оказывается система после выбора решения на k-м шаге, зависит только от данного решения и исходного состояния к началу k-го шага

Уравнение Беллмана имеет вид:
---((dJ*)/(dt)) = max[I(x, u, t) +
{u(t)}
((dJ*)/(dx))f(x, u, t)].

Алексей-ко
18.05.2018, 17:54
ответы на теорию алгоритмов 3 модуля

qwertyHAX
27.07.2018, 16:09
Пользуясь полученной информацией, построить оптимальное решение.

---3,4,1,2
---2,1,4,3
---2,4,3,1

+++1 2 3 4

Tane4ka8686
20.02.2019, 23:19
Правильные ответы
Контроль 1
Алгоритм – совокупность правил….
определяющих данный вычислительный процесс (точное предписание, определяющее вычислительный процесс, ведущий от варьируемых исходных данных)
В каком из видов общей задачи математического программирования целевая функция является линейной формой?
В задаче линейного программирования
Глобальный максимум является строгим (сильным), если:
Значение целевой функции при Х = Х* строго больше любого другого значения функции на допустимом множестве
Дайте название теоремы, условия которой звучат следующим образом: «Пусть допустимое множество не пусто и является компактным и выпуклым, а непрерывная функция F(x) вогнута на Х. Тогда локальный максимум является глобальным, а множество точек, на котором достигается максимум, выпукло.
Теорема достаточного условия глобального максимума
Если вектор инструментальных переменных x* принадлежит допустимому множеству и целевая функция принимает на этом векторе значение не меньшее, чем в любой другой допустимой точке, то он является:
Точкой глобального максимума
Задачу называют задачей выпуклого программирования, когда:
Множество X выпукло и выпукла функция (х)
Из какой теоремы следует, что во всех точках локального минимума выпуклая функция имеет одинаковые значения?
Если внутренняя точка Х* множества Д является точкой локального минимума в задаче выпуклого программирования, то в этой точке функция F(X) достигает глобального минимума.
Как называется вектор-строка из m новых переменных y = (y1, y2, …, ym)?
Вектором множителей Лагранжа
Какая теорема формулирует условия существования глобального максимума?
Теорема Вейерштрасса
Какая теорема даёт условие существования решения задачи выпуклого программирования?
Пусть функция F(X) выпукла на выпуклом множестве D Rnи дифференцируема в точке Х*ϵ D. Тогда для того чтобы эта точка была точкой минимума функции F(X) , необходимо и достаточно, чтобы для любой точки Х ϵ D выполнялось неравенство (∇ F(X*), (X-X*))≥0.
Массовость – это …
Свойство алгоритма служить для решения класса задач
Определённость алгоритма – это …
Свойство алгоритма, характеризующее однозначность преобразований
Основные свойства алгоритма:
Определенность
Массовость
Дискретность
Характерные свойства алгоритма (укажите неверный ответ):
Формальность

123456qwerty
24.03.2019, 14:45
Для управления какими объектами применим принцип оптимальности?
+Объектами, у которых выбор оптимального управления не зависит от предыстории управляемого процесса, т. е. от того, каким путем система пришла в текущее состояние.

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

Дайте название теоремы, условия которой звучат следующим образом: «Пусть допустимое множество Х является компактным и непустым. Тогда непрерывная целевая функция F(x), определённая на этом множестве, достигает глобального максимума на внутренней или граничной точке множества Х*.
+Теорема Вейерштрасса