Содержание к диссертации
ВВЕДЕНИЕ 6
ГЛАВА 1. ВЫБОР И ПРИНЯТИЕ РЕШЕНИЙ В МОДЕЛИ-РОВАНИИ ТЕХНОЛОГИЧЕСКИХ СИСТЕМ
1.1. Модели и методы многокритериальной оптимизации, выбора и принятия решений.
1.2. Коллективный выбор 33
1.3. Нечеткость в задачах выбора 42
1.4. Метод экстраполяции экспертных оценок 46
1.5. Особенности решения дискретных задач поэтапного выбора в технологических системах
1.6. Поиск неулучшаемых решений задач непрерывной многокритериальной оптимизации в моделировании технологических систем.
1.7. Выводы. Цель и задачи исследования. 75
ГЛАВА 2. МЕТОД ЭКСТРАПОЛЯЦИИ ЭКСПЕРТНЫХ ОЦЕНОК. ИНДИВИДУАЛЬНЫЙ ВЫБОР. ЭКСТРАПОЛЯЦИЯ ПО ВЕКТОРУ
2.1. Предпосылки построения системы моделей выбора на основе МЭЭО.
2.2. Экспертиза на порядковой шкале. Алгоритм бисекции.
2.3. Экспертиза на лингвистической шкале 89
2.4. Приближенное нахождение сильной оценки коэффициентов ФП
2.5. Получение случайных точек на множестве допустмых оценок
2.6. Пример использования МЭЭО в маркетинговых исследованиях
Выводы по главе 105
ГЛАВА 3. ЭКСТРАПОЛЯЦИЯ ПО ВЕКТОРУ. КОЛЛЕКТИВНЫЙ ВЫБОР
3.1. Групповая экспертиза на порядковой и лингвистиче- ской шкалах
Вопросы существования и единственности решения
Групповая экспертиза на шкале отношений
3.4. Асимптотические свойства ММП-оценок коэффициентов.
3.5. Применение МЭЭО для моделирования свойств многокомпонентной смеси
Выводы по главе 132
ГЛАВА 4. МЕТОД ЭКСТРАПОЛЯЦИИ ЭКСПЕРТНЫХ ОЦЕНОК. ЭКСТРАПОЛЯЦИЯ ПО КОНУСУ
4.1. Модель выбора на основе экстраполяции по конусу 134
4.2. Экстраполяция по конусу на лингвистической шкале 136
4.3. Применение экстраполяции по конусу для получения точечных оценок коэффициентов ФП.
4.4. Нелинейная функция полезности 141
Выводы по главе 143
ГЛАВА 5. ПОЭТАПНЫЙ ВЫБОР В ТЕХНОЛОГИЧЕСКИХ СИСТЕМАХ
5.1. Алгоритмы циклического выбора в дискретной оп- тимизации
5.2. Векторный вариант алгоритма Форда-Беллмана 148
5.3. Поиск эффективных путей в бесконтурном графе 154
5.4. Применение векторной оптимизации на графах для моделирования раскроя лесоматериалов.
Выводы по главе 162
ГЛАВА 6. ПРИМЕНЕНИЕ АЛГОРИТМОВ ПОЭТАПНОГО 163 ВЫБОРА ДЛЯ МОДЕЛИРОВАНИЯ ТС БОЛЬШОЙ РАЗМЕРНОСТИ И СЛОЖНОЙ СТРУКТУРЫ
6.1. Обсуждение возможностей алгоритмов поиска R- оптимальных путей
6.2. Вычислительные эксперименты по проверке алго-ритмов поэтапного выбора
6.3. Системная модель многокритериального поэтапного выбора решений в ТС сложной структуры
6.4. Модели декомпозиции графа и синтеза интегральных решений
6.5. Поэтапный выбор при оптимизации функционирования кристаллизационного отделения в производстве сахара
Выводы по главе 194
ГЛАВА 7. АЛГОРИТМЫ ЦИКЛИЧЕСКОГО ВЫБОРА В НЕПРЕРЫВНОЙ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ
7.1. Выбор по Парето 195
7.2. Ужесточение выбора. Регулярный случай.
7.3. Применение совокупно-экстремального выбора 212
Выводы по главе 217
ГЛАВА 8. МЕТОДЫ СКАЛЯРИЗАЦИИ В НЕПРЕРЫВНОЙ 2НОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ 242
8.1. Построение и упорядочение множества параметровЛ(А)
8.2. Свойство множества A(h) 230
8.3. Универсальные условия непрерывности эффективных решений по параметру
8.4. Условия непрерывности для логических серток 238
8.5. Свойства сети на множестве Г
8.6. Построение сети на множестве Г
Выводы по главе 254
ГЛАВА 9. ОПИСАНИЕ МЕТОДИКИ ПОИСКА МНОЖЕСТВА НЕУЛУЧШАЕМЫХ АЛЬТЕРНАТИВ
9.1. Зондирование и локализация 256
9.2. Оптимизация 265
9.3. Фильтрация множества Парето. Точное решение за дачи
9.4. Фильтрация множества Парето. Приближенное решение задачи
Выводы по главе 284
Заключение 286
Список литературы 289
Приложение 1 325
Приложение 2 335
Введение к работе
Актуальность проблемы. Высокий уровень капиталовложений, необходимых при создании высокотехнологичных производств, требует эффективного использования средств, которое в первую очередь достигается за счет оптимизации структуры и параметров таких производств на основе применения новых информационных технологий (ИТ), и математического моделирования на базе современной вычислительной техники.
Особое место в этом комплексе задач занимают проблемы выбора и принятия решений, потребность в разрешении которых возникает на всем протяжении жизненного цикла любой, сколько-нибудь сложной системы. При этом процесс решения происходит в условиях ограничений, обусловленных спецификой функционирования системы: сложность математической модели, большое число рассматриваемых альтернативных вариантов, наличие вектора конфликтующих критериев, значительная неопределенность исходной информации. В этих условиях решающую роль должны сыграть модели и методы поддержки принятия решений, основанные на последних достижениях математического моделирования, векторной оптимизации и теории принятия решений.
Однако, многие существующие модели и методы недостаточно эффективны для решения столь сложных задач. Серьезным препятствием является также слабая связь между отдельными этапами решения общей задачи выбора. Вследствие этого возникают проблемные вопросы, связанные с разработкой единой методологии с позиций системного подхода, теоретическим обоснованием реализующих ее моделей и алгоритмов, модификацией существующих, а также разработкой новых методов и соответствующих программных продуктов.
Диссертационная работа выполнена в рамках госбюджетной НИР, № госрегистрации 01960007318 по теме № 1.6.2 "Моделирование, выбор и принятие решений в структурно-параметрическом представлении функционирования многоцелевых систем применительно к теории конфликта" (№ г/р 01.2001.16818).
Целью исследований является разработка методологии и научных основ, а также создание конкретных моделей выбора, обеспечивающих построение инструментальных средств в виде математического и программного обеспечения автоматизированных систем поддержки принятия решений при проектировании и оптимизации функционирования технологических систем.
Поставленная цель достигается посредством решения следующих задач.
1. Исследование и разработка моделей и методологии, позволяющих с единых позиций рассмотреть задачи непрерывной и дискретной векторной оптимизации и сужения множества эффективных альтернатив, как составные части единой задачи выбора.
2. Теоретическое обоснование метода экстраполяции экспертных оценок (МЭЭО), исследование вопросов существования и единственности решения задачи параметрического синтеза модели выбора и сходимости соответствующих итерационных процедур; разработка на этой основе конкретных методов синтеза моделей выбора.
3. Анализ различных условий применения МЭЭО в проектировании и оптимизации функционирования технологических систем (ТС); разработка на этой основе системы моделей выбора, соответствующих различным шкалам оценивания альтернатив, индивидуальной или групповой экспертизе, механизмам выбора, применяемым в построенных моделях.
4. Обоснование и разработка новых эффективных методов аппроксимации множества неулучшаемах решений задач дискретной и непрерывной многокритериальной оптимизации в структурном и параметрическом синтезе ТС.
5. Разработка методов декомпозиции моделей ТС сложной структуры, содержащих разветвления и циклы технологических потоков, позволяющих использовать эффективные алгоритмы поиска множества неулучшаемых технологических решений.
6. Создание программного обеспечения, реализующего модели и методы решения задач выбора.
7. Проведение вычислительных экспериментов и апробация программного обеспечения на решении практически значимых задач проектирования и оптимизации функционирования ТС.
Методы исследования. Выполненные исследования базируются на использовании аппарата теории графов, математического программирования, теории выбора и принятия решений, теории вероятностей и математической статистики. Общей методологической основой является системный подход.
Научная новизна работы состоит в следующем.
1. Создана единая методология, объединяющая способы решения задач, возникающих на различных этапах и уровнях иерархии оптимизационного моделирования технологических систем.
2. Проведены теоретическое обоснование, разработка и исследование моделей выбора, расширяющих возможности известных аналогов за счет использования лингвистической и числовой шкал экспертного оценивания.
3. Выделен новый класс численных методов непрерывной и дискретной оптимизации - алгоритмы циклического выбора (АЦВ), получено общее необходимое и достаточное условие корректности отсева неудовлетворительных решений для всех процедур данного класса; на основе найденного условия разработаны три варианта АЦВ непрерывной оптимизации, использующие более эффективные механизмы выбора по сравнению с известными аналогами; доказана их сходимость по Хаусдорфу в пространствах оценок и решений.
4. Получено обобщение принципа оптимальности Беллмана на случай бинарного отношения предпочтения на множестве векторных оценок; на его основе разработаны два алгоритма поиска на графах произвольного вида
всего множества путей, недоминируемых по отношению предпочтения.
5. Получены новые достаточные условия непрерывности Парето-оптимальных решений по параметрам свертки критериев; по сравнению с известными результатами, данные условия обладают меньшей жесткостью и большей универсальностью, т.к. применимы к различным сверткам и предусматривают случаи однозначных и многозначных отображений множества параметров на множество оценок.
6. Разработаны два метода параметризации непрерывной векторной оптимизационной задачи для произвольных вариантов логических сверток; первый использует сеть на ранее не применявшемся множестве параметров, и, вследствие этого, адаптируется к погрешностям оценок границ множества Парето; второй метод отличается возможностью быстрого упорядочения множества сгенерированных весов сверток для произвольного числа критериев и узлов сети, что дает сокращение количества итераций за счет рационального подбора начальных приближений при решении каждой скалярной задачи.
7. Предложено новое, более общее, определение конфликта случайных величин; получено его необходимое и достаточное условие при нормальном распределении величин.
8. Доказана iVP-полнота задачи оптимальной фильтрации произвольного конечного множества точек; выделена задача фильтрации частного вида, не являющаяся iVP-полной, для которой разработан эффективный алгоритм точного решения.
На защиту выносятся
1. Методология и фундаментальные научные основы синтеза моделей выбора технологических решений.
2. Разработанные новые модели, методы и алгоритмы выбора, непрерывной и дискретной многокритериальной оптимизации для решения задач проектирования и оптимизации функционирования ТС.
Практическая значимость работы состоит в построении комплекса инструментальных средств на основе новых моделей, численных схем и алгоритмов выбора, непрерывной и дискретной многокритериальной оптимизации. С помощью разработанного программного обеспечения решен ряд практически важных задач лесной, деревообрабатывающей и пищевой промышленности. Достоверность и полнота результатов исследований подтверждена их практической реализацией на примере оптимизации функционирования кристаллизационного отделения производства сахара на АООТ "Сахарный завод "Балашовский". Результаты исследований внедрены в учебный процесс Воронежской государственной технологической академии, Воронежской государственной лесо-технической академии, Орловского государственного технического университета, Орловского коммерческого института.
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались
- на Всероссийских научных конференциях "Информационные технологии и системы - Воронеж, 1995, 1999; "Комплексная продуктивность лесов и организация многоцелевого (многопродуктового) лесопользования" - Воронеж, 1995; "Физико-химические основы пищевых и химических производств" - Воронеж, 1996; "Повышение эффективности методов и средств обработки информации" - Тамбов, 2000, "Теория конфликта и ее приложения" - Воронеж, 2000, 2004;
- на конференциях "Математическое и машинное моделирование" — Воронеж, 1988; "Актуальные проблемы информационного мониторинга" -Воронеж, 1998; "Современные методы в теории краевых задач. Понтрягинские чтения" - Воронеж, 1998, 1999,2000.
- на отчетных научно-технических конференциях ВГТА. Публикации. Основное содержание работы изложено в 43 публикациях, из них 10 - в изданиях, рекомендуемых ВАК РФ.
Объем и структура работы. Диссертационная работа состоит из введения, девяти глав, заключения, списка литературы из 361 наименований и двух приложений. Основной текст изложен на 288 страницах без списка литературы. Работа содержит 16 таблиц, 12 рисунков. Объем приложений -19 страниц.
В первой главе отмечено, что предметом исследований являются системы и задачи, соответствующие тезису: объективные модели - субъективные решения. Анализируются три основных подхода к решению задач многокритериальной оптимизации таких систем. Делается вывод о преимуществе двухэтапной мажоритарной схемы. На основании проведенного анализа и сделанных выводов формулируется цель, и ставятся задачи исследований.
Во второй главе рассматриваются методы построения моделей выбора на основе экстраполяции экспертных оценок при использовании индивидуальной экспертизы на порядковой и лингвистической шкалах.
В третье главе предлагаются статистические методы построения ска-лярно-оптимизационных моделей выбора при коллективной экспертизе.
В четвертой главе исследуются модели выбора, основанные на механизме блокировки по бинарному отношению предпочтения, построенному по результатам экспертизы - экстраполяции по конусу.
В пятой главе описывается новый класс численных методов решения задач первого этапа мажоритарной схемы - алгоритмы циклического выбора. Также предлагаются два метода этого класса для построения множества неулучшаемых решений дискретных задач на основе принципа оптимальности Бэллмана, обобщенного на случай векторного критерия и наличия отношения предпочтения на множестве оценок.
В шестой главе исследуется возможность применения алгоритмов поэтапного выбора для моделирования ТС большой размерности и сложной структуры, т.е. содержащей разветвления и циклы технологических потоков.
В седьмой главе рассматриваются алгоритмы циклического выбора решения задачи непрерывной многокритериальной оптимизации. Исследуется их сходимость по Хаусдорфу.
В восьмой главе исследуется применение методов скаляризации для построения набора Парето-оптимальных точек задачи непрерывной многокритериальной оптимизации, а также предлагается алгоритм построения и упорядочения набора параметров сверток в целях повышения скорости оптимизации.
В девятой главе описывается реализация первого этапа мажоритарной схемы, состоящая из четырех фаз: зондирование, локализация, оптимизация, фильтрация.
