Теория игр и исследование операций

Упражнение 1:

Номер 1

Что такое допустимый маршрут в "задаче коммивояжера"?

Ответ:

(1) cовокупность прямых участков и поворотов

(2) тот маршрут, который не содержит остановок

(3) множество упорядоченных пар городов

Номер 2

Что такое маршрут?

Ответ:

(1) цикл

(2) не содержащая циклов последовательность

(3) план передвижения

Номер 3

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

Ответ:

(1) командировочное удостоверение

(2) предписание

(3) матрица

Упражнение 2:

Номер 1

В задаче коммивояжера матрица расстояний …

Ответ:

(1) не содержит нулей

(2) не содержит бесконечных элементов

(3) обязательно содержит бесконечные элементы

Номер 2

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

Ответ:

(1) только на транспорте

(2) только коммивояжерами при оформлении отчетности

(3) для организации переналадки станков

Номер 3

Что означает бесконечный элемент матрицы?

Ответ:

(1) означает, что допущена ошибка

(2) ничего не означает, если рядом с бесконечностью стоит цифра 8

(3) означает, что переход из состояния в состояние запрещен

Упражнение 3:

Номер 1

Задача коммивояжера относится к …

Ответ:

(1) целочисленному программированию

(2) аналитической геометрии

(3) анализу бесконечно малых величин

Номер 2

Что является целью решения задачи коммивояжера?

Ответ:

(1) отладка решения

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

(3) нахождение максимума целевой функции

Номер 3

Решение задачи коммивояжера это:

Ответ:

(1) набор векторов

(2) несколько иррациональных чисел

(3) только нули и единицы

Упражнение 4:

Номер 1

При решении задачи коммивояжера приходится искать …

Ответ:

(1) минимум аналитической функции

(2) максимум длины кривой

(3) минимум суммы произведений

Номер 2

Метод ветвей и границ использует:

Ответ:

(1) треугольники

(2) графы

(3) параллелограммы

Номер 3

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

Ответ:

(1) он не содержит циклов

(2) содержит только один цикл

(3) соответствует самому быстрому циклу

Упражнение 5:

Номер 1

Укажите термин из теории решения задачи коммивояжера

Ответ:

(1) редуцированная матрица

(2) транспонированная матрица

(3) обратная матрица

Номер 2

Укажите термин из теории решения задачи коммивояжера

Ответ:

(1) ветвление

(2) дробление

(3) контраргументация

Номер 3

Процесс ветвления можно представить в виде дерева, в котором …

Ответ:

(1) каждая вершина – это один маршрут

(2) каждая вершина – это множество маршрутов

(3) есть циклы

Упражнение 6:

Номер 1

На каждом шаге ветвления выбирается множество …

Ответ:

(1) с наибольшей оценкой

(2) с наименьшей оценкой

(3) с оптимальной оценкой

Номер 2

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

Ответ:

(1) редукция матриц

(2) умножение матриц

(3) обращение матриц

Номер 3

Решение задачи коммивояжера …

Ответ:

(1) состоит из перебора всех вариантов

(2) перебора наиболее эффективных вариантов

(3) проводится методом ветвей и границ

Упражнение 7:

Номер 1

Дана матрица стоимостей перевода системы из состояния в состояние
1 2 3 4 5
1 10 8 25 10
2 1 10 15 20
3 8 9 20 7
4 14 5 24 15
5 10 8 25 6 
Найти самый дешевый способ провести систему по всем состояниям с возвращением в исходное состояние

Ответ:

(1) 1-3-5-4-2-1

(2) 1-4-3-5-2-1

(3) 1-2-5-3-4-1

Номер 2

Дана матрица стоимостей перевода системы из состояния в состояние
1 2 3 4 5
1 10 15 7 10
2 5 10 15 20
3 8 12 20 7
4 14 8 6 15
5 10 3 25 6 
Найти самый дешевый способ провести систему по всем состояниям с возвращением в исходное состояние

Ответ:

(1) 1-3-5-4-2-1

(2) 1-4-3-5-2-1

(3) 1-2-5-3-4-1

Номер 3

Дана матрица стоимостей перевода системы из состояния в состояние
1 2 3 4 5
1 5 13 8 9
2 12 9 13 7
3 7 11 5 8
4 4 9 8 14
5 11 7 6 7 
Найти самый дешевый способ провести систему по всем состояниям с возвращением в исходное состояние

Ответ:

(1) 1-3-5-4-2-1

(2) 1-4-3-5-2-1

(3) 1-2-5-3-4-1

Упражнение 8:

Номер 1

Дана матрица стоимостей перевода системы из состояния в состояние
1 2 3 4 5
1 10 8 25 10
2 1 10 15 20
3 8 9 20 7
4 14 5 24 15
5 10 8 25 6 
Найти стоимость самого дешевого способа проведения системы по всем состояниям с возвращением в исходное состояние

Ответ:

27

Номер 2

Дана матрица стоимостей перевода системы из состояния в состояние
1 2 3 4 5
1 10 15 7 10
2 5 10 15 20
3 8 12 20 7
4 14 8 6 15
5 10 3 25 6 
Найти стоимость самого дешевого способа проведения системы по всем состояниям с возвращением в исходное состояние

Ответ:

28

Номер 3

Дана матрица стоимостей перевода системы из состояния в состояние
1 2 3 4 5
1 5 13 8 9
2 12 9 13 7
3 7 11 5 8
4 4 9 8 14
5 11 7 6 7 
Найти стоимость самого дешевого способа проведения системы по всем состояниям с возвращением в исходное состояние

Ответ:

27

Теория игр и исследование операций - тест 12