ВВЕДЕНИЕ
Актуальность проблемы. Высокий уровень капиталовложений, необходимых при создании высокотехнологичных производств, требует эффективного использования средств, которое в первую очередь достигается за счет оптимизации структуры и параметров таких производств на основе применения новых информационных технологий (ИТ), и математического моделирования на базе современной вычислительной техники.
Особое место в этом комплексе задач занимают проблемы выбора и принятия решений, потребность в разрешении которых возникает на всем протяжении жизненного цикла любой, сколько-нибудь сложной системы. При этом процесс решения происходит в условиях ограничений, обусловленных спецификой функционирования системы: сложность математической модели, большое число рассматриваемых альтернативных вариантов, наличие вектора конфликтующих критериев, значительная неопределенность исходной информации. В этих условиях решающую роль должны сыграть модели и методы поддержки принятия решений, основанные на последних достижениях математического моделирования, векторной оптимизации и теории принятия решений.
Однако, многие существующие модели и методы недостаточно эффективны для решения столь сложных задач. Серьезным препятствием является также слабая связь между отдельными этапами решения общей задачи выбора. Вследствие этого возникают проблемные вопросы, связанные с разработкой единой методологии с позиций системного подхода, теоретическим обоснованием реализующих ее моделей и алгоритмов, модификацией существующих, а также разработкой новых методов и соответствующих программных продуктов.
Диссертационная работа выполнена в рамках госбюджетной НИР, № госрегистрации 01960007318 по теме № 1.6.2 "Моделирование, выбор и принятие решений в структурно-параметрическом представлении
функционирования многоцелевых систем применительно к теории конфликта" (№ г/р 01.2001.16818).
Целью исследований является разработка методологии и научных основ, а также создание конкретных моделей выбора, обеспечивающих построение инструментальных средств в виде математического и программного обеспечения автоматизированных систем поддержки принятия решений при проектировании и оптимизации функционирования технологических систем.
Поставленная цель достигается посредством решения следующих задач.
1. Исследование и разработка моделей и методологии, позволяющих с единых позиций рассмотреть задачи непрерывной и дискретной векторной оптимизации и сужения множества эффективных альтернатив, как составные части единой задачи выбора.
2. Теоретическое обоснование метода экстраполяции экспертных оценок (МЭЭО), исследование вопросов существования и единственности решения задачи параметрического синтеза модели выбора и сходимости соответствующих итерационных процедур; разработка на этой основе конкретных методов синтеза моделей выбора.
3. Анализ различных условий применения МЭЭО в проектировании и оптимизации функционирования технологических систем (ТС); разработка на этой основе системы моделей выбора, соответствующих различным шкалам оценивания альтернатив, индивидуальной или групповой экспертизе, механизмам выбора, применяемым в построенных моделях.
4. Обоснование и разработка новых эффективных методов аппроксимации множества неулучшаемах решений задач дискретной и непрерывной многокритериальной оптимизации в структурном и параметрическом синтезе ТС.
5. Разработка методов декомпозиции моделей ТС сложной структуры, содержащих разветвления и циклы технологических потоков, позволяющих
8
использовать эффективные алгоритмы поиска множества неулучшаемых технологических решений.
6. Создание программного обеспечения, реализующего модели и методы решения задач выбора.
7. Проведение вычислительных экспериментов и апробация программного обеспечения на решении практически значимых задач проектирования и оптимизации функционирования ТС.
Методы исследования. Выполненные исследования базируются на использовании аппарата теории графов, математического программирования, теории выбора и принятия решений, теории вероятностей и математической статистики. Общей методологической основой является системный подход.
Научная новизна работы состоит в следующем.
1. Создана единая методология, объединяющая способы решения задач, возникающих на различных этапах и уровнях иерархии оптимизационного моделирования технологических систем.
2. Проведены теоретическое обоснование, разработка и исследование моделей выбора, расширяющих возможности известных аналогов за счет использования лингвистической и числовой шкал экспертного оценивания.
3. Выделен новый класс численных методов непрерывной и дискретной оптимизации - алгоритмы циклического выбора (АЦВ), получено общее необходимое и достаточное условие корректности отсева неудовлетворительных решений для всех процедур данного класса; на основе найденного условия разработаны три варианта АЦВ непрерывной оптимизации, использующие более эффективные механизмы выбора по сравнению с известными аналогами; доказана их сходимость по Хаусдорфу в пространствах оценок и решений.
4. Получено обобщение принципа оптимальности Беллмана на случай бинарного отношения предпочтения на множестве векторных оценок; на его основе разработаны два алгоритма поиска на графах произвольного вида
всего множества путей, недоминируемых по отношению предпочтения.
5. Получены новые достаточные условия непрерывности Парето-оптимальных решений по параметрам свертки критериев; по сравнению с известными результатами, данные условия обладают меньшей жесткостью и большей универсальностью, т.к. применимы к различным сверткам и предусматривают случаи однозначных и многозначных отображений множества параметров на множество оценок.
6. Разработаны два метода параметризации непрерывной векторной оптимизационной задачи для произвольных вариантов логических сверток; первый использует сеть на ранее не применявшемся множестве параметров, и, вследствие этого, адаптируется к погрешностям оценок границ множества Парето; второй метод отличается возможностью быстрого упорядочения множества сгенерированных весов сверток для произвольного числа критериев и узлов сети, что дает сокращение количества итераций за счет рационального подбора начальных приближений при решении каждой скалярной задачи.
7. Предложено новое, более общее, определение конфликта случайных величин; получено его необходимое и достаточное условие при нормальном распределении величин.
8. Доказана iW-полнота задачи оптимальной фильтрации произвольного конечного множества точек; выделена задача фильтрации частного вида, не являющаяся iVP-полной, для которой разработан эффективный алгоритм точного решения.
На защиту выносятся
1. Методология и фундаментальные научные основы синтеза моделей выбора технологических решений.
2. Разработанные новые модели, методы и алгоритмы выбора, непрерывной и дискретной многокритериальной оптимизации для решения задач проектирования и оптимизации функционирования ТС.
10
Практическая значимость работы состоит в построении комплекса инструментальных средств на основе новых моделей, численных схем и алгоритмов выбора, непрерывной и дискретной многокритериальной оптимизации. С помощью разработанного программного обеспечения решен ряд практически важных задач лесной, деревообрабатывающей и пищевой промышленности. Достоверность и полнота результатов исследований подтверждена их практической реализацией на примере оптимизации функционирования кристаллизационного отделения производства сахара на АООТ "Сахарный завод "Балашовский". Результаты исследований внедрены в учебный процесс Воронежской государственной технологической академии, Воронежской государственной лесо-технической академии, Орловского государственного технического университета, Орловского коммерческого института.
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались
- на Всероссийских научных конференциях "Информационные технологии и системы - Воронеж, 1995, 1999; "Комплексная продуктивность лесов и организация многоцелевого (многопродуктового) лесопользования" - Воронеж, 1995; "Физико-химические основы пищевых и химических производств" - Воронеж, 1996; "Повышение эффективности методов и средств обработки информации" - Тамбов, 2000, "Теория конфликта и ее приложения" - Воронеж, 2000, 2004;
- на конференциях "Математическое и машинное моделирование" — Воронеж, 1988; "Актуальные проблемы информационного мониторинга" — Воронеж, 1998; "Современные методы в теории краевых задач. Понтрягинские чтения" - Воронеж, 1998, 1999,2000.
- на отчетных научно-технических конференциях ВГТА. Публикации. Основное содержание работы изложено в 43
публикациях, из них 10 - в изданиях, рекомендуемых ВАК РФ.
Объем и структура работы. Диссертационная работа состоит из введения, девяти глав, заключения, списка литературы из 361 наименований
11
и двух приложений. Основной текст изложен на 288 страницах без списка литературы. Работа содержит 16 таблиц, 12 рисунков. Объем приложений — 19 страниц.
В первой главе отмечено, что предметом исследований являются системы и задачи, соответствующие тезису: объективные модели - субъективные решения. Анализируются три основных подхода к решению задач многокритериальной оптимизации таких систем. Делается вывод о преимуществе двухэтапной мажоритарной схемы. На основании проведенного анализа и сделанных выводов формулируется цель, и ставятся задачи исследований.
Во второй главе рассматриваются методы построения моделей выбора на основе экстраполяции экспертных оценок при использовании индивидуальной экспертизы на порядковой и лингвистической шкалах.
В третье главе предлагаются статистические методы построения ска-лярно-оптимизационных моделей выбора при коллективной экспертизе.
В четвертой главе исследуются модели выбора, основанные на механизме блокировки по бинарному отношению предпочтения, построенному по результатам экспертизы - экстраполяции по конусу.
В пятой главе описывается новый класс численных методов решения задач первого этапа мажоритарной схемы - алгоритмы циклического выбора. Также предлагаются два метода этого класса для построения множества неулучшаемых решений дискретных задач на основе принципа оптимальности Бэллмана, обобщенного на случай векторного критерия и наличия отношения предпочтения на множестве оценок.
В шестой главе исследуется возможность применения алгоритмов поэтапного выбора для моделирования ТС большой размерности и сложной структуры, т.е. содержащей разветвления и циклы технологических потоков.
В седьмой главе рассматриваются алгоритмы циклического выбора решения задачи непрерывной многокритериальной оптимизации. Исследуется их сходимость по Хаусдорфу.
В восьмой главе исследуется применение методов скаляризации для
12
построения набора Парето-оптимальных точек задачи непрерывной многокритериальной оптимизации, а также предлагается алгоритм построения и упорядочения набора параметров сверток в целях повышения скорости оптимизации.
В девятой главе описывается реализация первого этапа мажоритарной схемы, состоящая из четырех фаз: зондирование, локализация, оптимизация, фильтрация.
13
ГЛАВА 1
ВЫБОР И ПРИНЯТИЕ РЕШЕНИЙ В МОДЕЛИРОВАНИИ ТЕХНОЛОГИЧЕСКИХ СИСТЕМ
Потребность в решении различного типа задач выбора возникает на всем протяжении жизненного цикла любой сколько-нибудь сложной системы. В [123] сформулировано пять основных классифицирующих признаков задач выбора и принятия решений. Первым и определяющим из них является наличие или отсутствие объективной модели, связывающей большинство параметров исследуемого объекта.
Будем предполагать, что в распоряжении исследователя имеется математическая модель объекта. Это означает, что существует система алгоритмов, позволяющих по заданному набору входных параметров вычислить любые интересующие характеристики системы. Помимо этого на множестве входов определен набор критериев качества, то есть характеристик системы, связанных с её качеством монотонной зависимостью [252]. Таким образом, речь в данной работе пойдет о задачах, соответствующих тезису: объективные модели - субъективные решения [168].
1.1. Модели и методы многокритериальной оптимизации,
выбора и принятия решений
Формально задачу многокритериальной оптимизации можно записать в виде
y{x)^opt, xeDqE", (1.1)
где х - вектор входных параметров; D - область допустимых решений (ОДР); у(х) - вектор-функция критериев.
Поскольку отдельные критерии обычно конфликтуют между собой, то, как правило, не существует такого набора входных параметров, при которых достигался бы оптимум одновременно всех критериев. В связи с этим возникает неопределенность в выборе оптимального решения.
14
Сложность решения задачи (1.1) заключается в том, что в самой постановке задачи отсутствует какая-либо дополнительная информация, которая позволила бы снять эту неопределенность. Поэтому основное назначение моделей и методов решения задач многокритериальной оптимизации — получение необходимой информации либо посредством более детального изучения объекта моделирования и формирования на этой основе какого-нибудь формального правила снятия неопределенности, либо с помощью опроса экспертов и использования их опыта и интуиции. В этом плане можно выделить три подхода к решению данной задачи:
- применение скалярно-оптимизационного выбора;
- использование человеко-машинных процедур поиска;
- применение мажоритарных схем.
Скалярно-оптимизационный выбор.
Скалярно-оптимизационный механизм выбора состоит в поиске решения, на котором достигается оптимум выбранной скалярной функции. При наличии нескольких критериев данный механизм подразумевает применение некоторого обобщенного критерия. При его синтезе используется априорный и апостериорный подходы.
С априорным подходом связаны, прежде всего, начальные шаги векторной оптимизации, когда для раскрытия неопределенности применялись простейшие свертки, казавшиеся достаточно разумными. В настоящее время подобный подход применяется крайне редко и имеет в основном вспомогательное либо теоретическое значение.
Обозначим F - обобщенный критерий. Будем считать, что в задаче (1.1) все частные критерии необходимо минимизировать. Можно отметить следующие априорные принципы формирования обобщенного критерия:
- принцип Нэша [204]: F = Y[ У[ (х) \
i принцип доминирующего результата [177]: F = таху^х);
15 - принцип гарантированного результата: F = min yt(х);
i
- принцип Гурвица [177]: F = ammyj(x) + (l-a)max yj(x); a> 0.
- принцип главного критерия [79] с переводом остальных в разряд ограничений;
- минимум уклонения от идеальной точки а* по заданной норме, не
использующей весов значимости критериев [37]: F = у(х) — ah
- суммарная эффективность [96]: F =
i
Апостериорные методы синтеза обобщенного критерия опираются, прежде всего, на понятие относительной важности критериев. Согласно [253] можно выделить два подхода к определению коэффициентов значимости частных критериев.
В методах 1-й группы коэффициенты назначаются непосредственно или получаются с помощью прямого сравнения критериев по важности. Результаты такого сравнения представляются либо в виде упорядочивания критериев, либо в виде матрицы парных сравнений. Из наиболее известных процедур оценки весов по результатам анализа матрицы парных сравнений можно отметить метод Уэя [357] и его усовершенствованный вариант [23], метод собственного вектора Саати [350], метод Коггера [321], а также метод остовного дерева Юшманова [310].
Для всех способов 1-й группы понятие важности критериев формально не определено, эксперты исходят из своих интуитивных представлений. Кроме того, важность оценивается без связи с видом нормировки и структуры свертки.
В методах 2-й группы коэффициенты важности отыскиваются по информации о сравнении некоторых "контрольных " оценок по предпочтению, обычно искусственно сгенерированных. По результатам сравнений составляется система равенств и неравенств для обобщенного критерия с неизвестными весами.
16
Существенному продвижению в повышении качества идентификации функции обобщенного критерия с весами значимости способствовали работы В.В. Подиновского. Во-первых, им предположено формальное определение понятия обобщенного критерия [221]. Согласно этому определению
функция F(b,k) называется обобщенным критерием, а её параметры 6/ - коэффициентами важности критериев kj, i = 1,2,...т, если для любых номеров р,# е {1,—» т), всяких bj> 0 и у,zeEm выполняются условия:
1) неравенство F(b,y)>F(b,z) влечет F(ab,y) > F(ab,z) при любом
ос>0;
2) если у > уд и bp>bq, то имеет место неравенство
F(b,y)> F(b,ypq),ypq - векторная оценка, полученная из у перестановкой
координат ур, уд;
3) если zp>yp,zq), что при b Ib>$ выполняется неравенство F(b,z)>F(b,y).
Несколько иной вариант приведенного определения был дан Полищу-ком[231].
Во-вторых, В.В. Подиновским была решена проблема формального описания качественной важности критериев [221, 224 - 226, 349]. Основу разработанной теории составили строгие определения понятий: «Один критерий важнее другого» и «Оба критерия равноценны».
Утверждение «критерии кр и к равноценны» означает, что всякие
две векторные оценки у и у одинаковы по предпочтительности (yp,q
имеет тот же смысл, что и выше).
Утверждение «критерий к важнее, чем к » означает, что векторная
оценка у, в которой ур > yq предпочтительней, чем ypq.
17
Для определения коэффициентов важности строится специальная система отношений на подмножествах критериев.
В более поздней работе [227] В.В. Подиновским был предложен формальный подход и к количественному описанию важности критериев, в котором дается строгое определение понятия степени превосходства важности одного критерия над другим: «Критерий кр в npq раз важнее kq».
Формальный подход к количественному описанию важности критериев предложен также в работах других авторов [201, 346]. Однако, он предполагает наличие специальных числовых характеристик предпочтений по каждому критерию и в принципе не применим к качественным критериям.
Многие процедуры синтеза обобщенного критерия используют определенные аксиоматические допущения, на основании которых доказывается существование функции критерия данного вида. Например, в [72, 141, 142, 198, 281, 340] приводятся различные аксиомы, в основном аксиомы независимости, на основании которых доказывается существование обобщенных критериев аддитивной формы
S/)) (1.2)
где Х[ — некоторый /-й признак; fi(xf)- интенсивность /-го признака; ?//— частная полезность /-го признака; А,,— коэффициент значимости.
Аналогично в [141] доказывается теорема существования мультипликативной функции полезности:
Что же касается конкретных процедур второй группы синтеза обобщенного критерия, то отметим следующие. Во-первых, методы, основанные на построении линейной системы неравенств, определяющей возможные значения весовых векторов:
- метод Черчмена-Акофа [320] и его варианты [317, 355];
- метод лексикографии Подиновского [229].

Получить работу