Введение к работе
Актуальность темы диссертации. При изучении различного рода математических моделей (физических явлений, технических систем, экономических процессов) важную роль играет понятие устойчивости. Модель предполагает упрощение реальности, поэтому качественные выводы, получаемые с помощью модели, должны быть устойчивыми по отношению к малым изменениям входных параметров. В технических системах часто требуется, чтобы алгоритм управления был устойчив к малым возмущениям параметров, поскольку резкие изменения в алгоритме управления могут оказаться весьма дорогостоящими (например, смена маршрутизации в сетях связи). Многие модели в той или иной форме используют принцип экстремальности. Это означает, что при моделировании возникают либо экстремальные задачи, либо задачи поиска решений систем равенств и неравенств. Условия устойчивости таких задач (множеств их решений) - традиционная область исследования в математике.
Данная диссертациоЕшая работа ориентирована на изучение моделей сетевых систем многих пользователей. Указанные модели возникают в результате явного учета инфраструктуры моделируемого объекта и применяются при решении большого числа практических задач, связанных с территориально распределенными пользователями (например, в энергетике, телефонии, транспорте,...). Необходимость выяснения устойчивости подобных задач в первую очередь объясняется тем, что входящие в модель параметры сильно агрегированы, а сами модели могут лишь качественно отражать реальные процессы.
При математическом описании сетевых систем достаточно распространены линейные модели, такой является базовая модель сети связи - многопродуктовая (МП-) сеть. Поэтому основное внимание 3 работе уделяется линейным моделям. Для линейных моделей — решения соответствующих оптимизационных задач являются полиэдральными множествами и их удобно представлять (хранить, запоминать) с помощью их крайних точек. Множество крайних точек также играет существенную роль в задачах многоэтапного проектирования или принятия решений на основе линейных моделей, в частности, в лексикографических и многокритериальных задачах линей-
ного программирования (ЛП). Кроме того, один из основных методов решения задач ЛП, симплекс-метод, в качестве решения выдает крайнюю точку. Отметим еще, что в случае неограниченности полиэдра общепринятые понятия устойчивости точечно-множественных отображений не применяются напрямую и тогда естественно исследовать устойчивость множества его крайних точек.
Однако, общие условия устойчивости множеств крайних точек полиэдров остались за рамками классических работ по устойчивости ЛП. Имеющихся результатов - об устойчивости крайних точек при возмущении лишь вектора правых частей - оказалось недостаточно для выяснения устойчивости экстремальных сетевых задач, в которых возмущениям могут подвергаться также некоторые элементы матрицы ограничений. Таким образом, представляется актуальной проблема выявления условий устойчивости множества крайних точек полиэдра и применения полученных условий для изучения конкретных сетевых моделей.
Цели диссертационной работы.
Разработка математического аппарата исследования устойчивости множества крайних точек полиэдра по отношению как к произвольным (сохраняющим свойство непустоты полиэдра) возмущениям матрицы и вектора правых частей, так и априорно ограниченным классам возмущений. Обоснование устойчивости по отношению к возмущениям входных параметров для ряда экстремальных задач на МП-сетях (включая многокритериальные задачи).
Результаты, выносимые на защиту.
-
Дана характеризация Липшиц-непрерывности многозначного отображения, которое матрице и вектору правых частей, задающих полиэдр, ставит в соответствие множество его крайних точек.
-
Исследована Липшиц-непрерывность соответствующего отображения для множеств эффективных и полуэффективных (слей-теровских) крайних точек в многокритериальном ЛП и обоснована устойчивость ряда задач векторной оптимизации на МП-сетях.
-
Доказана устойчивость по отношению к возмущениям входных параметров лексикографической максиминной задачи анализа предельных возможностей МП-сети по обеспечению требований пользователей.
Методы исследования, применяемые в работе, используют математический аппарат теории исследования операций, теорию численных методов оптимизации, выпуклый анализ, линейную алгебру.
Обоснованность научных положений. Теоретические положения и выводы диссертации сформулированы в виде лемм и теорем и строго доказаны. Предложенные методы апробированы на тестовых задачах.
Научная новизна работы. Простейшие примеры показывают, что устойчивость полиэдра не гарантирует устойчивости множества его крайних точек по отношению к возмущениям матрицы ограничений. Как постановка задачи так и полученные условия устойчивости для крайних точек полиэдра по отношению к указанным возмущениям являются новыми. Кроме того, традиционно в работах по устойчивости ограничиваются компактными множествами, а проведенное рассмотрение учитывает возможность неограниченности полиэдра.
В работе впервые доказано, что Липшиц-полунепрерывность сверху (снизу) многозначного отображения, которое матрице и вектору правых частей, задающих полиэдр, ставит в соответствие множество его крайних точек, эквивалентна полунепрерывности сверху (снизу) этого отображения.
Для содержательного класса многопродуктовых сетевых задач, являющегося специальным подклассом линейных лексикографических задач, в общем случае неустойчивых, доказана Липшиц-полунепрерывность сверху многозначного отображения, сопоставляющего входным параметрам множество оптимальных крайних точек в этой задаче.
Практическая ценность работы. Полученные в диссертации результаты с одной стороны подтверждают адекватность рассматриваемых сетевых моделей для анализа предельных функциональных возможностей МП-сетей. С другой стороны они могут служить обоснованием корректности правил распределения многопродуктового потока в сети, получаемых в результате решения соответствующих экстремальных задач. Для решения задач о допустимости и лексикографического максиминного анализа МП-сети применимы алгоритмы, описываемые в работе. Ряд результатов диссертации включен в научные отчеты ВЦ РАН по темам НИР "ТРАКТ-ВЦ", 1992-93
гг. и "ДОВЕРИЕ-РАН", 1994 г., а также используется в работе по проекту РФФИ N.95-01-00232a.
Апробация работы. Основные результаты диссертации докладывались на научно-исследовательских семинарах ИПУ и ВЦ РАН, факультета ВМиК МГУ.
Публикации. По материалам диссертационной работы опубликовано 5 печатных работ.
Структура и объем работы. Диссертация состоит из введения, двух глав (в 1-й - 8, а во 2-й - 6 параграфов), приложений А и Б и списка литературы. Содержит 96 страниц текста, включая приложения и список литературы из^^наименований.
Похожие диссертации на Условия устойчивости множества крайних точек полиэдра и их применение для исследования многопродуктовых сетевых моделей
