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

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

У

'Г']-

ЧИКУНОВ Сергей Владимирович

СТРУКТУРНО-ПАРАМЕТРИЧЕСКИЙ СИНТЕЗ МОДЕЛЕЙ МНОГОКРИТЕРИАЛЬНОГО ПОЭТАПНОГО ВЫБОРА РЕШЕНИЙ В ТЕХНОЛОГИЧЕСКИХ СИСТЕМАХ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Воронеж 2003

Работа выполнена на кафедре "Математическое моделирование информационных и технологических систем" Воронежской государственной технологической академии (ВГТА).

Научный руководитель: доктор технических наук, профессор,

Заслуженный деятель науки РФ

Сысоев Валерий Васильевич

Научный консультант: доктор технических наук, профессор

Сербулов Юрий Стефанович

Официальные оппоненты: доктор технических наук, профессор

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

Ведущая организация: Белгородский государственный

технологический университет им. В.Г. Шухова, г. Белгород

Защита диссертации состоится " 16 " октября 2003 г. в [5_час.

на заседании диссертационного совета Д 212.035.02 в Государственном образовательном учреждении Воронежской государственной технологической академии по адресу: 394000, г. Воронеж, проспект Революции, 19, а. 30 (конференц-зал).

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

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

Ученый секретарь ' ^

диссертационного совета ^^ Самойлов В.М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

Диссертационная работа выполнена в рамках госбюджетной НИР (№ г.р. 01960007318) по теме № 1.6.2 "Моделирование, выбор и принятие решений в структурно-параметрическом представлении функционирования многоцелевых систем применительно к теории конфликта" (№ г.р. 01.2001.16818).

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

Поставленная цель достигается в результате решения задач:

- разработка системной модели многокритериального поэтапного выбора решений в ТС в структурном представлении;

- разработка механизма МПВ эффективных решений;

- разработка моделей многокритериального поэтапного выбора решений в ТС с инвариантными свойствами к предметной области;

- разработка алгоритмических моделей МПВ в задачах поиска эффективных вариантов решений в ТС;

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

- проведение вычислительных экспериментов и практическая реализация результатов исследования в реальных производственных условиях.

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

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

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

- модели декомпозиции и синтеза интегральных решений, позволяющие решать задачи МПВ эффективных решений в ТС с разветвлениями и/или возвратами технологических потоков;

- механизм поэтапного выбора решений, отличающийся от известных обобщением на случай нескольких критериев скалярных схем, реализующих ПОБ, и представленный в терминах ФВ;

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

- алгоритмические модели МПВ решений в технологических системах с инвариантными свойствами к предметной области.

Практическая значимость работы состоит в разработке инструментальных средств в виде моделей, алгоритмов и ППП, обеспечивающих поиск эффективных решений в многоэтапных задачах оптимизации произвольной структуры по совокупности критериев, использование которых целесообразно в СППР, САПР, АСНИ, АСУТП, АСУ различного предметного назначения. Разработанный ППП "МРУТ8" внедрен на АООТ "Сахарный завод "Балашовский" путем включения в комплексные системы управления различного уровня, передачи документации на математическое и программное обеспечения, а также применяется в учебном процессе ВГТА для обучения студентов по специальности 071900 "Информационные системы и технологии", в учебном процессе ВГЛТА - по специальности 210200

"Автоматизация технологических процессов и производств". Эффект от внедрения - социальный.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на Всероссийских научно-технических конференциях: "Информационные технологии и системы" (Воронеж, 1999г.), "Повышение эффективности методов и средств обработки информации" (Тамбов, 2000г.), "Теория конфликта и ее приложения" (Воронеж, 2000г.); на научно-практической конференции "Актуальные проблемы информационного мониторинга" (Воронеж, 1998г.); на научном семинаре школы "Понтрягинские чтения -IX" (Воронеж, 1998г.); на научно-практической конференции аспирантов и соискателей ВГТА "Актуальные проблемы научно-практических исследований и методологий" (Воронеж, 1997г.); на ХХХУ-ХХХУН, XXXIX, ХЬ отчетных научных конференциях ВГТА за 1996-1998 г.г., 2000 г., 2001 г., соответственно (Воронеж).

Публикации. По теме диссертационной работы опубликовано 15 печатных работ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 134 наименований и приложения. Работа изложена на 170 страницах машинописного текста (основной текст занимает 146 страниц), содержит 32 рисунка и 14 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

Вторая глава посвящена структурному синтезу моделей • выбора при поэтапном поиске эффективных вариантов решений в ТС.

На основе принципов системного подхода была разработана системная модель, согласно которой задача МПВ решений в ТС разбивается на следующие последовательно выполняемые процедуры:

1. Формализация задачи. Структура рассматриваемой ТС описывается в виде ориентированного графа в = (V, Е ), где

У = {у1,у2, ..., уп} - множество вершин, представляющих собой возможные варианты технологических операций (ТО); Е = {[у15у]3} = {е}> (] = 1,п, - множество дуг, соединяющих

эти вершины (множество материальных, информационных и других потоков между ними), и каждая дуга е е Е характеризуется набором

весов сок (е), к = 1, ш . Тогда решение ассоциируется с некоторым подграфом § = (У§,Её), ^с V, Её с Е исходного графа (например, маршрут изготовления изделий). На множестве всех возможных решений {ц} определена векторная критериальная функция

X(g) = (x,(g), x2(g), ..., xm(g)), где xk(g) = £юк (e) - к-й крите-

eeEg

рий эффективности каждого решения, аддитивный в силу спецификг рассматриваемого класса задач (например, затраты, время обработки).

В таком представлении задача МПВ заключается в выборе и: множества возможных решений некоторой совокупности эффективных альтернатив X = {x(g)} =C({g}) с PAR, предпочтительных ( точки зрения ЛПР, где PAR - множество Парето-оптимальных решений, С - функция выбора.

2. Декомпозиция полученного графа G на отдельные фрагменте

- ациклические подграфы Gv =(Vl(/,El|;), G^cG, \\i = 1,J, такие

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

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

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

будет содержать множество эффективных путей Gv : {р* , у = 1, J

где р* - эффективный путь.

5. Формирование множества интегральных решений (композиция решений), осуществляемая объединением фрагментов путей < учетом связей и ограничений, обеспечивающих целостность ТС. Однако среди найденных вариантов решений могут оказаться и неэффективные, которые необходимо отбросить. Для этого предлагается использовать функцию выбора на множестве возможных интегральны? вариантов ТС. В итоге получим множество эффективных интегральных вариантов {р*}.

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

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

1. Структура в виде совокупности линейных цепочек с постоянным числом операций. Задача в этом случае представляет собой выбор на каждой операции оптимального варианта ее реализации, например, тип оборудования, вариант управляющего воздействия и т.п. Теоретико-множественное объединение возможных вариантов структуры (обобщенная структура) представляет собой многодольный граф в, в котором все множество вершин V разбито на подмножества 11), и2,ик таким образом, что каждая дуга соединяет две вершины и, V/ из смежных подмножеств: и е и;, е и|+]. Решение представляет собой совокупность путей на графе с оптимальным вектором весов, соединяющих начальную и конечную вершины.

2. Структура в виде совокупности линейных цепочек с различным числом операций. В ТС этого типа допускается вариантность в функциональном назначении каждой операции. Обобщенная структура такой ТС представляет собой бесконтурный ориентированный граф общего вида в. Здесь все множество вершин V также разбито на подмножества II], и2,...,ик , но, в отличие от п.1, каждая дуга соединяет

две вершины и, из которых ие11р а \veUj, и = 1,к, то

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

3. Структура ТС с разветвлениями. В структурах этого типа каждый вариант технологического маршрута содержит разветвление технологических потоков.

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

Два последних варианта структуры ТС не допускают представление решения в виде множества путей на графе, так как каждый тех-

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

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

7

> - вариант технологического маршрута Рис. 1. Декомпозиция графа в с возвратами технологических потоков

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

Обозначим: - подмножества вершин графа в,

каждое из которых представляет собой совокупность однотипных вершин, соответствующих разветвлениям, соединениям или местам входа возвратов технологических потоков; \¥0, Wk+1 - подмножества, состоящие из одного элемента - начальной и конечной вершин, соответственно; - подмножество вершин из совокупности

] Ф1, смежных с подмножеством . Эти подмножества разбивают исходный граф в на отдельные фрагменты (рис.2) - ацикличе-

ские подграфы G^, ц/ = 1,J, состоящие из путей между смежными множествами вершин Wj и Next (\W-) .

Рис. 2. Подграфы Gv графа G с возвратами технологических потоков

Предложен подход к построению модели синтеза интегральных решений. Поиск таких решений предлагается осуществлять последовательным объединением их фрагментов - эффективных путей, найденных в ациклических подграфах между подмножествами W; и Next (Wj), то есть определенных на декартовом произведении Wj х Next (Wj), i = 0, k , с учетом целостности ТС и сужением посредством функции выбора. Условие целостности заключается в сов-1адении вершин смежных фрагментов при их объединении.

Численная реализация модели синтеза интегральных решений:

1. Выбираем смежные подграфы: G v, расположенный между

годмножествами W; и Next(W;)cWj, и G([/+1 - между Wj и Next(Wj)eWr, i* j*r.

2. Все эффективные пути, найденные между вершинами не W| и wе Wj, объединяем со всеми эффективными путями между

¡ершинами w е Wj и z е Wr, i Ф j Ф г, при условии существования

штегрального пути через вершину w (условие целостности). Причем,

•2

2

4

если в графе присутствует контур, то подмножества и \УГ, (1 = г) - одно и то же подмножество и, следовательно, вершина г есть вершина и. Это позволяет построить множество интегральных путей, каждый из которых характеризуется совокупностью оценок критериев, полученных, в силу условия аддитивности, изначально накладываемого на критерии, сложением оценок отдельных фрагментов. Среди найденных вариантов могут оказаться неэффективные. Для отсева таких решений предлагается использовать функцию выбора по бинарному отношению предпочтения И. В результате получаем множество эффективных интегральных путей из и в г. Согласно ПОБ, обобщенному на случай нескольких критериев, любые фрагменты этих путей также эффективны, то есть не может быть эффективного интегрального пути, состоящего из неэффективных фрагментов.

3. Между вершинами ие^, г е \¥г и всеми \у е , при выполнении условия целостности, определяем множество интегральных решений и {р*}™+12' которое затем сужаем посредством

функции выбора С: {р*}и^+1 = с({р* и {р*}^)-

4. Для всех вершин ие^ и г е \\'г аналогично определяем множество эффективных интегральных путей в графе и С :

{Р*}¥,н,+>=С({Р% и {р%+1).

После рассмотрения всех подграфов О у, получаем множестве эффективных интегральных путей (технологических вариантов'

{р*} = С( У( р* ), ц/ = 1,1 на графе обобщенной структуры О, сред;

¥

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

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

выбора используются функции выбора на основе механизмов доминирования (1) и блокировки (2) по бинарному отношению II, обладающему свойствами транзитивности и асимметричности:

Са(Х) = {хеХ| V у еХ хЛу), (1)

Ск(Х) = {хеХ| УуеХ уЯх}. (2)

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

Ух,у, УЬ хЯу => (х + Ь)Л(у + Ь), где х, у - альтернативы; Ь - вектор.

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

вариантов, полученное к к-й итерации; Мк - генерируемое множество. Тогда обобщение однокритериальных схем на векторный случай.

1. На к-й итерации 1-го этапа (¡-я вершина графа) поиска генерируется Мк. Способ генерации определяется элементами используемого однокритериального алгоритма.

2. Множество Мк 11МИ сужается посредством функции выбора (2) до множества Мк: Мк =С(Мк 11МИ). (3)

Для доказательства корректности применения этой схемы в задачах МПВ решений была сформулирована и доказана теорема 1, согласно которой для выбора вариантов ТР на каждом этапе поиска используется функция выбора, порождаемая асимметричным, транзитивным бинарным отношением, то есть качественным порядком.

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

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

1 ситуация. Вычислительные ресурсы ЭВМ и алгоритмы, реализующие механизм поэтапного выбора (3), позволяют получить множество недоминируемых решений в смысле бинарного отношения Паре-то К пар • Для сужения этого множества с учетом предпочтений ЛПР в работе предлагается использовать модель выбора на основе метода ЭЭО, а именно, экстраполяцию по конусу, адекватному экспертизе.

2 ситуация. Множество эффективных решений не удается получить вследствие нехватки вычислительных ресурсов ЭВМ. В данном случае предлагается использовать алгоритмы п.1, но на основе бинарного отношения К1, построенного с помощью метода ЭЭО по конусу, адекватному экспертизе. Это позволяет уменьшить мощность множеств эффективных решений на промежуточных этапах .с учетом предпочтений ЛПР и получить множество так называемых И-оптимальных решений. В связи с отсутствием множества эффективных решений на последнем этапе, для получения ограниченной выборки, предоставляемой экспертам, предлагается использовать алгоритм линейной свертки критериев.

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

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

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

Множество Парето

истинная оценка

оценка, полученная по экспертизе вариант работы К-алгоритма

•йг - эффективные варианты хь хг - критерии эффективности

Рис. 3. Выбор эффективных вариантов с помощью К-алгоритма в соответствии с ОФП

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

Математическую модель выбора решений на основе метода ЭЭО по конусу предпочтений будем искать в виде бинарного отношения учитывающего предпочтения экспертов, используемого в механизме поэтапного выбора (3). Качество каждого варианта хеХ оценивалось функцией полезности (ФП) вида

ш

Г(х)=£архр, (4)

Р=1

где хр - оценки критериев, а а = (а),а2,...,ат) - неизвестные веса функции полезности, соответствующие относительной значимости частных критериев, ар > 0, р = 1, ш.

Для устранения неоднозначности задания ФП, вводится условие

т

нормировки: 2ар=1. (5)

р=1

Линейность ФП обусловлена условием аддитивности каждого критерия эффективности. Обработка результатов экспертизы по ограниченной выборке объемом т « Т, где Т - количество элементов в

выборке, позволила определить-ранжировку х1 >-х2 >-х3 Используя ФП в виде (4) и данную ранжировку, было получено математическое описание множества допустимых значений коэффициентов ФП, которое представляет собой сечение некоторого многогранного конуса (6) гиперплоскостью (5):

т ... -

Хар(хр -хр 1 = 1,1,

Р=1 (в: т _

£ар=1, ар >0, р = 1,т, р=1

где 1 = х — 1 - число парных сравнений.

Искомую модель определяли в виде бинарного отношения :

_ т

(х,у)еЯ1 о V а еА £ар(хр"Ур)^0 л

- (Г

__Ш

3 ао бА| 1]а0р(хр-ур)<0, Р=1

где А- множество векторов а, определяемое системой неравенств (6) Согласно теореме 1, бинарное отношение, используемое в меха низме поэтапного выбора (3), должно быть качественным порядком и кроме того, не зависеть от смещения. Введенное отношение удовле творяет этим свойствам, что доказано в теоремах 2 и 3.

Теорема 2. Бинарное отношение определяемое соотноше нием (7), является качественным порядком и не зависит от смещения.

Теорема 3. Если А,сА2, то СЯа' (X) с С*А2 (X), где 11А- от ношение предпочтения вида (7), определенное на множестве весо аеА; Ы{А-1)*0, 1 = 1/2.

Качественный порядок можно представить как бинарное отношение Парето на некотором наборе скалярных критериальных функций (р, (х),..., <ра (х), в данном случае также линейных:

(х,у)еЯ <=> фк(х)<<рк(у) л Зг| фг(х)<фг(у),

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

ш _

териальных функций Фк(х) = Хакрхр ' к = 1, (1.

р=1

Построение ОФП было проведено с использованием ЭЭО по вектору, адекватному экспертизе. Как и в предыдущем случае используется ФП в виде (4). Для устойчивости экспертных оценок в качестве искомого вектора предлагается искать центр тяжести многогранника (6). Для повышения эффективности определения данного вектора предлагается подход, основанный на теореме Шаракшанэ. Алгоритм, реализующий такой подход, позволил получить набор точек, равномерно распределенных в единичном симплексе (5) и удовлетворяющих системе неравенств (6), и по ним найти требуемый вектор.

Третья глава посвящена разработке алгоритмических моделей МПВ решений в технологических системах.

Приведены разработанные алгоритмические модели, являющиеся обобщением на векторный случай известных алгоритма поиска множества нехудших путей в ациклическом графе (ВАПАГ) и алгоритма Форда-Беллмана (ВАФБ).

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

Предлагаемый многокритериальный алгоритм ВАФБ позволяет найти все множество эффективных путей между двумя фиксированными вершинами ориентированного графа, описывающего обобщенную структуру линейной ТС, при следующих допущениях: в графе отсутствуют кратные дуги и все возможные контуры доминируются контуром с нулевым векторным весом в смысле бинарного отношения II. Корректность использования алгоритма для решения задач МПВ доказана теоремой 5: если бинарное отношение Я является качественным порядком и не зависит от смещения, то алгоритм ВАФБ позволяет найти все Я-оптимальные пути в графе.

Приводится описание разработанных алгоритмов в виде программ на неформальной версии языка Паскаль.

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

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

т

(2= 2архр ' оптимального пути на графе, осуществляется скалярным р=1

алгоритмом нахождения оптимального пути в ациклическом графе.

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

Четвертая глава посвящена рассмотрению вопросов, связанных с программной реализацией разработанных моделей и алгоритме!

многокритериального поэтапного выбора решений в ТС, вычислительным экспериментам и результатам внедрения ППП.

Программное обеспечение представлено в виде ППП "MPVTS", эеализованного в интегрированной среде разработки TURBO PASCAL с применением процедур и функций библиотеки TURBO VISION, ориентированной на создание приложений под управлением ЭС MS DOS и Windows любой версии. ППП "MPVTS" включает в себя двенадцать основных функциональных модулей, связь между которыми осуществляется через файлы на жестком диске. Программа VÎPVTS является головным модулем, который непосредственно связан с модулями, отвечающими за основные расчеты и вспомогательные функции, и эсуществляет координацию работы всей системы в диалоговом режиме.

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

Результаты практической реализации рассмотрены на примере зешения задачи параметрической оптимизации двухпродуктового отделения кристаллизации в производстве сахара на АООТ "Сахарный завод "Балашовский". Оптимизация процесса кристаллизации была направлена на максимальное извлечение сахарозы из свеклы за минимально возможное по технологии время с наименьшими энергозатратами. Задача заключалась в выборе из множества возможных управ-1яющих воздействий на каждом этапе некоторой совокупности аль-

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

В заключении приводятся основные результаты работы.

В приложении - акты внедрения результатов исследования на АООТ "Сахарный завод "Балашовский" и в учебный процесс ВГЛТА.

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

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

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

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

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

ш алгоритмами поэтапного выбора или уменьшить мощность множе-:тва эффективных вариантов на последнем этапе.

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

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

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

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

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

10. Достоверность и полнота результатов исследования подтверждается их практической реализацией на примере решения задачи траметрической оптимизации двухпродуктового отделения кристал-шзации в производстве сахара-песка и внедрением на АООТ "Сахар-1ый завод "Балашовский" путем включения разработанного ППП в сомплексные системы управления различного уровня, передачи документации на математическое и программное обеспечения.

Основное содержание диссертации отражено в работах: 1. Бугаев Ю.В. Алгоритм поиска оптимальных путей в бесконтур-юм графе / Ю.В. Бугаев, C.B. Чикунов // Математическое моделиро-

вание технологических систем: Сб. науч. тр. Вып.З / Воронеж, roc, технол. акад. - Воронеж, 1999. - С. 58-61.

Чикунову C.B. принадлежит доказательство корректности и возможности применения векторного алгоритма.

2. Бугаев Ю.В. Поиск R-оптимальных путей на графах / Ю.В. Бугаев, C.B. Чикунов // Понтрягинские чтения - IX: Тез. докл. школы / Воронеж, гос. ун-т. - Воронеж, 1998. - С. 35.

Чикунову C.B. принадлежит способ нахождения нехудших решений, основанный на обобщении алгоритмов на векторный случай.

3. Бугаев Ю.В. Поэтапный синтез в моделях принятия решений (реализация на ЭВМ) / Ю.В. Бугаев, C.B. Чикунов // Актуальные проблемы информационного мониторинга: Тез. докл. науч.-практ. конф, / Воронеж, филиал Моск. акад. экономики и права, Межд. акад. информатизации. - Воронеж, 1998. - С. 82-84. •

Чикунову C.B. принадлежат методы поиска эффективных решений не основе прямого обобщения на случай нескольких критериев известных скалярных схем.

4. Бугаев Ю.В. Эффективный алгоритм структурной оптимизации технологических систем / Ю.В. Бугаев, В.В. Сысоев, C.B. ЧикуноЕ // Нелинейные явления в открытых системах: Сб. научн. тр. Вып. 10. -М.: Гос. ИФТП, 1999. - С. 77-86.

Чикунову C.B. принадлежат результаты вычислительных экспериментов и пример использования алгоритма для решения задач МПВ.

5. Чикунов C.B. Алгоритмы структурной векторной оптимизация технологических систем, основанные на принципе оптимальности Беллмана // Информационные технологии и системы: Матер. III Все-росс, науч.-техн. конф. / Воронеж, гос. технол. акад. - Воронеж, 1999 -С. 45-47.

6. Чикунов C.B. Векторные алгоритмы для поэтапного принятш решений // Информационные технологии и системы. Вып.2. - Воронеж: Региональное отделение Межд. акад. информатизации "Математическое и компьютерное моделирование", ВГТА, 1998. - С.149-150.

7. Чикунов C.B. Выбор оптимальных проектных решений при наличии нескольких критериев качества // Актуальные проблемы научно-практических исследований и методологий: Матер, науч.-практ конф. аспирантов и соискателей ВГТА на иностранных языках / Воронеж. гос. технол. акад. - Воронеж, 1997. - С. 14-15.

8. Чикунов C.B. Поэтапный выбор в моделях многокритериальной оптимизации / C.B. Чикунов, Ю.В. Бугаев, А.И. Бубнов // Повышение эффективности методов и средств обработки информации: Матер. VI Всеросс. науч.-техн. конф. / Тамбов, воен. авиац. инжен. ин-т. - Тамбов, 2000.-С. 197-198.

Чикунову C.B. принадлежит системная модель МПВ решений в ТС.

9. Чикунов C.B. Синтез информационных технологий поэтапного выбора на основе принципа оптимальности Беллмана в производственных системах // Математическое моделирование информационных и технологических систем: Сб. науч. тр. Вып.4 / Воронеж, гос. технол. акад. - Воронеж, 2000. - С. 272-276.

10. Чикунов C.B. Система алгоритмов решения задач поэтапного выбора / C.B. Чикунов, Ю.В. Бугаев // Теория конфликта и ее приложения: Матер. I Всеросс. науч.-техн. конф. / ВГТА, РАИИ, ВО МАИ. -Воронеж, 2000.-С. 13-15.

Чикунову C.B. принадлежат алгоритмические модели для решения задач МПВ, использующие принцип ЭЭО.

И. Бугаев Ю.В. Многокритериальное динамическое программирование / Ю.В. Бугаев, В.В. Сысоев, C.B. Чикунов // Материалы XXXV отчетной научной конференции за 1996 год: В 2-х ч. / Воронеж, гос. технол. акад. - Воронеж, 1997. - 4.1. - С. 149.

Чикуновым C.B. предложено перспективное направление разработки методов поиска решений в многоэтапных задачах оптимизации.

12. Бугаев Ю.В. Комплекс программных средств для поэтапного принятия решений / Ю.В. Бугаев, C.B. Чикунов // Материалы XXXVI отчетной научной конференции за 1997 год: В 2-х ч. / Воронеж, гос. технол. акад. - Воронеж, 1998. - 4.2. - С. 186.

Чикунову C.B. принадлежат модификации векторных алгоритмов поэтапного выбора решений в ТС.

13. Чикунов C.B. Сравнительный анализ методов векторной оптимизации на графах // Материалы XXXVII отчетной научной конференции за 1998 год: В 2-х ч. / Воронеж, гос. технол. акад. - Воронеж, 1999. -4.1.-С. 216.

14. Чикунов C.B. Концептуальная модель информационной технологии структурной оптимизации технологических процессов // Материалы XXXIX отчетной научной конференции за 2000 год: В 2-х ч. / Воронеж, гос. технол. акад. - Воронеж, 2001. - 4.2. - С. 5.

15. Чикунов C.B. Об актуальности решения задач поэтапного выбора в технологических системах / C.B. Чикунов, Ю.В. Бугаев // Материалы XL отчетной научной конференции за 2001 год: В 2-х ч. / Воронеж. гос. технол. акад. - Воронеж, 2002. - 4.2. - С. 5-7. Чикуновым C.B. показана актуальность решения задач поэтапного выбора при проектировании и управлении ТС.

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

Подписано в печать 27.03.2003 Формат 60x84 1/16.Бумага офсетная. Гарнитура Тайме. Ризография Усл. печ. п.1,0. Тираж 100 экз. Заказ № 3Об

Воронежская государственная технологическая академия (ВГТА) Участок оперативной полиграфии ВГТА Адрес академии и участка оперативной полиграфии 394017, г. Воронеж, пр. Революции, 19