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

АКТУАЛЬНОСТЬ ТЕМЫ

.

В практике экономико-математического моделирования часто встречаются задачи, при решении которых приходится учитывать большое число взаимосвязанных факторов, включая плохо формализуемые [16, 21, 22, 25]. Процесс решения плохо формализуемой задачи включает в себя преобразование ее формулировки путем уточнений и упрощений. В результате этого процесса мы получаем формализованную задачу, имеющую некоторое отношение к исходной постановке задачи. Во многих случаях удается построить формализованную задачу в виде задачи линейного программирования [7, 12, 14, 18, 52]. Однако решение формализованной задачи может сколь угодно сильно отличаться от решения исходной задачи в силу наличия неформализованных ограничений.

Помимо формальных методов и моделей для решения плохо формализуемой задачи используются средства неформального анализа, включающие в себя суждения экспертов для учета так называемых «внемодель-ных» факторов [26, 51]. При этом человеческий компонент в процессе экспертизы может постепенно, с помощью обучения, заменяться машинным компонентом путем использования экспертных систем [8, 36, 54] или ней-росетевых программ [28, 29, 30, 63, 64]. Однако при решении задач линейного программирования большой размерности эти подходы могут оказаться неэффективными, если их применять для решения всей задачи в целом. Это объясняется тем, что трудно адекватно настроить (обучить) экспертную систему или нейронную сеть в случае, когда система ограничений содержит тысячи линейных неравенств и десятки тысяч переменных. В таких ситуациях перспективным является подход, основанный на сочетании методов линейной оптимизации с процедурами экспертного оценивания. Алгоритм решения задачи в этом случае строится как итерационный процесс, в ходе которого шаг за шагом происходит уточнение ограничений, относящихся к неформализованной части задачи. Приближенные решения исходной задачи, получаемые в ходе итерационного процесса, формируют множество образцов, квалифицируемых экспертом. Применяя к этому множеству образцов процедуру дискриминантного анализа [23, 32, 37, 66, 71], мы получаем разделяющую поверхность, аппроксимирующую неформализованные ограничения.

В соответствии с этим актуальной является задача разработки, анализа и реализации на ЭВМ алгоритмов решения задач линейного программирования с неформализованными ограничениями путем синтеза методов дискриминантного анализа и линейной оптимизации.

ЦЕЛЬ И ЗАДАЧИ ИССЛЕДОВАНИЯ

.

Цель данной работы состояла в разработке и исследовании методов и алгоритмов решения задач линейного программирования с неформализованными ограничениями и их реализации в виде программного комплекса. Для достижения этой цели необходимо было решить следующие задачи:

1. Построить математическую модель задачи линейного программирования с неформализованными ограничениями (ЛПНО) и описать общий подход к ее решению.

2. На базе данного подхода разработать метод решения задачи ЛПНО, допускающий реализацию в виде алгоритма для ЭВМ, и исследовать сходимость этого метода.

3. На основе описанного метода разработать и исследовать алгоритм ЛП-ДА (Линейное Программирование — Дискриминантный Анализ), соединяющий алгоритмы линейного программирования с алгоритмами дискриминантного анализа.

4. Спроектировать и реализовать программный комплекс для решения задач ЛПНО, использующий предложенные методы и алгоритмы.

5. Провести вычислительные эксперименты для анализа эффективности предложенного подхода.

6. Разработать и реализовать параллельную версию алгоритма ЛП-ДА. Провести вычислительные эксперименты на кластерной системе для исследования ускорения и расширяемости параллельного алгоритма.

МЕТОДЫ ИССЛЕДОВАНИЯ.

В исследованиях, проводимых в диссертационной работе, используется аппарат теории математического программирования и распознавания образов, применяются методы дискриминантного анализа и линейной оптимизации.

НАУЧНАЯ НОВИЗНА.

Научная новизна работы заключается в следующем:

1. предложен метод решения задачи линейного программирования с неформализованными ограничениями, базирующийся на синтезе методов дискриминантного анализа и методов линейной оптимизации, и доказана сходимость генерируемой им итерационной последовательности к точному решению задачи ЛПНО;

2. предложен оригинальный метод осцилляций, позволяющий существенно ускорить сходимость последовательности приближений к точному решению задачи ЛПНО;

3. разработан новый алгоритм, соединяющий симплекс-метод и метод линейной коррекции, и предложена его параллельная версия;

4. выполнена реализация алгоритма решения задач ЛПНО в виде программного комплекса для персональных компьютеров и многопроцессорных систем на основе стандарта МР1−2.

ТЕОРЕТИЧЕСКАЯ И ПРАКТИЧЕСКАЯ ЦЕННОСТЬ.

Теоретическая ценность работы состоит в том, что в ней представлены доказательства теоремы об устойчивости задачи линейного программирования по неформализованному ограничению и теоремы о сходимости метода, соединяющего дискриминантный анализ и рандомизацию с линейной оптимизацией. Практическая ценность работы заключается в том, что предложенный программный комплекс в сочетании с системами экспертного оценивания может быть использован для решения плохо формализуемых задач, возникающих в экономико-математическом моделировании.

СТРУКТУРА И ОБЪЕМ РАБОТЫ.

Диссертация состоит из введения, четырех глав, заключения, библиографии и приложения, в котором приводятся основные обозначения, используемые в диссертационной работе. Объем диссертации составляет 92 страницы, объем библиографии — 77 наименований.

Основные результаты диссертации полностью опубликованы в следующих печатных работах.

1. Соколинская И. М. Синтез симплекс-метода и метода линейной коррекции в задачах линейной оптимизации с неформализованными ограничениями // Вычислительные методы и программирование. -2005. -Том 6, № 2.-С. 103−115.

2. Mazurov Vl.D., Sokolinskaya I.M. Discrimination analysis and randomization in linear optimization problems with not formalized restrictions // Pattern Recognition and Image Analysis. -2006. -Vol. 16, No. 2. -P. 170−178.

3. Соколинская И. М. Метод осцилляций в задачах линейного программирования с неформализованным ограничением // Алгоритмический анализ неустойчивых задач: Тез. докл. Всерос. науч. конф. (2−6 февраля 2004 г., Екатеринбург). -Екатеринбург: Изд.-во Урал, ун-та. -2004.-С. 302−303.

4. Соколинская И. М., Соколинский Л. Б. Программный комплекс для решения задач линейного программирования с неформализованными ограничениями // Первая Международная Конференция «Системный Анализ и Информационные Технологии» САИТ-2005 (12−16 сентября 2005 г., Переславль-Залесский, Россия): Труды конференции. В 2 т. Т. 2. -М.: КомКнига. -2005. -С. 286−292.

5. Соколинская И. М., Соколинский Л. Б. Параллельный алгоритм решения задачи линейного программирования с неформализованными ограничениями // Проблемы оптимизации и экономические приложения: Тезисы докладов международной конференции. -Омск: Омск. гос. ун-т. -2006. -С. 1.

АПРОБАЦИЯ РАБОТЫ.

Основные положения диссертационной работы, разработанные модели, методы, алгоритмы и результаты вычислительных экспериментов докладывались автором на следующих международных и всероссийских научных конференциях: на Всероссийской научной конференции «Алгоритмический анализ неустойчивых задач» (2−6 февраля 2004 г., Екатеринбург) — на Международной научной конференции «Системный Анализ и Информационные Технологии» САИТ-2005 (12−16 сентября 2005 г., Пе-реславль-Залесский) — на III Всероссийской научной конференции «Проблемы оптимизации и экономические приложения» (Омск, 11−15 июля 2006 г.).

НАПРАВЛЕНИЯ ДАЛЬНЕЙШИХ ИССЛЕДОВАНИЙ.

Теоретические исследования и практические разработки, выполненные в рамках этой диссертационной работы, предполагается продолжить по следующим направлениям.

1. Доказательство сходимости представленного в данной диссертации алгоритма? при более слабых ограничениях. В частности, может быть сформулирована гипотеза о том, что теорема сходимости для алгоритма? остается справедливой и в случае устранения условия нормализации. В пользу этой гипотезы свидетельствуют теорема 3 (см. раздел 1.6 диссертации) и проведенные в ходе диссертационного исследования эксперименты на реальных и искусственных задачах (см. главу 4 диссертации), так как во всех экспериментах был использован вариант алгоритма без условия нормализации.

2. Создание версии программного комплекса для 64-разрядных процессоров. Здесь основной проблемой является подбор оптимальных значений допусков, связанных с преодолением ошибок округления.

3. Создание в рамках программного комплекса альтернативных блоков для решения задач линейного программирования и дискриминантно-го анализа (в дополнение к симплекс-методу и методу линейной коррекции предполагается реализовать методы фейеровского типа [2, 3, 9, 10] и метод комитетов [20, 26, 27, 46]).

ЗАКЛЮЧЕНИЕ

.

В диссертационной работе были рассмотрены вопросы, связанные с решением задач линейного программирования при наличии неформализованных ограничений. Было показано, что задачу с несколькими неформализованными ограничениями можно свести к задаче с одним неформализованным ограничением. Предложен общий метод для решения задач с одним неформализованным ограничением, базирующийся на дискриминантном анализе и экспертизе новых образцов, получаемых в результате решения задачи линейного программирования. Каждый новый образец получается как решение аппроксимационной задачи линейного программирования, где вместо неформализованного ограничения фигурирует неравенство на основе разделяющей функции. В случае, когда решение аппроксимационной задачи уже присутствует в наборе образцов, применяется процедура рандомизации. Для описанного метода была доказана теорема сходимости и рассмотрены вопросы его практической реализации. В качестве реализации общего метода предложен итерационный алгоритм ЛП-ДА для решения задач линейного программирования при наличии нескольких неформализованных ограничений. Этот алгоритм базируется на сочетании симплекс-метода и метода линейной коррекции. Рассмотрены различные аспекты реализации алгоритма ЛП-ДА в виде программы для ЭВМ. Предложена параллельная версия алгоритма. Выполнены проектирование и реализация программного комплекса на языке Си и проведено большое количество вычислительных экспериментов на реальных и искусственных задачах, подтверждающих эффективность предложенных подходов.

Работа выполнялась при поддержке Российского фонда фундаментальных исследований (проекты 03−01−565, 06−01−380).

В заключение перечислим основные полученные результаты диссертационной работы, приведем данные о публикациях и апробациях, и рассмотрим направления дальнейших исследований в данной области.