Cтраница 2
Каким условиям должна удовлетворять матрица А, чтобы при любом целочисленном векторе правых частей b ( bi, 62, , bm) T многогранное множество L ( b) (1.4.1), (1.4.2) было целочисленным. Ответ на этот вопрос дает следующая теорема. [16]
Следовательно, по правилу Крамера получаем, что хв - целочисленный вектор. [17]
Действительно, пусть В - базис, а у - произвольный целочисленный вектор, такой, что у B - ej 0, где е, есть i - й единичный вектор-столбец. Тогда Bz By - f e; - целочисленный вектор, так как В, у, е, целочисленны. По условию 2 z является целочисленным вектором. Вектор В-1 е; является i - м вектор-столбцом в В 1, значит, i - й столбец матрицы В 1 целочислен. Следовательно, матрица В 1 целочислепна. [18]
Решение задачи ( 7) и структура выпуклой оболочки всех целочисленных векторов t, являющихся решением системы ( 6), интересуют нас по трем причинам. Во-первых, задача ( 7), имеющая в качестве ограничения только одно сравнение, может быть решена методом, аналогичным методу решения задачи о рюкзаке. Поэтому решение задачи ( 7) можно рассматривать как решение целочисленной задачи, у которой значения Ь в правой части достаточно велики. Иными словами, любое отсечение Гомори, введенное без использования условия ХБ 0, будет линейной выпуклой комбинацией граней выпуклой оболочки. [19]
Целочисленным базисом подпространства называется базис этого подпространства, состоящий из целочисленных векторов. Каждое из следующих двух условий является необходимым и достаточным для равномерности линейного подпространства L: 1) L имеет целочисленный базис; 2) L может быть задано системой линейных уравнений с целыми коэффициентами. [20]
В простой решетке нумерация узлов совпадает с нумерацией атомов, поэтому целочисленный вектор п является одновременно номером или номер-вектором соответствующего атома. Однако координата узла решетки (1.1) отличается от координаты соответствующего атома, когда атомы смещены относительно своих положений равновесия. Если положения равновесия атомов совпадают с узлами решетки (1.1), то для определения координат атома помимо его номера следует указать также его смещение относительно своего узла. [21]
Покажите, что, если А - вырожденная матрица, такого ненулевого целочисленного вектора, на котором достигается наибольшая нижняя граница ( 18), может не существовать. [22]
Докажите, что наибольшая нижняя граница величины ( 18), взятая по всем ненулевым целочисленным векторам х, достигается при некотором х, если А - невырожденная матрица. [23]
Например, если расширенная матрица А, Ь а-модулярная, то B - lb - целочисленный вектор и, следовательно, М ( А, Ь) - целочисленный полиэдр. [24]
Достаточным условием того, что крайние точки X ( А, Ъ) будут целочисленными при любом целочисленном векторе Ь, является унимодулярность базиса. Пользуясь правилом Крамера, можно решить систему относительно всех xi, и, так как определитель матрицы коэффициентов, стоящий в знаменателе, равен 1, а Ь имеет целочисленные компоненты, xt должны быть целочисленными. Докажем теперь, что унимодулярность является и необходимым условием. [25]
При любом ( ЭЯ ( 0) / Эр) т, вообще говоря, можно указать целочисленный вектор k такой, что в ( 31) выражение ( ЭЯ ( 0) / Эр) т) очень близко к нулю. [26]
Заметим, что среди функций на торе имеются гармоники - функции вида e ( kz где k - целочисленный вектор. Для гармоник теорема проверяется непосредственным вычислением интеграла. [27]
В тех случаях, когда результат выборочной проверки выражается упоминавшимся вектором группировки, решающая функция определена на множестве допустимых целочисленных векторов, размерность которых равна числу групп ( подробней см. в гл. [28]
Если каждая компонента вектора у ограничена сверху целым числом М, то существует ( М 1) таких неотрицательных целочисленных векторов у. Мы должны проверить каждый из них на допустимость и выбрать допустимое решение с минимальным значением целевой функции в качестве оптимального решения. Поскольку число ( М 1) обычно очень велико, в алгоритмах типа дерева поиска делается попытка исключить проверку вариантов, которые доминируются проверенными ранее решениями. [29]
Применяя лемму 7.1.1, легко устанавливаем, что вершины полиэдра j / GlR yQ A у w являются целочисленными векторами. Но отсюда не следует, что они суть 0 - 1-векторы. [30]