Содержание
Введение...............................................................4
Глава 1. Основные определения и вспомогательные утверждения...........12
§ 1.1 Необходимые сведения из алгебры и геометрии. Перестановки, произведение независимых циклов. Гиперплоскости и линейные многообразия
в Яп. Выпуклость......................................................12
§ 1.2 Необходимые сведения из функционального анализа. Положительно определенная квадратичная форма, скалярное произведение, норма, метрика, связи между ними. Теорема Колмогорова. Расстояние в норме Ьг до линейных
многообразий..........................................................13
§ 1.3 Необходимые сведения из теории приближений. Приближение в нормированных пространствах. Теоремы единственности и существования. Метрический проектор и метрическая проекция...........................16
Глава 2. 11-свонство для симметричных и специальных симметричных норм..................................................................19
§ 2.1 Основные определения и примеры. Симметрическая, специальная симметрическая нормы, и-свойство и свойство униэкстремальности для
введенных классов норм. Зависимость свойств...........................19
§ 2.2 и-свойство для симметричных норм ..........................23
§ 2.3 и-свойство для специальных симметричных норм................32
Глава 3. Униэкстремальность для симметричных и специальных симметричных норм......................................................35
§ 3.1 Свойство униэкстремальности гиперплоскостей в пространстве Я", не являющихся подпространствами, относительно симметричных норм 35
§ 3.2 Униэкстремальность гиперплоскостей-подпространств...........45
§ 3.3 Свойство униэкстремальности гиперплоскостей в пространстве R", не являющихся подпространствами, относительно специальных симметричных норм........................................................................................................................................
§ 3.4 Униэкстремальность гиперплоскостей-подпространств относительно специальных симметричных норм............................... ...........57
Глава 4. Результаты для целочисленных задач. Применение полученных
результатов.............................. ^
§ 4.1 U-свойство и униэкстремальность для симметричных норм в
целочисленном случае.................................................... 52
§ 4.2 U-свойство и униэкстремальность для специальных симметричных
норм в целочисленном случае............................................. 58
§ 4.3 Алгоритм нахождения точки метрического проектора..............70
§ 4.4 Приложение к оптимизационным задачам .........................75
Глава 5. Результаты для случая функциональных пространств...............77
§ 5.1 Униэкстремальные гиперплоскости симметричных банаховых пространств........................... у у
§ 5.2 Униэкстремальность гиперплоскости \f(x)dx = const.............79
о
§ 5.3 Необходимое и достаточное условия униэкстремальности........90
Заключение.............................................................98
Список литературы.....................................................99
3
Введение
п
Известно [49], что гиперплоскость — 0 п-мерного пространства об-
1
ладает следующим свойством: для любого многогранника вида а* < Хі < Ьі (і = 1,2,..., п.) в этой гиперплоскости существует точка этого многогранника, в которой достигается минимум любой симметричной нормы.
Другими словами, метрический проектор нуля на указанную гиперплоскость в определенном смысле не зависит от метрики.
Назовем указанное свойство униэкстремальным. Дадим точное определение:
Непустое пересечение гиперплоскостей (и линейных многообразий) с различными параллелепипедами аі < Хі < Ьі (і = 1,2,..., п) называются многогранниками вида £>.
Свойство и выполнено для гиперплоскости (или многогранника егіда й), если точка этой гиперплоскости ('или многогранника вида В), в которой достигается минимум евклидовой нормы, является точкой минимума любой другой симметричной нормы.
Гиперплоскость пространства Я71 называется униэкстремалъпой, если па любом многограннике вида Г) этой гиперплоскости выполнено свойство и.
Рассмотренный подход допускает обобщение на функциональный случай:
Гиперплоскость обладает II-свойством, если ближайшая к нулю по норме пространства Д>[0,1] точка гиперплоскости является и одной из ближай-ших к нулю точек по норме любого другого симметричного функционального банахова пространства.
Гиперплоскость называется уииэкстрсмальпой, если данное свойство остается верным и для любых ее подмножеств вида:
0(/.' п/ > Іяир ) = {/(з) : /іп} < /(*) ^ їзирі
Уж Є [0,1]},
4
где fmtu fup некоторые существенно ограниченные на отрезке [0,1] функции.
В журнале ДАН [47] приведена теорема об униэкстремальности 1
гиперплоскости \f(s)ds = const.
о
Данные свойства были обнаружены при исследовании некоторых оптимизационных задач. Особую группу представляют целочисленные оптимизационные задачи.
В приложениях часто возникают задачи целочисленной оптимизации: округление экономического плана [35, 36], планирование железнодорожных перевозок [19], округление остатков на валютных счетах при конвертации валюты [38], целочисленное сбалансировании двумерной [19] и трехмерной [37, 39-42] матриц, равномерное назначение работ [22, 23, 48, 50, 51]. В этих задачах возникает вопрос о выборе критерия оптимизации, часто рассматривается несколько вариантов задач для различных критериев оптимизации. Иногда бывает известно, что для некоторых критериев проще получить решение, чем для других. В этих случаях требуется установить наиболее сильный критерий (в том смысле, что он влечет выполнение других критериев). Возникает вопрос о взаимосвязи критериев, выявлении наиболее сильного критерия, о частичном упорядочивании критериев. При ответе на некоторые из этих вопросов может быть использована указанная теорема.
Поэтому представляется актуальным исследовать класс гиперплоскостей в векторных и функциональных пространствах, обладающих свойством униэкстремальности, возможность расширения класса исследуемых гиперплоскостей за счет наложения ограничений на нормы, возможность упрощения решения некоторых оптимизационных задач за счет выбора более простого критерия.
Целью данной работы является исследование класса гиперплоскостей в симметричных конечномерных векторных пространствах и функциональных
5
банаховых пространствах, для которых выполнено свойство униэкстремалыюсти. Среди основных задач выделяются:
1) описание класса униэкстремальных гиперплоскостей в конечномерных векторных пространствах относительно симметричных и специальных симметричных норм;
2) описание класса униэкстремальных гиперплоскостей в функциональных банаховых пространствах с симметричной нормой;
3) описание вида экстремальных векторов и функций;
4) построение эффективного алгоритма поиска экстремальных векторов и функций;
5) исследование униэкстремальности гиперплоскостей и поиск экстремальных векторов для целочисленных задач в конечномерных векторных пространствах.
В диссертационной работе используются методы теории функций и функционального анализа, теории приближении, методы линейной алгебры и аналитической геометрии. Помимо этого, в работе используются отдельные методы высшей алгебры, дискретной математики, теории алгоритмов.
Как известно [11], задача наилучшего приближения включает в себя следующие пять проблем:
a) проблема существования элемента наилучшего приближения;
b) установление характеристических свойств этого элемента;
c) проблема единственности элемента наилучшего приближения; с!) вычисление (или оценка) наилучшего приближения;
е) построение алгоритма отыскания ближайшего элемента.
Все эти вопросы исследованы в данной работе применительно к некоторым задачам исследования, как в конечномерных нормированных пространствах, так и в функциональных пространствах.
В первой главе работы вводятся основные определения, необходимые в дальнейшем для исследования, приводится ряд определений и
6
вспомогательных утверждений из высшей алгебры, из аналитической геометрии и функционального анализа.
Во второй главе приводятся определение симметричного функционального банахова пространства и на его основе приводится два варианта определения симметричной нормы в конечномерных векторных пространствах. Симметричной нормой в конечномерном векторном пространстве называется норма, которая не изменяется при любой перестановке координат произвольного вектора, а специальной симметричной нормой называется норма, обладающая свойством: Н(М,|х2|,...|хп|)||=||( Х^,, х^2,... х^п )|| для любой перестановки 5- Далее вводятся определения свойств и, II5, униэкстремальности в смыслах симметричной и специальной симметричной норм, приводятся примеры, устанавливается взаимосвязь введенных понятий. Выясняется, для каких классов гиперплоскостей в пространстве Кп выполнено И-свойство и для каких классов гиперплоскостей выполнено и5-свойство, т.е. метрический проектор нуля в метрике Ь2 (ровно одна точка) принадлежит метрическим проекторам нуля в любых симметричных (специальных симметричных) нормах.
В работе делается замечание, что свойство униэкстремальности гиперплоскости сильнее, чем и-свойство. Кроме того, класс специальных симметрических норм в конечномерных векторных пространствах уже, чем класс симметричных норм, поэтому гиперплоскостей, обладающих и-свойством или свойством униэкстремальности относительно класса специальных симметричных норм больше, чем гиперплоскостей, обладающих данными свойствами относительно симметричных норм.
Во втором параграфе отмечается, что любая гиперплоскость, проходящая через начало координат, обладает П-свойством (^-свойством), поскольку минимум вообще любой нормы достигается в нуле. Поэтому во
п
второй главе исследуются гиперплоскости вида ^а,х, =сот1 * 0 (все
1-1
7
коэффициенты уравнения гиперплоскости не могут быть равны нулю одновременно).
Следующие теоремы 1 и 2, полностью описывают класс гиперплоскостей в конечномерном векторном пространстве, обладающих U (Ц^-своЙством.
Теорема 1. Гиперплоскость п-мерного пространства, обладает свойством тогда и только тогда, когда она задаётся уравнением одного и3 следующих видов:
(1) £а,х,=0 1*1
я
(2) = const * О;
(3) £а,х, = const * 0 (а,£{-1,0,1}, i=l,2,...,n и =0, т е. количество
|'| 1-1
коэффициентов, равных единице, совпадает с количеством коэффициентов,
равных минус единице).
Теорема 2. Гиперплоскость п-мерного пространства, обладает lf~ свойством тогда и только тогда, когда она задаётся уравнением одного из следующих видов:
(О X«,*, =0 1*1
п
(2) Yja'x>-const а,е{-1,0,1), i-l,2,...,n.
4-1
у*
Как легко видеть, класс гиперплоскостей, обладающих (/-свойством* оказался действительно шире класса гиперплоскостей, обладающих U-свойством, поскольку специальных симметричных норм в пространстве К меньше, чем просто симметричных.
8
- Київ+380960830922