Синтез методов оптимизации и дискриминантного анализа в математических моделях экономики

• Автор: Соколинская, Ирина Михайловна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Челябинск
• Количество страниц: 92 с. : ил.

ОГЛАВЛЕНИЕ
Введение

Глава 1. Синтез дискриминантного анализа и линейной оптимизации

1.1. Математическая модель задачи ЛПНО.

1.2. Общий метод решения задачи ЛПНО.

1.3. Устойчивость задачи ЛПНО

1.4. Алгоритм порождения образцов

1.5. Теорема сходимости для алгоритма

1.6. Реализационные аспекты алгоритма

1.7. Случай нескольких неформализованных ограничений.

Глава 2. Алгоритм ЛПДА

2.1. Общая схема алгоритма ЛПДА.
2.2. Формирование начального набора образцов.
2.3. Критерий завершения итерационного процесса
2.4. Рандомизация
2.5. Метод осцилляций
2.6. Проблема погрешности вычислений.
Глава 3. Программный комплекс ЛПДА
3.1. Модульная структура комплекса.
3.2. Формат входных данных ЬРНС
3.3. Параллельная реализация.
3.3.1. Классификация параллельных методов решения задачи ЛПНО
3.3.2. Параллельная версия алгоритма ЛПДА
3.4. Реализация прототипа
Глава 4. Компьютерный анализ алгоритма ЛПДА.
4.1. Эксперименты на искусственных задачах.
4.1.1. Модельная задача Мосп
4.1.2. Влияние радиуса рандомизации на эффективность
4.1.3. Влияние хмощности рандомизации на эффективность.
4.1.4. Эффективность метода осцилляций.
4.1.5. Эксперименты с неполными наборами образцов
4.2. Эксперименты на реальной задаче
4.3. Масштабируемость параллельного алгоритма.
Заключение
Литература


Помимо формальных методов и моделей для решения плохо формализуемой задачи используются средства неформального анализа, включающие в себя суждения экспертов для учета так называемых «внемодель-ных» факторов [, ]. При этом человеческий компонент в процессе экспертизы может постепенно, с помощью обучения, заменяться машинным компонентом путем использования экспертных систем [8, , ] или ней-росетевых программ [, ,, ,]. Однако при решении задач линейного программирования большой размерности эти подходы могут оказаться неэффективными, если их применять для решения всей задачи в целом. Это объясняется тем, что трудно адекватно настроить (обучить) экспертную систему или нейронную сеть в случае, когда система ограничений содержит тысячи линейных неравенств и десятки тысяч переменных. В таких ситуациях перспективным является подход, основанный на сочетании методов линейной оптимизации с процедурами экспертного оценивания. Приближенные решения исходной задачи, получаемые в ходе итерационного процесса, формируют множество образцов, квалифицируемых экспертом. Применяя к этому множеству образцов процедуру дискриминантного анализа [, , , , ], мы получаем разделяющую поверхность, аппроксимирующую неформализованные ограничения. В соответствии с этим актуальной является задача разработки, анализа и реализации на ЭВМ алгоритмов решения задач линейного программирования с неформализованными ограничениями путем синтеза методов дискриминантного анализа и линейной оптимизации. Цель данной работы состояла в разработке и исследовании методов и алгоритмов решения задач линейного программирования с неформализованными ограничениями и их реализации в виде программного комплекса. Построить математическую модель задачи линейного программирования с неформализованными ограничениями (ЛПНО) и описать общий подход к ее решению. На базе данного подхода разработать метод решения задачи ЛПНО, допускающий реализацию в виде алгоритма для ЭВМ, и исследовать сходимость этого метода. На основе описанного метода разработать и исследовать алгоритм ЛП-ДА (Линейное Программирование - Дискриминантный Анализ), соединяющий алгоритмы линейного программирования с алгоритмами дискриминантного анализа. Спроектировать и реализовать программный комплекс для решения задач ЛПНО, использующий предложенные методы и алгоритмы. Провести вычислительные эксперименты для анализа эффективности предложенного подхода. Разработать и реализовать параллельную версию алгоритма ЛП-ДА. Провести вычислительные эксперименты на кластерной системе для исследования ускорения и расширяемости параллельного алгоритма. В исследованиях, проводимых в диссертационной работе, используется аппарат теории математического программирования и распознавания образов, применяются методы дискриминантного анализа и линейной оптимизации. МР1-2. Теоретическая ценность работы состоит в том, что в ней представлены доказательства теоремы об устойчивости задачи линейного программирования по неформализованному ограничению и теоремы о сходимости метода, соединяющего дискриминантный анализ и рандомизацию с линейной оптимизацией. Практическая ценность работы заключается в том, что предложенный программный комплекс в сочетании с системами экспертного оценивания может быть использован для решения плохо формализуемых задач, возникающих в экономико-математическом моделировании. Диссертация состоит из введения, четырех глав, заключения, библиографии и приложения, в котором приводятся основные обозначения, используемые в диссертационной работе. Объем диссертации составляет страницы, объем библиографии - наименований. Первая глава, «Синтез дискриминантного анализа и линейной оптимизации», посвящена описанию и исследованию общего метода решения задач ЛГ1НО, сочетающего дискриминантный анализ, линейную оптимизацию и рандомизацию. Строится общая математическая модель задачи и процесса нахождения ее приближенного решения. Доказывается теорема об устойчивости задачи линейного программирования по неформализованному ограничению. Эта теорема играет важную роль при решении проблемы сходимости. Далее описывается алгоритм получения новых образцов, служащих основой итерационного процесса.