Об одном классе гиперплоскостей симметричных банаховых пространств тема автореферата и диссертации по математике, 01.01.01 ВАК РФ
|
Федотова, Наталья Петровна
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Ярославль
МЕСТО ЗАЩИТЫ
|
||||
|
2011
ГОД ЗАЩИТЫ
|
|
01.01.01
КОД ВАК РФ
|
||
|
|
||||
Федотова Наталья Петровна
Об одном классе гиперплоскостей симметричных банаховых пространств
Специальность 01.01.01 - вещественный, комплексный и функциональный анализ
АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук
1 2 МАЙ 2011
Воронеж - 2011
4845233
Работа выполнена на кафедре теоретической информатики Ярославского государственного университета им. П.Г. Демидова
Научный руководитель:
кандидат физико-математических наук, профессор Рублев Вадим Сергеевич
Официальные оппоненты:
доктор физико-математических наук, доцент Гельман Борис Данилович
доктор физико-математических наук, профессор Родин Владимир Александрович
Недушаи организация:
Самарский государственный университет
Защита состоится 24 мая 2011 года в 15 часов 10 минут на заседании диссертационного совета Д 212.038.22 при Воронежском государственном университете по адресу: 394006, г.Воронеж, Университетская пл., 1, ауд. 335.
С диссертацией можно ознакомиться в научной библиотеке Воронежского государственного университета.
Автореферат разослан 14 апреля 2011 г.
Ученый секретарь
диссертационного совета Д 212.038.22 доктор физико-математических наук, профессор #
Смагин В.В.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы
п
Известно1, что гиперплоскость = О пространства Rn обладает
¿=о
следующим свойством: для любого многогранника вида а,- < ж,- < b,(i — 1,2,..., п) в этой гиперплоскости существует точка этого многогранника, в которой достигается минимум любой симметричной нормы.
Другими словами, метрический проектор нуля на указанную гиперплоскость в определенном смысле не зависит от метрики. Назовем указанное свойство униэкстремальным. Дадим точное определение:
Непустое пересечение гиперплоскостей (и линейных многообразий) с различными параллелепипедами (ii < Xj < bt(i = 1,2, ...,п) называются многогранниками вида D.
Свойство U выполнено для множества, если точка этого множества, в которой достигается минимум евклидовой нормы, является точкой минимума любой другой симметричной нормы.
Гиперплоскость пространства Rn называется униэкстремальной, если на любом многограннике вида D этой гиперплоскости выполнено свойство U.
Рассмотренный подход допускает обобщение на функциональный случай:
Гиперплоскость обладает U-свойством, если ближайшая к нулю по норме пространства £г[0) 1] точка гиперплоскости является и одной из ближайших к нулю точек по норме любого другого симметричного функционального банахова пространства.
Гиперплоскость называется униэкстремальной, если данное свойство остается верным и для любых ее подмножеств вида:
D(finf,fsuP) = {f(x) : finf(x) < f(x) < fsnp{x) Ух e [0,1]},
где finf(x) и fSUp{x) некоторые существенно ограниченные на отрезке [0,1] функции.
В журнале ДАН2 приведена теорема об униэкстремалыюсти гипер-1
плоскости f f(s)ds = const. о
1 Рублев В. С., Чаплыгина Н. Б. Выбор критерия оптимизации в задаче о равномерном назначении }j Дискретная математика, 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., Макаров A.B. Задачи оптимального округления. // Дискретные модели в теории управляющих систем: VIII Международная конференция, Москва, 6-9 апреля 2009г.: Труды. - М.: Издательский отдел факультета ВМиК МГУ им. М.В. Ломоносова; МАКС Пресс, 2009, С. 185-187.
^Коршунова Н.М., Рублев B.C. Задача целочисленного сбалансирования матрицы // Современные проблемы математики и информатики, вып. 3. Ярославль: ЯрГУ им. П.Г. Демидова, 2000. с. 145 - 150.
^Рублев B.C., Смирнов A.B. Задача оптимального округления плапа валютных счетов // Кибернетика и высокие технологии XXI века. - Воронеж: НПФ "Саквоее2008. - Т. 1. - С. 112-123.
6 Рублев B.C., Смирнов A.B. Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения // Моделирование и анализ информационных систем. - 2010. - Т. 17, № 2. - С. 72-98.
7Рублев B.C. Задача о равномерном распределении работ. // Ярославский госуниверситет. Ярославль, 198Н. - Деп. ВИНИТИ ЖП1-В87 2fj.01.87
симметричных норм;
2) описание класса униэкстремальных гиперплоскостей в функциональных банаховых пространствах с симметричной нормой;
3) описание вида экстремальных векторов и функций;
4) построение эффективного алгоритма поиска экстремальных векторов и фупкций;
5) исследование униэкстремальности гиперплоскостей и поиск экстремальных векторов для целочисленных задач в конечномерных векторных пространствах.
Методы исследования
В диссертационной работе используются методы теории функций и функционального анализа, теории приближений, методы линейной алгебры и аналитической геометрии. Помимо этого, в работе используются отдельные методы высшей алгебры, дискретной математики, теории алгоритмов.
Научная новизна
Все основные результаты работы являются новыми:
1) полностью описаны классы гиперплоскостей в конечномерном векторном пространстве, обладающие ¿/-свойством и свойством униэкстремальности относительно симметричных и специальных симметричных норм;
2) определен вид экстремальных векторов и найден эффективный алгоритм их нахождения в конечномерных векторных пространствах с трудоемкостью 0(п2), где п - размерность пространства;
3) описан класс униэкстремальных гиперплоскостей в функциональных банаховых пространствах с симметричной нормой;
4) определен вид экстремальных функций и найден эффективный алгоритм их нахождения в функциональных банаховых пространствах с симметричными нормами, количество шагов которого О (1од2 , где е - требуемая точность;
5) в конечномерных векторных пространствах решены аналоги задач для целочисленного случая.
Теоретическая и практическая значимость работы
Результаты данной работы можно применять при решении оптимизационных задач. Например, задач дискретной математики - задачи о равномерном назначении работ, задачи о целочисленном сбалансировании двумерной
и трехмерной матриц. Описаны случаи, когда можно выбирать в качестве критерия оптимизации наиболее удобный критерий - евклидову норму. Кроме того, при поиске оптимальных решений в некоторых задачах можно использовать эффективные алгоритмы их нахождения, описанные в работе.
Апробация работы
Основные результаты работы докладывались и обсуждались на международной конференции, посвященной 70-летию ректора МГУ академика В.А.Садовничего «Современные проблемы математики, механики и их приложений»; 62 региональной научно-технической конференции студентов, магистрантов и аспирантов высших учебных заведений с международным участием «Молодежь, наука, инновации 2009»; международной научно-технической конференции «Чтения Ушинского» - 2010; всероссийской научной конференции «Современные проблемы теории функций и их приложения» -2010; XV всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании» - 2010; II всероссийской молодежной научно-практической конференции «Научно-практические исследования современной молодежи» - 2010; семинарах Ярославского государственного университета под руководством профессора Соколова В.А. - 2010.
Публикации
Результаты диссертации опубликованы в работах [1|-[11]. Работы [4], |5|, [6], [11] опубликованы в рецензируемых журналах, входящих в перечень ВАК РФ. Из совместных публикаций [1], [10] в диссертацию вошли результаты, принадлежащие лично автору.
Структура и объем диссертации
Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы, содержащего 77 наименований. Диссертация содержит 8 рисунков. Объем диссертации составляет 107 страниц.
СОДЕРЖАНИЕ РАБОТЫ
Во введении приведена краткая история возникновения проблемы данного исследования, обосновывается актуальность исследования, его связь с прикладными задачами дискретной математики. Далее во введении формулируется ряд качественных вопросов, которые изучаются в дальнейшем в тексте данной работы, и ответы на которые приводятся в исследовании.
В первой главе вводятся основные определения, необходимые в дальнейшем для исследования, приводится ряд определений и вспомогательных утверждений из высшей алгебры, аналитической геометрии, функционального анализа и теории приближений.
Во второй главе Во второй главе приводятся определения симметричной и специальной симметричной нормы, свойств U, Vs, упиэкстремальпости, их взаимосвязь, приводятся примеры; выясняется, для каких классов гиперплоскостей в пространстве Rn выполнено U- и [/"-свойство.
В первом параграфе второй главы приводятся два варианта определения симметричной нормы в пространстве Rn. Симметрично» нормой в конечномерном векторном пространстве называется норма, которая не изменяется при любой перестановке координат произвольного вектора, а специальной симметричной нормой называется норма, обладающая свойством: II (Ы, Ы, • ■ •, |яп|) 11=11 .. .,xin) II для любой перестановки
Приводится определение ¿/-свойства линейного многообразия и определение упиэкстремальпости гиперплоскости. Один из вариантов определения приведен выше. В терминах метрического проектора это определение выглядит так: гиперплоскость G обладает свойством U, если Pg,e{0) £ Pg,n{0) для любой симметрической нормы N, где Е - евклидова норма, - метрический проектор, 0 - нулевой элемент пространства Л".
После введения определений делается замечание, что свойство униэкстре-мальности гиперплоскости сильнее, чем [/-свойство. Кроме того, класс специальных симметричных норм в конечномерных векторных пространствах уже, чем класс симметричных норм, поэтому гиперплоскостей, обладающих [/-свойством или свойством упиэкстремальпости относительно класса специальных симметричных норм больше, чем гиперплоскостей, обладающих данными свойствами относительно симметричных норм.
Во втором параграфе отмечается, что любая гиперплоскость, проходящая через начало координат, обладает [/-свойством ([/"-свойством), поскольку минимум вообще любой нормы достигается в нуле. Поэтому во второй главе
п
исследуются гиперплоскости вида ^ = const ф 0 (все коэффициенты
¿=1
уравнения гиперплоскости не могут быть равны нулю одновременно).
Итоговой теоремой, полностью описывающей класс гиперплоскостей в конечномерном векторном пространстве, обладающих [/-свойством, является:
Теорема 1. Гиперплоскость п-мерного пространства, обладает и-свойством тогда и только тогда, когда она задается уравнением одного из следующих видов:
= ° (1)
¿=1
п
y}Txi = const ф 0 (2)
(3)
i=i
п п
У]ajXj = const ф 0 {pii е {-1,0,1}, г = 1,2,...,п и У^щ — О ¡=1 ¿=1
т.е. количество коэффициентов, равных единице, совпадает
с количеством коэффициентов, равных минус единице).
Для построения ряда контрпримеров была найдена некая симметричная норма JV*, которая определяется квадратичной формой, заданной в следующем утверждении:
п п-1 п
Утверждение 1. Квадратичная форма Ж1 + 2 Y1 x<xj является сим-
1=1 r:;l j=i+1
метричиой и положительно определенной и, следовательно, порождает симметричную норму N* в R".
Итоговой теоремой, полностью описывающей класс гиперплоскостей в конечномерном векторном пространстве, обладающих U' -свойством, является
Теорема 2. Гиперплоскость пространства Rn, обладает Us-свойством тогда и только тогда, когда она задается уравнением одного из следующих видов:
п
]Г ctiXi = 0 (1)
п
У ajXi — const, «¿е {—1,0,1}, г = 1,2,..., п. (4)
¿=1
В третьей главе выясняется, для каких классов гиперплоскостей в пространстве Rn выполнено свойство униэкстремальности относительно симметричных и специальных симметричных норм.
Устанавливается, что свойство униэкстремальности гиперплоскостей сильнее, чем [/-свойство. Для того, чтобы убедиться в этом, достаточно рассмотреть любой многогранник, содержащий экстремальную точку гиперплоскости
в норме ¿2- Поэтому проверку униэкстремальности имеет смысл проводить только для тех гиперплоскостей, которые обладают [/([/^-свойством.
Отдельно проводится исследование гиперплоскостей, не проходящих через начало координат и гиперплоскостей-подпространств. Итоговой теоремой, полностью описывающей класс униэкстремальных гиперплоскостей в конечномерном векторном пространстве, является
Теорема 6. В пространстве R2 гиперплоскость является униэкстре-мальной тогда и только тогда, когда она задается уравнением одного из следующих видов:
х\ ± Х2 = const (5)
otx\ 4- /Зх2 = 0, а2 + /?2 ^ 0 (6)
В пространстве Rn при п > 2 гиперплоскость является униэкстремалъной тогда и только тогда, когда она задается уравнением одного из следующих видов:
п
Xi = const (7)
•=i п—1
Х> = 0 (8)
t=i
Одной из ключевых теорем данной главы и всей работы является Теорема 3. Любое линейное многообразие, описываемое уравнениями
к
y^Xj = const, 1=1
Xi = aii, г = к + 1, к + 2,..., п является униэкстремалъпым.
Доказательство теоремы 3 проводится индукцией по размерности линейного многообразия.
В третьем и четвертом параграфе третьей главы исследована униэкстре-мальность гиперплоскостей пространства Л" относительно специальных симметричных норм. При этом исследование снова производилось отдельно для подпрострапств и для линейных многообразий, а аппарат исследований частично опирался на доказанные выше утверждения.
Итоговой теоремой, полностью описывающей класс униэкетремальных гиперплоскостей относительно специальных симметричных норм, является
Теорема 7. В пространстве Rn гиперплоскость является униэкстре-малъной относительно специальных симметричных норм тогда и только тогда, когда она задается уравнением одного из следующих видов:
п
1) X) aixi — const, где сч € {—1,0,1} ¿=1
п
2) aixi — 0) причем среди коэффициентов уравнения отличны от нуля i=1
только один или два коэффициента.
В четвертой главе исследовался вопрос о том, как меняются полученные нами результаты в случай, когда на параметры и переменные наклаг дываготся дополнительные ограничения целочисленности. Это представляет интерес, поскольку задачи, рассматриваемые в диссертации, появились как обобщение некоторых задач дискретной математики, а, как правило, все ограничения в таких задачах являются целочисленными, так же как и ответы.
Диссертационное исследование ограничилось изучением сохранения U -свойства и свойства униэкстремальности для тех классов гиперплоскостей, которые обладают им в непрерывном случае. Соображения, почему не должно возпикнуть новых классов гиперплоскостей с данными свойствами в целочисленном случае, приведены в начале четвертой главы.
Результаты исследования показали, что все классы гиперплоскостей из теорем 1 и 2 обладают ¿/-свойством, а классы гиперплоскостей из теорем б и 7 обладают свойством униэкстремальности и для целочисленных задач тоже. А именно, доказано, что справедливы следующие утверждения:
Лемма 1. Пусть дана произвольная симметричная норма N и точка Е с координатами (х*,х2,..-,х^), где х\ > Рассмотрим точку F с координатами (жJ + 6, х\ — 5,х\,..., ж*), где 0 < <5 < хг~х>. Тогда значение нормы N во второй точке не превосходит значения нормы в первой точке N(F) < N(E), причем в некоторых нормах (например, норме Ь2 и других строго выпуклых нормах) неравенство строгое.
Утверждение 2. Рассмотрим произвольное линейное многообразие к
y^Xj = const, Xi — di при i = к + 1,к + 2,... , п.
t=i
Здесь значения at и const являются целыми числами. Тогда для любой симметричной нормы N минимум расстояния до начала координат, по данной норме от целочисленных точек многообразия достигается в точке Е с координатами (тп + 1, m + 1,..., т + 1, т, т,..., т, • • •, ап), где
координат, равных т+ 1, всего I штук, координат, равных т, всего к — I штук, и т-это частное от деления const на k , а I остаток от деления const на к.
Теорема 8. Рассмотрим произвольный параллелепипед с целыми границами {а< < х, < bi, aitbi £ Z, г = 1,2,... ,п} в пересечении с гипер-
п
плоскостью Ylxi = const 6 Z и назовем его множеством М. Тогда для «=1
всех симметричных норм минимум расстояния от начала координат до целочисленных точек М достигается в одной и той же точке.
н— 1
Утверждение 3. Гиперплоскость, задаваемая уравнением хг ~ 0 в
1=1
пространстве Rn обладает свойством целочисленной униэкстремалъности.
п
Утверждение 4. Гиперплоскости Ylaixi = const, где a, е {—1,0,1}
г=1
обладают свойством целочисленной униэкстремальности относительно специальных симметричных норм.
Утверждение 5. Все подпространства в Rn при п > 2, задаваемые уравнениями ахi+¡3x2 =0, а,(3 € Z, а2+/32 ф 0 обладают свойством целочисленной униэкстремальности относительно специальных симметричных норм.
Конструктивное доказательство теоремы 8 позволило сформулировать эффективный алгоритм нахождения искомых экстремальных точек и обосновать его правильность. Приведенный в третьем параграфе главы 4 алгоритм работает как в целочисленных задачах, так и в непрерывном случае. Приведено краткое описание предложенного алгоритма. Его применение во всех случаях состоит из отдельных шагов, на каждом из которых осуществляется сведение задачи поиска экстремальной точки в параллелепипеде к задаче ее поиска на некоторой грани меньшей размерности. Тем самым, число шагов алгоритма не превышает размерности задачи. На каждом шаге проводится некоторое число сравнений (не более размерности текущей грани) и вычисляется две суммы, выполняется снова количество действий, равное текущей
размерности грани. Отсюда делается вывод, что нужная точка находится за 0(п2) действий, где п - размерность пространства.
В четвертом параграфе четвертой главы рассматривается применение теоретических исследований к оптимизационным задачам.
В пятой главе изучаются аналоги {/-свойства и свойства униэкстремаль-ности гиперплоскостей в функциональных пространствах. Для этого рассматривается на отрезке [0,1] с мерой Лебега множество ограниченных измеримых функций So[0,1]. На нем можно ввести стандартную шкалу норм Lp[0,1]
IMU„ = (^j |1(а)рУя j при1 < p < oo,
а также определить другие симметричные нормы. Следуя классическим определениям8, нормированное пространство Е называется симметричными, если выполнены следующие два свойства:
1) если у G Я, \x(t)\ < |j/(i)| п.в., то а: е ||а;||в < ||</]|£,
2) если у е Е, |а:(£)| и |j/(i)| равноизмеримы, то х 6 Е, ||а:||е = ||у||я. Про-
1
ведено исследование гиперплоскости / f(s)g(s)ds = const для различных
о
измеримых ограниченных функций д(х) на отрезке [0,1]. При этом рассмотрение ограничилось случаем гиперплоскостей, не являющихся подпространствами, т.е. считалось, что const ф 0, так как в противном случае гиперплоскость, очевидно, обладает ¿/-свойством. Кроме того, ясно, что функция д(х) пе может быть равна нулю почти всюду.
Как и в конечномерном векторном пространстве, под ¿/-свойством гиперплоскости понимается, что проектор нуля на нее в пространстве ¿2 [О,1] принадлежит всем проекторам нуля в различных симметричных нормах.
Свойство униэкстремальности гиперплоскости понимается, как выполнение [/-свойства для всех ее подмножеств, задаваемых двумя существенно ограниченными измеримыми функциями /¿„/(ж) и fsup{%):
D{fi„fJsup) = У(х) : finf{x) < f{x) < fsupix)Mx 6 [0,1]}.
Такое определение аналогично определению данных свойств в пространствах К1. Рассматриваются только непустые подмножества гиперплоскостей
8Крейп С.Г., Петушш Ю.И., Семенов Е.М. Интерполяция лилейных операторов. // М.: Физматлит, 1978.
данного вида, хотя для удобства можно считать, что для пустых подмножеств исследуемые свойства выполнены.
Во втором параграфе доказывается униэкстремальность гиперплоскости
1
f f(s)ds = const и устанавливается вид экстремальной функции, изобра-о
женный на рис 1. Идеи доказательств результатов, изложенных в этом параграфе, принадлежат Рублеву B.C.
Pire. 1. вид минимизирующей функции
Для определения приближенного значения константы С существует простой эффективный алгоритм, поскольку при изменении ее значения от rain ,f,nf{x) до max fsup(x) значение интеграла в условии монотонно возрастает, а потому можно воспользоваться методом деления пополам.
В третьем параграфе исследуются все униэкстремальные гиперплоскости в функциональном случае. Необходимое условие {/-свойства гиперплоскости, а значит и ее униэкстремальности, определяется следующей леммой.
Лемма 20. Если перестановка д*(х) функции д(х) принимает хотя бы
1
два разных ненулевых значения, то гиперплоскость J f(s)y(s)ds = const не
о
обладает U-свойством.
Из леммы 20 непосредственно вытекает, что униэкстремальные гиперплоскости надо искать только среди тех, которые задаются измеримыми функциями д(х), принимающими по модулю только одно ненулевое значение.
Далее, в главе 5 доказывается, что полученное необходимое условие униэкстремальности является и достаточным. Кроме того показано, что, независимо от выбора нормы симметричного функционального банахова пространства и подмножества D(finf,fsup) гиперплоскости, ближайшая к нулю функция будет на множестве /?0 устроена одинаково. Справедлива
Лемма 21. Пусть измеримая функция д(х) на отрезке [0,1] принимает только значения О, 1 и -1. Пусть, далее, выбрано некоторое подмножество D{finf,isup) исследуемой гиперплоскости. Тогда для любой симметричной нормы || • Цв ближайшая к нулю функция /¿(ж) из множества D(f{nf, fsup) на множестве Ео для Ух £ Eq принимает значения
(0, если finf{x) < 0 < fsupix) fmf(x), если\fi„f(x)\ < \fsup(x)\, fSUp(x), если\finf{x)\ > |/SUp(a;)| которые не зависят от || • || ¡¡.
Итогом рассуждений в главе 5 является
1
Теорема 11. Гиперплоскость f f(s)g(s)ds = const обладает свойством
о
униэкстремальности тогда и только тогда, когда функция д(х) принимает только значения 0,1 и -1 на измеримых множествах Ео, Е{, причем mes{Ef U Ef} > 0.
1
Полученный вид экстремальной функции для случая f f(s)ds = const и
о
1
алгоритм ее поиска обобщаются на случай / f(s)g(s)ds = const с помощью
о
преобразований, обратных к тем, которые проводился при сведении общей задачи к известному частному случаю.
В заключении описаны и соотнесены с целями основные результаты исследования.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
В данной диссертационной работе получены следующие результаты:
1) описаны классы гиперплоскостей в конечномерном векторном пространстве, обладающие ¡[/-свойством и свойством униэкстремальности относительно симметричных норм;
2) за счет введения специальных симметричных норм расширены классы гиперплоскостей, обладающих U-свойством и свойством униэкстремальности;
3) описан класс уииэкстремальпых гиперплоскостей в функциональных банаховых пространствах с симметричной нормой;
4) определен вид экстремальных векторов и функций и описаны эффективные алгоритмы их нахождения;
5) в конечномерных векторных пространствах решены аналогичные задаг чи для целочисленного случая.
Таким образом, все цели, поставленные перед данным исследованием, достигнуты.
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
1. Рублев В. С. Униэкстремальные гиперплоскости конечномерных симметрических пространств. / В. С. Рублев, Н. П. Федотова // Материалы. науч. конф. «Современные проблемы математики, механики и их приложений», посвященной 70-летию ректора МГУ академика В.А.Садовничего - М.: Изд-во Моск. ун-та, 2009. - С. 401.
2. Федотова Н. П. Об одном классе гиперплоскостей симметричных пространств / Н. П. Федотова // Труды 62 региональной науч.-техн. конф. «Молодежь, наука, инновации 2009» - Ярославль.: Изд-во Ярославск. гос. ун-та, 2009. - С. 206.
3. Федотова Н. П. Униэкстремальные гиперплоскости и их применение в оптимизационных задачах / Н. П. Федотова // Материалы науч.-техн. конф. «Чтения Ушинского» - Ярославль.: Изд-во Ярославск. гос. пед. ун-та, 2010. - С.8-13.
4. Федотова Н. П. Гиперплоскости универсальной экстремали некоторых задач оптимизации / Н. П. Федотова // Моделирование и анализ информационных систем. - Ярославль, 2010. - Т. 17, № 3. - С. 91-106.
5. Федотова Н.П. О расстоянии до гиперплоскостей в симметричных нормах / Н. П. Федотова // Ярославский педагогический вестник. Серия «Физико-математические и естественные науки» - Ярославль, 2010. -Вып.2. - С.33-38.
6. Федотова Н.П. О расстоянии до многогранников некоторого класса в симметричных нормах / Н. П. Федотова // Ярославский педагогический вестник. Серия «Физико-математические и естественные науки» -Ярославль, 2010. - Вып.З. - С.37-42.
7. Федотова Н.П. Об одном свойстве гиперплоскостей конечномерных пространств. / Н. П. Федотова // Труды науч. конф. «Современные проблемы теории функций и их приложения» - Саратов: Изд-во Сара-товск. гос. ун-та, 2010. - С. 68-70.
8. Федотова II.П. Целочисленные оптимизационные задачи и трудоемкость их решения. / Н. П. Федотова // Материалы XV Всероссийской науч.-техн. конф. студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании» -Рязань: Редакционно-издательский центр РГРТУ, 2010. - С. 195-196.
9. Федотова Н.П. Уииэкстремапьные гиперплоскости конечномерных симметрических пространств в дискретном случае / Н. П. Федотова // Материалы II всерос. молодежной пауч.-практ. конф. «Научно-практические исследования современной молодежи» (Елабуга, 23-24 декабря 2010) - г.Казань: Изд-во Казан, гос. техн. ун-та, 2010. - Т.З - С. 153-156.
10. Рублев B.C., Федотова Н.П. Униэкстремальные гиперплоскости симметричных банаховых пространств / В. С. Рублев, Н. П. Федотова // Вестник Ярославского гос. ун-та им. П.Г. Демидова, серия «Естесвен-ные и технические науки» - Ярославль, 2010. - №2 - С. 89-98.
11. Федотова Н.П. Униэкстремальные гиперплоскости конечномерных дискретных пространств / Н. П. Федотова // Ярославский педагогический вестник. Серия «Физико - математические и естественные науки» -Ярославль, 2011. - Вып.1. - С.37-47.
Работы [4], [5], [б] и [11] опубликованы в журналах, входящих в перечень ВАК РФ.
Подписано в печать 7.04.11. Формат 60x84/16. Бумага оф. Отпечатано на ризографе.
Тираж 100 экз. Заказ 7/11. Отдел оперативной полиграфии ЯрГУ 150000, Ярославль, ул. Советская, 14
Введение.
Глава 1. Основные определения и вспомогательные утверяедения.
§ 1.1 Необходимые сведения из алгебры и геометрии. Перестановки, произведение независимых циклов. Гиперплоскости и линейные многообразия в Я". Выпуклость.
§ 1.2 Необходимые сведения из функционального анализа. Положительно определенная квадратичная форма, скалярное произведение, норма, метрика, связи между ними. Теорема Колмогорова. Расстояние в норме Ь2 до линейных многообразий.
§ 1.3 Необходимые сведения из теории приближений. Приближение в нормированных пространствах. Теоремы единственности и существования. Метрический проектор и метрическая проекция.
Глава 2. и-свойство для симметричных и специальных симметричных норм.
§ 2.1 Основные определения и примеры. Симметрическая, специальная симметрическая нормы, и-свойство и свойство униэкстремальности для введенных классов норм. Зависимость свойств.
§ 2.2 И-свойство для симметричных норм.
§ 2.3 и-свойство для специальных симметричных норм.
Глава 3. Униэкстремальность для симметричных и специальных симметричных норм.
§ 3.1 Свойство униэкстремальности гиперплоскостей в пространстве Ып, не являющихся подпространствами, относительно симметричных норм.
§ 3.2 Униэкстремальность гиперплоскостей-подпространств.
§ 3.3 Свойство униэкстремальности гиперплоскостей в пространстве Я", не являющихся подпространствами, относительно специальных симметричных норм.
§ 3.4 Униэкстремальность гиперплоскостей-подпространств относительно специальных симметричных норм.
Глава 4. Результаты для целочисленных задач. Применение полученных результатов.
§ 4.1 и-свойство и униэкстремальность для симметричных норм в целочисленном случае.
§ 4.2 и-свойство и униэкстремальность для специальных симметричных норм в целочисленном случае.
§ 4.3 Алгоритм нахождения точки метрического проектора.
п
Известно [49], что гиперплоскость Ylxi = 0 n-мерного пространства об1 ладает следующим свойством: для любого многогранника вида щ < Xi < bi (i = 1,2,. ,п) в этой гиперплоскости существует точка этого многогранника, в которой достигается минимум любой симметричной нормы.
Другими словами, метрический проектор нуля на указанную гиперплоскость в определенном смысле не зависит от метрики.
Назовем указанное свойство униэкстремальным. Дадим точное определение:
Непустое пересечение гиперплоскостей (и линейных многообразий) с различными параллелепипедами щ < Х{ < Ьг- (г = 1,2,., п) называются многогранниками вида D.
Свойство U выполнено для гиперплоскости (или многогранника вида D), если тючка этой гиперплоскости (или многогранника вида D), в которой достигается минимум евклидовой нормы, является точкой минимума любой другой симметричной нормы.
Гиперплоскость пространства Rn называется униэкстремалъной, если на любом многограннике вида D этой гиперплоскости выполнено свойство U.
Рассмотренный подход допускает обобщение на функциональный случай:
Гиперплоскость обладает U-свойством, если ближайшая к нулю по норме пространства L2 [0,1] точка гиперплоскости является и одной из ближайших к нулю точек по норме любого другого симметричного функционального банахова пространства.
Гиперплоскость называется униэкстремалъной, если данное свойство остается верным и для любых ее подмножеств вида:
D(finf, fsup) = {fix) finf < f(x) < fsup, Vrr 6 [0,1]}, где fm(u /sup некоторые существенно ограниченные на отрезке [0,1] функции.
В журнале ДАН [47] приведена теорема об униэкстремальности 1 гиперплоскости \f(s)ds = const. о
Данные свойства были обнаружены при исследовании некоторых оптимизационных задач. Особую группу представляют целочисленные оптимизационные задачи.
В приложениях часто возникают задачи целочисленной оптимизации: округление экономического плана [35, 36], планирование железнодорожных перевозок [19], округление остатков на валютных счетах при конвертации валюты [38], целочисленное сбалансировании двумерной [19] и трехмерной [37, 39-42] матриц, равномерное назначение работ [22, 23, 48, 50, 51]. В этих задачах возникает вопрос о выборе критерия оптимизации, часто рассматривается несколько вариантов задач для различных критериев оптимизации. Иногда бывает известно, что для некоторых критериев проще получить решение, чем для других. В этих случаях требуется установить наиболее сильный критерий (в том смысле, что он влечет выполнение других критериев). Возникает вопрос о взаимосвязи критериев, выявлении наиболее сильного критерия, о частичном упорядочивании критериев. При ответе на некоторые из этих вопросов может быть использована указанная теорема.
Поэтому представляется актуальным исследовать класс гиперплоскостей в векторных и функциональных пространствах, обладающих свойством униэкстремальности, возможность расширения класса исследуемых гиперплоскостей за счет наложения ограничений на нормы, возможность упрощения решения некоторых оптимизационных задач за счет выбора более простого критерия.
Целью данной работы является исследование класса гиперплоскостей в симметричных конечномерных векторных пространствах и функциональных банаховых пространствах, для которых выполнено свойство униэкстремальности. Среди основных задач выделяются:
1) описание класса униэкстремальных гиперплоскостей в конечномерных векторных пространствах относительно симметричных и специальных симметричных норм;
2) описание класса униэкстремальных гиперплоскостей в функциональных банаховых пространствах с симметричной нормой;
3) описание вида экстремальных векторов и функций;
4) построение эффективного алгоритма поиска экстремальных векторов и функций;
5) исследование униэкстремальности гиперплоскостей и поиск экстремальных векторов для целочисленных задач в конечномерных векторных пространствах.
В диссертационной работе используются методы теории функций и функционального анализа, теории приближений, методы линейной алгебры и аналитической геометрии. Помимо этого, в работе используются отдельные методы высшей алгебры, дискретной математики, теории алгоритмов.
Как известно [11], задача наилучшего приближения включает в себя следующие пять проблем: a) проблема существования элемента наилучшего приближения; b) установление характеристических свойств этого элемента; c) проблема единственности элемента наилучшего приближения; с!) вычисление (или оценка) наилучшего приближения; е) построение алгоритма отыскания ближайшего элемента.
Все эти вопросы исследованы в данной работе применительно к некоторым задачам исследования, как в конечномерных нормированных пространствах, так и в функциональных пространствах.
В первой главе работы вводятся основные определения, необходимые в дальнейшем для исследования, приводится ряд определений и вспомогательных утверждений из высшей алгебры, из аналитической геометрии и функционального анализа.
Во второй главе приводятся определение симметричного функционального банахова пространства и на его основе приводится два варианта определения симметричной нормы в конечномерных векторных пространствах. Симметричной нормой в конечномерном векторном пространстве называется норма, которая не изменяется при любой перестановке координат произвольного вектора, а специальной симметричной нормой называется норма, обладающая свойством: Il(|xi|5|x2|,.|xn|)||=||( х^ь х^2,• •. х^п )|| для любой перестановки Далее вводятся определения свойств U, Us, униэкстремальности в смыслах симметричной и специальной симметричной норм, приводятся примеры, устанавливается взаимосвязь введенных понятий. Выясняется, для каких классов гиперплоскостей в пространстве Rn выполнено U-свойство и для каких классов гиперплоскостей выполнено ИТ-свойство, т.е. метрический проектор нуля в метрике L2 (ровно одна точка) принадлежит метрическим проекторам нуля в любых симметричных (специальных симметричных) нормах.
В работе делается замечание, что свойство униэкстремальности гиперплоскости сильнее, чем U-свойство. Кроме того, класс специальных симметрических норм в конечномерных- векторных пространствах уже, чем класс симметричных норм, поэтому гиперплоскостей, обладающих U-свойством или свойством униэкстремальности относительно класса специальных симметричных норм больше, чем гиперплоскостей, обладающих данными свойствами относительно симметричных норм.
Во втором параграфе отмечается, что любая- гиперплоскость, проходящая через начало координат, обладает U-свойством ([/-свойством), поскольку минимум вообще любой* нормы достигается в нуле. Поэтому во п второй главе исследуются гиперплоскости вида = const ф О (все 1 коэффициенты уравнения гиперплоскости не могут быть равны нулю одновременно).
Следующие теоремы 1 и 2, полностью описывают класс гиперплоскостей в конечномерном векторном пространстве, обладающих U ( US)-CBOftCTBOM.
Теорема 1. Гиперплоскость n-мерного пространства, обладает U-свойством тогда и только тогда, когда она задаётся уравнением одного г*3 следующих видов:
1) 5>Л= О 1 п
2) const ф О/ 1
3) = const * 0 (aiе{-1,0,1}, i=l,2, .,П и ¿а, =О, т.е. количество коэффициентов, равных единице, совпадает с количеством коэффициентов, равных минус единице).
Теорема 2. Гиперплоскость n-мерного пространства, обладает if ~ свойством тогда и только тогда, когда она задаётся уравнением одного глз следующих видов:
1) ±а,х,=0
1=1 п
2) - const ccie{-l,0,l}, i=l,2, .,п. i=i
V.
Как легко видеть, класс гиперплоскостей, обладающих и5-свойство]у<? оказался действительно шире класса гиперплоскостей, обладающих XJч" свойством, поскольку специальных симметричных норм в пространстве ^ меньше, чем просто симметричных.
В третьей главе выясняется, для каких классов гиперплоскостей в пространстве R" выполнено свойство униэкстремальности относительно симметричных и специальных симметричных норм.
Устанавливается, что свойство униэкстремальности гиперплоскостей сильнее, чем U-свойство. Для того, чтобы убедиться в этом, достаточно рассмотреть любой многогранник, содержащий экстремальную точку гиперплоскости в норме L2. Поэтому проверку униэкстремальности имеет смысл проводить только для тех гиперплоскостей, которые обладают U-свойством (и^-свойством).
Итоговыми теоремами, полностью описывающими класс униэкстремальных гиперплоскостей в пространстве конечномерном векторном пространстве, являются следующие теоремы:
Теорема 6. В пространстве R гиперплоскость является униэкстремалъной тогда и только тогда, когда она задаётся уравнением одного из следующих видов:
1) х, ±х2 = const
2) axl + fix2 = 0, се2 + 01 * О
В пространстве R" при п>2 гиперплоскость является униэкстремалъной тогда и только тогда, когда она задаётся уравнением одного из следующих видов: п
1) = const 1
Теорема 7. В пространстве R" гиперплоскость является униэкстремалъной относительно специальных симметричных норм тогда и только тогда, когда она задаётся уравнением одного из следующих видов: п
1) = const, где atG{-1,0,1}
1=1
2) 2^=0, причём среди коэффициентов уравнения отличны от нуля~ 1 только один или два коэффициента.
В четвертой, главе исследовался вопрос о том, как меняются полученные нами результаты в случае, когда на параметры и переменные накладываются дополнительные ограничения целочисленности. Это представляет интерес, поскольку задачи, рассматриваемые в диссертации, появились как обобщение некоторых задач дискретной математики, а, как правило, все ограничения в таких задачах являются целочисленными, так же как и ответы.
Диссертационное исследование ограничилось изучением сохранения и - свойства и свойства униэкстремальности для тех классов гиперплоскостей, которые обладают имс в непрерывном случае. Соображения, почему не должно возникнуть новых классов гиперплоскостей с данными свойствами в целочисленном случае, приведены в начале четвертой главы.
Результаты исследования показали, что все классы гиперплоскостей из-теорем 1 и 2 обладают И-свойством, а классы гиперплоскостей из теорем 6 и-7 обладают свойством униэкстремальности и для целочисленных задач тоже.
Доказательства теорем и утверждений этой части работы основаны на идеях, которые позволили сформулировать, эффективный алгоритм нахождения искомых экстремальных точек. Приведенный в третьем параграфе главы 4 алгоритм работает как в целочисленных задачах, так и в непрерывном случае.
Приведено краткое описание предложенного алгоритма. Его применение во всех случаях состоит из отдельных шагов, на каждом из которых осуществляется сведение задачи поиска экстремальной точки в параллелепипеде к задаче ее поиска на некоторой грани меньшей размерности. Тем самым, число шагов алгоритма не превышает размерности задачи. На каждом шаге проводится некоторое число сравнений (не более размерности текущей грани) и вычисляется; две суммы, выполняется снова количество действий, равное текущей размерности грани. Отсюда делается вывод, что нужная точка находится за 0{п2) действий, где п- размерность пространства.
В четвертом параграфе четвертой главы рассматривается применение теоретических исследований к оптимизационным задачам.
В пятой главе изучаются аналоги U-свойства и свойства униэкстремальности гиперплоскостей в функциональных пространствах. Итоговой теоремой, описывающей класс униэкстремальных гиперплоскостей в функциональном случае является
Теорема 11. Гиперплоскость |/(s)g(s)ds = const обладает свойством о униэкстремальности тогда и только тогда, когда функция g(x) принимает только значения 0,1 и -1 на измеримых множествах Е0,Е^,Е^, причём mes{El U £г}> 0.
Заключение.
В данной работе рассмотрена задача об униэкстремальных гиперплоскостях.
Установлены все униэкстремальные гиперплоскости, т.е. показано, что метрический проектор в некотором смысле не зависит от метрики для конкретного класса задач. Найдены наиболее сильные критерии оптимизации. Получен общий вид единого экстремума.
Кроме того, найдены все гиперплоскости, обладающие более слабым и-свойством. Установлены связи между и, ТТ-свойствами, свойствами униэкстремальности для симметричных и специальных симметричных норм. Рассмотрены линейные многообразия, обладающие свойством униэкстремальности.
За счет введения специальной симметричной нормы расширены классы гиперплоскостей, обладающих и-свойством и свойством униэкстремальности. Ограничение не сильно сужает класс исследуемых задач, поскольку все нормы Ьр являются специальными симметрическими нормами.
Найдены все гиперплоскости, обладающие и, ^-свойствами, свойствами униэкстремальности в целочисленном случае для симметричных и специальных симметричных норм. Рассмотрено применение этих результатов к непрерывным и дискретным оптимизационным задачам.
Результаты проведенного исследования перенесены на функциональный случай, описаны все униэкстремальные гиперплоскости симметричных банаховых пространств, найден общий вид минимизирующей функции.
Таким образом, получен ответ на все вопросы исследования.
1. Б.Л. Ван-дер-Варден. Алгебра. // М.: Мир, 1976
2. Балашов М. В., Иванов Г. Е. Свойства метрической проекции на множество, слабо выпуклое по Виалю, и параметризация многозначных отображений со слабо выпуклыми значениями. // Матем. заметки, том 80, вып.4, 2006, 483^89
3. Бердышев В .И., Петрак Л.В. Аппроксимация функций, сжатие численной информации, приложения // Екатеринбург, УрО РАН, 1999.
4. Бондаренко В.А., Клоеден П.Е., Краснов М.В. О лексикографической оптимизации в многокритериальных дискретных задачах. // Автоматика и телемеханика. №2, 2000.
5. Бондаренко В.А., Краснов М.В. Сложность многокритериальных задач на графах. // Математика в Ярославском университете. Ярославль, 2000, Т.7, №2, С. 3-12.
6. Бураго Д.Ю., Бураго Ю.Д., Иванов C.B. Курс метрической геометрии // Москва Ижевск: Институт компьютерных исследований, 2004.
7. Виноградов И.М. Математическая энциклопедия // т.1,2,3,5 М.: Советская энциклопедия, 1985.
8. Власов Л.П. Аппроксимативные свойства множеств в линейных нормированных пространствах // Успехи математических наук, 1973, т.28, вып.6, с.3-66.
9. Г. Е. Шилов Математический анализ. Функции одного переменного Ч.З//М.: Наука, 1970
10. Гаркави А. Л. О чебышевском центре и выпуклой оболочке множества. //Успехи мат. наук, том 19, вып.6(120), 1964, 139—145
11. Гаркави А.Л. Теория наилучшего приближения в линейных нормированных пространствах // Итоги науки и техники. Мат. анализ, М.: ВИНИТИ, 1967.
12. Гохберг И.Ц., Крейн М.Г. Введение в теорию линейных несамосопряженных операторов в гильбертовом пространстве. // М.: Наука, 1965.
13. Дей М.М. Нормированные линейные пространства // пер. с англ., М.: Издатинлит, 1961
14. Канторович JI.B., Акилов Г.П. Функциональный анализ. // М.: Наука, 1977
15. Кини P.JL, Райфа X. Принятие решений при многих критериях: предпочтения и замещения. // М.: Радио и связь, 1981.
16. Кириллов A.A., Гвишиани А.Д. Теоремы и задачи функционального анализа // М.: Наука, 1979.
17. Колмогоров А.Н. Избранные труды т1. Математика и механика // М.: Наука, 1985, с168-171
18. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. //М.: Наука, 1972.
19. Коршунова Н.М., Рублев B.C. Задача целочисленного сбалансирования матрицы // Современные проблемы математики и информатики, вып. 3. Ярославль: ЯрГУ им. П.Г. Демидова, 2000. с. 145 -- 150.
20. Кострикин А. И. Введение в алгебру. Часть I. Основы алгебры // 3 изд., М.: ФИЗМАТЛИТ, 2004.
21. Крейн С.Г., Петунин Ю.И., Семенов Е.М. Интерполяция линейных операторов. //М.: Физматлит, 1978.
22. Кропанов В.А., Рублев B.C. Задача о равномерном назначении работ и ее обобщения // Моделирование и анализ информационных систем. Ярославль, 2000, Т.7, №2, С. 3-12.
23. Кропанов В.А., Рублев B.C. Равномерное назначение работ минимальной стоимости // Дискретная математика, 2001, Т. 13, №4, С. 144-156.
24. Куржанский А.Б. Управление и наблюдение в условиях неопределенности. //М.: Наука, 1977
25. Курош А.Г. Курс высшей алгебры. // изд.9, М.; Наука, 1968
26. Люстерник Л.А. Соболев В.И. Элементы функционального анализа, // 2изд., М., 1965
27. Маламед И.И. Теория линейной параметризации критериев в многокритериальной оптимизации, ДАН, 1996, Т.348. №4, С.446-448.
28. Маламед И.И., Сигал И.Х. Бикритериальные задачи дискретного программирования с MINSUM-MINSUM критериями, М.: ВЦ РАН, 2000.
29. Маламед И.И., Сигал И.Х. Вычислительное исследование трехкритериальных задач о деревьях и назначениях, // Журнал вычислительной математики и математической, физики, 1998, Т.38. №10, С.1780-1787.
30. Маламед И.И., Сигал И.Х. Задачи комбинаторной оптимизации с двумя и тремя критериями, ДАН, 1999, Т.366. №2, С.170-173.
31. Маламед И.И., Сигал И.Х. Исследование линейной свертки критериев в многокритериальном дискретном программировании. // Журнал вычислительной математики и математической физики, 1995, Т.35. №8, С.1260-1270.
32. Маламед И.И., Сигал И.Х. Распределение эффективных решений в некоторых бикритериальных задачах дискретного программирования, М.: ВЦ РАН, 2001.
33. Рокафеллар Р. Выпуклый анализ. // М.: Мир, 1973.
34. Рублев B.C. Задача о равномерном распределении работ. // Ярославский госуниверситет. Ярославль, 1986. Деп. ВИНИТИ №611-В87 26.01.87
35. Рублев B.C. Минимизация ошибок округления плана. // Математика, кибернетика, информатика. Труды международной конференции,посвященной памяти профессора А.Ю. Левина, Ярославль: ЯрГУ, 2008, С. 145-150.
36. Рублев B.C., Смирнов A.B. TVP-полнота задачи целочисленного сбалансирования трехмерной матрицы // ДАН. 2010. - Т. 435, № 3. -С. 311-313.
37. Рублев B.C., Смирнов A.B. Задача оптимального округления плана валютных счетов // Кибернетика и высокие технологии XXI века. -Воронеж: НПФ «Саквоее», 2008. Т. 1. - С. 112-123.
38. Рублев B.C., Смирнов A.B. Задача целочисленного сбалансирования 3-мерной матрицы NP-трудная // Доклады Одесского семинара по дискретной математике. / Южный научный центр HAH и МОН Украины. - Одесса: Астропринт, 2010. - Вып. 10. - С. 47-49.
39. Рублев B.C., Смирнов A.B. Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения // Моделирование и анализ информационных систем. 2010. - Т. 17, № 2. - С. 72-98.
40. Рублев B.C., Смирнов A.B. Послойный алгоритм целочисленного сбалансирования трехмерной матрицы // Материалы IX Международного семинара «Дискретная математика и ее приложения», посвященного 75-летию со дня рождения академика
41. О. Б. Лупанова (Москва, МГУ, 18-23 июня 2007 г.). М.: МГУ, 2007.-С. 351-353.
42. Рублев B.C., Смирнов A.B. Послойный алгоритм целочисленного сбалансирования трехмерной матрицы плана (тезисы) // Доклады Одесского семинара по дискретной математике. / Южный научный центр HAH и МОН Украины. Одесса: Друк, 2007. - Вып. 5. - С. 44-45.
43. Рублев B.C., Смирнов A.B. Целочисленное сбалансирование 3-мерной матрицы плана // Труды VII международной конференции «Дискретные модели в теории управляющих систем» (Покровское 4-6 марта 2006 г.). М.: МГУ, 2006. - С. 302-308.
44. Рублев B.C., Смирнов A.B. Целочисленное сбалансирование трехмерной матрицы плана и обобщенная теория потоков // Доклады Одесского семинара по дискретной математике. / Южный научный центр HAH и МОН Украины. Одесса: Астропринт, 2006. -Вып. З.-С. 38-46.
45. Рублев B.C., Чаплыгина Н.Б. Выбор критерия оптимизации в задаче о равномерном назначении // Дискретная математика, 2005, т. 17, вып 4, 150-157.
46. Рублев B.C., Чаплыгина Н.Б. Критерий среднеквадратичного отклонения наилучший для области определенного вида в Rn. // Тез. конф. Современные проблемы функционального анализа и диффенциальных уравнений. Воронеж, 2003, С. 199.
47. Рублев B.C., Чаплыгина Н.Б. О некоторой характерной точке одного класса многогранников в симметрических пространствах // ДАН, 2006, т. 407, №2, 176-178.
48. Рублев B.C., Чаплыгина Н.Б. Расширение задачи о назначениях. // Моделирование и анализ информационных систем. Ярославль, 2002, Т.9,№2, С. 3-11.
49. Рублев B.C., Чаплыгина Н.Б. Расширение задачи о назначениях. // Тез. докл. XIII межд. конф. Проблемы теоретической кибернетики, Москва, 2002, С. 156.
50. Рудин У., Функциональный анализ // пер. с англ., М.: Мир, 1975
51. Сигал И.Х., Иванова А.П., Введение в прикладное дискретное программирование. Модели и вычислительные алгоритмы. М.: Физматлит, 2002.
52. Смирнов A.B. Задача целочисленного сбалансирования трехмерной матрицы и сетевая модель // Моделирование и анализ информационных систем. 2009. - Т. 16, № 3. - С. 70-76.
53. Смирнов A.B. Сравнительный анализ алгоритмов целочисленного сбалансирования матрицы // Материалы X Международногосеминара «Дискретная математика и ее приложения» (Москва, МГУ, 1-6 февраля 2010 г.). -М.: МГУ, 2010. С. 430-432.
54. Сосов E.H., Введение в метрическую геометрию. Часть 2. Некоторые приложения метрической геометрии. // Казань: Казанский гос. ун-т, 2008
55. Стечкин С.Б. Аппроксимативные свойства множеств в линейных нормированных пространствах// Rev. Roum. Math. Pur. et Appl.-1963.- Vol. 8,N 1.- P. 5-18.
56. Стрекаловский A.C., Васильев И.JI. Об одном подходе к решению квадратичной задачи о назначениях. // Тез. докл. конф. Математическое программирование и приложения. Екатеринбург, 1999.
57. Тихомиров В.М. Некоторые вопросы теории приближений. // М.: издательство МГУ, 1976.
58. Федотова Н.П. Гиперплоскости универсальной экстремали некоторых задач оптимизации. // Моделирование и анализ информационных систем. 2010. - Т. 17, № 3. - С. 91-106.
59. Федотова Н.П. О расстоянии до гиперплоскостей в симметрических нормах. // Ярославский педагогический вестник. Серия «Физико-математические и естественные науки» Вып.2. Ярославль, 2010, С.33-38.
60. Федотова Н.П. Об одном классе гиперплоскостей симметрических пространств. // Тр. 62 региональной науч.-техн. конф. «Молодежь,наука, инновации 2009», Ярославль.: Изд-во Ярославск. гос. ун-та,2009, С. 206.
61. Федотова Н.П. Об одном свойстве гиперплоскостей конечномерных пространств. // Тр. науч. конф. «Современные проблемы теории функций и их приложения», Саратов: Изд-во Саратовск. гос. ун-та,2010. С. 68-70
62. Харди Г.Г., Литлвуд Д.Е., Полиа Г. Неравенства // Перевод с английского. М.: ИЛ, 1948.
63. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974
64. Чаплыгина Н.Б. Задача о назначении минимальной стоимости среди равномерных назначений. // Вопросы теории групп и гомологической алгебры, Ярославль, ЯрГУ, 2003.
65. Чаплыгина Н.Б. Задача о равномерном назначении минимальной стоимости. // Труды V межд. конф. Дискретные модели в теории управления систем, Ратмина, 2003, С. 90-91.
66. Чаплыгина Н.Б. Оптимальный критерий равномерного назначения. // Тез. докл. XIII межд. конф. Проблемы теоретической кибернетики, Москва, 2002, С. 187.
67. Чаплыгина Н.Б. Расширенная задача о равномерном назначении минимальной стоимости. // Моделирование и анализ информационных систем. Ярославль, 2003, Т.11, №2, С. 20-30.
68. Чаплыгина Н.Б. Сравнение критериев равномерности в задаче о назначениях. // Математика. Материалы науч. конф. посвящ. 200-летию ЯрГУ им. П.Г. Демидова, Ярославль, 2003, С. 144-151.
69. Шилов Г.Е. Математический анализ (Специальный курс) // 2изд., М., 1961
70. Штойер Р. Многокритериальная оптимизация. Теория, вычисления и приложения. // М.: Радио и связь, 1992.
71. Lorentz G.G., Bernstein Polynomials. // Toronto: University of Toronto Press, 1953
72. Frederick A. Valentine, Convex Sets. // McGRAW-HILL SERIES IN HIGHER MATHEMATICS, Department of Mathematics University of California, Los Angeles.
