Верно или неверно 1. Любая полностью или частично целочисленная задача может быть записана в булевых переменных.
2. Нельзя получить допустимое целочисленное решение путем округления решения задачи с ослабленными
ограничениями в виде равенств.
3. Последовательно вводимые отсечения исключают области (не содержащие точек с целыми координатами)
многогранника допустимых решений задачи с ослабленными ограничениями до тех пор, пока некоторое вновь
полученное оптимальное решение не окажется целочисленным.
4. Значение целевой функции в оптимальном решении целочисленной задачи максимизации (минимизации)
может быть больше (меньше) оптимального значения целевой функции соответствующей задачи с ослабленными
ограничениями.
5. При построении отсечения Гомори для полностью целочисленной задачи нет необходимости накладывать
на дополнительную переменную условие целочисленности.
6. В процессе реализации метода отсечений следует сохранять в симплекс-таблице все строки и столбцы,
соответствующие введенным отсечениям, до получения оптимального решения.
7. Отсечение может исключить некоторое допустимое целочисленное решение, заведомо не являющееся
оптимальным.
8. Если в процессе реализации первого алгоритма Гомори двойственный симплекс-метод укажет на отсутствие
допустимых решений, то задача не имеет допустимых целочисленных решений.
9. Полностью целочисленную задачу можно решить путем введения отсечений Гомори для частично
целочисленной задачи.
10. При реализации метода ветвей и границ нижняя граница для значений целевой функции задачи
максимизации устанавливается в соответствии с допустимым целочисленным решением, полученным на
предыдущем шаге.
11. Ветвление, осуществляемое в процессе реализации метода ветвей и границ, исключает некоторые области
многогранника допустимых решений, не содержащие точек с целыми координатами.
12. Процесс ветвления, реализуемый в рамках метода ветвей и границ, основывается на той же идее, которая
используется при построении отсечения Гомори для частично целочисленных задач.
13. Количество подзадач, порожденных в процессе реализации метода ветвей и границ, можно существенно
уменьшить, если уже на первых этапах вычислений найти значение границы, достаточно близкое к оптимальному
значению целевой функции.
14. Граница, полученная в процессе реализации метода ветвей и гра-ниц, не всегда соответствует
допустимому решению целочисленной задачи.
15. Разработанные для метода ветвей и границ правила выбора переменной, инициирующей процесс
ветвления в некоторой вершине, обеспечивают относительно быстрое выявление границы, значение которой
оказывается достаточно близким к оптимальному значению целевой функции.
16. Основной недостаток метода ветвей и границ заключается в том, что количество порожденных подзадач в
ряде случаев оказывается очень большим.
17. Переменная, инициирующая процесс ветвления в некоторой вершине, не может инициировать процесс
ветвления в последующих вершинах, порожденных исходной вершиной.
18. Процедура частичного перебора решений задачи с булевыми переменными является частным случаем
более общего метода ветвей и границ.
19. Процедура частичного перебора предполагает непосредственное или неявное исследование всех
n
2
значений
n
булевых переменных задачи.
20. В результате применения метода ветвей и границ к задаче с
n
булевыми переменными нельзя построить
более чем
n
последовательно соединенных между собой ветвей, первая из которых исходит из данной вершины.