Cтраница 3
В приложениях А, В, С рассматривается процесс приведения целочисленной матрицы к нормальной форме Смита ( лежащий в основе решения систем линейных уравнений в пространстве целочисленных векторов), приводится один из вариантов доказательства теорем двойственности линейного программирования, и, наконец, кратко обсуждается схема типа упорядоченного перебора для решения целочисленных задач. [31]
Результат, полученный Гофманом и Краскалом, означает, что выпуклый многогранник, определяемый ограничениями Ах Ь, х О, имеет целочисленные крайние точки при любом целочисленном векторе Ь, если матрица А абсолютно унимодулярна. Ясно, что условие абсолютной унимодулярности матрицы А достаточно для существования целочисленного оптимального решения. Труднее показать, что это условие является и необходимым. [32]
Теперь Bz By - - t Ъ - целочисленный вектор и z содержит ненулевые компоненты крайней точки множества X ( А, Ь); следовательно, z - целочисленный вектор. [33]
Задача 0 - 1 целочисленного программирования состоит в том, чтобы определить, существует ли вектор-столбец из нулей и единиц, такой, что Сх а для целочисленной матрицы С и целочисленного вектора А. Докажите, что эта задача - полная. [34]
Излагаемые здесь методы позволяют, в принципе, решить произвольную полностью целочисленную задачу ЛЦП, в которой определяемое условиями (10.4) и (10.5) множество M Rn содержит, по крайней мере, один целочисленный вектор, а линейная функция (10.3) на этом множестве ограничена сверху. В других же случаях решение находится за сравнительно небольшое время для, казалось бы, более сложных задач, содержащих десятки ограничений и сотни переменных. В этой связи невольно вспоминается ответ знаменитого скульптора на вопрос о том, как он производит свои замечательные монументы. Технология оказывается очень простой: берется каменная глыба, и от нее отсекается все лишнее. [35]
Если всю плоскость перенести параллельно на вектор аЪ, то каждая из ( п - -) точек ai перейдет в точку bv где Ь - аа, значит, bbi aai есть целочисленный вектор, а так как b есть узел решетки, то и все точки bi суть ее узлы. Итак, после параллельного сдвига на вектор длины меньше 1, фигура Q покрыла ( п - - 1) узлов решетки. [36]
При интегрировании периодических или условно-периодических функций, представленных кратными рядами Фурье, изменение амплитуд отдельных гармоник зависит от двух факторов: от малости величины а, характеризующей резонанс частот, и от нормы целочисленного вектора k, присутствующего в резонансных соотношениях. Поясним это на примере. [37]
Здесь Uj ( n) - векторы смещения атомов в решетке; а, р, v - векторные индексы, пробегающие значения х, у, z slt s2, s3 - номера атомов в элементарной ячейке; nt, na, n3 - целочисленные векторы, определяющие положение ячейки в решетке; символ ( ns) под знаком суммы означает, что суммирование производится по всем п и по всем s; ввиду однородности кристалла функции Л зависят только от взаимных расстояний пх - п3, п2 - п8 между ячейками, но не от их абсолютных положений в решетке. [38]
Здесь Us ( n) - векторы смещения атомов в решетке; а, / 3, 7 - - векторные индексы, пробегающие значения х у, z s, sz, s % - номера атомов в элементарной ячейке; HI, П2, пз - целочисленные векторы, определяющие положение ячейки в решетке; символ ( ns) под знаком суммы означает, что суммирование производится по всем п и по всем s; ввиду однородности кристалла функции Л зависят только от взаимных расстояний HI - 113, П2 - пз между ячейками, но не от их абсолютных положений в решетке. [39]
Выполним каноническое преобразование х, у - х у по формулам у ( ВТ) - 1у, х Вх, где В - целочисленная унимодулярная матрица. Целочисленные векторы m преобразуются так же, как и импульсы у, поэтому выполнение условия интегрируемости (5.3) можно проверять в исходных переменных. [40]
Действительно, пусть В - базис, а у - произвольный целочисленный вектор, такой, что у B - ej 0, где е, есть i - й единичный вектор-столбец. Тогда Bz By - f e; - целочисленный вектор, так как В, у, е, целочисленны. По условию 2 z является целочисленным вектором. Вектор В-1 е; является i - м вектор-столбцом в В 1, значит, i - й столбец матрицы В 1 целочислен. Следовательно, матрица В 1 целочислепна. [41]
Поэтому по правилу Крамера получаем, что KB - целочисленный вектор. Но поскольку остальные компоненты вектора к равны нулю, х - целочисленная вершина. [42]
Действительно, пусть х - произвольная крайняя точка выпуклого многогранника С, а В - соответствующий ей базис. Тогда по правилу Крамера следует, что хв - целочисленный вектор. Значит, крайняя точка х [ хв, х ] целочисленна. [43]
В новой постановке Л. Г. Хачиян решил поставленный вопрос и, что самое удивительное, положительно. Заметим, что решение такой задачи не обязано быть целочисленным вектором. Поэтому на первый взгляд кажется, что такая задача не укладывается в круг: понятий дискретной математики. Это, однако, не так: среди решений рассматриваемой задачи ( если они вообще имеются) есть л решение с рациональными координатами и его можно закодировать, кодируя наборы из числителей и знаменателей соответствующих дробей. [44]
Поскольку В - базис матрицы А, то система (2.2) совместна. Так как левая часть равенства гв - у - B-lei - целочисленный вектор, то и вектор B - I, являющийся t - м столбцом матрицы В 1, целочисленный. [45]