NEW
Font size
WorksheetsТеория алгоритмов
Total questions: 20
Worksheet time: 10mins
Пусть m – количество поставщиков, n – количество потребителей. Тогда количество занятых клеток в базисном плане транспортной таблицы =
m+n-1
mn
(m-1)(n-1)
m+n
В задаче линейного программирования значения свободных переменных
>0
=0
не определены
<0
В ориентированном графе замкнутая цепочка дуг называется
циклом
путем
контуром
маршрутом
При построении наивыгоднейшего пути методом динамического программирования на очередном шаге рассматриваются
множество управлений
одно управление
один или два управления
два управления
Логическая структура диска может быть представлена в виде
сети
дерева
маршрута
цикла
Два различных пути в одном графе
не могут пересекаться
не имеют общих дуг
могут иметь общие дуги
всегда проходят через разные вершины
Величина максимального потока равна
величине минимального разреза
величине максимального разреза
максимальной длине пути
весу дуги
В задаче о рюкзаке (вместимостью R) на первом шаге рассматривается
два управления
одно управление
R управлений
R+1 управление
При решении транспортной задачи методом потенциалов оптимальным будет план, в котором перевозки осуществляются по направлениям, где разность потенциалов
равна цене цикла
больше цены перевозки груза
равна цене перевозки груза
меньше цены перевозки груза
В динамическом программировании оценка состояний системы начинается
с любого шага
с последнего шага
с первого шага
с указанного шага
Метод Жордана-Гаусса позволяет найти
базисное решение задачи динамического программирования
оптимальное решение задачи динамического программирования
оптимальное решение транспортной задачи
базисное решение транспортной задачи
Цена цикла в транспортной таблице показывает
сколько груза надо перевозить
увеличение цены перевозок
на сколько изменится цена перевозки груза при переброске по циклу
на сколько изменится стоимость перевозки всего груза
Вектор нормали показывает направление
убывания перемещения
убывания целевой функции
возрастания целевой функции
возрастания перемещения
Алгоритм Дейкстры позволяет найти кратчайший путь
от начальной до конечной точки сети
от начальной до любой другой точки сети
между двумя выбранными вершинами
между любыми вершинами сети
Остов содержит все
вершины графа
дуги графа
ребра графа
циклы графа
Величина переброски по циклу определяется, как
максимум перевозок в отрицательных вершинах цикла
минимум перевозок в положительных вершинах цикла
минимум цен в отрицательных вершинах цикла
минимум перевозок в отрицательных вершинах цикла
В ориентированном графе связь между двумя вершинами называется
ребром
дугой
путем
маршрутом
В линейном программировании количество базисных переменных
равно числу независимых уравнений
равно числу зависимых уравнений
равно числу свободных переменных
не известно
В задачах линейного программирования решение, если оно существует, достигается
только на сторонах области допустимых решений
на границе области допустимых решений
внутри области допустимых решений
только в вершинах области допустимых решений
Метод динамического программирования служит для поиска
оптимального решения многоэтапных задач
оптимального решения транспортной задачи
базисного решения многоэтапных задач
базисного решения транспортной задачи
