Введение к работе
Актуальность проблемы. Моделирование различных процессов с использованием случайных размещений вызывает все больший интерес в научных и технических кругах Это обусловлено бурным развитием криптографии, теории автоматов, потребностями физики элементарных частиц и математической статистики Постоянно совершенствуется вычислительная техника и возрастают вычислительные возможности, появляются новые, более эффективные численные методы Это позволяет строить сложные модели и решать задачи, которые ранее считались слишком трудоемкими При расчете процесса функционирования сложных систем иногда приходится делать упрощающие предположения, приводящие к схемам случайного размещения
Каждая схема случайного размещения частиц по ячейкам является моделью, которая может быть использована при решении некоторых задач физики, техники, биологии и пр. В последнее время появилось множество работ в области случайных размещений, в которых рассматривались различные схемы размещений и изучались случайные величины Самой простой и наглядной является так называемая "классическая задача о дробинках"
Эту задачу достаточно подробно изучали Р Мизес1, А Бекеши2, И Вейс3, А Реньи4
Равновероятная схема, на которой основана задача о дробинках, не может использоваться в достаточно обширном классе задач математиче-
Mises R. Uber Anfteilungs und Besetzungs — Wahrscheinlichkeiten / R Mises // Revu de la Faculte des Sciences de l'Umversite d'Istandbul N S 1939 Vol 4 P 145—163
Bekessy A On classical occupancy problems / A Bekessy // I Magy tud akad Mat kutato mt kozl 1963 Vol 8, № 1—2 P 59—71
Weiss I Limiting distributions in some occupancy problems / I Weiss // Ann Math Stat 1958 Vol 29, № З P 878—884
Renyi A. Three new proofs and generalization of a theorem of Irving Weiss / A Renyi // Magy tud akad Mat kutato int kozl 1962 Vol 7, № 1—2, P 203—214
ского моделирования В связи с этим повышенный интерес представляет более общая схема размещения — полиномиальная В данной схеме вероятности попадания в ячейку не меняются от опыта к опыту, но могут быть различными для каждой ячейки Значительная часть результатов, полученных до 1975 года для числа ячеек, содержащих ровно г частиц (величина цг), приведена в монографии В Ф Колчина, Б А Севастьянова, В.П. Чистякова5. Более поздние результаты содержатся в работах Г И Ивченко, В А Иванова, Ю И Медведева, В Г Михайлова и др
Необходимо подчеркнуть, что при рассмотрении различных схем размещения особое внимание авторов занимает нахождение закона распределения случайной величины либо выяснение его асимптотического поведения Но при решении ряда практических задач часто возникает необходимость построения таких моделей, в которых определенные случайные величины или их характеристики принимают экстремальные значения Надо отметить, что экстремальные задачи в теории случайных размещений почти не рассматривались, за исключением работ в которых исследовалось поведение максимального и минимального членов вариационного ряда, а также работ, где изучалось распределение максимального заполнения в выбраной схеме случайного размещения
Значительный интерес представляет задача нахождения таких параметров модели полиномиального размещения (набора вероятностей, с которыми размещаются частицы), при которых обеспечивается экстремальное значение Mfxr — математического ожидания величины цг
Несмотря на широкий спектр возможного применения, данная задача практически не была изучена
Постановка задачи принадлежит А М Зубкову Им же в работе6 со-
5) Колчин В.Ф Случайные размещения / В Ф Колчин, Б А Севастьянов, В П Чистяков М
Наука, 1976 224 с
6) Зубков А М Отношение частичного порядка, порожденное распределением числа занятых
ячеек /AM Зубков, Н Н Попов // Матем заметки 1982 Т 32, № 1 С 97—102
вместно с Н Н. Поповым в качестве следствия из основной теоремы отмечено, что число занятых ячеек в равновероятной схеме "стохастически больше" числа занятых ячеек в любой полиномиальной схеме с таким же числом ячеек и размещаемых частиц
Необходимость дальнейшего исследования проблемы и ее практическая значимость определили тематику данной диссертации
Цель работы. Основные цели диссертации
Исследование необходимого условия экстремума функции Mfir в полиномиальной схеме случайного размещения
Получение двусторонних оценок максимума функции М/лг
Рассмотрение одной модели размещения с вероятностями, изменяющимися в зависимости от состояния системы
Разработка и программная реализация метода численного поиска экстремума Его сравнение с классическими методами Проведение вычислительного эксперимента
Общая методика исследования основана на использовании аппарата математического анализа, теории вероятностей, методов поиска экстремума функции, теории комбинаторных полиномов и компьютерного моделирования
Научная новизна. Основные результаты работы являются новыми Впервые изучены экстремальные значения математического ожидания числа ячеек, содержащих ровно г частиц, в множестве полиномиальных моделей размещения те частиц по JV ячейкам Исследованы свойства распределений, на которых достигаются экстремальные значения, получены двусторонние оценки экстремальных значений Построены в явном виде В(г, 1,5г)-полиномы для г = 1,12 Поставлена и решена задача случайного блуждания с равновесными траекториями
Основные результаты, выносимые на защиту:
теорема о структуре набора вероятностей, при которых функция Мцг может достигать экстремума,
свойства "экстремальных распределений",
оценки для максимума функции Mfir;
метод численного поиска экстремума на основе комбинаторных полиномов,
критерии равновесности траекторий неоднородного по пространству дискретного случайного блуждания
Теоретическая и практическая значимость. Существует множество реальных процессов, математические модели которых сводятся к случайному размещению частиц по ячейкам Решение экстремальной задачи позволяет на основе известных параметров дать оценку неизвестному параметру размещения, например, по среднему значению наблюдаемой величины (лг и известному числу ячеек N можно ограничить с заданной вероятностью количество размещаемых частиц Кроме прикладного значения, полученные результаты представляют и теоретический интерес в плане дальнейшего развития методов оптимизации в теории случайных размещений
Личный вклад автора. Разработан метод оценивания неизвестных параметров полиномиальной схемы, исследована задача поиска экстремума величины M/Jbr, найдены методы поиска ее решений Разработан и обоснован численный метод нахождения решений задачи Все основные результаты, включенные в диссертацию, являются новыми и получены автором лично
Апробация работы. Основные результаты работы докладывались на ежегодных научно-теоретических конференциях молодых ученых
ИГУ (1999, 2000 и 2001 годах), на конференции, посвященной 275-летию Академии наук и памяти А И Кокорина (Иркутск, 1999), на XII Байкальской международной конференции " Методы оптимизации и их приложения" (Иркутск-Слюдянка, 2001), на второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе (Иркутск, 2003), на международной конференции "Колмогоров и современная математика" (Москва, 2003), на шестой Международной конференции "Вероятностные методы в дискретной математике" (Петрозаводск, 2004), на XIII Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск-Северобайкальск, 2005), на IV Всероссийской конференции "Математика, информатика, управление" (Иркутск, 2005)
Материалы диссертации докладывались и обсуждались на семинарах кафедры теории вероятностей и дискретной математики Иркутского государственного университета (1999—2007), кроме того, результаты обсуждались в отделе дискретной математики Математического института им В А Стеклова РАН
Публикации. По теме диссертации опубликовано 11 научных работ Наиболее значимые результаты, представленные в диссертации, опубликованы в работах [1]—[10] В число указанных работ входят 1 статья [1] из "Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2001—2007 гг.", 1 работа [2] из " Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2001—2006 гг " 1 статья [3] в научном сборнике, 1 депонированная статья [4], 3 полных текста докладов [5], [6], [7] в материалах международных конференций Работы [5], [8] выполнены в нераздельном соавторстве с научным руководителем Из совместной публикации [1] в диссертационную работу включены результаты, полученные автором самостоятельно и не затрагивающие интересы других соавторов
Структура и объем работы. Работа состоит из введения, трех глав, заключения, приложения и списка литературы Общий объем диссертации составляет 139 страниц, включая 16 рисунков Список литературы содержит 69 наименований
Похожие диссертации на Решение экстремальных задач при моделировании случайных размещений
