Содержание к диссертации
Введение
1 Вспомогательные результаты 13
1.1 Возможностное пространство и его свойства 14
1.2 Нечеткие величины и их исчисление 16
1.2.1 Преобразования 19
1.2.2 Операции 20
1.2.3 Нечеткие числа (L, і?)-типа 21
1.3 Нечеткие отношения, нечеткое подмножество недоминируемых решений 22
1.4 Противоречивые модели линейного программирования . 27
2 Исследование структуры задач возможностной оптимизации 32
2.1 Исследуемый класс задач возможностной оптимизации . 32
2.2 Непрямые методы решения задач возможностной оптимизации 34
2.2.1 Проблема модальной оптимизации 34
2.2.2 Максимаксная модель 35
2.2.3 Задача максимизации возможности достижения нечеткой цели 36
2.2.4 Максимизация возможности достижения целей-ограничений 40
2.2.5 Модальные ограничения 41
2.2.6 Ограничения по возможности и необходимости . 42
2.3 Совместность и избыточность систем возможностных ограничений 44
2.4 Основные результаты 45
2.4.1 Системы построчных ограничений по возможности в случае ограничений типа неравенств 46
2.4.2 Системы построчных ограничений по возможности в случае ограничений равенств 49
2.4.3 Системы построчных ограничений по необходимости 54
2.5 Выводы по второй главе 57
Совместные системы возможностных ограничений 60
3.1 Исследование зависимости совместности и избыточности ограничений от требований на меру их выполнения 60
3.2 Системы возможностных ограничений, содержащие ограничение, совместное с максимальной степенью возможности 64
3.2.1 Построчные ограничения по возможности в случае ограничений типа неравенств 64
3.2.2 Построчные ограничения по возможности в случае ограничений типа равенств 66
3.2.3 Построчные ограничения по необходимости 69
3.3 Модель нахождения недоминируемого вектора возможностей, обеспечивающего совместность системы возможностных ограничений 72
3.4 Выделение нечеткого подмножества недоминируемых решений 74
3.5 Основные теоремы 78
3.6 Выводы по главе 3 80
Система поддержки моделей и методов возможностной оптимизации 84
4.1 Архитектура системы 85
4.2 Банк моделей и методов 86
4.3 Реализация системы на основе объектно-ориентированного подхода 87
4.3.1 Подсистема хранения, обработки и визуализации нечетких данных 88
4.3.2 Подсистема генерации задач возможностной оптимизации 92
4.3.3 Подсистема работы с распределениями возможностей 92
4.4 Алгоритмы решения и анализа задач возможностного программирования 95
4.5 Технология работы пользователя с системой 100
4.5.1 Интерфейс СППР FIESTA 100
4.5.2 Представление задачи возможностного программирования 101
4.5.3 Редактирование задачи 102
4.5.4 Анализ совместности системы возможностных ограничений 104
4.5.5 Построение детерминированных аналогов и решение задач 106
4.6 Модельные расчеты 106
4.6.1 Задача модальной оптимизации 106
4.6.2 Задача с максимаксной моделью 112
4.6.3 Задача максимизации возможности достижения нечеткой цели 117
4.6.4 Задача максимизации возможности выполнения нечетких целей-ограничений 122
4.6.5 Анализ и коррекция несовместной системы ограничений 128
4.7 Выводы по главе 4 130
Заключение 134
Литература 136
- Нечеткие отношения, нечеткое подмножество недоминируемых решений
- Системы построчных ограничений по возможности в случае ограничений равенств
- Построчные ограничения по возможности в случае ограничений типа равенств
- Подсистема хранения, обработки и визуализации нечетких данных
Введение к работе
Актуальность
Проблема принятия решений (ПР) постоянно возникает перед человеком как в повседневной жизни, так и в управлении производством, бизнесом, финансами и т.п. В повседневной жизни выбор нередко производится почти автоматически - интуитивно в силу простоты и повторяемости задачи ПР. Однако в управлении человек часто не может сразу принять решение, сомневается либо желает прибегнуть к помощи специалиста. Если в повседневной жизни ошибки в выборе решений могут не иметь существенного значения, то в производственной сфере они могут привести к различного рода потерям или даже катастрофам. Поэтому необходимо принятие решений, обоснованных обстоятельным изучением и анализом различных вариантов с оценкой последствий их реализации. Человек вручную не в состоянии произвести подобные исследования.
Опыт практического использования вычислительной техники в научных исследованиях и производстве показывает, что компьютеры могут быть с успехом применены в задачах анализа решений. Компьютеры дают возможность рационального объединения логического мышления и интуиции человека со строгими математическими методами и возможностью выполнения большого объема вычислений с целью существенного увеличения вероятности принятия оптимальных решений.
Таким образом, возникает проблема разработки и внедрения программных систем, обеспечивающих поддержку лицу, принимающему решения, (ЛПР) на этапах сбора и хранения больших объемов информации, обработки полученной информации с использованием различных методов при-
нятия решений в зависимости от класса поставленной задачи; выбора оптимальной альтернативы и выдачи рекомендаций по реализации полученного решения. Подобные системы получили название систем принятия решений (СППР).
Многие практические задачи могут быть формализованы в форме задач линейного программирования. В настоящее время теория классического линейного программирования хорошо разработана и реализована в различных программных системах. Однако в связи с недостатком информации, большой сложностью или самой сутью проблемы может оказаться невозможно точно опеределить значения части параметров задачи и применение аппарата линейного программирования оказывается невозможным. Для решения задач в условиях неопределенности хорошо зарекомендовал себя математический аппарат теории возможностей. Вот что говорит об этом создатель теории нечетких множеств Лотфи Заде:
"Я считаю, что излишнее стремление к точности стало оказывать действие, сводящее на нет теорию управления и теорию систем, так как оно приводит к тому, что исследования в этой области сосредоточиваются на тех гі только тех проблемах, которые поддаются точному решению. В результатне многие классы важных проблем, в которых данные, цели и ограничения являются слишком сложными или плохо определенными для того, чтобы допустить точный математический анализ, оставались и остаются в стороне по той причине, что они не поддаются математической трактовке. Для того, чтобы сказать что-либо существенное для проблемм подобного рода, мы должны отказаться от наших требований точности и допустить результаты, которые являются несколько размытыми или неопределенными ".
Одним из основных недостатков существующего аппарата возможност-ного программирования до настоящего времени является отсутствие методов, позволяющих проводить коррекцию задач, которые в исходной постановке не имеют решения. Разработка и реализация таких методов позволит существенно расширить круг практических задач, решаемых в рамках воз-
можностного программирования. На решение этих задач направлено диссертационное исследование.
Методы решения задач возможностного программирования разрабатывались в работах Язенина А.В. и других авторов. Однако для их широкого применения необходима разработка соответствующего программного обеспечения. Это требует дополнительного исследования и спецификации разработанных методов и реализации на их основе систем поддержки принятия решений. Это вторая цель диссертационного исследования.
Обзор литературы
Теория несобственных задач математического программирования является хорошо изученной. Из большого числа работ, посвященной данной тематике, в первую очередь следует отметить общепринятые монографии А.Н. Тихонова, В.Я. Арсенина [62], В.К. Иванова, В.В. Васина, В.П. Танана [27], а также монографии С.А. Ашманова [6], Ф.П. Васильева, А.Ю. Иваницкого [13], В.В. Васина и А.Л. Агеева [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].
Непрямые методы возможностной оптимизации были разработаны А.В. Язениным в работах [80] - [84], [116], [118] а также в совместной с М. Wagenknecht работе [119]. Эти методы основаны на построении эквивалентных детерминированных аналогов исходных задач.
В соответствии со сложившимся подходом к исследованию задач линейного программирования, следующим шагом является исследование их устойчивости. Этой схеме придерживаются и в возможностной оптимизации. В работах R. Fuller [95], [96], [97] заложены основы этих исследований. Дальнейшее исследование вопросов было продолжено в работах В.А. Рыбкина и А.В. Язенина. Основными из них являются: [52], [50], [113]. В них, в возможностном контексте, исследована слабая и сильная устойчивость задач нечеткого линейного программирования и получены методы их регуляризации.
Следующим шагом в традиционном подходе к исследованию задач линейного программирования является разработка методов коррекции несобственных задач. Этому вопросу посвящена статья Weldon Lodwick [102]. В ней исследуется задача возможностной линейной оптимизации при фиксированных уровнях возможности выполнения ограничений. Известными методами для нее строится эквивалентная задача интервального программирования. Для этой системы Lodwick использует понятия оптимистического и пессимистического набора ограничений, а также определяет понятия слабой и сильной избыточности возможностных ограничений.
В этой статье автором получены также необходимые и достаточные условия слабой и сильной избыточности для ограничений рассматривае-
мой системы возможностных неравенств. В данной диссертационной работе этот подход полуил дальнейшее развитие. Соответствующие результаты получены для ограничений типа равенств. Наряду с системами возможностных ограничений в диссертации исследуется также и системы снеоб-ходимостных ограничений. Современный подход к моделированию неопределенности предполагает исследования задачи в двойственном контексте. Lodwick также исследует дополнительные ограничения, которые накладывает структура системы ограничений на переменные, строки и столбцы системы. Также рассмотрено, как понятие двойственности может быть применено к задаче линейного возможностного программирования.
Тем не менее ряд вопросов остается открытым. Здесь наиболее важными нам представляется исследование корректности системы ограничений в зависимости от требования на уровень возможности (необходимости) их выполнения. Стоит отметить, что в работе Lodwick исследованы лишь отдельные ограничения системы. Однако практика принятия решений требует исследования корректности всей системы ограничений. Этим и определяются цели и задачи диссертационного исследования.
Цель работы
Целью работы является исследование корректности задач возможност-ной оптимизации и разработка программного комплекса их поддержки.
В рамках диссертационного исследования, актуальность которого показана выше, проводится исследование структуры систем ограничений задач возможностной оптимизации. Под исследованием структуры системы ограничений понимается:
нахождение избыточных ограничений;
нахождение несовместных ограничений;
нахождение максимальных уровней возможности (необходимости) при которых система ограничений будет совместна.
Для несовместных ограничений исследуется возможность коррекции исходной постановки задачи путем снижения уровня возможности (необходимости) выполнения ограничений.
Разработанные методы коррекции задач возможностного программирования реализуются в системе поддержки принятия решений.
Основные задачи
Сформулированная цель диссертационного исследования достигается путем решения следующего ряда задач:
установление необходимых и достаточных условий избыточности ограничений задач возможностного программирования;
установление необходимых и достаточных условий несовместности ограничений задач возможностного программирования;
исследование влияния изменения возможности (необходимости) выполнения ограничения на совместность систем возможностных ограничений;
обоснование методов поиска максимального уровня возможности (необходимости) выполнения отдельного ограничения, обеспечивающего совместность системы возможностных ограничений;
разработка модели нахождения недоминируемого вектора возможности, обеспечивающего совместность системы возможностных ограничений контексте задачи векторной оптимизации;
реализация методов коррекции, основанных на понижении уровней возможностей (необходимостей) выполения ограничений, в качестве модуля программной системы поддержки принятия решений.
Методика исследования
Для формального описания изучаемого класса задач используется математический аппарат современной теории возможностей, при доказательстве теорем используются методы возможностной оптимизации, математического программирования, математического и функционального анализа. Методологическую основу исследования составляют результаты классической теории корректности задач оптимизации и векторной оптимизации. При разработке програмной системы использовались высокоуровневые методы программирования, включая объектно-ориентированное программирование.
Практическая значимость работы
Полученные методы коррекции систем возможностных ограничений позволяют расширить класс задач, решаемых в рамках методов возмож-ностного программирования. Разработанная в ходе работы над диссертацией система поддержки принятия решений может быть применена для решения задач производственного планирования, портфельного анализа и т.д.
Внедрение результатов работы
Проведенные научные исследования поддержаны грантами РФФИ, проекты №02-01-01137, №04-01-96720. Результаты диссертации внедрены в учебный процесс на факультете прикладной математики и кибернетики Тверского государственного университета, в качестве программной составляющей учебно-методического комплекса по дисциплине "Теория неопределенностей".
Апробация
Основные результаты работы докладывались автором на 2-ом международном научно-практическом семинаре "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (Коломна, 2003 год), на семинарах в ТвГУ, ВЦ РАН.
Структура работы и ее содержание
Диссертация состоит из введения, четырех глав, заключения и библиографии.
Во введении обосновывается актуальность темы, формулируются цели исследования, приводится краткое изложение основных положений и результатов диссертационной работы.
Первая глава состоит из пяти параграфов и является вспомогательной. В ней подготавливается и систематизируется необходимый математический аппарат теории возможностей, приводятся определения и теоремы, составляющие теоретическую основу исследуемых далее моделей возможностнои оптимизации. Вводятся понятия мер неопределенности, нечетких величин, операций и отношений над нечеткими величинами, рассматриваются их свойства, описываются наиболее значимые для практики замкнутые семейства. Также рассматривается теория противоречивых моделей в линейном программировании.
Вторая глава посвящена исследованию структуры задач возможностно-го программирования. В ней вводится класс исследуемых задач возмож-ностного программирования, выделяются типы задач, которые будут изу-чатся. Приводится обзор непрямых методов решения задач возможностно-го программирования, используемых для решения подобных задач. В параграфе 3 вводятся определения понятий "несовместность" и "избыточность" для систем ограничений задачи возможностного программирования. Параграф 4 "Основные результаты" посвящен получению и доказательству необходимых и достаточных условий избыточности и несовместности для
различных типов задач возможностного программирования.
Содержание третьей главы составляет исследование методов коррекции несовместных задач возможностного программирования. В первом параграфе исследуется влияние требований к уровню возможности выполнения ограничения на его совместность. Изучаются методы коррекции, позволяющие определить максимальный уровень, обеспечивающий совместность одного из ограничений системы. На основе полученных методов и в предположении о наличии нечеткой информации о важности ограничений для ЛПР в параграфе 3 строится модель нахождения нахождения совместной системы ограничений, позволяющая определить недоминируемый вектор уровней возможностей (необходимостей) выполения ограничений, обеспечивающий совместность исследуемой системы. Ее формализация и исследование основано на использовании математического аппарата нечетких отношений и концепции недоминируемых решений, разработанной С.А. Орловским [46]. Параграфы 4 и 5 посвящены выделению ** нечеткого подмножества недоминируемых решений поставленной задачи и исследованию его свойств.
В четвертой главе описывается система поддержки принятия решений FIESTA, основанная на методах возможностной оптимизации. В ней реализован ряд непрямых методов возможностной оптимизации и методы коррекции соответствующих задач, полученные в данной диссертации. В главе описаны архитектура системы, поддерживаемые модели критериев и ограничений задач возможностного программирования, реализованные в данной системе. В параграфе 3 рассмотрена реализация основных подсистем СППР FIESTA, методы представления и обарботки нечеткой информации. Параграф 4 посвящен описанию интерфейса системы. Примеры модельных расчетов, проводимых с помощью СППР FIESTA, приведены в 5-ом параграфе.
В заключении подводятся итоги диссертационного исследования и намечаются возможные направления дальнейших исследований.
Нечеткие отношения, нечеткое подмножество недоминируемых решений
Проблема принятия решений (ПР) постоянно возникает перед человеком как в повседневной жизни, так и в управлении производством, бизнесом, финансами и т.п. В повседневной жизни выбор нередко производится почти автоматически - интуитивно в силу простоты и повторяемости задачи ПР. Однако в управлении человек часто не может сразу принять решение, сомневается либо желает прибегнуть к помощи специалиста. Если в повседневной жизни ошибки в выборе решений могут не иметь существенного значения, то в производственной сфере они могут привести к различного рода потерям или даже катастрофам. Поэтому необходимо принятие решений, обоснованных обстоятельным изучением и анализом различных вариантов с оценкой последствий их реализации. Человек вручную не в состоянии произвести подобные исследования.
Опыт практического использования вычислительной техники в научных исследованиях и производстве показывает, что компьютеры могут быть с успехом применены в задачах анализа решений. Компьютеры дают возможность рационального объединения логического мышления и интуиции человека со строгими математическими методами и возможностью выполнения большого объема вычислений с целью существенного увеличения вероятности принятия оптимальных решений.
Таким образом, возникает проблема разработки и внедрения программных систем, обеспечивающих поддержку лицу, принимающему решения, (ЛПР) на этапах сбора и хранения больших объемов информации, обработки полученной информации с использованием различных методов принятия решений в зависимости от класса поставленной задачи; выбора оптимальной альтернативы и выдачи рекомендаций по реализации полученного решения. Подобные системы получили название систем принятия решений (СППР).
Многие практические задачи могут быть формализованы в форме задач линейного программирования. В настоящее время теория классического линейного программирования хорошо разработана и реализована в различных программных системах. Однако в связи с недостатком информации, большой сложностью или самой сутью проблемы может оказаться невозможно точно опеределить значения части параметров задачи и применение аппарата линейного программирования оказывается невозможным. Для решения задач в условиях неопределенности хорошо зарекомендовал себя математический аппарат теории возможностей. Вот что говорит об этом создатель теории нечетких множеств Лотфи Заде:
"Я считаю, что излишнее стремление к точности стало оказывать действие, сводящее на нет теорию управления и теорию систем, так как оно приводит к тому, что исследования в этой области сосредоточиваются на тех гі только тех проблемах, которые поддаются точному решению. В результатне многие классы важных проблем, в которых данные, цели и ограничения являются слишком сложными или плохо определенными для того, чтобы допустить точный математический анализ, оставались и остаются в стороне по той причине, что они не поддаются математической трактовке. Для того, чтобы сказать что-либо существенное для проблемм подобного рода, мы должны отказаться от наших требований точности и допустить результаты, которые являются несколько размытыми или неопределенными ".
Одним из основных недостатков существующего аппарата возможност-ного программирования до настоящего времени является отсутствие методов, позволяющих проводить коррекцию задач, которые в исходной постановке не имеют решения. Разработка и реализация таких методов позволит существенно расширить круг практических задач, решаемых в рамках возможностного программирования. На решение этих задач направлено диссертационное исследование.
Методы решения задач возможностного программирования разрабатывались в работах Язенина А.В. и других авторов. Однако для их широкого применения необходима разработка соответствующего программного обеспечения. Это требует дополнительного исследования и спецификации разработанных методов и реализации на их основе систем поддержки принятия решений. Это вторая цель диссертационного исследования.
Теория несобственных задач математического программирования является хорошо изученной. Из большого числа работ, посвященной данной тематике, в первую очередь следует отметить общепринятые монографии А.Н. Тихонова, В.Я. Арсенина [62], В.К. Иванова, В.В. Васина, В.П. Танана [27], а также монографии С.А. Ашманова [6], Ф.П. Васильева, А.Ю. Иваницкого [13], В.В. Васина и А.Л. Агеева [14], Е.Г. Гольштейна и Д.Б. Юдина [15], И.И. Еремина [22], В.А. Морозова [40], А.Н. Тихонова [60].
Развитие теории нечетких множеств положила работа "Fuzzy Sets" профессора Калифорнийского университета Лофти А. Заде [121]. В этой работе Заде расширил классическое понятие множества, допустив, что характеристическая функция может принимать значения в интервале [0,1]. Такие множества Заде назвал нечеткими (fuzzy). Заде были введены ряд операций над нечеткими множествами, понятие лингвистической переменной.
Системы построчных ограничений по возможности в случае ограничений равенств
Основные результаты работы докладывались автором на 2-ом международном научно-практическом семинаре "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (Коломна, 2003 год), на семинарах в ТвГУ, ВЦ РАН.
Диссертация состоит из введения, четырех глав, заключения и библиографии. Во введении обосновывается актуальность темы, формулируются цели исследования, приводится краткое изложение основных положений и результатов диссертационной работы.
Первая глава состоит из пяти параграфов и является вспомогательной. В ней подготавливается и систематизируется необходимый математический аппарат теории возможностей, приводятся определения и теоремы, составляющие теоретическую основу исследуемых далее моделей возможностнои оптимизации. Вводятся понятия мер неопределенности, нечетких величин, операций и отношений над нечеткими величинами, рассматриваются их свойства, описываются наиболее значимые для практики замкнутые семейства. Также рассматривается теория противоречивых моделей в линейном программировании.
Вторая глава посвящена исследованию структуры задач возможностно-го программирования. В ней вводится класс исследуемых задач возмож-ностного программирования, выделяются типы задач, которые будут изу-чатся. Приводится обзор непрямых методов решения задач возможностно-го программирования, используемых для решения подобных задач. В параграфе 3 вводятся определения понятий "несовместность" и "избыточность" для систем ограничений задачи возможностного программирования. Параграф 4 "Основные результаты" посвящен получению и доказательству необходимых и достаточных условий избыточности и несовместности для различных типов задач возможностного программирования.
Содержание третьей главы составляет исследование методов коррекции несовместных задач возможностного программирования. В первом параграфе исследуется влияние требований к уровню возможности выполнения ограничения на его совместность. Изучаются методы коррекции, позволяющие определить максимальный уровень, обеспечивающий совместность одного из ограничений системы. На основе полученных методов и в предположении о наличии нечеткой информации о важности ограничений для ЛПР в параграфе 3 строится модель нахождения нахождения совместной системы ограничений, позволяющая определить недоминируемый вектор уровней возможностей (необходимостей) выполения ограничений, обеспечивающий совместность исследуемой системы. Ее формализация и исследование основано на использовании математического аппарата нечетких отношений и концепции недоминируемых решений, разработанной С.А. Орловским [46]. Параграфы 4 и 5 посвящены выделению нечеткого подмножества недоминируемых решений поставленной задачи и исследованию его свойств.
В четвертой главе описывается система поддержки принятия решений FIESTA, основанная на методах возможностной оптимизации. В ней реализован ряд непрямых методов возможностной оптимизации и методы коррекции соответствующих задач, полученные в данной диссертации. В главе описаны архитектура системы, поддерживаемые модели критериев и ограничений задач возможностного программирования, реализованные в данной системе. В параграфе 3 рассмотрена реализация основных подсистем СППР FIESTA, методы представления и обарботки нечеткой информации. Параграф 4 посвящен описанию интерфейса системы. Примеры модельных расчетов, проводимых с помощью СППР FIESTA, приведены в 5-ом параграфе.
В заключении подводятся итоги диссертационного исследования и намечаются возможные направления дальнейших исследований. Пусть Г есть обычное множество элементов, обозначаемых далее как 7 Є Г. Пусть С(Г) - некоторое множество подможеств Г, причем 0, Г Є С(Г). Существуют различные возможности оценки полезности элементов из С(Г) в соответствии с заданными уловиями и ситуацией. Классический путь состоит в определении вероятностей меры на С(Г), обычно на походящей сг-алгебре событий. Однако, по мере того, как в область научных интересов стали попадать вопросы, связанные с восприятием мира живыми существами и, в частности, человеком (В основном это относится, конечно к работам в области искусственного интеллекта) адекватность теории вероятностей начала вызывать сомнения. В практических работах стали использоваться эмпирические модели заменяющие вероятностную меру ее суррогатами. Это ограничение удалось преодолеть благодаря работам Заде, Шейфера и других, которые ввели понятие нечеткой меры, для которой, в отличии от вероятностной меры, не требуется выполнения свойства аддитивности. С другой стороны, некоторые "естественные" свойства меры сохраняются. В первую очередь следует упомянуть свойство монотонности, которое соответствует принципу "чем больше множество, тем более мы можем быть уверены, что встретиться ожидаемое свойство".
Построчные ограничения по возможности в случае ограничений типа равенств
Результаты теорем, полученых в предыдущей главе, позволяют исследовать систему ограничений (2.3) на заданных аг-уровнях. Если же будет установлено, что на заданном уровне система является несовместной, и задача, таким образом, не имеет решения, то практический интерес может представлять поиск уровня возможности, на котором система ограничений станет совместной. Для решения этой задачи исследуем, что происходит с несовместностью и избыточностью ограничений при изменении а-уровня.
Теорема 3.1 Если к-я строка является сильно несовместной для уровня а.\ то она сильно несовместна и на уровне а2 «і Доказательство. Пусть k-я строка является сильно несовместна для а\. Тогда \/akj Є [а а ацУ/б є [Ь ,Ь ]аік-я строка матрицы А несовместна для вектора Ь. Так как нечеткие величины а , Ъь имеют квазивогнутые распределения возможностей, то из Q!2 а\ следует, что [aL, а ]ах Э [% ajfcj]a2 и К, b]ai 2 К, Ь ]а2. Следовательно, и на уровне а2 к-я строка является несовместной для всех А Є А1 и b Є б7, что по определению означает сильную несовместность к-ой строки на уровне о . Теорема доказана. Следствие. Если к-я строка не является сильно несовместной для уровня а\ то она не является сильно несовместной и на уровне а.2 OL\ Теорема 3.2 Если к-я строка является слабо или сильно несовместной для уровня а\, то она слабо несовместна для уровня ct2 OL\.
Доказательство. Пусть на уровне а\ k-я строка является слабо или сильно несовместной, тогда 3a kj Є [akjJakj]ai,3bl Є [b,b]ai Для которых к-я строка является несовместной. Так как нечеткие величины ajy, 6 имеют квазивогнутые распределения возможностей, то из »2 сщ следует, что [%ЯаЙ«і [% аЙ«2 и Keflex С [Ь ,&]а2. Но тогда a kj Є [%-,а]а2 и fyfe Є [ fcj fc]a2- Следовательно, AJ-Я строка является слабо несовместной на уровне с 2- Теорема доказана. Следствие. Если к-я строка не является слабо несовместной для уровня ai то она не является слабо несовместной и на уровне с 2 сх\. Аналогичные результаты могут быть получены и для избыточности. Теорема 3.3 Если к-я строка является сильно избыточной для уровня а.\ то она сильно избыточна и на уровне а?2 а\. Теорема 3.4 Если k-я строка является слабо или сильно избыточной для уровня а\, то она слабо избыточна для уровня с 2 &\ Доказательства этих теорем в точности повторяют доказательства теорем 3.1 и 3.2. При применении результатов теорем 3.1-3.4 к случаю меры необходимости нужно учитывать, что вычисления производятся на уровне (3 = 1 — а (для которого и нужно применять теоремы 3.1-3.4) и понижение уровня необходимости а приводит к увеличению / -уровня и наоборот. Следует отметить, что утверждения, обратные утверждениям теорем 3.1-3.4, вообще говоря не верны. Это показывает следующий пример системы, содержащей ограничение по возможности. Пусть Ь имеет триангулярное распределение с параметрами (4,0.5,0.5). При таком значении Ь на уровне а = 0.75 система сильно несовместна, в чем легко убедиться применив теорему 2.4- Понижение уровня возможности в данном случае ничего не дает, система остается сильно несоместной на всех а-уровнях. Рассмотрим, что произойдет, если величина Ь будет иметь триангулярное распределение с параметрами (4,2,2). На уровне 0.75 система все еще является сильно несовместной. Однако при понижении уровня до 0.5 она становится слабо несовместной и мы можем найти решение поставленной задачи. Слабая несовместность при повышении уровня возможности не всегда переходит в сильную. Если в нашем примере взять Ъ с триангулярным распредлением с параметрами (3,1,1), то задача будет оставаться слабо несовместной до уровня а = 1. Рассмотрим, как эти свойства слабой и сильной совместности влияют на существование решения задачи возможностного программирования. Система построчных ограничений по возможности интерпретруется на интервальном уровне как оптимистическая модель принятия решений. При этом, если какое либо ограничение системы является сильно несовместным, то область допустимых значений, определяемая такой системой пуста и решение задачи не существует. Если же в системе нет сильно несовместных ограничений, то множество допустимых значений будет не пусто, даже если некоторые ограничения системы являются слабо несовместными. Из нашего примера видно, что если одно из ограничений системы является сильно несовместным, то возможны два варианта: 1. понижение уровня возможности выполнения ограничения приведет к переходу к слабой несовместности, и множество допустимых решений задачи станет не пусто; 2. при любом а-уровне ограничение будет оставаться сильно несовместным. Решение задачи с системой построчных ограничений по необходимости на интервальном уровне может быть обосновано в рамках пессимистической модели. Поэтому множество допустимых значений системы будет пусто как при наличии сильно несовместных ограничений, так и при наличии слабо несовместных ограничений. Теорема 3.5 Если к-я строка системы (2.6) является сильно несовместной для некоторого уровня а, то задача (2.1),(2.2) не имеет решения Пусть k-я строка системы (2.6) является сильно несовместной для уровня а\. Тогда, согласно теореме 3.1, то она сильно несовместна и на уровне «2 о: А, согласно теореме 3.2, она слабо несовместна на всех уровнях Таким образом, мы видим, что на всех уровнях а Є [0,1] наша система ограничений является либо слабо либо сильно несовместной, а так как решение задачи ищется в условиях пессимистической модели, то задача (2.1),(2.2) не имеет решения при любом уровне необходимости к-то ограничения.
Подсистема хранения, обработки и визуализации нечетких данных
В зависимости от моделей критерия и ограничений отдельные зоны (например элементы векторов ресурсов или возможностей) могут не иснользо-ватся. Каждая зона документа соответствует некоторому объекту в математической записи задачи. Представление конкретного элемента зависит от тина того объекта, с которым он связан. Так, например, элементы технологической матрицы соответствуют нечетким числам и отображают соответствующие распределения. В случае, если задача полностью не умещается в окно, на экране отображается только часть задачи. Видимую часть можно смещать с помощью клавиш курсора или полос прокрутки. Для удобства работы имена целей, ограничений и переменных не смещаются при прокрутке и всегда видны. Один из элементов задачи выделяется цветом - это текущий элемент. Все команды, подаваемые через меню или с клавиатуры, применяются к текущему элементу или строке/столбцу в котором он расположен (если эти команды направлены на изменение всей строки/столбца). Изменить текущий элемент можно с помощью одинарного щелчка мышью или клавишами курсора. Пользователь может изменять ширину столбцов и высоту строк задачи. С помощью диалога «формат» можно задать шрифты, используемые для отображения различных элементов задачи, а также выбрать способ отображения нечетких параметров (название, распределениє или одноверменно - и название, и распределение).
Предусмотрена возможность изменения размерности задачи после ее создания. Для этого нужно воспользоваться соотвествующими пунктами меню «правка». Добавление или удаление каких-либо элементов задачи может быть недоступно в случае, если такая операция нарушит ограничения, налагаемые на размерность задачи моделью критерия. Для удаления переменной необходимо выделить какой-либо элемент из столбца, соответствующего удаляемой переменной, и выбрать команду «удалить переменную». Для удаления строки ограничений или целевого вектора необходимо выделить элемент соотвествующей строки и выполнить команду «удалить строку». Для добавления переменной нужно воспользоваться пунктом «добавить переменную». После выбора этой команды технологичская матрица будет расширена и появится столбец, соответствующий новой переменной. При добавлении новых ограничений и целевых векторов появится диалоговое окно, в котором необходимо ввести название добавляемой строки и, в случае добавления ограничения, выбрать его модель. При добавлении целевого вектора возможность изменения модели блокируется.
FIESTA не накладывает ограничений на имена переменных, ограничений и целевых функций. Для изменения этих имен достаточно выделить соответствующий элемент и нажать кнопку «enter» или дважды щелкнуть по нему мышкой. Редактирование имен переменных происходит в строке ввода, появляющейся непосредственно в окне задачи. При редактировании имен целевых функций и ограничений открывается диалоговое окно, содержащее имя строки и тип модели. Модель ограничений может быть изменена в любой момент, в то время как модель критерия задается только при создании задачи и не может быть изменена в дальнейшем. Это обусловлено тем, что изменение модели критерия может повлечь изменение вида всей задачи.
Редактирование детерминированных параметров задачи (вектор возможностей) происходит в строке ввода, открывающейся в окне задачи. Для активации редактирования необходимо либо дважды щелкнуть но изменяемому элементу мышкой или выделить его и нажать «enter» на клавиатуре. Для изменения отношения в ограничениях задачи нужно дважды щелкнуть но символу ограничения мышкой или выделить его и нажать «enter». При этом знак ограничения будет менятся, циклически проходя все возможные варианты. Отношение может измениться в момент замены модели ограничения, если старое ограничение недопустимо для новой модели. В этом случае отношение будет заменено одним из допустимых.
Редактирование нечетких параметров задачи (элементы технологической матрицы, векторов целей и вектора ресурсов) также активизируется двойным щелчком мышью или нажатием на клавишу «enter». Пользователь может выбрать два режима редактирования нечетких чисел -обычный режим, ориентированный на пользователей, знакомых с теорией возможностей, и режим «помощник» позволяющий построить распределение возможностей математически неподготовленным пользователям. Режим редактирования запоминается и при редактировании последующих параметров автоматически начинается в том же режиме, который использовался до этого. В обычном режиме пользователю предлагается выбрать тип распределения (детерминированное число, триангулярное, трапецевидное, нормальное, возрастающее и убывающее) и задать соответствующие параметры распределения (границы интервала толерантности или модальное значение и коэффициенты нечеткости). Выбор пользователя иллюстрируется графиком функции распределения текущей нечеткой велечины. В режиме «помощник» пользователю предлагается специальный опросник, реализованный в виде меню-системы, позволяющей на семантическом уровне извлечь из пользователя информацию, необходимую для восстановления возможностного распределения [84].
