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

На правах рукописи

Сху-

Сорокин Сергей Владимирович

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

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Тверь 2004

Работа выполнена на кафедре информационных систем и технологий факультета прикладной математики Тверского государственного университета.

Научный руководитель -Официальные оппоненты

Ведущая организация -

доктор физико-математических наук, профессор А. В. Язенин

доктор физико-математических наук, профессор Е. А. Андреева кандидат физико-математических наук, доцент Ю. А. Егоров

Вычислительный центр РАН

Защита состоится 24 декабря 2004 г. в 10:45 на заседании диссертационного совета Д212.263.04 при Тверском государственном университете по адресу: 170013, г. Тверь, ул. Желябова 33.

С диссертацией можно ознакомиться в библиотеке Тверского государственного университета.

Автореферат разослан ноября 2004 г.

15923

Общая характеристика работы

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

Методы решения задач возможностного (нечеткого) программирования разрабатывались в работах J.J. Buckley, M. Ковач, С А Орловского, R. Fuller, H.J. Zimmerman, M. Wagenknecht, A.B. Язенина и других авторов. Однако, для их широкого применения необходима разработка соответствующего программного обеспечения. Это требует дополнительного исследования и спецификации разработанных методов и реализации на их основе систем поддержки принятия решений.

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

Начало исследованию вопросов корректности задач возможностного программирования положила работа W. Lodwick. В ней исследуется задача возможностной линейной оптимизации при фиксированных уровнях возможности выполнения ограничений. Однако, ряд важных вопросов, таких, как зависимость совместности возможностных СЯ

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

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

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

• нахождение избыточных ограничений;

• нахождение несовместных ограничений;

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

Для систем несовместных ограничений исследуется возможность коррекции исходной постановки задачи путем снижения уровня возможности (необходимости) выполнения ограничений.

Разработанные методы коррекции задач возможностного программирования реализуются в системе поддержки принятия решений.

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

Научная новизна. Основные результаты работы являются новыми:

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

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

3. Исследовано влияние изменения уровня возможности (необходимости) выполнения ограничения на совместность систем возможиостных огра-

ничений.

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

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

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

Положения, выносимые на защиту. На защиту выносятся следующие результаты диссертационного исследования:

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

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

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

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

5. Архитектура системы поддержки принятия решений, реализующей непрямые методы решения задач возможностной оптимизации.

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

Внедрение результатов работы. Проведенные научные исследования поддержаны грантами РФФИ, проекты №02-01-01137, №04-01-96720. Результаты диссертации внедрены в учебный процесс на факультете прикладной математики и кибернетики Тверского государственного университета в качестве программной составляющей учебно-методического комплекса по дисциплине "Теория неопределенностей".

Апробация работы. Основные результаты работы докладывались автором на 2-ом международном научно-практическом семинаре "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (Коломна, 2003 год), на семинарах в ТвГУ, ВЦ РАН.

Публикации автора. Основные результаты диссертации опубликованы в 6 работах, приведенных в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения и изложена на 147 страницах. Список литературы содержит 125 наименований, включая работы автора.

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

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

Пусть Г есть обычное множество элементов, обозначаемых далее как 7 € Г, Р(Г) есть множество всех подмножеств Г.

Определение 1.2 Мерой возможности называется функция

обладающая следующими свойствами:

Определение 1.3 Мерой необходимости называется функция ^ : Р(Г) -> [0,1],

обладающая следу,^ = ^^ € р(г)>у/

Определение 1.4 Триплет (Г, Р(Г),тг) называется возможностным пространством.

Возможностная величина определяется следующим образом.

Определение 1.5 Возможностной величиной (переменной) называется функция I : Г -)• Е1. Функция цг'Е1 -л [0,1] называется распределением возможностной величины I и определяется следующим образом:

б

Значение интерпретируется как "возможность того, что переменная 2 может принять значение z". Здесь и далее Е1, Е* обозначают евклидовы пространства соответствующей размерности.

Определение 1.10 Возможностная величина 2 называется выпуклой, если ее функция распределения является квазивогнутой, то есть

ММ + (1 - Д)г2) ^ тт{1лг(г1),11г(г2)}Угьг2 £ Е\УА 6 [0,1].

Выпуклые возможностью величины со значениями в Е', имеющие конечные носители, обычно называют возможностными (нечеткими) числами.

Введем понятие минисвязанности. Пусть А,В € -Р(Г). Следуя М.Б. Рао, назовем множества А и В минисвязанными (относительно возможностной меры если

Теперь введем понятие минисвязанности для возможностных переменных. Для этой цели определим распределение возможностей для совокупности нечетких величин. Пусть ...,£„- возможностные переменные.

Функция распределения совокупности возможностных переменных определяется следующим образом:

Определение 1.11 Возможностные величины Z\,..., 2п называются минисвязанными, если для любого подможества {¿1,..., ¿¡ъ} множества {1,..., п}

Здесь есть одномерные функции распределения возможностей.

Перейдем к краткому изложению основных результатов диссертации.

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

(с, я)

• тах,

(1)

(2)

где /¿¡-бинарное отношение»;- нечеткая м е ¿(30,7)- возможностные функции ■): Е" X Г Е1, Г - элемент возможностного пространства (Г, Р(г),7г), Еп - п-мерное евклидово пространство.

Рассматриваются линейные возможностные функции /г(х,у) — = (т)2^ ~ Мт)- В этом случае система ограничений (2) принимает

вид:

В роли нечеткой меры и может выступать мера возможности 7Г или необходимости v. В качестве отношений Л рассматриваются отношения равенства и неравенства. Возможностные переменные 0^(7), £>,(7) являются выпуклыми и минисвязанными, а их функции распределения полунепрерывны сверху. Фиксируя нечеткую меру и отношение можно получить три вида систем возможностных ограничений: построчные ограничения-равенства по возможности, построчные ограничения-неравенства по возможности, построчные ограничения-неравенства по необходимости. В диссертационной работе рассматриваются эти три случая.

Для системы возможностных ограничений (3) строится эквивалентная система ограничений интервального программирования:

' а'х д б1, х^О,

(4)

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

Определение 2.1 к-я строка матрицы ограничений (3) является сильно избыточной, если она является избыточной для всех

Определение 2.2 к-я строка матрицы ограничений (3) является слабо избыточной, если существуют А 6 А1 и Ь £ Ь1 для которых к-я строка является избыточной.

Определение 2.3 к-я строка матрицы ограничений (3) является сильно несовместной, если она является несовместной для всех

Определение 2.4 к-я строка матрицы ограничений (3) является слабо несовместной, если существуют А 6 А1 И 6 £ Ь1 для которых к-я строка является несовместной.

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

Для систем построчных ограничений по возможности при Я они формулируются следующим образом.

Теорема 2.1. к-я строка системы ограничений является сильно избыточной тогда, и только тогда, когда к-ая строка является избыточной для матрицы А* с вектором правой стороны й= ..., Щ, ...,

Здесь и далее а+,а~ - матрица правых и левых границ а-уровней воз-можностных переменных векторы границ а-уровней возможност-

ных переменных 6,.

Теорема 2.2. к-я строка системы ограничений является слабо избыточной тогда и только тогда, когда избыточна к-я строка матрицы а~ с вектором правой стороны

Теорема 2.3. к-я строка системы ограничений является сильно несовместной тогда и только тогда, когда к-я строка несовместна для матрицы с вектором

Теорема 2.4. к-я строка системы ограничений является слабо несовместной тогда и только тогда, когда к-я строка несовместна для матрицы

Соответствующие теоремы для системы построчных ограничений по возможности при имеют следующие формулировки.

Теорема 2.5. Пусть к-я строка системы ограничений является сильно избыточной. Тогда избыточны к-ая и (к+т)-ая строки следующей системы ограничений задачи линейного программирования:

Теорема 2.6. Если к-я строка системы ограничений слабо избыточна, то избыточны к-ая и (к + т)-ая строки следующей системы ограничений задачи линейного программирования:

Теорема 2.7. к-я строка системы ограничений является сильно несовместной тогда и только тогда, когда несовместны к-я или (к + т)-я строка

а+х <

(6)

системы ограничении

^А+х^д,-. (7)

Теорема 2.8. к-я строка системы ограничений является слабо несовместной тогда и только тогда, когда несовместны к-я или (т + к)-я строка системы ограничений

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

Теорема 2.9. к-я строка системы ограничений является сильно избыточной тогда и только тогда, когда избыточна ^ая строка следующей системы ограничений задачи линейного программирования:

(8)

{А+х 4 <Г

(9)

Теорема 2.10. к-я строка системы ограничений слабо избыточна тогда и только тогда, когда избыточна ^ая строка следующей системы ограничений задачи линейного программирования:

(10)

Теорема 2.11. к-я строка системы ограничений является сильно несовместной тогда и только тогда, когда несовместна к-я строка системы ограничений

{А~ х ^ (п)

Теорема 2.12. к-я строка системы ограничений задачи (3) является слабо несовместной тогда и только тогда, когда несовместна к-я строка системы ограничений

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

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

Теорема 3.1. Если к-я строка является сильно несовместной для уровня то она сильно несовместна и на уровне

Следствие. Если к-я строка не является сильно несовместной для уровня то она не является сильно несовместной и на уровне

Теорема 3.2. Если к-я строка является слабо или сильно несовместной для уровня то она слабо несовместна для уровня

Следствие. Если к-я строка не является слабо несовместной для уровня то она не является слабо несовместной и на уровне Аналогичные теоремы доказаны и для избыточных ограничений. Теоремы 3.1-3.2 верны как для меры возможности, так и для меры необходимости. Однако в последнем случае необходимо учитывать, что вычисления производятся на уровне для которого и нужно применять результаты этих теорем.

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

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

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

Теорема 3.5. Если к-я строка системы ограничений по необходимости является сильно несовместной для некоторого уровня а, то задача (1),(2) не имеет решения при любом уровне

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

ограничение будет совместным.

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

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

Построчные ограничения по возможности, К —

ауи —> тах,

(13)

Построчные ограничения по возможности, К ='=':

ак —> тах,

(14)

(15)

(16)

Построчные ограничения по необходимости, r =%':

dk —У тах,

(17)

]Г"=1 а+®, ь;, 1 ^г^к^т,

< ^.=1а+к](1-ак)х^Ь-к(1-ак), (18)

В этих моделях переменными являются искомый уровень Се^ и вектор х. Границы уровневых множеств й^сек), = 1, • • •, П,

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

В работе доказаны теоремы, которые дают основание проводить коррекцию несовместных систем возможностных ограничений путем воздействия на одно из ограничений системы. Однако понятно, что для решения задач, возникающих на практике, необходимо исследовать все ограничения системы одновременно. Такой подход приводит к постановке задачи следующего вида: "Найти наиболее предпочтительный для лица принимающего решения (ЛПР) вектор а-уровней а = (а^,..., Сет), обеспечивающий совместность системы возможностных ограничений (3)".

Формализация этой задачи приводит к модели векторной оптимизации а —Ъ У-таХаед. Ее решение состоит в нахождении одного из эффективных решений (оптимальных по Парето), то есть таких решений ар Е А, для которых не существует решения такого, что

Здесь А - множество векторов а, обеспечивающих совместность системы возможностных ограничений.

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

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

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

a*eA:a* = argmax/4ö(a), (19)

а£ А

где

{а) = inf supmin{ sup min {/¿¿(A1)}, sup min {/¿¿(A2)}},

äeN(a) u X'eff(ä,u)ia"m A2eЩа,и)>е1-т

(20)

N(a) = {d € Aj sup min{ sup mm{jUj(Ax)},

sup min{/z,(A2)}} = l}, (21) A 3eH(a,u2) ,6)-m

m

h(a,u) = {A 6 Л+|(А,а) = и,А+ = {АЁ > = 1}}, (22)

«=а

/Xi - функции принадлежности, характеризующие нечеткие коэффициенты важности критериев.

Из результатов, приведенных выше, следует, что для нахождения вектора а* нужно решить задачу

l4D{a) max, (23)

i аиЬ)хз ~ Ш 0}>ац, г = 1,..., т, ^

Wo,

где Rf= =}, а - нечеткая мера.

Особое внимание в диссертационной работе уделено исследованию множества AUND. Это множество тех решений, которые имеют степень недо-минируемости, равную 1.

Параграф 3.5 посвящен исследованию свойств множества недоминируемых решений Avnd. В частности, показано, что имеют место следующие теоремы.

Теорема 3.9 Пусть функции /г„г £ 1: m являются строго унимодальными на отрезках А;, существует вектор А* € Л>, такой, что 1ч(К) = М € 1, тогда Атр С Ар.

Здесь Л+ = {А € F»|Ai > 0, А,- = 1}.

Эта теорема показывает, что построенное множество недоминируемых решений является сужением множества решений, эффективных по Парето.

Теорема 3.10 Если множества AUND, Arg тахаед(А*, а) не пусты, и функции Hi строго унимодальны на отрезках Д* соответственно, то

kVND ^ Argmax(A*,a) ае А

Теорема 3.11 Пусть функции щ строго унимодальны на отрезках A¡, существует вектор А* € обладающий свойством: jt¿j(A|) = 1, * € 1 : т. Тогда AUND ф 0.

Эта теорема представляет собой достаточное условие существования множества

Разработанные методы коррекции задач возможностного программирования реализованы автором в системе поддержки принятия решений FIESTA, описанной в 4-ой главе диссертации.

Система FIESTA обеспечивает:

• выбор модели принятия решений;

• настройку системы принятия решений в соответствии с выбранной моделью принятия решений;

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

• представление и обработку нечетких данных;

• решение задачи по выбранной модели;

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

Реализация интеллектуальной системы поддержки принятия решений

требует архитектуры, которая включает:

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

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

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

• блок анализа несовместных ограничений;

• решатель;

• графические подсистемы;

• блок интерфейса с пользователем.

Диаграмма, показывающая взаимосвязи между этими блоками, показана на рис. 1.

При разработке СППР FIESTA была выбрана объектно-ориентированная концепция построения системы. Применение принципов объектно-ориентированного программирования позволило разработать гибкую архитектуру программного обеспечения, позволяющую с минимальными затрата-

Рис. 1: Структура СППР FIESTA

ми на программирование расширять возможности системы. FIESTA реализована на языке C++ с применением библиотеки классов Microsoft Foundation Classes (MFC). Иерархия классов СППР FIESTA включает около 40 классов, образующих следующие подсистемы:

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

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

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

В данный момент СППР FIESTA позволяет решать задачи по следующим моделям:

• задача модальной оптимизации;

• максимаксная модель;

• задача максимизации возможности достижения нечеткой цели;

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

Поддерживаются следующие модели ограничений:

• модальные ограничения;

• построчные ограничения по возможности;

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

Архитектура СППР FIESTA позволяет включать в нее и другие оптимизационные модели.

CFuzzyDoc

^ -Л

CFModel CConsModel ^

CLPExport CSimplexSolver CAdvSolver

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

Векторы целей и ограничений детерминированного аналога

Решение

CShowResultDlg

Рис. 2: Решение задачи возможиостного программирования

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

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

В параграфе 4.4 обосновано применение алгоритма бинарного поиска для нахождения максимальных уровней возможностей (необходимостей) выполнения ограничений, обеспечивающих совместность системы. Это вызвано его высокой вычислительной эффективностью и способностью работать с распределениями возможности различных видов.

Для решения задачи нахождения недоминируемого вектора возможностей, обеспечивающего совместность системы возможностных ограниче-ний,реализованы два алгоритма: алгоритм генетической оптимизации и алгоритм симплексного спуска, предложенный J.A Neider и R. Mead. Выбор этих алгоритмов обусловлен минимальными требованиями к свойствам оптимизируемой функции (достаточно возможности вычисления значения функции в отдельных точках), что позволяет использовать данные алгоритмы не ограничивая классы возможностных распределений параметров задачи.

СППР FIESTA функционирует в среде Windows 32 и выполнена в стандарте Multiple Document Interface. Использование стандартной концепции интерфейса Windows облегчает освоение программы новыми пользователями. Пользователю предоставляется возможность работать одновременно с несколькими задачами, каждая из которых располагается в своем окне.

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

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

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

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

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

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

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

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

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

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

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

Публикации автора по теме диссертации

1. Сорокин СВ., Язенин А.В. Система поддержки принятия решений на базе моделей и методов возможностной оптимизации // Программные продукты и системы, 2000. №2. С. 9-13.

2. Сорокин СВ., Язенин А.В. Анализ структуры задач возможностно-го программирования // Сложные системы: обработка информации, моделирование и оптимизация. Тверь: ТвГУ, 2002. С. 120-130.

3. Сорокин СВ. Анализ структуры задач возможностного программирования в контексте мер возможности и необходимости // Вестник Тверского государственного университета, серия "Прикладная математика". Тверь, 2003. №2. С. 44-51.

4. Сорокин СВ., Язенин А.В. Методы коррекции задач возможностной оптимизации и их реализация в системах поддержки принятия решений // П-й международный научно-практический семинар "Интегрированные модели и мягкие вычисления в искусственном интеллекте". М.: Физматлит, 2003. С 131-136.

5. Сорокин СВ. К задаче нахождения недоминируемого вектора возможностей совместности систем возможностных ограничений // Сложные системы: обработка информации, моделирование и оптимизация. Тверь, 2004 (в печати).

6. Сорокин СВ. Программная система поддержки моделей и методов возможностной оптимизации. Методические рекомендации. Тверь: ТвГУ, 2004. 24 с.

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

»21485

РНБ Русский фонд

2005-4 19983

Технический редактор Т.В.Малахова Подписано в печать 18.11.2004. Формат 60 х 84 х!хь. Бумага типографская № 1. Печать офсетная. Усл.печл. 1,25. Уч.-изд.л. 1,0. Тираж 100 экз. Заказ № 555. Тверской государственный университет, Редакционно-издательское управление. Адрес: Россия, 170000, г. Тверь, ул. Желябова, 33. Тел. РЙУ: (0822) 42-60-63.

Введение

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 и описывающего рациональный выбор в задаче о нахождении недоминируемых уровней возможностей, обеспечивающих совместность систем возможностных ограничений. Также возможно исследование задач, решение которых невозможно не из-за несовместности систем ограничений, а из-за неограниченности области допустимых решений в направлении возрастания целевой функции.

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