II. ИТОГИ НАУЧНЫХ ИССЛЕДОВАНИЙ
2.1. Важнейшие научные результаты
Для класса цепей Маркова, описывающих динамику изменения качественного или количественного состава биологических популяций, разработаны методы получения оценок для случайного времени попадания в поглощающее состояние (к.ф.-м.н. Клоков С.А., д.ф.-м.н. Топчий В.А.).
Для моделей динамики популяций с жестко фиксированным объемом и однополыми частицами разных типов, порождающих потомков своего типа, получена оценка среднего времени фиксации, то есть времени, когда все частицы станут однотипными. При этом все частицы имеют равные возможности, то есть распределение численности потомства и вероятность его отсутствия для всех частиц одинаковы. Фиксацию можно интерпретировать как момент времени, когда вся популяция будет состоять из родственников особи, тип которой случайно победил в процессе случайного биологического отбора. В общем случае формула достаточно сложна, но, если начать с N частиц разных типов, то время фиксации пропорционально объему популяции. Популяции с ограничениями на максимальную численность потомства и возможностью гибели особей, размножающихся независимо друг от друга частиц в каждый дискретный момент времени, с вероятностью единица вырождаются. Численное моделирование таких процессов для популяций среднего и большого размеров практически никогда не приводит к вырождению в силу того, что типичное время вырождения огромно, а также из-за накопления ошибок округления. При выполнении ряда конкретных условий получены экспоненциальные оценки для среднего времени вырождения в терминах стандартных характеристик ветвящихся процессов. Если допустить, что k – верхняя граница численности популяции или ее среднего, то доказано, что для некоторого числа q из интервала (0,1) среднее время вырождения процесса имеет порядок q-k.
Разработаны методы реализации OLAP-технологии на основе межмодельных преобразований данных (д.т.н. Зыкин С.В.).
Разработаны методы построения гиперкубического (многомерного) представления данных, которое является основой технологии оперативной аналитической обработки данных OLAP (online analytical processing). Предложена и исследована следующая последовательность преобразования данных: RDB -> TJ -> ST -> TJ -> RDB, где RDB - реляционная модель (исходная), TJ - модель 'таблица соединений' (промежуточная), ST - модель гиперкуба 'семантическая трансформация' (целевая). Для модели TJ получены и доказаны свойства, важные для построения преобразований. Разработаны алгоритмы преобразования, переводящие представление TJ к виду, эквивалентному представлению реляционной базы данных после выполнения базисных операций: дополнение, удаление и модификация кортежа. Для этих алгоритмов доказана корректность формирования результата и получены оценки вычислительной сложности, квазилинейные относительно количества кортежей в таблице соединений. Для модели ST получены образы ограничений целостности на данные (функциональные и многозначные зависимости) при их трансформации в гиперкуб. Разработан алгоритм представления формирования ST с использованием контекстных ограничений на данные. В дополнение к традиционным операциям для гиперкуба определен набор операций по модификации данных. Разработаны полиномиальные алгоритмы, реализующие эти операции для моделей ST и RDB.
Проведено исследование алгоритмов решения ряда задач оптимального размещения предприятий, основанных на использовании моделей целочисленного линейного программирования и декомпозиции Бендерса, получены оценки числа итераций и глубины отсечений, изучена проблема устойчивости алгоритмов, предложены и апробированы новые варианты алгоритмов (д.ф.-м.н. Колоколов А.А, к.ф.-м.н. Косарев Н.А.).
Задачи оптимального размещения предприятий имеют широкий круг приложений, возникающих при планировании и реконструкции производства, проектировании сетей обслуживания, в стандартизации и других областях. Значительный интерес к таким задачам связан также с трудностью их решения. Выполнено исследование алгоритмов решения ряда задач оптимального размещения предприятий, основанных на использовании моделей целочисленного линейного программирования и декомпозиции Бендерса. Найдены семейства указанных задач, позволившие получить оценки числа итераций алгоритмов и глубины отсечений, изучить влияние значений двойственных оценок, применяемых при построении отсечений, на эффективность алгоритмов. Выделен подкласс трудных задач, изучена проблема устойчивости рассматриваемых алгоритмов, разработаны новые варианты декомпозиционных алгоритмов и проведено их экспериментальное исследование.
|
