Содержание к диссертации
Введение
ГЛАВА 1. Поэтапный выбор в задачах синтеза решений в технологических системах 10
1.1. Актуальность решения задач поэтапного выбора в технологических системах 10
1.2. Существующие подходы и методы выбора в моделях оптимизации по совокупности критериев 16
1.3. Особенности и методы решения дискретных задач поэтапного выбора в технологических системах 20
1.4. Модели выбора решений в условиях функционирования систем 27
1.4.1. Механизмы и отношения рационального выбора вариантов технологических систем 27
1.4.2. Модели выбора на основе экстраполяции экспертных оценок 34
1.5. Выводы и задачи исследования 38
ГЛАВА 2. Структурный синтез моделей выбора при поэтапном поиске эффективных решений в технологических системах 40
2.1. Системная модель многокритериального поэтапного выбора решений в технологических системах 40
2.2. Модели декомпозиции графа и синтеза интегральных решений 45
2.3. Синтез механизма многокритериального поэтапного выбора решений
в технологических системах 53
2.4. Анализ возможных ситуаций при поэтапном выборе решений по совокупности критериев 58
2.5. Экстраполяция экспертных оценок в моделях многокритериального поэтапного выбора эффективных решений 62
2.5.1. Построение бинарного отношения предпочтения экспертов 62
2.5.2. Построение оценочной функции полезности 73
2.6. Выводы 80
ГЛАВА 3. Алгоритмические модели многокритериального поэтапного выбора решений в технологических системах 82
3.1. Алгоритмическая реализация механизма многокритериального
поэтапного выбора 82
3.1.1. Многокритериальный алгоритм поиска нехудших путей в ациклическом графе 82
3.1.2. Обобщение алгоритма Форда-Беллмана на случай нескольких критериев 89
3.2. Обобщенный алгоритм поэтапного выбора эффективных решений в технологических системах 93
3.3. Модификация алгоритма линейной свертки критериев 99
3.4. Алгоритмы подготовки исходных данных 105
3.4.1. Алгоритм расшивки кратных дуг 105
3.4.2. Алгоритм перенумерации вершин графа 107
3.5. Выводы 111
ГЛАВА 4. Экспериментальные исследования и практическая реализация моделей многокритериального поэтапного выбора решений в технологических системах 112
4.1. Пакет прикладных программ многокритериального поэтапного выбора эффективных решений 112
4.2. Вычислительные эксперименты результатов исследования 120
4.2.1. Оценка вычислительной сложности многокритериальных алгоритмов поэтапного выбора 121
4.2.2. Оценка трудоемкости много- и однокритериальных алгоритмов, используемых в задачах поэтапного выбора решений в технологических системах 130
4.2.3. Анализ численных результатов применения метода экстраполяции экспертных оценок в многокритериальных алгоритмах поэтапного выбора 139
4.3. Практическая реализация результатов исследования. Поэтапный выбор при оптимизации функционирования кристаллизационного отделения в производстве сахара 144
4.4. Выводы 154
Заключение 155
Список литературы 158
Приложение 171
- Особенности и методы решения дискретных задач поэтапного выбора в технологических системах
- Анализ возможных ситуаций при поэтапном выборе решений по совокупности критериев
- Обобщенный алгоритм поэтапного выбора эффективных решений в технологических системах
- Оценка трудоемкости много- и однокритериальных алгоритмов, используемых в задачах поэтапного выбора решений в технологических системах
Введение к работе
Актуальность темы. Предметом исследования настоящей работы являются задачи многокритериального поэтапного выбора, возникающие в рамках моделирования технологических систем (ТС). Продуктом таких систем может быть изделие технологической линии, план развития предприятия и другое. Под понятие ТС попадает широкий круг объектов, предназначенных для реализации различных целей проектирования, планирования и управления, например, разработка новых технологий, замена морально устаревшего оборудования, реконструкция и техническое перевооружение предприятия, оптимальное управление и многое другое.
Технологические системы характеризуются наличием большого количества операций, выполняемых на различном оборудовании, многообразием различных по своим физическим, химическим и другим условиям протекания технологических процессов (ТП), которые естественно трудно объединить в одну операцию, реализуемую одним устройством. При этом не всегда параметры ТП принимают любые значения в пределах некоторой допустимой области. Это связано, прежде всего, со стандартизацией комплектующих изделий в различных областях техники, что накладывает ряд ограничений на них. Все это определяет дискретность большинства ТС, которые представляют собой последовательное количественное и/или качественное изменение объекта производства с дискретными значениями параметров.
Кроме того, существует много ТС, например в пищевой и химической промышленности, структура которых состоит не только из цепочки выполняемых операций, как в случае последовательной переработки сырья, но и разветвлений и/или возвратов различных технологических потоков.
Многообразие средств и методов выполнения однотипных операций, отличающихся между собой по трудоемкости и себестоимости, многовариантность использования оборудования и оснастки на предприятиях во многом обусловили необходимость решения задачи выбора оптимальных вариантов ТС из множества возможных реализаций.
Решение этой задачи связано со значительными трудностями, обусловленными наличием разветвлений и/или возвратов различных технологических потоков, наличием нескольких критериев эффективности, в общем случае конфликтующих между собой, отсутствием точных методов решения, что невозможно без применения методов математического моделирования и средств автоматизации.
Методы поиска оптимальных вариантов дискретной многоэтапной задачи должны исключать перебор всего множества возможных решений, объединять в себе одновременно оба этапа поиска (выделение множества недоминируемых альтернатив и выбор среди них оптимальной) и иметь возможность получения любых точных эффективных решений (во избежание безосновательного отсева какого-либо их подмножества). Этим требованиям во многом удовлетворяют методы, основанные на принципе оптимальности Беллмана (ПОБ), методология которого позволяет проводить поэтапный выбор оптимальных альтернатив.
Существующие в настоящее время методы многокритериального поэтапного выбора решений являются недостаточно эффективными. Это связано, во-первых, с отсутствием методологических подходов к синтезу процедур многокритериального выбора. Во-вторых, большинство методов основано на однокритериальном подходе, другая группа - на прямом обобщении скалярных схем на случай нескольких критериев, часть из которых является приближенными, а отдельные имеют в основном лишь теоретическое значение. В-третьих, существующие методы позволяют находить оптимальные решения только для ТС частного вида, например для ТС, структура которых является линейной. В-четвертых, множества недоминируемых альтернатив могут достигать больших размеров и выбрать окончательное решение весьма проблематично. В-пятых, все известные методы записаны на языке критериев качества, который, по сравнению с другими языками теории выбора, недостаточно чувствителен к отдельным аспектам принятия решений, например, не учитывает предпочтений лица, принимающего решение (ЛПР).
Возникают проблемные вопросы, связанные с разработкой, модификацией и численной реализацией моделей, основанных на прямом обобщении
на случай нескольких критериев известных однокритериальных схем, ис-польз>тощих ПОБ, и построением на их основе моделей и алгоритмов многокритериального поэтапного выбора решений (ТР) в ТС, записанных в терминах языка функций выбора, как наиболее универсальном и удобном для ана-лиза описания концепции выбора. Стремление на основе системного подхода и принципа поэтапного решения задачи наилучшим образом распределить вычислительные ресурсы так, чтобы удовлетворить реализуемость полного решения, является важной и актуальной задачей.
Диссертационная работа выполнена на кафедре математического моделирования информационных и технологических систем ВГТА в рамках госбюджетной НИР (№ г.р. 01960007318) по теме № 1.6.2 "Моделирование, выбор и принятие решений в структурно-параметрическом представлении
функционирования многоцелевых систем применительно к теории конфликта"^ г.р. 01.2001.16818).
Цель и задачи работы. Целью диссертационного исследования является синтез моделей, алгоритмов и механизма многокритериального поэтапного выбора решений в технологических системах в структурно-параметрическом представлении с инвариантными свойствами к предметной области, обеспечивающих построение инструментальных средств в виде математического, алгоритмического и программного обеспечения автоматизированных систем поддержки принятия решений
Поставленная цель достигается посредством решения следующих за-дач:
разработка системной модели многокритериального поэтапного выбора решений в ТС в структурном представлении;
разработка механизма многокритериального поэтапного выбора эффективных решений;
разработка моделей многокритериального поэтапного выбора решений в ТС с инвариантными свойствами к предметной области;
разработка алгоритмических моделей многокритериального поэтапного выбора в задачах поиска эффективных вариантов решений в ТС;
- разработка инвариантного к предметной области пакета прикладных
$ программ (ШЛИ), реализующего многокритериальный поэтапный выбор ре
шений в ТС;
- проведение вычислительных экспериментов и практическая реализа
ция результатов исследования в реальных производственных условиях.
Методы исследования. Выполненные теоретические и экспериментальные исследования базируются на использовании аппарата теории графов, теории выбора и принятия решений, методов математического моделирования и программирования. Общей методологической основой является системный подход. Ф
Научная новизна. Разработаны модели и механизм многокритериального поэтапного выбора решений в технологических системах с инвариантными свойствами к предметной области:
системная модель, предусматривающая поиск эффективных ТР методами, основанными на ПОБ, и* создающая основу для структурно-параметрического синтеза моделей многокритериального поэтапного выбора решений в ТС;
модели декомпозиции и синтеза интегральных решений, позволяющие решать задачи многокритериального поэтапного выбора эффективных
ц решений в ТС с разветвлениями и/или возвратами технологических потоков;
механизм поэтапного выбора решений, отличающийся от известных обобщением на случай нескольких критериев скалярных схем, реализующих ПОБ, и представленный в терминах функций выбора;
математические модели выбора эффективных решений в ТС как на последнем, так и на промежуточных этапах поиска, повышающие избирательность отсева бесперспективных вариантов и использующие метод экстраполяции экспертных оценок;
алгоритмические модели многокритериального поэтапного выбора решений в ТС с инвариантными свойствами к предметной области.
Практическая значимость работы состоит в разработке инструменталь-
Ш ных средств в виде моделей, алгоритмов и пакета прикладных программ,
обеспечивающих поиск эффективных решений в многоэтапных задачах оп-
тимизации произвольной структуры по совокупности критериев, использование которых целесообразно в СПГТР, САПР, АСНИ, АСУТП, АСУ различного предметного назначения. Разработанный ППП "MPVTS" внедрен на АООТ "Сахарный завод "Балашовский" путем включения в комплексные системы управления различного уровня, передачи документации на математическое и программное обеспечения. Эффект от внедрения - социальный. ППП применяется в учебном процессе ВГТА для обучения студентов по специальности 071900 "Информационные системы и технологии", в учебном процессе ВГЛТА - по специальности 210200 "Автоматизация технологических процессов и производств".
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Ш Всероссийской научно-технической конференции "Информационные технологии и системы" (г. Воронеж, 1999г.), VI Всероссийской научно-технической конференции "Повышение эффективности методов и средств обработки информации" (г. Тамбов, 2000г.), I Всероссийской научно-технической конференции "Теория конфликта и ее приложения" (г. Воронеж, 2000г.), научно-практической конференции "Актуальные проблемы информационного мониторинга" (г. Воронеж, 1998г.), научном семинаре математической школы "Понтрягинские чтения - IX" (г. Воронеж, 1998г.), научно-практической конференции аспирантов и соискателей ВГТА "Актуальные проблемы научно-практических исследований и методологий" (г. Воронеж, 1997г.), XXXV, XXXVI, XXXVII, ХХХГХ, XL отчетных научных конференциях за 1996 г., 1997 г., 1998 г., 2000 г., 2001 г. (г. Воронеж).
Публикации. По материалам диссертации опубликовано 15 печатных работ.
Структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 134 наименований и приложения. Работа изложена на 170 страницах машинописного текста (основной текст занимает 146 страниц), содержит 32 рисунка и 14 таблиц.
Автор искренне благодарен доценту, к.т.н. Ю.В. Бугаеву за научные консультации и внимание, проявленное к настоящей работе.
Особенности и методы решения дискретных задач поэтапного выбора в технологических системах
Рассматривая проблему выбора недоминируемых вариантов ТР при моделировании ТС с позиций системного подхода, можно выделить два основных этапа ее решения [93, 95, 103]: - выделение из допустимого множества решений подмножества недоминируемых альтернатив; - получение оптимального в некотором смысле решения на недоминируемом множестве альтернатив. Поскольку количество возможных вариантов ТР может быть очень велико, а между основными показателями качества наблюдается конфликт, то решение задачи выбора на первом шаге заключается в решении задачи многокритериальной оптимизации, которую в общем виде можно представить следующей моделью [95, 103]: где qj =qj(X), i = l,m; X = (xi, x.2,..., xs) - вектор внутренних (варьируемых) параметров системы, например вариант плана реконструкции ТС; q = (q1,q2,...,qm) - вектор показателей качества; opt - оператор, реализующий один из принципов оптимизации по совокупности критериев. Исследованию и анализу современных подходов и методов решения задач многокритериального выбора вариантов ТР и проблемы в целом посвящено достаточно большое число публикаций, содержательный анализ которых можно найти в [1, 8, 9, 40, 55, 61, 62, 71, 79, 85, 100, 126, 129, 130, 131, 133, 134]. Среди них основными, наиболее используемыми, являются: - аксиоматический подход, предполагающий справедливость ряда аксиом о системе предпочтений лица, принимающего решения (ЛПР); - эвристический подход, основывающийся на некоторых соображениях о системе предпочтений лица, принимающего решения, а не на четко сформулированных допущениях.
Разные методы принятия решений в рамках данных подходов отличаются видом получаемой от ЛПР информации и способом перехода от сравнения вариантов ТР по отдельным критериям к выбору по векторному критерию.
Аксиоматический подход лежит в основе прескриптивной теории полезности, в которой рассматриваются различные наборы аксиом, характеризующих систему предпочтений ЛПР и позволяющих доказать существование скалярной функции полезности (аддитивной, мультилинейной и др.), определенной на множестве векторных оценок и обладающей измерительными свойствами [45, 72, 109]. Широкое распространение в рамках данного подхода получили также методы рационального выбора, использующие для описания предпочтений язык функций выбора [65]. Иллюстрацией аксиоматического подхода могут служить работы [46, 107, 108]. В [107] приводится обзор исследований различных аспектов проблемы нахождения значений функции полезности, удовлетворяющих аксиомам фон Неймана и Моргенштерна.
Основной проблемой при использовании аксиоматического подхода для выбора вариантов ТР является проверка аксиом (в основном аксиом независимости). Подробно эта проблема обсуждается в [59] и резюмируется, что удовлетворительные способы построения функции полезности при зависимости критериев практически отсутствуют. В эвристическом подходе можно выделить прямые методы и методы, в которых постулируется форма функциональной зависимости, а параметры вычисляются с использованием экспертной информации. В прямых методах принцип оптимальности формируется в явном виде, позволяя непосредственно выражать цель векторной оптимизации в виде функции частных критериев. Известны несколько принципов оптимальности [23, 59, 81]: принцип гарантированного уровня или максимина, принцип квазиравенства частных критериев, принцип абсолютной уступки, принцип относительной уступки, лексикографический метод, принцип выделения главного критерия, принцип последовательной уступки и др. При использовании прямых методов к ЛПР предъявляются слишком жесткие требования. Человек далеко не всегда в состоянии сформулировать явно принцип оптимальности, соответствующий его предпочтениям. В [59] приводятся методы, в которых форма зависимости частных критериев постулируется, а ее параметры либо непосредственно назначаются ЛПР, либо определяются путем обработки экспертной информации. Наиболее употребительными являются метод взвешенных сумм и мультипликативный метод [32, 41, 43]. В этих методах выбор той или иной формы, как правило, ничем не оправдывается, кроме как простотой получения решения. Но даже эта простота относительна. В [123], например, отмечается, что метод последовательного сравнения для определения весовых коэффициентов при его экспериментальном использовании оказался настолько трудоемким для усвоения его экспертами и занял так много времени, что в дальнейшем от него пришлось отказаться. Для решения задач многокритериального поэтапного выбора эффективных вариантов ТР многие перечисленные методы следует признать малоперспективными по следующим причинам: 1. При использовании лексикографических методов отношение жесткого приоритета между некоторыми показателями может привести к неоправданным решениям. Например, отношение приоритета между стоимостью оборудования и его надежностью приведет либо к недопустимой стоимости, либо к неоправданно малой надежности. 2. Лексикографический метод и методы уступок требуют достаточно точного решения однокритериальных оптимизационных задач, что не всегда возможно из-за сложной топологической структуры множества допустимых решений и сложного поведения критериев. 3. Многие прямые методы оптимизации, как показывают экспериментальные и теоретические исследования, имеют весьма медленную сходимость [47, 105]. 4. При использовании метода взвешенных сумм основной проблемой является получение информации, позволяющей определить веса критериев в свертках. 5. Методы "ELECTRE" [87, 88] и последовательного сужения человеко-машинными процедурами множества допустимых ТР с привлечением ЯПР [29, 30, 39, 75] очень трудоемки для множеств с большими мощностями (например, в задачах выбора оптимальной структуры ТП), поскольку предполагают перебор всех их элементов.
Таким образом, к основным недостаткам, не позволяющим в полной мере применять эти методы к задачам многокритериального поэтапного выбора решений, следует отнести: необходимость решения очень большого числа однокритериальных задач оптимизации, которое сравнимо с числом эффективных вариантов, сильно растущим с ростом количества критериев [25, 26, 58] и отсутствие эффективных быстродействующих методов одно-критериальной оптимизации.
Разнообразие применяемых технико-экономических показателей при проектировании и управлении, неоднородность их представления, большая трудоемкость используемых в каждом отдельном случае численных методов говорят о необходимости разработки специальных, достаточно простых методов поиска эффективных решений, основанных не на сведении задачи оптимизации к множеству однокритериальных, а на прямом обобщении наиболее простых оптимизационных схем на случай нескольких критериев. Среди методов, поддающихся обобщению, для решения задач многокритериального поэтапного выбора в технологических системах можно использовать методы случайного поиска, динамического программирования и другие [10, 93, 95, 103].
Анализ возможных ситуаций при поэтапном выборе решений по совокупности критериев
В [20, 103] дается теоретическое обоснование возможного применения схемы прямого обобщения метода динамического программирования (МДП) на случай нескольких критериев для ТС, описываемых многодольными графами. Показано, что использование такой схемы при числе критериев больше 3 может стать малоэффективным вследствие лавинообразного возрастания числа нехудших вариантов и, как следствие, привести к нехватке оперативной памяти ЭВМ. Однако, множество Парето редко соизмеримо с полным числом вариантов, поэтому теоретическая оценка сложности данной реализации МДП, приведенная на случай полного перебора, завышена, и условия ее применения на многодольных ориентированных графах при количестве критериев не больше 3 имеют частный характер. Следовательно, необходимы не только теоретические, но и экспериментальные исследования условий применения такой схемы.
Выше речь шла о достаточно простых структурах ТС, не содержащих разветвлений и циклов (возвратов, контуров) материальных, информационных, энергетических и других потоков. Однако, существует много ТС более общего вида, структура которых состоит не только из цепочки выполняемых операций (этапов), как в случае последовательной переработки сырья, но и разветвлений и возвратов различных технологических потоков. Например, выполнение разных стадий обработки изделий на одном и том же станке, подача растворов сахара 11 и III продуктов на уваривание сахара I продукта для более полного извлечения сахарозы из утфеля, производство кисломолочных продуктов и многое другое. То есть, в общем случае, оптимальное решение многостадийной задачи содержит в своем составе цикл и/или разветвление. Существующие же методы позволяют искать оптимальные решения только в тех случаях, когда структура ТС представляет линейную последовательность этапов обработки предмета производства.
Таким образом, известные к настоящему времени методы многокритериального поэтапного выбора решений являются недостаточно эффективными. Это связано, во-первых, с отсутствием методологических подходов к синтезу процедур многокритериального выбора. Во-вторых, большинство методов основано на однокритериальном подходе, другая группа - на прямом обобщении скалярных схем на случай нескольких критериев, часть из которых является приближенными, а отдельные имеют в основном лишь теоретическое значение. В-третьих, существующие методы позволяют находить оптимальные решения только для технологических систем частного вида, например для ТС, структура которых является линейной. В-четвертых, множества недоминируемых альтернатив могут достигать больших размеров и выбрать окончательное решение весьма проблематично. В-пятых, все известные методы записаны на языке критериев качества, который, по сравнению с другими языками теории выбора, недостаточно чувствителен к отдельным аспектам принятия решений, например, не учитывает предпочтений ЛПР.
В связи с этим методы поиска оптимальных вариантов дискретной многоэтапной задачи должны исключать перебор всего множества возможных решений, объединять в себе одновременно оба этапа поиска (выделение множества недоминируемых альтернатив и выбор среди них оптимальной) и иметь возможность получения любых точных эффективных решений (во избежание безосновательного отсева какого-либо их подмножества). Этим требованиям во многом удовлетворяют методы, основанные на принципе оптимальности Беллмана, методология которого позволяет проводить поэтапный выбор эффективных альтернатив.
Возникают проблемные вопросы, связанные с разработкой, модификацией и численной реализацией моделей, основанных на прямом обобщении на случай нескольких критериев известных однокритериальных схем, использующих принцип оптимальности Беллмана, и построением на их основе моделей и алгоритмов многокритериального поэтапного выбора решений в ТС, записанных в терминах языка функций выбора, как наиболее универсальном и удобном для анализа описания концепции выбора.
Современная теория выбора решений представляет собой синтез моделей и методов, возникающих в различных дисциплинах. Исторически сложились различные подходы и соответственно разные языки теории выбора решений - язык критериев качества, язык бинарных отношений, язык функций выбора, аксиоматический язык [124]. Эти языки по-разному чувствительны к отдельным аспектам принятия решений и изложение одних и тех же или близких проблем в различных понятиях и терминах усложняет исследование и освоение принципов и механизмов принятия рациональных ТР.
Согласно классической аксиоматики рационального выбора общая модель выбора решений в ТС может быть представлена преобразователем (рис. 1.1), в результате работы которого каждому X є А, где А - некоторое заданное множество непустых подмножеств X вариантов ТС, то есть ставится в соответствие YcX, то есть формируется отображение Y = С(Х)с X, называемое функцией выбора (ФВ) [1, 65, 122, 124]. Сам процесс выбора вариантов ТР рассматривается как "черный ящик", на вход которого поступает множество рассматриваемых альтернатив X єА, называемое предьявлением, а на выходе получается множество YcX выбранных альтернатив, называемое выбором. Таким образом, ФВ определяет "внешнее" описание процесса выбора. В свою очередь "внутреннее" описание, то есть описание того, как множество Y выделяется из X, определяется механизмом выбора, обозначаемым через М = а, тс , где и - структура на множестве X (совокупность сведений, в том числе полученных от ЛПР, о всех рассматриваемых вариантах ТР из X, позволяющих сравнивать эти варианты), а л - правило выбора, которое указывает как, используя структуру а, выделить из X подмножество Y.
Обобщенный алгоритм поэтапного выбора эффективных решений в технологических системах
После того, как в строке 2 будут рассмотрены все вершины, множества {D[v]} V v є V содержат все R-оптимальные пути из источника s в остальные вершины на этапе к = 1 (строка 1).
Но, в связи с наличием контуров в графе, найденные пути могут быть не окончательными. Могут существовать и другие пути, более лучшие (в смысле бинарного отношения R). Чтобы их найти, нужно процедуру поиска повторить снова. И так до тех пор, пока к не станет равным п - 2. Очевидно, что вычисления можно закончить и раньше, когда выполнение цикла 2 не вызывает изменения ни одной из переменных { D[v]}.
Корректность рассматриваемого алгоритма доказывает следующая теорема: если граф G не содержит кратных дуг и все возможные контуры доми-нируются контуром с нулевым векторным весом в смысле бинарного отношения R, являющегося качественным порядком и не зависящего от смещения, то векторный алгоритм Форда-Беллмана позволяет найти все R-оптимальные пути в графе G. Доказательство теоремы приведено в [13] и в работе не приводится.
Оценим теперь вычислительную сложность данного алгоритма. Векторный алгоритм Форда-Беллмана отличается от векторного алгоритма поиска нехудших путей в ациклическом графе лишь одним внешним циклом 1 (for к := 1 to n - 2 do ), вычислительная сложность которого имеет порядок О (п). Следовательно, общая вычислительная сложность алгоритма ВАФБ составляет О (L" п ), против О (n ) в скалярном случае, то есть она выше, чем у алгоритма поиска в ациклическом графе. Таким образом, получена еще одна численная реализация механизма поэтапного выбора эффективных решений (2.1) в виде алгоритма Форда-Беллмана, обобщенного на случай нескольких критериев. Рассмотрим теперь обобщенный алгоритм, предназначенный для многокритериального поэтапного выбора эффективных решений в ТС с разветвлениями и/или возвратами различных технологических потоков. Рассмотренные в предыдущем разделе алгоритмические модели многокритериальной поэтапной оптимизации непосредственно могут применяться для поиска эффективных решений только в технологических системах с последовательной переработкой предмета производства, то есть ТС, обобщенная структура которых описывается бесконтурными ориентированными графами (1-й и 2-й типы структур см. п.2.2) и эффективные ТР которых представляют собой оптимальные пути на таких графах. Для выбора эффективных решений в ТС с разветвлениями и/или возвратами различных технологических потоков (3-й и 4-й типы структур см. п.2.2) предлагается использовать специально разработанный обобщенный алгоритм, представляющий собой реализацию системной модели многокритериального поэтапного выбора решений в ТС (см. п.2.1), а также моделей декомпозиции графа и синтеза интегральных решений (см. п.2.2), блок-схема которого приведена на рис.3.1. Пусть обобщенная структура рассматриваемой технологической системы допускает представление в виде ориентированного графа общего вида (с разветвлениями и/или контурами) G. Будем предполагать: - все возможные варианты структуры технологической системы идентичны в смысле общего числа звеньев в линейных цепочках, характера и числа разветвлений и/или возвратов; - все критерии эффективности удовлетворяют условию аддитивности; - граф обобщенной структуры G не содержит кратных дуг. Обозначим: W;, і = 1, k - подмножества вершин графа G, каждое из которых представляет собой совокупность однотипных вершин, соответствующих местам разветвлений, соединений или входа возвратов технологических потоков; W0, Wk+, - множества, состоящие из единственного элемента - начальной и конечной вершин соответственно; Next ( Wj) - подмножество вершин из совокупности {Wj}, j Ф і, смежных с Wj . В этом случае каждый допустимый вариант ТР является объединением путей, соединяющих вершины, принадлежащие смежным множествам Wj и Wjsi j. Обобщенный алгоритм поэтапного выбора эффективных решений в технологических системах следующий. Шаг 1. Декомпозиция графа. Вначале в графе G выделяются множества однотипных вершин Wj, і = 1, k, соответствующие местам входа контура, соединениям и/или разветвлениям. К ним добавляются множества W0 и Wk+l. Множества Wj, і = 0, k + 1 разбивают граф обобщенной структуры G на ациклические подграфы G без кратных дуг, ц = 1, J, где J - количество таких подграфов, состоящие из путей между смежными множествами вершин Шаг 2. Из полученного списка подграфов выбирается очередной по порядку ациклический подграф Gw с соответствующими смежными множествами вершин W; и Next (Wj). Шаг 3. Выбираются две вершины: ueWj и we Next( Ws). Одним из обобщенных на случай нескольких критериев алгоритмов поэтапного выбора (ВАПАГ или ВАФБ см. п.3.1) проводится поиск множества эффективных путей между этими вершинами { р }" w. Шаг 4. Данная процедура повторяется для всех вершин w є Next (Wj), а затем все это повторяется и для всех ue Wj. В результате получается множество эффективных путей между всеми вершинами и є Wj и всеми вершинами w є Next (Wj) в подграфе G Vj, - { р } то есть на декартовом произведении Wj х Next (Wj). Шаг 5. Аналогичным образом (шаги 2-4) проводится поиск эффективных путей во всех ациклических подграфах G - {р } ч/, \/ = 1, J. Шаг 6. Получение интегрального решения. Выбираются два смежных подграфа G v и G v+1 таких, что для G v : W; и Next (Ws) с Wj, а для G V/+1: WjHNext(Wj)cWr, i j r. Шаг 7. Выбираются три вершины: ueW;, w є W: и z e Wr. Шаг 8. Проверка условия целостности, то есть существования фрагмента пути из вершины и в вершину z через вершину w. Если такой путь существует, то переход к шагу 9, если нет, то к шагу 10. Шаг 9. При условии аддитивности каждого критерия эффективности проводится объединение всех эффективных путей между вершинами и и W в подграфе GM, - {р }" w со всеми эффективными путями между вершинами w и z в подграфе G v+, - { р } J;f, то есть {р } J"w U {р } f. Шаг 10. Шаги 7-9 повторяются для всех вершин weWj при тех же и и z. В результате получается множество интегральных вариантов возможных путей из вершины и в вершину z, среди которых могут быть и неэффективные. Заметим, что если подграфы GV/ и Gy[,+1 образуют контур на графе обобщенной структуры G, то подмножества Wj и Wr - одно и то же подмножество и, следовательно, вершина zeWr есть вершина и є Wj.
Оценка трудоемкости много- и однокритериальных алгоритмов, используемых в задачах поэтапного выбора решений в технологических системах
Выходными данными являются множества нехудших по заданному бинарному отношению R решений в каждом ациклическом подграфе, а также эффективные интегральные ТР в графе обобщенной структуры.
Программа MPVTS является головным модулем, который непосредственно связан с модулями, отвечающими за основные расчеты и вспомогательные функции, и осуществляет координацию работы всей системы.
Программа MPVTS представляет собой сервисную оболочку, состоящую из главного меню и встроенного редактора для просмотра и корректировки исходных данных и результатов. ППП включает в себя следующие основные и вспомогательные программы: 1) головная программа MPVTS на основе обобщенного алгоритма (см. п.3.2) в диалоговом режиме осуществляет декомпозицию исходного графа обобщенной структуры и формирование интегральных решений в ТС с разветвлениями и/или возвратами технологических потоков; 2) программа BESKVEK, разработанная на основе алгоритма ВАПАГ (см. п.3.1.1), осуществляет поиск эффективных по бинарному отношению предпочтения R пАР (1.12) или отношению R, (2.12) путей в ациклическом графе; 3) программа FORDVEK на основе алгоритма ВАФБ (см. п.3.1.2) осуществляет поиск эффективных по бинарному отношению предпочтения RnAP (1.12) или отношению R! (2.12) путей в фафе, у которого нет контуров отрицательной длины ни по одному из критериев; 4) профамма FORDALF на основе модификации алгоритма АЛСК (см. п.3.3) производит поиск оптимальньгх по Парето вариантов по линейной свертке критериев (3.3), количество реализаций векторов а задается; 5)профамма PEREBOR обеспечивает поиск оптимальных по Парето (1.12) вариантов путем полного перебора; 6) программа PREOBR на основе алгоритма расшивки кратных дуг (см. п.3.4.1) выполняет преобразование мультиграфа в обычный путем ввода фиктивных вершин с нулевыми весами дуг; 7) программа PERENUM на основе алгоритма перенумерации вершин графа (см. п.3.4.2) тестирует заданный граф на наличие контуров и, еслм их нет, осуществляет перенумерацию вершин графа в соответствии с условием: каждая дуга выходит из вершины с меньшим номером и заходит в вершину с большим номером; 8) программа VYBEXP осуществляет выборку заданного количества альтернатив из множества нехудших решений следующими способами: случайный отбор, отбор по max свертки, max дисперсионные точки, поверхность безразличия, центр тяжести, и имитирует работу эксперта - проводит ранжирование альтернатив (только для тестовых примеров): 9) программа BASIS осуществляет поиск фундаментальных решений конуса экспертных предпочтений (2.11) в виде набора базисных точек а системы (2.20); 10) программа OCFPOL производит поиск оценки вектора коэффициентов а оценочной функции полезности (2.6), используя результаты экспертизы в виде системы (2.11) и метод случайного поиска на основе оператора (2.23); 11) программа CONUS осуществляет отсев элементов конфликтного множества согласно функции выбора С R (1.11) по бинарному отношению R [ (2.12) или по отношению RnAP (112); 12) программа KALGOR производит поиск К вариантов в соответствии с оценочной функцией полезности. Взаимосвязь между модулями пакета осуществляется через файлы на диске, имена которых задаются по желанию пользователя. Все программы работают в удобном диалоговом режиме, позволяющем последовательно вводить исходные данные и получать результаты, выводимые как на экран монитора, так и в отдельные файлы на диске (по желанию пользователя они могут выводиться и на АЦПУ). На рис.4.1 представлена структура ГТПП "MPVTS". Для экономии машинных ресурсов программы поиска оптимальных путей в графе имеют ряд версий, которые реализуют хранение промежуточных элементов конфликтного множества в файле на диске, хранение в памяти ЭВМ только рассматриваемой вершины графа с последующим ее удалением и другие. Рассмотрим подробнее работу разработанного ГТПП. Пусть обобщенная структура рассматриваемой ТС с разветвлениями и/или возвратами технологических потоков допускает представление в виде ориентированного графа общего вида, хранимого в виде файла на диске. 1. Данный граф с помощью программы PERENUM анализируется на принадлежность тому или иному типу структуры (см. п.2.2) - проверяется на наличие контуров. 2. Разветвления и/или контуры отсутствуют (1-й и 2-й тип структуры, см. п.2.2), то есть ТС представляет собой последовательное линейное выполнение каких-либо операций. Поиск эффективных ТР в этом случае осуществляется одним из обобщенных на случай нескольких критериев алгоритмов поэтапного выбора ВАПАГ или ВАФБ (программы BESKVEK или FORD_VEK), переход к шагу 4, или по ОФП с помощью программы К ALGOR, переход к шагу 14. 3. Разветвления и/или контуры имеют место (3-й и 4-й тип структуры, см. п.2.2), то есть каждый возможный вариант ТС содержит разветвления и/или контуры технологических потоков. Решение в этом случае ищется с помощью обобщенного алгоритма (см. п.3.2), реализуемого головной программой MPVTS, а именно: в диалоговом режиме проводится декомпозиция исходного графа обобщенной структуры на ациклические подграфы, каждый из которых сохраняется в отдельном файле на диске. Фрагменты эффективных ТР ищутся теперь в каждом из них при помощи обобщенных на случай нескольких критериев алгоритмов поэтапного выбора ВАПАГ или ВАФБ (программы BESKVEK или FORD_VEK). 4. Ациклический граф анализируется на наличие кратных дуг. Если та кие существуют, проводится "расшивка" путем введения фиктивных вершин с нулевыми весами дуг. Преобразованный граф хранится в файле. Эта процедура осуществляется при помощи программы PREOBR. 5. С помощью программы PERENUM проводится перенумерация вершин ациклического графа. Результат - файл на диске. 6. Согласно обобщенному алгоритму (программа MPVTS) поиск эффективных решений в ациклическом графе по безусловному критерию предпочтения (1.12) проводится одним из векторных алгоритмов: ВАПАГ - программа BESK VEK, ВАФБ - программа FORD_VEK. Предусмотрен также поиск алгоритмом АЛСК - программа FORDALF и полным перебором - программа PEREBOR. Результат - матрица оптимальных по Парето альтернатив - файл на диске. 7. При поиске эффективных решений в ТС алгоритмами, обобщенными на случай нескольких критериев, возможны два случая, которые имеют место, если используемое для выбора оптимальных альтернатив отношение предпочтения R обладает недостаточной избирательной способностью (см. п.2.4): а). Полученное множество нехудших по бинарному отношению R (в частности RnAp) ТР имеет большую размерность и из него требуется выбрать несколько лучших альтернатив (переход к шагу 8).
