Итоговые тесты совпадают с промежуточными.
Вот результаты моих запар, ребят, пришлось применять теорию алгоритмов к тестам по теории алгоритмов(
) чтобы отобрать правильные ответы, и ещё погуглить. К сожалению, мне дико не хватило ответов на вопросы, когда я их искал, и эта ветка - единственная во всём интернете (хотя бы с частичными вариантами ответов); поэтому я решил, что если получится сдать, то выложу и выручу тех, кто будет искать так же, как и я
Сдал на отлично.
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)].