Модели и методы коррекции задач возможностного программирования и программный комплекс их поддержки тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Сорокин, Сергей Владимирович

• Сорокин, Сергей Владимирович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Сорокин, Сергей Владимирович

Введение

1 Вспомогательные результаты 1.1 Возможностное пространство и его свойства.

1.2 Нечеткие величины и их исчисление.

1.2.1 Преобразования.

1.2.2 Операции.

1.2.3 Нечеткие числа (L, Я)-типа.

1.3 Нечеткие отношения, нечеткое подмножество недоминируемых решений.

1.4 Противоречивые модели линейного программирования

2 Исследование структуры задач возможностной оптимизации

2.1 Исследуемый класс задач возможностной оптимизации

2.2 Непрямые методы решения задач возможностной оптимизации

2.2.1 Проблема модальной оптимизации.

2.2.2 Максимаксная модель.

2.2.3 Задача максимизации возможности достижения нечеткой цели.

2.2.4 Максимизация возможности достижения целей-ограничений

2.2.5 Модальные ограничения.

2.2.6 Ограничения по возможности и необходимости

2.3 Совместность и избыточность систем возможностных ограничений

2.4 Основные результаты

2.4.1 Системы построчных ограничений по возможности в случае ограничений типа неравенств.

2.4.2 Системы построчных ограничений по возможности в случае ограничений равенств.

2.4.3 Системы построчных ограничений по необходимости

2.5 Выводы по второй главе.

Совместные системы возможностных ограничений

3.1 Исследование зависимости совместности и избыточности ограничений от требований на меру их выполнения.

3.2 Системы возможностных ограничений, содержащие ограничение, совместное с максимальной степенью возможности

3.2.1 Построчные ограничения по возможности в случае ограничений типа неравенств.

3.2.2 Построчные ограничения по возможности в случае ограничений типа равенств.

3.2.3 Построчные ограничения по необходимости.

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

3.4 Выделение нечеткого подмножества недоминируемых решений

3.5 Основные теоремы.

3.6 Выводы по главе 3.

Система поддержки моделей и методов возможностной оптимизации

4.1 Архитектура системы.

4.2 Банк моделей и методов.

4.3 Реализация системы на основе объектно-ориентированного подхода.

4.3.1 Подсистема хранения, обработки и визуализации нечетких данных.

4.3.2 Подсистема генерации задач возможностной оптимизации

4.3.3 Подсистема работы с распределениями возможностей

4.4 Алгоритмы решения и анализа задач возможностного программирования

4.5 Технология работы пользователя с системой.

4.5.1 Интерфейс СППР FIESTA

4.5.2 Представление задачи возможностного программирования

4.5.3 Редактирование задачи.

4.5.4 Анализ совместности системы возможностных ограничений

4.5.5 Построение детерминированных аналогов и решение задач.

4.6 Модельные расчеты.

4.6.1 Задача модальной оптимизации.

4.6.2 Задача с максимаксной моделью.

4.6.3 Задача максимизации возможности достижения нечеткой цели.

4.6.4 Задача максимизации возможности выполнения нечетких целей-ограничений

4.6.5 Анализ и коррекция несовместной системы ограничений

4.7 Выводы по главе 4.

Введение диссертации (часть автореферата) на тему «Модели и методы коррекции задач возможностного программирования и программный комплекс их поддержки»

Актуальность

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

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

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

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

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

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

Методы решения задач возможностного программирования разрабатывались в работах Язенина А.В. и других авторов. Однако для их широкого применения необходима разработка соответствующего программного обеспечения. Это требует дополнительного исследования и спецификации разработанных методов и реализации на их основе систем поддержки принятия решений. Это вторая цель диссертационного исследования.

Обзор литературы

Теория несобственных задач математического программирования является хорошо изученной. Из большого числа работ, посвященной данной тематике, в первую очередь следует отметить общепринятые монографии А.Н. Тихонова, В.Я. Арсенина [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-01137, №04-01-96720. Результаты диссертации внедрены в учебный процесс на факультете прикладной математики и кибернетики Тверского государственного университета, в качестве программной составляющей учебно-методического комплекса по дисциплине "Теория неопределенностей".

Апробация

Основные результаты работы докладывались автором на 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.70555 Найденный вектор уровней:

Огр 1 :0.00483401

0гр2 0.984127 0гр3: 0,801221 Назад | Готово | Отмена

Рис. 4.39: Недоминируемый вектор уровней

Результат оптимизации

Значение целевой функции

Цель J 6.50611 Значения переменных:

X]

Перменная Значение

Перем1 2.49512

Перем2 0

Перем3 4.01099

Закрыть

Рис. 4.40: Решение задачи выборе параметров проектируемых изделий, при решении задач оперативного управления.

Заключение

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

Среди полученных результатов основными являются следующие:

• получены необходимые и достаточные условия несовместности систем возможностных ограничений;

• получены необходимые и достаточные условия избыточности систем возможностных ограничений;

• получены результаты, описывающие влияние изменения уровня возможности (необходимости) выполнения ограничения на совместность систем ограничений задач возможностного программирования;

• получены и обоснованы методы нахождения максимального уровня возможности (необходимости) выполнения отдельного ограничения, обеспечивающего совместность системы возможностных ограничений;

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

• разработана архитектура системы поддержки принятия решений, опирающейся на теорию возможностей;

• разработана система поддержки принятия решений FIESTA, основанная на методах возможностной оптимизации, в которой реализованы методы, описанные в диссертационной работе.

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

Список литературы диссертационного исследования кандидат физико-математических наук Сорокин, Сергей Владимирович, 2004 год

1. Аверкин А.Н. и др. Нечеткие множества в моделях управления и искусственного интеллекта. / Под редакцией Поспелова Д.А. М.: Наука, 1986.

2. Агаян Г.М., Рютин А.А., Тихонов А.Н. О задаче линейного программирования с приближенными данными // ЖВМиМФ. 1984. Т. 24. № 9. С. 1303-1311.

3. Алексеева Л.Я. Принципы построения и процедуры функционирования систем поддержки принятия решений в организационных системах. / /Диссертация на соискание ученой степени доктора инженерных наук. Рига, 1998.

4. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. М.: Мир, 1987.

5. Ашманов С. А. Условие устойчивости задач линейного программирования // ЖВМиМФ. 1981. Т. 21. № 6. С. 1402-1410.

6. Ашманов С. А. Линейное программирование. М.: Наука, 1981.

7. Борисов А.Н., Алексеев А.В., Меркурьева Г.В. и др. Обработка нечеткой информации в системах принятия решений. М.: Радио и связь, 1989.

8. Борисов А.Н., Крумберг О.А., Федоров И.П. Принятие решений на основе нечетких моделей. Рига: Зинатне, 1990.

9. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980.

10. Васильев Ф.П., Ковач М., Потапов М.М., Чеканов Ю.Н. Оценка скорости сходимости метода невязки для задач линейного программирования с приближенными данными. // ЖВМиМФ. 1990. Т.ЗО. №8. С. 12571262.

11. Васильев Ф.П. Критерии устойчивости общей задачи линейного программирования // Вест. Моск. ун-та, сер. 15. Вычислительная математика и кибернетика. 1998. К0- 2. С. 17-20.

12. Васильев Ф.П. К вопросу устойчивости методов регуляризации в линейном программировании // Вест. Моск. ун-та, Сер. 15. Вычислительная математика и кибернетика. 1998. N2 3. С. 19-23.

13. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 1998.

14. Васин В.В., Агеев A.J1. Некорректные задачи с априорной информацией. // Екатеринбург: Уральская издательская фирма "Наука", 1993.

15. Гольштейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. М.: Советское радио, 1966.

16. Горелик В.А., Кондратьева В.А. Параметрическое программирование и несобственные задачи линейной оптимизации. Сб. работ ВЦ РАН "Моделирование, декомпозиция и оптимизация". М.: Изд-во ВЦ РАН, 1999. С. 57-82.

17. Данциг Дж. Линейное программирование, его обобщения и применение. М.: Прогресс, 1966.

18. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972.

19. Дюбуа Д., Прад А. Теория возможностей. Приложения к представлению знаний в информатике. М.: Радио и связь, 1990.

20. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.22