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

ВВВДЕНИЕ.

1. АНАЛИЗ МЕТОДОВ ШОГСКЕИЕЕРШШОЙ ОПТИМИЗАЦИИ.

1.1. Введение.

1.2. Классификация методов многокритериальной оптимизации • ••••••••.•••••••••••

1.3. Методы, предполагающие существование функции полезности. .II

1.4. Методы, не предполагающие существования функции полезности.

1.5. Априорные методы оптимизации.

1.6. Диалоговые методы оптимизации.

1.7. Порядковые задачи выбора

1.8. Использование дополнительной информации при решении многокритериальных задач.

1.9. Выводы и цель диссертации.

2. ПОРЯДКОВЫЕ ОТНОШЕНИЯ.

2.1. Введение.

2.2. Функция выбора и бинарное отношение.

2.3. Выбор в строгих и нестрогих шкалах.

2.4. Свойства наследования и монотонности. Обоснование применения графодоминантных функций выбора в задачах оптимизации.

2.5. Бинарные отношения в . Порядковые сравнения

2.6. Представление порядковых сравнений верхними конусами

2.7. Критерии транзитивности и ацикличности.

2.8. Представление порядковых сравнений полиномами

2.9. Реализация бинарных отношений порядковыми сравнениями

2.10 .Порядковые сравнения

2. II .Выводы.

3. АППРОКСИМАЦИЯ ПРВДШШЕНИЯ ЛПР

3.1. Введение.

3.2. Определения сравнительной важности критериев.

3.3. Сравнительная важность критериев для порядковых сравнений

3.4. Сравнение некоторых способов упорядочения критериев.

3.5. Использование информации о важности критериев при идентификации структуры предпочтений ЛПР.

3.6. Использование информации о важности критериев при аппроксимации структуры предпочтений ЛПР.

3.7. Выводы.

4. МАТЕМАТИЧЕСКОЕ ОЖИДАНИЕ МОЩНОСТИ ВЫБОРА КАК

ХАРАКТЕРИСТИКА ТОЧНОСТИ АППРОКСИМАЦИИ.

4.1. Сравнение точности аппроксимации.

4.2. Математическое ожидание мощности выбора для порядковых сравнений. Строгие шкалы.

4.3. Ациклические порядковые сравнения в строгих шкалах. Сравнения Вл* и

4.4. 1 -оптимальность

4.5. Сравнение

4.6. Нестрогие шкалы

4.7. Выводы.96 •

5. МЕТОДИКА РЕШЕНИЯ ПОРЯДКОВЫХ МНОГОКРИТЕНШШНЫХ ЗАДАЧ

5.1. Алгоритмы выявления структуры предпочтений ЛПР.

5.1.1. Идентификация на основе попарного сравнения вариантов.

5.1.2. Аппроксимация на основе информации об упорядочении критериев по важности . ют

5.2. Методика.

5.3. Выбор проекта технологической линии для производства белково-витаминных концентратов. . юб

5.4. Формирование оптимального плана технической подготовки инструментального производства модели автомобиля ВАЗ-2107.НО

5.5. Выводы. .ИЗ

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

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

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

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

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

Работа состоит из пяти глав и заключения.

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

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

Третья глава посвящена формализации и использованию качественной информации о сравнительной важности критериев при решении задач многокритериальной оптимизации.

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

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

В заключении излагаются основные результаты дис -сертационной работы. Список литературы состоит из 71 наименования.

- 7

I; АНАЛИЗ МЕТОДОВ МНОГОКРИТЕИШШНОЙ ОПТИМИЗАЦИЙ

1.1. Введение

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

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

1.2. Классификация методов многокритериальной оптимизации

Приоритет в постановке многокритериальной задачи выбора принадлежит итальянскому экономисту В. Парето [65] , предложившему еще в XIX веке метод, получивший впоследствии название оптимизации по Парето. Существует ряд работ, посвященных вопросу поиска оптимума Парето. Карлин [18] , в частности, показал, что при некоторых предположениях для этого может быть использована линейная свертка с переменными коэффициентами.

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

1) По характеру сделанных предположений о задаче (рис. 1.1).

2) По способу получения информации, необходимой для решения задачи (рис. 1.2).

Основным предположением, используемым во многих методах многокритериальной оптимизации, является предположение о том, что структура предпочтений ЛИР описывается функцией полезности. Функцией полезности исх>) [45-47] называется числовая функция, ставящая в соответствие варианту некоторое число, так называемую "полезность" варианта, и обладающая следующим свойством: исаГ) > и Су) тогда и только тогда, когда вариант сс более предпочтителен, чем вариант у . ^

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

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

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

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

Классификация методов по указанным признакам приведена на

Методы многокритериальной оптимизации

Предполагается существование функции полезности

Известен вид функции полезности

Функция полезности задана неявно, известны её свойства

Не предполагается существование функции полезности

Оптимизация основана на попарном сравнении вариантов

Оптимизация не представляет выбор по бинарным отношениям ы со Я нЗ а г а> со й ьэ Ьт* о

I Тч м

I—) о. 1^ и р <<1 в и

13 «

33 о а о е я о

ЕВ •о г—V

1 СП со го

-3, 1—1 я м со I со нз о ст> сл нэ

1 »<1 о а ьЭ §

43

Ьг» д ы

О к

О сх о ь*

1—к со н

1—1

МО в о схи о о *< а ш по м I

Ч О ф 3 г ьл в ас I со I а» о ы го В о я я я га о о о а о о о о. << а о « л со д

Я & I

Методы многокритериальной оптимизации нЗ со

13

1 о

8Р

43

Апостериорные методы га со

01

05 3

Й аз

Л

М к?

В е со со со >а

1—1 1—1

СГ> го 11 го 11

Итерационные методы

Получение информации о сравниваемых вариантах 1

Получение информации о критериях I в я ш м оо

33 ьЗ а со а со 1-3

0 и 1 а

I—1 со я а со

3 §

03 X В ш о и о й

Ке 3 ¡Я и

13 го с—' о

Не со X о о из

С|7

1=4

Уз .со ьэ о т сл со со ьз о 1=1 о ш со

1.

Г"7 СП ы

5? р г со §

СИ I о м о рис. 1.1.

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

5.5. Выводы

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

2. Изложенная в работе методика применялась для решения следующих задач предварительного проектирования:

- выбор проекта технологической линии для производства белково-витаминных концентратов;

- формирование оптимального плана технической подготовки инструментального производства новой модели автомобиля ВАЗ-2107.

- 114 -ЗАКЛЮЧЕНИЕ

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

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

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

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

3. Для решения порядковых задач выбора введен новый класс бинарных отношений в критериальном пространстве - порядковые отношения. Исследованы свойства порядковых отношений. Получены критерии транзитивности и ацикличности, используемые при разработке алгоритмов выбора. Показано, что многие известные бинарные отношения содержатся в классе порядковых.

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

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

6. На основании теоретических результатов работы создана методика решения порядковых задач предварительного проектирования. Разработаны интерактивные алгоритмы, позволяющие в процессе диалога выявлять структуру предпочтений ЛПР, не накладывая на нее жестких априорных ограничений. Алгоритмы включены в состав системы диалогового автоматизированного многокритериального проектирования (ДАМП), разработанной при участии автора в Институте проблем управления.

Методика использована для решения следующих задач:

- выбор проекта технологической линии для производства белково-витаминных концентратов;

- формирование оптимального плана технической подготовки инструментального производства новой модели автомобиля ВАЗ-2107.

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

Суммарный экономический эффект от внедрения результатов диссертационной работы, подтвержденный актами о внедрении, составил 85 тыс. рублей.

1. АЙЗЕРМАН М.А., МАЛИШЕВСКИЙ A.B. Некоторые аспекты общей теории выбора лучших вариантов. Препринт Ин-та проблем управления. АН СССР. М., 1980.

2. БАУМАН Е.В. Выбор на графе и в критериальном пространстве. -Автоматика и телемеханика, 1977, J£ 5.

3. БЕНАЙЮН Р., ЛАРИЧЕВ О.й., де МОНГОЖЬФЬЕ Ж., ТЕРНИ Ж. Линейное программирование с многими критериями. Метод ограничений. Автоматика и телемеханика, 1971, Л 8.

4. БЕРЕЗОВСКИЙ Б.А., БОРЗЕНКО В.И., КЕМПНЕР Л.М. Бинарные отношения в многокритериальной оптимизации. М.: Наука, 1981.

5. БЕРЕЗОВСКИЙ Б.А., КЕМПНЕР Л.М. Вложенные модели многокритериальной оптимизации с упорядоченными по важности критериями.- Автоматика и телемеханика, 1981, № I.

6. БЕРЕЗОВСКИЙ Б.А., КЕМПНЕР Л.М. Об одном способе упорядочения критериев по важности.- Автоматика и телемеханика,1979, № 4.

7. БЕРЕЗОВСКИЙ Б.А., КЕМПНЕР Л.М. Оценка влияния информации об упорядочении критериев на число оптимальных вариантов. -Автоматика и телемеханика, 1980, # 6.

8. БЕРЕЗОВСКИЙ Б.А., ТРАВКИН С.И. Модель многокритериальной оптимизации с доминирующим показателем. Автоматика и телемеханика, 1981, № 4.

9. БЕРЕЗОВСКИЙ Б.А., ДОБРЯЖСКИЙ A.A., КЕМПНЕР Л.М. Алгоритмы аппроксимации функций выбора. В сб.: Организация вычислений на многопроцессорных ЭВМ. Ин-т проблем управления, вып. 26. М., 1981.

10. ВЕНТЦЕЛЬ E.C. Исследование операций: задачи, принципы, методология. М.: Наука, 1980.

11. ВИНОГРАДСКАЯ Т.М. Два алгоритма выбора многокритериальной альтернативы. Автоматика и телемеханика, 1977, № 3.

12. ВИНОГРАДСКАЯ Т.М., РУБЧИНСКИЙ A.A. Бинарные координатные отношения в критериальном пространстве. Автоматика и телемеханика, 198I, № 3-4.

13. ДАЙЕР Дж. Многоцелевое программирование с использованием человеко-машинных процедур. В кн.: Вопросы анализа и процедуры принятия решений. М.: Мир, 1976.

14. ДЖОФФРИОН А., ДАЙЕР Дж., ФАЙНБЕРГ А. Решение задач оптимизации при многих критериях на основе человеко-машинных процедур. В кн.: Вопросы анализа и процедуры принятия решений. М.: Мир, 1976.

15. ИВАНИН В.М. Асимптотическая оценка математического ожидания числа элементов множества Парето. Кибернетика, 1975, № I.

16. ИВАНИН В.М. Об одной оценке математического ожидания числа элементов множества Парето. Кибернетика, 1975, В 3.

17. КАРЛИН С. Математические методы в теории игр, программировании и экономике. М.: Мир, 1964.

18. КЕМПНЕР Л.М. Аппроксимация предпочтений в многокритериальных задачах. В кн.: Прикладная математика и задачи транспорта. Межвузовский сборник, МИИТ, 1982, вып.

19. КЕМПНЕР Л.М. Влияние ранжировки критериев на размер множества Парето. В сб.: Вопросы автоматики, электроника и систем энергоснабжения на железнодорожном транспорте. М., 1980.

20. КЕМПНЕР Л.М. Использование информации о важности критериев в диалоговых системах при решении многокритериальных задач. В сб.: Автоматизация технологических процессов. Тула,1981.

21. КЕМПНЕР Л.М. О распределении числа недоминируемых альтернатив в одной модели многокритериальной оптимизации. Автоматика и телемеханика, 1982, № 5.

22. КЕМПНЕР Л.М. О реализации бинарных отношений в критериальном пространстве. Автоматика и телемеханика, 1981, № 10.

23. КИНИ Р. Функции полезности многомерных альтернатив. В кн.: Вопросы анализа и процедуры принятия решений. М.; Мир, 1976.

24. КОРШУНОВ А.Д. О числе монотонных булевых функций. В сб.: Проблемы кибернетики, вып. 13, М.: Наука, 1981.

25. КУКСА А.И., ШОР Н.З. О методе оценки количества условно-оптимальных траекторий дискретного сепарабельного динамического программирования. Кибернетика, 1972, № 3.

26. ЛАРИЧЕВ О.И. Наука и искусство принятия решений. М.: Наука, 1979.

27. ЛЬЮС Р.Л., РАЙФА Г. Игры и решения. М.: ИЛ, 1961.

28. МАКАРОВ И.М., ВИНОГРАДСКАЯ Т.М. Глобальная характеристика структуры предпочтения в задачах выбора. ДАН СССР, 1979, т. 245, № 2.

29. МИРКИН Б.Г. Проблема группового выбора. М.: Наука, 1974.

30. НЕЙМАН Дж. фон, МОРГЕНШТЕРН 0. Теория игр и экономическое поведение. М.: Наука, 1970.

31. ПОДИНОВСКИЙ В.В., ГАФТ М.Г. О построении решающих правил в задачах принятия решений. Автоматика и телемеханика,198I, & 6.

32. ПОДИНОВСКИЙ В.В. Задачи принятия решений по нескольким однородным равноценным критериям. В кн.: Ш Всесоюзная конференция по теории игр. Тезисы докладов. Из-во Одесского ун-та,1974.

33. ПОДИНОВСКИЙ В.В. Многокритериальные задачи с однородными равноценными критериями. Курн. вычисл. мат. и мат. физ.,1975, т. 15, № 2.

34. ПОДИНОВСКИЙ В.В. Многокритериальные задачи с упорядоченными по важности однородными критериями. Автоматика и телемеханика, 1976, № II.

35. ПОДИНОВСКИЙ В.В. Об относительной важности критериев в многокритериальных задачах принятия решений. В сб.: Многокритериальные задачи принятия решений. М.: Машиностроение, 1978.

36. ПОДИНОВСКИЙ В.В., ГАВРИЛОВ В.М. Оптимизация по последовательно применяемым критериям. М.: Советское радио, 1975.

37. РАЙФА Г. Анализ решений. М.: Наука, 1977.

38. РУА Б. Классификация и выбор при наличии нескольких критериев (метод ЭЛЕКТРА). В кн.: Вопросы анализа и процедуры принятия решений. М.: Мир, 1976.

39. РУА Б. Проблемы и методы принятия решений в задачах с многими целевыми функциями. В кн.: Вопросы анализа и процедуры принятия решений. М.: Мир, 1976.

40. САЛУКВАДЗЕ М.Е. 0 задаче линейного программирования с векторным критерием качества. Автоматика и телемеханика, 1975, № 10.

41. СОКОЛОВ В.Б., ВИНОГРАДСКАЯ Т.М., АБРАМОВ А.Л. Целевые комплексные программы и иерархические отношения. Препринт Ин-та проблем управления, М., 1980.

42. ФАНДЕЛЬ Г., ВИЛЬГЕЛЬМ Й. 0 теории принятия решений при многих критериях. В кн.: Статистические модели и многокритериальные задачи принятия решений. М.: Статистика, 1979.

43. ФИШБЕРН П. Методы оценки аддитивных ценностей. В кн.: Статистическое измерение качественных характеристик. М.: Статистика, 1972.

44. ФИШБЕРН П. Многомерные функции полезности в теории ожидаемой полезности. В кн.: Статистические модели и многокритериальные задачи принятия решений. М.: Статистика, 1979.

45. ФИШБЕРН П. Теория полезности для принятия решений. М.: Наука, 1978.

46. ЧЕРНОВ Г., МОЗЕС Л. Элементарная теория статистических решений. М.: Советское радио, 1962.

47. АШШШ R.J. Utility theory without the completeness axiom.-Econometrics, 1962, vol.30,

48. ARROW K.J. national choice functions and orderings.- Econo-metrica,I959,vol.26,№I02.

49. ARROW K.J. Social choice and individual values. Yale Univ. Press., 1963.

50. BARUDORFF-NIELSEEi 0.,S0BEL M. On the distribution of the number of admissible points in a vector rendom sample.

51. Теория вероятности и её применения, т.II, вып.З, 1966.

52. BEREZOVSKY В.А. ,KEMPHER L.M. A class of multicriterial optimization models with criteria ordered by importance.-"Large Scale syst.: Theory and Appl. Proc.2nd IFAC Symp., Toulouse,1980". Oxford e.a;I98I.

53. BOLDUR G. Linear programming problems with complex desision conditions.-In.:7th Math.Programm.Simp.,The Hague,1970.55« CHAMES A.,COOPER W. Management models and industrial applications of linear programming. Wiley; 1961.

54. CHEHNOFF H. Rational selection of decision functions.-Econometrica,19 54,vol.22,№ 3.

55. FISHBUKN P.C. Schould social choice be based on binary comparisons? J .Math.Social.,1971»vol.I,№ I.

56. GEOFFRION A.M. A paramej?iic programming solutions to the vector maximum problem, with applications to decisions under uncertainly.- Stanford,California,I965.

57. GEOFFRION A.M. Vector maximal decomposition programming. In: 7th Math.Programm.Symp., the Hague, 1970.

58. JAMISON D.T.,IAU L.J. Semiorders and the theory of choice^-Econometri ca,1973,vol.41,№ 5.

59. KLEE A.J. The role of decision models in the evaluation of competing enviromental health alternatives.- Manag.Sci., I97I»vol.18,№ 2.

60. КОНИ H.W.,TACKER A.W. Nonlinear programming. In: Proe. of 2ndBerceley Symp.on Math.Stat. Berceley, California, 1951.

61. MAIER-ROTHE C.,STAKEAED J.M. A linear programming approach to choosing between multiobjective alternatives. In:7th Math. Programm.Symp.,the Hague,1970.

62. MILLER J.R. The assessment of worth: asistematic procedure and its experimental validation. Doct.diss.,M.I.Т.,1966.

63. PARETO V. Cours d'Economie Politique.Rouge,Lausanne,1889.

64. PLOTT C.R. PAth independence, rationality and social choice.-Econometri ca,1973,vol.41,№ 6.

65. SAVAGE L.J. The foundations of statistics. Wiley,New Jork,I954

66. SEN A.K. Collective choice and social welfare. San.Francisco: Hoiden-Day,1970.

67. SUZUMURA K. Rational choice and revealed preference. Rev. Econ.Stud.,1976;vol.44,№ I.

68. TERRY H. Comparative evaluation of performance using multiple criteria. Manag.Sei., 1962, vol.9,№3.

69. TRACKTENGEBIDS E.A.,BEREZOVSKY B.A.,TRA.VKIN S.I. Stochastic approach to the problem of multicriterial choice. In: Proc. of IPAC S$mp.on Large Scale Syst.,Udina,1976.