Решение экстремальных задач при моделировании случайных размещений

• Автор: Гильманшин, Роман Ралифович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Иркутск
• Количество страниц: 139 с. : ил.

Оглавление
Введение

Глава I. Экстремальная задана в полиномиальной схеме

1. Задачи случайных размещений, приводящие к поиску экстремума функции i.

2. Постановка задачи

3. Вид набора вероятностей i, .,рлг

4. Необходимое условие экстремума функции Мцг

5. Верхняя и нижняя оценки максимума целевой фунющи . .

6. Решение задачи на минимум для Мцг и нахождение максимума для некоторых частных случаев.
7. Исследование фзчшции Млг х на границе и в точке, соответствующей равновероятному набору.

8. Некоторые свойства функций и Фгг

9. Интервал, содержащий критические точки целевой функции . Исследование количества решений уравнения в необходимом условии экстремума.
. Исследование вида решения задачи по графикам функций
4, Фг
. Задачи с большим числом размещаемых частиц или ячеек .
Глава П. Численные методы решения экстремальной задачи
1. Поиск пар точек, в которых Ф принимает равные значения
2. Применение комбинаторных полиномов для отыскания
обратной функции.
3. Локализация корней с помощью функции фг.
4. Некоторые численные методы нахождения решении
5. Алгоритм решения экстремальной задачи.
Глава III. Случайные блуждания на прямой с равновесными
траекториями
1. Принятые понятия и обозначения
2. Постановка задачи
3. Число траекторий из множества Тпк.
4. Критерий равновесности
5. Существование равновесных траекторий
6. Асимптотика Рпк.
Заключение
ПРИЛОЖЕНИЕ 1.
1. Таблицы значений максимума функции Мх.
2. Графики функции Мх

Введение
Актуальность


Материалы диссертации докладывались и обсуждались на семинарах кафедры теории вероятностей и дискретной t математики Иркутского государственного университета (—), кроме того, результаты обсуждались в отделе дискретной математики Математического института им. В.А. Стеклова РАН. Публикации. По теме диссертации опубликовано научных работ. Наиболее значимые результаты, представленные в диссертации, опубликованы в работах []—[], []—[]. Перечня ведущих рецензируемых журналов и изданий ВЛК РФ — гг. Перечня ведущих рецензируемых журналов и изданий ВАК РФ — гг. Работы [], [] выполнены в нераздельном соавторстве с научным руководителем. Из совместной публикации [] в диссертационную работу включены результаты, полученные автором самостоятельно и не затрагивающие интересы других соавторов. Структура и объем работы. Работа состоит из введения, трех глав, заключения, приложения и списка литературы. Общий объем диссертации составляет 9 страниц, включая рисунков. Список литературы содержит . Автор искренне благодарен к. H.A. Колокольниковой за руководство ходом исследований, а также выражает признательность зав. МИ РАН. А.М. Зубкову за постам новку задачи и интерес к ходу ее решения. Во введении обосновывается актуальность темы диссертации, се научная новизна и практическая ценность. Первая глава посвящена всестороннему изучению особенностей задачи отыскания экстремума математического ожидания величины дт. В §1 указываются задачи, решение которых требует нахождения макси-мума функции . I . Обозначим цг — Цг(рь ^^^,pN1n,N) число ячеек, содержащих ровно г частиц, г = 1,7? Требуется найти такие наборы вероятностей для которых математическое ожидание Мрг принимает экстремальное значение. В §3 показано, что экстремум функции Мрг(р, п, IV) достигается только тогда, когда набор вероятностей состоит из двух значений. Параграф 4 посвящен нахождению необходимого условия экстремума. На этом результате базируется исследование экстремальной задатш. Доказано, что полином в необходимом условии в общем случае неразрешим в радикалах, следовательно, продолжать поиск решения имеет смысл численными методами. Для величин, нахождение которых представляет большую вычислительную сложность или для которых трудно найти аналитический вид, часто применяют двусторонние оценки. Такие оценки для шах Мрг получены в §5. Исследуемая экстремальная задача, как и большинство трудных задач, имеет частные случаи, для которых сразу можно получить решения. Такие случаи разбираются в §6. Там же решается задача поиска минимума для общего случая. Дальнейший интерес представляет только проблема поиска максимума функции математического ожидания. Вследствие того что поиск максимума ведется на отрезке, необходимо не только найти все критические точки, но и рассмотреть значение целевой функции на границе. Целевая функция в этих точках рассмотрена в §7. Как было отмечено ранее, исследование необходимого условия экстремума является основополагающим в данной работе, поэтому возникает необходимость в детальном изучении функций, фигурирующих в этом условии, что и сделано в §8. Используя полученную информацию о свойствах этих функций, можно уменьшить интервал, содержащий критические точки целевой функции, и, тем самым, отбросить промежутки, которые заведомо не содержат искомых точек. Как это сделать, показаг но в §9. В § доказано, что при достаточно большом количестве размещаемых частиц существует ровно три критические точки, причем одна из них соответствует равновероятному набору. Найдены отрезки, на которых они находятся. Графический метод определения количества критических точек и их характера описан в §. Предложенным методом иногда удается локализовать глобальный максимум. Рассмотрение в § задач с большим числом ячеек или большим числом размещаемых частиц, завершает главу. Во второй главе разрабатывается численный метод, применимый, в частности, для поиска решения рассматриваемой экстремальной задачи. Для оценки эффективности предложенного метода в качестве сравнения используются известные алгоритмы оптимизации. В §1 определяется функция ф(г), используемая для тшслеиного поиска решения. Метод нахождения обратной функции с помощью В-полинохмов, предложенный Селивановым описан в [].