Первым шагом решения задачи целочисленного программирования является:
Алгоритм для решения полностью целочисленных задач был предложен:
Метод ветвей и границ предполагает деление исходной задачи:
Метод ветвей и границ требует наличия:
Границы в методе ветвей и границ это:
При решении задачи коммивояжера методом ветвей и границ, верно, что:
В процессе решения задачи целочисленного программирования методом ветвей и границ по какой переменной осуществляется деление исходной задачи? (Найдите наиболее точный ответ):
Для задач целочисленного программирования (ЗЦЛП) с каким количестом переменных применяется метод ветвей и границ?
Метод ветвей и границ требует:
Редуцированной матрицей является:
Редуцированной НЕ является матрица:
Решение задачи коммивояжера методом ветвей и границ: при редуцировании исходной матрицы получена следующая матрица:
Редуцированная матрица для вершины, соответствующей подмножеству, включающему переезд (2, 3) имеет вид:
В результате ветвления исходной задачи получены следующие решения:
и
.
Какое из утверждений НЕВЕРНО?
В результате ветвления исходной задачи получены следующие решения:
и
Какое из утверждений верно?
В результате ветвления исходной задачи получены следующие решения:
и
.
Выберите наиболее подходящее утверждение:
Найти верхнюю F(x) и нижнюю границы d(x) стоимости маршрута для задачи:
Найти длину оптимального маршрута F(x*) для задачи:
Записать оптимальный маршрут для задачи коммивояжера:
. Задача с ослабленными ограничениями возникает:
Название «методы отсечений» связано с тем обстоятельством, что:
Задача коммивояжера заключается в отыскании значений переменных xij удовлетворяющих следующим соотношениям:
при условиях :
Для получения целочисленного решения задачи:
необходимо разбить исходную задачу на 2 с границами:
Необходимо разместить 4 датчика у 4 объектов таким образом, чтобы стоимость была минимальна. Матрица стоимости назначений имеет вид:
Минимальная стоимость назначений равна:
Транспортная задача является типичным примером задачи:
Объем перераспределяемого груза при построении нового опорного плана определяется из условия:
Существует план X = (xij)m x n транспортной задачи и числа (потенциалы) u1, u2, … um и v1, v2, … vn, такие, что ui + vj cij для xij = 0 и ui + vj = cij для xij > 0. Для оптимальности плана X = (xij) m x n это означает
Клетка текущего плана транспортной задачи, которая первая подлежит включению в число базисных клеток при использовании метода потенциалов, удовлетворяет условию:
Какое минимальное число клеток опорного плана транспортной задачи может участвовать в построении цикла?
Количество занятых клеток в опорном плане транспортной задачи должно быть (где m– число строк матрицы затрат, n- число столбцов):
Для применения метода потенциалов транспортная задача приводится:
Потенциалы Ui и Vj из решения транспортной задачи являются:
В случае запрещения перевозки от А2 в В3 в соответствующую клетку записывается:
Какой из перечисленных методов не относится к методам определения начального (исходного) решения (опорного плана) в транспортной задаче:
Какое из сочетаний квазипотенциалов показывает, что введение указанной ими небазисной (свободной) клетки в базис будет самым оптимальным?
Для данной транспортной задачи
Суммарные транспортные расходы (являются ли они минимальными?), соответствующие данной матрице транспортной задачи, составляют:
Данный план перевозок транспортной задачи является:
Для данного плана перевозок постройте систему потенциалов, если один из потенциалов задан. В ответе запишите потенциалы в следующем порядке: V1; V2; V3; V4; U2; U3
Для данного плана перевозок постройте систему потенциалов, если один из потенциалов задан. В ответе запишите потенциалы в следующем порядке: V1; V2; V3; V4; U1; U3
Для данного плана перевозок постройте систему потенциалов, если один из потенциалов задан. В ответе запишите потенциалы в следующем порядке: V1; V2; V3; V4; U1; U2
Суммарная стоимость оптимальной перевозки в транспортной задаче:
составляет:
Стоимость оптимальной перевозки в транспортной задаче:
составляет:
Найти величину
(количество перераспределяемого груза) для оптимизации плана транспортной задачи:
Найти величину (количество перераспределяемого груза) для оптимизации плана транспортной задачи:
Дана матрица транспортной задачи. Найти цикл для клетки (2,2).
Дана матрица транспортной задачи. Найти цикл для клетки (4,1).
Дана матрица транспортной задачи. Найти цикл для клетки (4,4).
Методы, основанные на вычислении функции и её производной относятся к методам:
Алгоритм Свенна является алгоритмом:
Градиентные методы являются методами:
На вычислении только значений функции для решения задач безусловной оптимизации основываются методы:
При графическом изображении решения по методу спуска Коши вблизи оптимальной точки, когда шаги по направлению становятся маленькими, наблюдается:
Градиентные методы, использующие одномерную оптимизацию, носят название «метод…»:
Элементы последовательности точек, монотонно увеличивающих значение целевой функции в нелинейном программировании, рассчитываются по формуле:
В задачах условной оптимизации (длина шага в направлении вектора Sk) определяется путем решения задачи одномерной оптимизации:
Начальный этап алгоритма метода Зойтендейка подразумевает:
Обычно в процессе применения методов одномерной оптимизации можно выделить два этапа:
Функция называется унимодальной если она:
Функция называется унимодальной на множестве Р, если существует единственная точка x* ее максимума на Р и для любых выполняются условия:
Метод, который использует деление отрезка на 2 неравные части так, чтобы отношение всего отрезка к длине большей части равнялось отношению длины большей части к меньшей части отрезка, называется:
откуда
.
Перечисленные формулы относятся к методу:
Исходная задача:
Целевая функция в двойственной задаче представляет собой:
Исходная задача:
Переменные в двойственной задаче представляют собой:
Значения целевой функции, полученные в результате решения прямой и двойственной задач:
Переменные двойственной задачи представляют собой:
Принцип двойственности в линейном программировании заключается в том, что:
Двойственная задача симплекс-метода – это
Число переменных двойственной задачи
Число ограничений двойственной задачи
Транспонированием матрицы ограничений прямой задачи можно добиться
Вектор коэффициентов целевой функции двойственной задачи – это
Если целевая функция прямой задачи в стандартной форме минимизируется, то для составления задачи, двойственной к данной
Задача, двойственная к двойственной
Одно из свойств прямой и двойственной задач (заданы в стандартной форме) гласит:
Взаимно двойственные задачи (симметричные взаимно двойственные задачи) – это
Двойственная задача – это
Получение оптимального решения двойственной задачи из симплекс-таблицы решения прямой (исходной) задачи:
Содержательная интерпретация экономического смысла двойственной задачи состоит в следующем.
Цены ресурсов (переменные двойственной задачи) в экономической литературе получили названия
Цены (оценки) в двойственной задаче
Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их целевых функций равны. Если целевая функция одной из задач не ограничена, то условия другой задачи противоречивы. Это
Экономический смысл первой (основной) теоремы двойственности состоит в следующем.
Если условия исходной задачи противоречивы, то
Дополнительные (неосновные) переменные двойственной задачи – это
Ненулевые параметры управления оптимального решения двойственной задачи (задачи заданы в стандартной форме)
Проблемой объективно обусловленных оценок исходной задачи и введением этого термина в теорию двойственности занимался ученый:
Объективно обусловленные оценки ресурсов
В соответствии со второй теоремой двойственности в оптимальный план могут попасть
Критерий рентабельности в теории двойственности выражается в следующем:
В соответствии с третьей теоремой двойственности компоненты оптимального решения двойственной задачи равны
Объективно обусловленные оценки ресурсов показывают
Задачей, двойственной к ЗЛП , называется следующая:
Если в исходной задаче в оптимальном плане основная переменная х2* =6, то о соответствующей ей дополнительной переменной y5* двойственной задачи можно сказать, что (найдите наиболее точный ответ)
Если в исходной задаче в оптимальном плане основная переменная х1* =0, то о соответствующей ей дополнительной переменной y4* двойственной задачи можно сказать, что (найдите наиболее точный ответ)
Какой из предложенных наборов параметров управления может служить решением задачи?
Расчетные нормы заменяемости ресурсов могут быть определены
Если в одной из взаимно двойственных задач нарушается единственность оптимального решения, то