Введение к работе
Актуальность работы
Известно1, что гиперплоскость ^ Хі = 0 пространства Rn обладает
г=0
следующим свойством: для любого многогранника вида щ < Хі < &j(i = 1,2,... ,п) в этой гиперплоскости существует точка этого многогранника, в которой достигается минимум любой симметричной нормы.
Другими словами, метрический проектор нуля на указанную гиперплоскость в определенном смысле не зависит от метрики. Назовем указанное свойство униэкстремальным. Дадим точное определение:
Непустое пересечение гиперплоскостей (и линейных многообразий) с различными параллелепипедами а,{ < Х{ < bi(i = 1,2,..., п) называются многогранниками вида D.
Свойство U выполнено для множества, если точка этого множества, в которой достигается минимум евклидовой нормы, является точкой минимума любой другой симметричной нормы.
Гиперплоскость пространства Rn называется униэкстремальной, если на любом многограннике вида D этой гиперплоскости выполнено свойство U.
Рассмотренный подход допускает обобщение на функциональный случай:
Гиперплоскость обладает U-свойством, если ближайшая к нулю по норме пространства L2[0,1] точка гиперплоскости является и одной из ближайших к нулю точек по норме любого другого симметричного функционального банахова пространства.
Гиперплоскость называется униэкстремальной, если данное свойство остается верным и для любых ее подмножеств вида:
D(finfjsup) = {f(x) : finf(x) < f(x) < fsup{x) Ух Є [0,1]},
где finf(x) и fsup(x) некоторые существенно ограниченные на отрезке [0,1]
функции.
В журнале ДАН2 приведена теорема об униэкстремальности гипер-1
плоскости J f(s)ds = const. о
Рублев В. С, Чаплыгина Н. Б. Выбор критерия оптимизации в задаче о равномерном назначении // Дискретная математика, 2005, т. 17, вып 4, с. 150-157
2Рублев B.C., Чаплыгина Н.Б. О некоторой характерной точке одного класса многогранников в симметрических пространствах // ДАН, 2006, т. 407, № 2, 176-178.
Данные свойства были обнаружены при исследовании некоторых оптимизационных задач. Особую группу представляют целочисленные оптимизационные задачи.
В приложениях часто возникают задачи целочисленной оптимизации: округление экономического плана3, планирование железнодорожных перевозок4, округление остатков на валютных счетах при конвертации валюты5, целочисленное сбалансировании двумерной и трехмерной6 матриц, равномерное назначение работ7.
В этих задачах возникает вопрос о выборе критерия оптимизации, часто рассматривается несколько вариантов задач для различных критериев оптимизации. Иногда бывает известно, что для некоторых критериев проще получить решение, чем для других. В этих случаях требуется установить наиболее сильный критерий (в том смысле, что он влечет выполнение других критериев). Возникает вопрос о взаимосвязи критериев, выявлении наиболее сильного критерия, о частичном упорядочивании критериев. При ответе на некоторые из этих вопросов может быть использована приведенная теорема. Поэтому представляется актуальным исследовать класс гиперплоскостей в векторных и функциональных пространствах, обладающих свойством уни-экстремальности.
Цель и задачи работы
Целью данной работы является исследование класса гиперплоскостей в симметричных конечномерных векторных пространствах и функциональных банаховых пространствах, для которых выполнено свойство униэкстремаль-ности. Среди основных задач выделяются:
1) описание класса униэкстремальных гиперплоскостей в конечномерных векторных пространствах относительно симметричных и специальных
3Рублев B.C. Минимизация ошибок округления плана. // Математика, кибернетика, информатика. Труды международной конференции, посвященной памяти профессора А.Ю. Левина, Ярославль: ЯрГУ, 2008, С. 145-150.
Рублев B.C., Макаров А.В. Задачи оптимального округления. // Дискретные модели в теории управляющих систем: VIII Международная конференция, Москва, 6-9 апреля 2009г.: Труды. - М.: Издательский отдел факультета ВМиК МГУ им. М.В. Ломоносова; МАКС Пресс, 2009, С. 185-187.
4Коршунова Н.М., Рублев B.C. Задача целочисленного сбалансирования матрицы // Современные проблемы математики и информатики, вып. 3. Ярославль: ЯрГУ им. П.Г. Демидова, 2000. с. 145 - 150.
5Рублев B.C., Смирнов А.В. Задача оптимального округления плана валютных счетов // Кибернетика и высокие технологии XXI века. - Воронеж: НПФ "Саквоее 2008. - Т. 1. - С. 112-123.
6Рублев B.C., Смирнов А.В. Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения // Моделирование и анализ информационных систем. - 2010. - Т. 17, № 2. - С. 72-98.
7Рублев B.C. Задача о равномерном распределении работ. // Ярославский госуниверситет. Ярославль, 1986. - Деп. ВИНИТИ №611-В87 26.01.87
симметричных норм;
описание класса униэкстремальных гиперплоскостей в функциональных банаховых пространствах с симметричной нормой;
описание вида экстремальных векторов и функций;
построение эффективного алгоритма поиска экстремальных векторов и функций;
исследование униэкстремальности гиперплоскостей и поиск экстремальных векторов для целочисленных задач в конечномерных векторных пространствах.
Методы исследования
В диссертационной работе используются методы теории функций и функционального анализа, теории приближений, методы линейной алгебры и аналитической геометрии. Помимо этого, в работе используются отдельные методы высшей алгебры, дискретной математики, теории алгоритмов.
Научная новизна
Все основные результаты работы являются новыми:
полностью описаны классы гиперплоскостей в конечномерном векторном пространстве, обладающие ^/-свойством и свойством униэкстремальности относительно симметричных и специальных симметричных норм;
определен вид экстремальных векторов и найден эффективный алгоритм их нахождения в конечномерных векторных пространствах с трудоемкостью 0(п2), где п - размерность пространства;
описан класс униэкстремальных гиперплоскостей в функциональных банаховых пространствах с симметричной нормой;
определен вид экстремальных функций и найден эффективный алгоритм их нахождения в функциональных банаховых пространствах с симметричными нормами, количество шагов которого О {lo2 Q)) , где є - требуемая точность;
в конечномерных векторных пространствах решены аналоги задач для целочисленного случая.
Теоретическая и практическая значимость работы
Результаты данной работы можно применять при решении оптимизационных задач. Например, задач дискретной математики - задачи о равномерном назначении работ, задачи о целочисленном сбалансировании двумерной
и трехмерной матриц. Описаны случаи, когда можно выбирать в качестве критерия оптимизации наиболее удобный критерий - евклидову норму. Кроме того, при поиске оптимальных решений в некоторых задачах можно использовать эффективные алгоритмы их нахождения, описанные в работе.
Апробация работы
Основные результаты работы докладывались и обсуждались на международной конференции, посвященной 70-летию ректора МГУ академика В.А.Садовничего «Современные проблемы математики, механики и их приложений»; 62 региональной научно-технической конференции студентов, магистрантов и аспирантов высших учебных заведений с международным участием «Молодежь, наука, инновации 2009»; международной научно-технической конференции «Чтения Ушинского» - 2010; всероссийской научной конференции «Современные проблемы теории функций и их приложения» -2010; XV всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании» - 2010; II всероссийской молодежной научно-практической конференции «Научно-практические исследования современной молодежи» - 2010; семинарах Ярославского государственного университета под руководством профессора Соколова В.А. - 2010.
Публикации
Гезультаты диссертации опубликованы в работах [1]-[11]. Габоты [4], [5], [6], [11] опубликованы в рецензируемых журналах, входящих в перечень ВАК ГФ. Из совместных публикаций [1], [10] в диссертацию вошли результаты, принадлежащие лично автору.
Структура и объем диссертации
Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы, содержащего 77 наименований. Диссертация содержит 8 рисунков. Объем диссертации составляет 107 страниц.
