Введение к работе
Актуальность темы. Диссертационная работа посвящена развитию стохастических методов реоения оптимизационных задач, сформулированных посредством бинарных отношений предпочтения. Возросший интерес к этим задачам обусловлен развитием диалоговых процедур принятия решений, лежащих в основе систем поддержки принятия решений (СППР).
Участие экспертов и лиц, принимающих решение (ЛПР), в процедурах принятия решений позволяет использовать опит и интуицию специалистов для повышения качества принимаемого решения,учесть не только количественную, но и качественную информацию. Если решение принимается при неполной информации, то недостаток данных может быть частично восполнен интуитивными прогнозами экспертов.
' Развитие СППР требует разработки специальных классов моделей и численных алгоритмов принятия решений, создающих необходимую информационно-вычислительную среду для работы экспертов и ЛПР. К их числу относятся диалоговые процедуры принятия решений, в которых функции ЛПР состоят в анализе генерируемых СППР вариантов решений, попарном их сравнении и отборе лучших из них. Подходящей математической моделью для описания этих функций служат бинарные отношения предпочтения, определенные на множестве всевозможных вариантов решений. Задачи поиска наилучшего решения в режиме диалога специалиста и СППР сводятся к оптимизационным задачам, сформулированным посредством отношений предпочтения. Рассмотрение диалоговой процедуры принятия решений как алгоритма решения таких задач позволяет дать математическое доказательство того, что при определенных предположениях об ответах ЛПР результатом процедуры будет наилучшее решение. Развитие данного подхода можно рассматривать как обобщение оптимизационных постановок на случай человеко-машинных процедур принятия решений. При этом возникают как традиционные для математического программирования проблемы (анализ методов, доказательство их сходимости, оценивание скорости сходимости), так и принципиально новые. Одна из них - исследование чувствительности методов к случайным ошибкам в оценках ЛПР и снижение влияния таких ошибок на эффективность полученного решения. С ней тесно связаны рассмотрение процедур коллективного принятия решений, оценивание степени компетентности ЛПР и использование таких оценок в процедурах принятия решений. Поэтому необходимо развитие
цельной теории построения и анализа численных методов решения оптимизационных задач, сформулированных посредством бинарных отношений. Такая теория служит математической основой для создания и анализа прикладных диалоговых процедур принятия решений.
3 силу отмеченного проблема построения и исследования численных уотодов решения оптимизационных задач, сформулированных посредством бинарных отношений предпочтения, актуальна в теоретическом и прикладном аспектах, сложна и требует отдельного рассмотрения.
Различные подходы к построению диалоговых процедур принятия решений рассматривались в работах В.Л.Волковича, В.А.Ирико-ва.П.С.Краснощекова, Г.С.Поспелова.
Бинарные отношения и оптимизационные задачи, сформулированные с их помощью, часто использовались для теоретического анализа экономических, технических и других сложных систем. Этому посвящены, в частности, работы Дж.Дебре, Н.П.Бусленко, В.В.Калашникова, Ю.П.Иванилова, И.Н.Коваленко, М.Месаровича. В работах Х.Никайцо, К.Эрроу указанный математический аппарат был использован для исследования поведения потребителей в условиях рыночной экономики. В меньшей степени развиты численные методы решения таких задач. Различные подхода к ним рассматривались, например, А.Вержбицким, Дж.Дайером, Д.В.Юдиным. Особенностью иселедуеїшх в данной работе алгоритмов является их повышенная устойчивость к случайным ошибкам ЖР, достигающаяся за счет увеличения количества обращений к JIT1P и роста общего объема вычислений. В их основу были положены стохастические квазиградиентные методы, развитые в работах Ю.М.Ермольева, A.M.Гупала, В.Т.Поляка и их учеников. Первые из таких алгоритмов были предложены А.Й.Ястремским. В то же время алгоритмы, рассматриваемые в данной работе, имеют существенные отличия от известных методов стохастической оптимизации. Во-первых, случайность в них не только порождается внешними причинами, связанными с постановкой задачи (например, случайными оиибками ДПР), но также заложена в вычислительную схему. Направление поиска на каждой итерации выбирается случайно, с заданным законом распределения. Поэтому данные алгоритмы можно рассматривать и как развитие методов случайного поиска, предложенных в работах В.Г.Кярманова и Л.А.Расстоигина. Bo-вторі-к, они отличаются от стохастических квазиградиентных методов тем, что используемое в них
направления поиска в среднем не совпадают с обобщенным градиентом ( или его аналогом ) целевой функции.
Отмеченные особенности потребовали дополнительного анализа методов стохастической оптимизации, в частности, исследования условий их сходимости и оценок вычислительной сложности. Затем на основе такого анализа было проведено детальное исследование предложенных в работе стохастических процедур принятия решений.
Цель работы. Целью настоящей работы является разработка и исследование (включая доказательство сходимости, анализ вычислительной сложности и устойчивости к ошибкам ЛПР)стохастических алгоритмов решения оптимизационных задач, сформулированных посредством бинарных отношений предпочтения. Рассматриваемые в работе методы основаны на проце.дурах случайного поиска и предназначены для реализации в режиме диалога в качестве типовых элементов алгоритмического обеспечения СШР.
Методика исследований базируется на результатах выпуклого анализа, теории вероятностей, теории полезности, теории многокритериальной оптимизации, условиях сходимости немонотонных алгоритмов стохастического программирования.
Научная новизна. Результаты диссертации можно квалифицировать как направление в теории стохастической оптимизации, связанное с применением её методов для решения оптимизационных задач, сформулированных посредством бинарных отношений предпочтения.
В работе определены классы таких задач, являющиеся аналогами задач выпуклой, квазивыпуклой и дифференцируемой оптимизации. Дня них построены стохастические алгоритмы, учитывающие различные способы задания области допустимых решений: при помощи линейных неравенств или уравнений, нелинейных неравенств, бинарных отношений. Доказана сходимость с вероятностью I предложенных алгоритмов к множеству решений задачи (в невыпуклом случае - к множеству особых точек). Исследована вычислительная сложность предложенных алгоритмов, для чего с заданной доверительной вероятностью было оценено количество их итераций, достаточное для достижения приближенного, с заданной степенью точности, решения задачи. Рассмотрена возможность снижения вычислительной сложности путем применения усредненных направлений спуска, получены условия, при выполнении которых такой подход обоснован, и рекомендации по оптимальному выбору параметров ач-гориткл. Рассмотрены стохастические, частично-целочисленные if
игровые постановки задач, сформулированных в терминах бинарных отношений, предложены алгоритмы их решения.
Исследована устойчивость к случайным ошибкам ЛПР рассмотренных в работе алгоритмов при предположениях о том, что вероятность ошибки ЛПР неизвестна. Определены условия, при выполнении которых устойчивость может быть повышена за счет использования приближенных оценок вероятности ошибки ЛПР и применения коллективных процедур принятия решений. Показана возможность построения алгоритмов, обладающих максимально возможной устойчивостью к ошибкам ЛПР.
Практическая ценность полученных результатов состоит в том, что они позволяют построить математически обоснованные диалоговые процедуры принятия решений, основанные на попарном сравнении ЛПР решений, формируемых СППР. Такие процедуры будут сходиться к оптимальному для ЛПР решению даже в случае, когда вероятность ошибочных оценок ЛПР отличается от 0.
Реализация результатов работы. Данная работа является составной частью исследований, проводившихся на факультете кибернетики Киевского государственного университета им. Т.Г.Шевченко по госбюджетной теме № 32 "Разработать оптимизационные человеко-машинные процедуры принятия решений в сложных социально-экономических системах". Разработанные алгоритмы реализованы в составе диалоговых процедур, созданных для прикладных СППР в ходе выполнения данной темы и хоздоговорной темы 407-88 на факультете кибернетики КГУ, а также при выполнении тем "Таможенник", "Аксон" в ВА ПВО СВ. Результаты работы также использовались в учебном процессе при создании программных средств и подготовке новых курсов лекций на факультете кибернетики Киевского государственного университета им. Т.Г.Шевченко.
Апробация работы. Результаты диссертационной работы докладывались на Международном семинаре по проблемам устойчивости стохастических моделей(пМосква, 1982), ІУ Советско-Японском симпозиуме по теории вероятностей и математической статистике(г Тбилиси, 1982), Международной конференции "Стохастическая оптимизация" (г.Киев, 1984), Международном семинаре "Стохастическая динамическая оптимизация: подходы и применения" (ВНР, г.Шапрон, 1988), Международной конференции "Многокритериальная оптимизация" (г.Ялта, 1988), И Международной конференции.по эконометрическим моделям принятия решений (ФРГ, г.Валберт,1989) на Всесоюзных и Республиканских конференциях, семинарах и
симпозиумах.
Публикации. По теме диссертации опубликовано 35 печатных работ, в том числе монография.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложений. Объем работы - 237 страниц машинописного текста, список литературы содержит 135 наименований.