Актуальность.
Проблема принятия решений (ПР) постоянно возникает перед человеком как в повседневной жизни, так и в управлении производством, бизнесом, финансами и т. п. В повседневной жизни выбор нередко производится почти автоматически — интуитивно в силу простоты и повторяемости задачи ПР. Однако в управлении человек часто не может сразу принять решение, сомневается либо желает прибегнуть к помощи специалиста. Если в повседневной жизни ошибки в выборе решений могут не иметь существенного значения, то в производственной сфере они могут привести к различного рода потерям или даже катастрофам. Поэтому необходимо принятие решений, обоснованных обстоятельным изучением и анализом различных вариантов с оценкой последствий их реализации. Человек вручную не в состоянии произвести подобные исследования.
Опыт практического использования вычислительной техники в научных исследованиях и производстве показывает, что компьютеры могут быть с успехом применены в задачах анализа решений. Компьютеры дают возможность рационального объединения логического мышления и интуиции человека со строгими математическими методами и возможностью выполнения большого объема вычислений с целью существенного увеличения вероятности принятия оптимальных решений.
Таким образом, возникает проблема разработки и внедрения программных систем, обеспечивающих поддержку лицу, принимающему решения, (ЛПР) на этапах сбора и хранения больших объемов информации, обработки полученной информации с использованием различных методов принятия решений в зависимости от класса поставленной задачивыбора оптимальной альтернативы и выдачи рекомендаций по реализации полученного решения. Подобные системы получили название систем принятия решений (СППР).
Многие практические задачи могут быть формализованы в форме задач линейного программирования. В настоящее время теория классического линейного программирования хорошо разработана и реализована в различных программных системах. Однако в связи с недостатком информации, большой сложностью или самой сутью проблемы может оказаться невозможно точно опеределить значения части параметров задачи и применение аппарата линейного программирования оказывается невозможным. Для решения задач в условиях неопределенности хорошо зарекомендовал себя математический аппарат теории возможностей. Вот что говорит об этом создатель теории нечетких множеств Лотфи Заде:
Я считаю, что излишнее стремление к точности стало оказывать действие, сводящее на нет теорию управления и теорию систем, так как оно приводит к тому, что исследования в этой области сосредоточиваются на тех и только тех проблемах, которые поддаются точному решению. В результате многие классы важных проблем, в которых данные, цели и ограничения являются слишком сложными или плохо определенными для того, чтобы допустить точный. математический анализ, оставались и остаются в стороне по той причине, что они не поддаются математической трактовке. Для того, чтобы сказать что-либо существенное для проблемм подобного рода, мы должны отказаться от наших требований точности и допустить результаты, которые являются несколько размытыми или неопределенными" .
Одним из основных недостатков существующего аппарата возможност-ного программирования до настоящего времени является отсутствие методов, позволяющих проводить коррекцию задач, которые в исходной постановке не имеют решения. Разработка и реализация таких методов позволит существенно расширить круг практических задач, решаемых в рамках возможностного программирования. На решение этих задач направлено диссертационное исследование.
Методы решения задач возможностного программирования разрабатывались в работах Язенина А. В. и других авторов. Однако для их широкого применения необходима разработка соответствующего программного обеспечения. Это требует дополнительного исследования и спецификации разработанных методов и реализации на их основе систем поддержки принятия решений. Это вторая цель диссертационного исследования.
Обзор литературы.
Теория несобственных задач математического программирования является хорошо изученной. Из большого числа работ, посвященной данной тематике, в первую очередь следует отметить общепринятые монографии А. Н. Тихонова, В. Я. Арсенина [62], В. К. Иванова, В. В. Васина, В. П. Танана [27], а также монографии С. А. Ашманова [6], Ф. П. Васильева, А. Ю. Иваницкого [13], В. В. Васина и A. J1. Агеева [14], Е. Г. Голыптейна и Д. Б. Юдина [15], И. И. Еремина [22], В. А. Морозова [40], А. Н. Тихонова [60].
Развитие теории нечетких множеств положила работа «Fuzzy Sets» профессора Калифорнийского университета Лофти А. Заде [121]. В этой работе Заде расширил классическое понятие множества, допустив, что характеристическая функция может принимать значения в интервале [0,1]. Такие множества Заде назвал нечеткими (fuzzy). Заде были введены ряд операций над нечеткими множествами, понятие лингвистической переменной.
Дальнейшие развитие теории нечетких множеств и ее применение для моделирования неопределенности привело к появлению, в частности, теории возможностной оптимизации. Первой работой в этой области стала работа профессоров Белмана и Заде «Decision making in fuzzy environment» [88]. В этой работе были обозначены такие научные направления, как нечеткое математическое программирование, нечеткое динамическое программирование, многокритериальная нечеткая оптимизация и другие. Достаточно полный обзор теории и практики нечеткой оптимизации может быть найден в работе М.К. Luhandjula [105]. Работы H.J. Zimmerman [123], [124] могут быть названы основопологающими. Наряду с уже перечисленными, также могут быть названы работы J.J. Buckley [89], Д. Дюбуа и А. Прада [93], Н. Tanaka и К. Asai, [115], А. В. Язенина и М. Wagenknecht [119].
Непрямые методы возможностной оптимизации были разработаны.
A.В. Язениным в работах [80] - [84], [116], [118] а также в совместной с М. Wagenknecht работе [119]. Эти методы основаны на построении эквивалентных детерминированных аналогов исходных задач.
В соответствии со сложившимся подходом к исследованию задач линейного программирования, следующим шагом является исследование их устойчивости. Этой схеме придерживаются и в возможностной оптимизации. В работах R. Fuller [95], [96], [97] заложены основы этих исследований. Дальнейшее исследование вопросов было продолжено в работах.
B.А. Рыбкина и А. В. Язенина. Основными из них являются: [52], [50], [113]. В них, в возможностном контексте, исследована слабая и сильная устойчивость задач нечеткого линейного программирования и получены методы их регуляризации.
Следующим шагом в традиционном подходе к исследованию задач линейного программирования является разработка методов коррекции несобственных задач. Этому вопросу посвящена статья Weldon Lodwick [102]. В ней исследуется задача возможностной линейной оптимизации при фиксированных уровнях возможности выполнения ограничений. Известными методами для нее строится эквивалентная задача интервального программирования. Для этой системы Lodwick использует понятия оптимистического и пессимистического набора ограничений, а также определяет понятия слабой и сильной избыточности возможностных ограничений.
В этой статье автором получены также необходимые и достаточные условия слабой и сильной избыточности для ограничений рассматривавмой системы возможностных неравенств. В данной диссертационной работе этот подход полуил дальнейшее развитие. Соответствующие результаты получены для ограничений типа равенств. Наряду с системами возможностных ограничений в диссертации исследуется также и системы снеоб-ходимостных ограничений. Современный подход к моделированию неопределенности предполагает исследования задачи в двойственном контексте. Lodwick также исследует дополнительные ограничения, которые накладывает структура системы ограничений на переменные, строки и столбцы системы. Также рассмотрено, как понятие двойственности может быть применено к задаче линейного возможностного программирования.
Тем не менее ряд вопросов остается открытым. Здесь наиболее важными нам представляется исследование корректности системы ограничений в зависимости от требования на уровень возможности (необходимости) их выполнения. Стоит отметить, что в работе Lodwick исследованы лишь отдельные ограничения системы. Однако практика принятия решений требует исследования корректности всей системы ограничений. Этим и определяются цели и задачи диссертационного исследования.
Цель работы.
Целью работы является исследование корректности задач возможност-ной оптимизации и разработка программного комплекса их поддержки.
В рамках диссертационного исследования, актуальность которого показана выше, проводится исследование структуры систем ограничений задач возможностной оптимизации. Под исследованием структуры системы ограничений понимается:
• нахождение избыточных ограничений;
• нахождение несовместных ограничений;
• нахождение максимальных уровней возможности (необходимости) при которых система ограничений будет совместна.
Для несовместных ограничений исследуется возможность коррекции исходной постановки задачи путем снижения уровня возможности (необходимости) выполнения ограничений.
Разработанные методы коррекции задач возможностного программирования реализуются в системе поддержки принятия решений.
Основные задачи.
Сформулированная цель диссертационного исследования достигается путем решения следующего ряда задач:
• установление необходимых и достаточных условий избыточности ограничений задач возможностного программирования;
• установление необходимых и достаточных условий несовместности ограничений задач возможностного программирования;
• исследование влияния изменения возможности (необходимости) выполнения ограничения на совместность систем возможностных ограничений;
• обоснование методов поиска максимального уровня возможности (необходимости) выполнения отдельного ограничения, обеспечивающего совместность системы возможностных ограничений;
• разработка модели нахождения недоминируемого вектора возможности, обеспечивающего совместность системы возможностных ограничений контексте задачи векторной оптимизации;
• реализация методов коррекции, основанных на понижении уровней возможностей (необходимостей) выполения ограничений, в качестве модуля программной системы поддержки принятия решений.
Методика исследования.
Для формального описания изучаемого класса задач используется математический аппарат современной теории возможностей, при доказательстве теорем используются методы возможностной оптимизации, математического программирования, математического и функционального анализа. Методологическую основу исследования составляют результаты классической теории корректности задач оптимизации и векторной оптимизации. При разработке програмной системы использовались высокоуровневые методы программирования, включая объектно-ориентированное программирование.
Практическая значимость работы.
Полученные методы коррекции систем возможностных ограничений позволяют расширить класс задач, решаемых в рамках методов возмож-ностного программирования. Разработанная в ходе работы над диссертацией система поддержки принятия решений может быть применена для решения задач производственного планирования, портфельного анализа и т. д.
Внедрение результатов работы.
Проведенные научные исследования поддержаны грантами РФФИ, проекты № 02−01−1 137, № 04−01−96 720. Результаты диссертации внедрены в учебный процесс на факультете прикладной математики и кибернетики Тверского государственного университета, в качестве программной составляющей учебно-методического комплекса по дисциплине «Теория неопределенностей» .
Апробация.
Основные результаты работы докладывались автором на 2-ом международном научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2003 год), на семинарах в ТвГУ, ВЦ РАН.
Структура работы и ее содержание.
Диссертация состоит из введения, четырех глав, заключения и библиографии.
4.7 Выводы по главе 4.
В ходе работы над диссертацией была разработана система поддержки принятн и я решений FIESTA. OX1IIР Fiesta основана на методах возможностной оптимизации, в ней реализованы методы, описанные в диссертационной работе.
СППР FIESTA построена с использованием объектно-ориентирован ной архитектуры, что позволяет расширять ее возможности в случае необходимости.
Интерфейс СППР FIESTA выполнен в знакомом большинству пользователей стиле и позволяет настроить режим отображения/ввода информации в зависимости от степени квалификации пользователя.
Система поддержки принятия решений FIESTA может быть использована для поддержки принятия решений при решении задач производственного планирования, в качестве интеллектуального компонента САПР при.
Недоминируемые уровни совместности — коэффициенты важности.
X].
Введите коэффициенты важности:
Ограничение Важность.
Огр 1 пПЛ).
0гр2 п (2,1].
0гр3 п (1.5.1] Й зменить!] Назад.
Далее >
Отмена.
Рис. 4.37: Ввод нечетких коэффициентов важности недоминируемые уровни совместности — параметры алгоритма.
Выберите алгоритм: Генетическая оптимизация.
Число поколений: |200 Размер популяции [200.
Коэффициент каления: |01.
Коэффициент мутаций: щ.
Коэффициент скрещивания: |о.1|.
С* Симплексный спуск Назад I Далее > I Отмена.
Рис. 4.38: Выбор алгоритма решения.
Недоминируемые уровни совместности — поиск решения.
Поколение: 200.
Соответствие: 0.70 555 Найденный вектор уровней:
Огр 1 :0.483 401.
0гр2 0.984 127 0гр3: 0,801 221 Назад | Готово | Отмена.
Рис. 4.39: Недоминируемый вектор уровней.
Результат оптимизации.
Значение целевой функции.
Цель J 6.50 611 Значения переменных:
X].
Перменная Значение.
Перем1 2.49 512.
Перем2 0.
Перем3 4.1 099.
Закрыть.
Рис. 4.40: Решение задачи выборе параметров проектируемых изделий, при решении задач оперативного управления.
Заключение
.
В ходе проведенного в рамках диссертационной работы исследования были получены результаты, позволяющие исследовать структуру систем возможностных ограничений, а также метод коррекции несобственных: задач возможностного программирования.
Среди полученных результатов основными являются следующие:
• получены необходимые и достаточные условия несовместности систем возможностных ограничений;
• получены необходимые и достаточные условия избыточности систем возможностных ограничений;
• получены результаты, описывающие влияние изменения уровня возможности (необходимости) выполнения ограничения на совместность систем ограничений задач возможностного программирования;
• получены и обоснованы методы нахождения максимального уровня возможности (необходимости) выполнения отдельного ограничения, обеспечивающего совместность системы возможностных ограничений;
• разработана модель нахождения недоминируемого вектора возможности, обеспечивающего совместность системы возможностных ограничений в контексте задачи векторной оптимизации при наличии нечеткой информации о важности критериев;
• разработана архитектура системы поддержки принятия решений, опирающейся на теорию возможностей;
• разработана система поддержки принятия решений FIESTA, основанная на методах возможностной оптимизации, в которой реализованы методы, описанные в диссертационной работе.
Дальнейшее развитие исследований, проведенных в диссертационной работе, может включать исследование различных свойств нечеткого подмножества решений, полученного в главе 4 и описывающего рациональный выбор в задаче о нахождении недоминируемых уровней возможностей, обеспечивающих совместность систем возможностных ограничений. Также возможно исследование задач, решение которых невозможно не из-за несовместности систем ограничений, а из-за неограниченности области допустимых решений в направлении возрастания целевой функции.
