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

• Кириллов, Юрий Васильевич
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Кириллов, Юрий Васильевич

Введение.

Глава 1. Векторная оптимизация в задачах управления.

1.1. Управление и задачи принятия решений.

1.1.1. Принятие решений как задача системного анализа.

1.1.2. Примеры задач векторной оптимизации.

1.1.2.1. Задача моделирования сложной системы управления.

1.1.2.2. Задача моделирования направлений деятельности фирмы.

1.1.2.3. Задачи моделирования инвестиционной деятельности фирмы.

1.1.3. Общие замечания о примерах задач векторной оптимизации.

1.:2. Аналитический обзор методов решения задач векторной оптимизации.

1.2.1. Общая постановка задачи векторной оптимизации.

1.2.2. Методы решения ВЗМП.

1.2.2.1. Методы, основанные на свертке критериев.

1.2.2.2. Методы, использующие ограничения на критерии.

1.2.2.3. Методы целевого программирования.

1.2.2.4. Методы поиска компромиссного решения.

1.2.2.5. Обзор других методов решения ВЗМП.

1.2.3. Общие недостатки существующих методов.

1.3. Выводы по главе 1.

Глава 2. Принципы построения алгоритма решения задач векторной оптимизации.

2.1. Формализованная постановка общей задачи векторной оптимизации.

2.2. Классификация векторных задач математического программирования.

2.3. Нормализация критериев в задачах векторной оптимизации.

2.4. Выбор алгоритма решения ВЗМП.

2.4.1. Принцип выбора компромиссного решения.

2.4.2. Принцип гарантированного результата.

2.4.3. Алгоритм гарантированного результата при нормализации критериев.

2.5. Выводы по главе 2.

Глава 3. Решение различных классов векторных задач с помощью алгоритма ГРНК.

3.1. Решение линейных векторных задач.

3.1.1. Решение равнозначных линейных векторных задач.

3.1.1.1. Решение однородных равнозначных ЛВЗ.

3.1.1.2. Решение неоднородных равнозначных ЛВЗ.

3.1.2. Алгоритм решения равнозначных линейных векторных задач.

3.1.3. Решение неравнозначных линейных векторных задач.

3.1.3.1. Определение приоритета критерия однородной векторной задачи.

3.1.3.2. Вычисление коэффициентов приоритета однородной векторной задачи.

3.1.3.3. Принцип гарантированного результата для неравнозначных ЛВЗ.

3.1.3.4. Решение неравнозначных однородных ЛВЗ.

3.1.3.5. Определение приоритета критерия неоднородной векторной задачи.

3.1.3.6. Решение неравнозначных неоднородных ЛВЗ.

3.1.4. Алгоритм решения неравнозначных линейных векторных задач.

3.2. Решение дискретных векторных задач.

3.2.1. Постановка неоднородной равнозначной дискретной векторной задачи.

3.2.2. Решение неоднородных равнозначных ЦЛВЗ.

3.2.2.1. Нормализация в ЦЛВЗ.

3.2.2.2. Выбор метода решения ЦЛВЗ.

3.2.3. Решение неоднородных неравнозначных ЦЛВЗ.

3.2.4. Алгоритм решения целочисленных линейных векторных задач.

3.3. Решение нелинейных векторных задач.

3.3.1. Решение неоднородных равнозначных НЛВЗ.

3.3.1.1. Нормализация в НЛВЗ.

3.3.1.2. Выбор метода решения НЛВЗ.

3.3.1.3. Условия сходимости метода решения НЛВЗ

3.3.2. Алгоритм решения неоднородных равнозначных НЛВЗ.

3.3.3. Решение неоднородных неравнозначных НЛВЗ.

3.3.4. Алгоритм решения неоднородных неравнозначных

НЛВЗ.

3.4. Выводы по главе 3.

Глава 4. Использование алгоритма ГРНК для решения прикладных задач векторной оптимизации.

АЛ.Задача оптимального обеспечения топливом предприятий энергетической промышленности с учетом качества энергоносителей.

4.1.1. Актуальность задачи.

4.1.2. Постановка векторной задачи.

4.1.3. Решение векторной задачи.

4.2. Задача оптимизации ценовой политики фирмы.

4.2.1. Актуальность задачи.

4.2.2. Постановка векторной задачи.

4.2.3. Решение векторной задачи.

4.3. Выводы по главе 4.

Введение диссертации (часть автореферата) на тему «Разработка и использование алгоритмов решения многокритериальных задач управления на основе принципа гарантированного результата»

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

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

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

Разработка методов решения подобных задач ведется достаточно давно и связана с работами отечественных и зарубежных ученых: Н.Н. Моисеева, B.C. Михале-вича, B.J1. Волковича, Ю.Б. Гермейера, В.В. Подиновского, Л.И. Полищука, В.В. Хоменюка, М.А. Айзермана, И.М. Макарова, Ю.К. Машунина, Б.А. Березовского, Р. Штойера, С. Карлина, Р. Кини, X. Райфа и др., которыми был сделан основополагающий вклад в теорию и практику решений различных задач системного анализа и многокритериальной оптимизации.

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

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

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

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

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

Для достижения этой цели в диссертации поставлены следующие задачи:

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

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

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

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

3. Объектом исследования являются математические модели сложных (многоуровневых) систем принятия управленческих решений в различных отраслях.

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

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

6. Научную новизну диссертационного исследования составляют:

1. Выполненная классификация задач многокритериальной оптимизации, кото9 рая позволяет идентифицировать тип решаемой векторной задачи и, соответственно, выбрать алгоритм ее решения.

2. Общая схема решения задач векторной оптимизации — алгоритм гарантированного результата при нормализации критериев (алгоритм ГРНК), который определяет общие принципы построения решения.

3. Полученные рабочие алгоритмы для решения конкретных классов следующих векторных задач с равнозначными критериями:

• линейных однородных и неоднородных задач;

• целочисленных неоднородных задач;

• нелинейных неоднородных задач.

Предложенные алгоритмы позволяют получить единственное Парето-оптимальное решение.

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

7. Практическая значимость результатов исследования состоит в том, что:

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

2. На конкретных примерах (задача оптимального обеспечения топливом предприятия ТЭЦ - 2 ОАО «Новосибирскэнерго» и задача оптимизации ценовой политики ООО «Сибирский берег») показана работоспособность разработанных алгоритмов.

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

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

10

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

2. Общая схема алгоритма ГРНК для решения задач векторной оптимизации, которая позволяет получить единственное Парето-оптимальное решение.

3. Рабочие алгоритмы ГРНК для решения следующих типов векторных задач с равнозначными и неравнозначными критериями:

• линейных однородных и неоднородных задач;

• целочисленных неоднородных задач;

• нелинейных неоднородных задач.

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

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

9. Апробация работы. Работа выполнялась в рамках инициативной НИР кафедры экономической информатики Новосибирского государственного технического университета (НГТУ) «Теоретические и прикладные аспекты экономической информатики». Разработанные алгоритмы использовались на факультете бизнеса НГТУ при проведении занятий по дисциплинам «Методы оптимизации» и «Математическая экономика».

Основные теоретические выводы и практические рекомендации диссертации докладывались автором на международной научно- практической конференции «Экономическое образование и наука в современных условиях: опыт, проблемы и перспективы» (Семипалатинск, 2002г.); международной научно-технической конференции «Информационные системы и технологии ИСТ'2003» (Новосибирск, 2003г.); 6-й Всероссийской научно-практической конференции «Стратегия бизнеса и социально-экономическое развитие региона» (Ярославль, 2003г.); V международной конференции по информационным технологиям «Modelling, Computation and Optimization in Information Systems and Management Sciences MCO 2004» (Метц, Фран

11 ция, 2004г.); VII международной конференции «Актуальные проблемы электронного приборостроения» (Новосибирск, 2004г.).

10. Публикации. По теме диссертации автором опубликовано 12 печатных работ общим объемом 4 п.л. Диссертация соответствует паспорту специальности 05.13.01 Паспорта специальностей ВАК, пункт 4.

11. Структура и объем диссертации. Цели и задачи исследования определили логику и структуру работы, состоящую из введения, четырех глав, заключения, списка литературы и приложения. Основной текст диссертации изложен на 157 страницах, включает 21 рисунок, 14 таблиц и 1 приложение. Список литературы содержит 66 наименований.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Кириллов, Юрий Васильевич

Основные результаты выполненной работы состоят в следующем.

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

2. Для решения нескольких классов задач многокритериальной оптимизации был разработан метод их решения - алгоритм гарантированного результата при нормализации критериев (алгоритм ГРНК). На основе принципа оптимальности по Парето и оригинальной методики получены доказательства существования и единственности компромиссного решения для следующих задач:

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

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

- нелинейных неоднородных с равнозначными критериями.

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

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

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

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

К перспективам дальнейших исследований по данной теме можно отнести:

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

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

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

4. Рассмотрение возможность применения алгоритмов ГРНК для решения других типов задач векторной оптимизации.

Заключение

Список литературы диссертационного исследования кандидат технических наук Кириллов, Юрий Васильевич, 2005 год

1. Моисеев Н.Н. Математические задачи системного анализа. — М.: Наука, 1981. -488с.

2. Перегудов Ф.И., Тарасенко Ф.П. Основы системного анализа. — М.: Логос, 1997.-389с.

3. Машунин Ю.К. Теоретические основы и методы векторной оптимизации в управлении экономическими системами. М.: Логос, 2001. - 252с.

4. Дегтярев Ю.И. Основы системного анализа. М.: Наука, 1996. — 356с.

5. Кухтенко А.И. Основные направления развития теории управления. — Киев: Наукова думка, 1968, вып. IV.

6. Системные исследования. М.: Наука, 1970. - 126с.

7. Системные исследования. М.: Наука, 1971. - 149с.

8. Михалевич B.C., Волкович В.Л. Вычислительные методы исследования и проектирования сложных систем. М.: Наука, 1982. — 295с.

9. Месарович М., Мако Д., Такахара И. Теория иерархических многоуровневых систем.-М.: Мир, 1973.-334с.

10. Моисеев Н.Н. Элементы теории оптимальных систем. М.: Наука, 1975. — 345с.

11. Бочаров В.В. Финансовый анализ. СПб.: Питер, 2001 — 240с.

12. Иванов Л.Н., Кириллов Ю.В. Использование многокритериальных моделей для информационной поддержки принятия решений. //Программные продукты и системы. 2005. - №1. - стр. 44 - 47.

13. Касимов Ю.Ф. Основы теории оптимального портфеля. — М.: Филинъ, 1998. -154с.

14. Капитоненко В.В. Финансовая математика и ее приложения. М.: «Издательство ПРИОР», 2001. - 144с.

15. Шарп У. и др. Инвестиции: Пер. с англ. М.: Инфра - М, 1997. - 1024с.

16. Развитие экономико-математических методов: итоги, проблемы, перспективы // Экономика и математические методы. 1987. Т.23, вып.4,5,6.

17. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. - 256с.

18. Полищук Л.И. Анализ многокритериальных экономико-математических моделей. Новосибирск: Наука. Сиб. Отделение, 1989. - 352с.

19. Горский Ю.М. Системно информационный анализ процессов управления. -Новосибирск: Энергия, 1988. - 326с.

20. Штойер Р. Многокритериальная оптимизация. Теория, вычисления и приложения: Пер. с англ. М.: Радио и связь, 1992. — 504с.

21. Карлин С. Математические методы в теории игр, программировании и экономике: Пер. с англ. М.: Мир, 1964. - 837с.

22. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.-383с.

23. Хоменюк В.В. Элементы теории многоцелевой оптимизации. — М.: Наука, 1983.- 123с.

24. Зак Ю.А. Многоэтапные процессы принятия решений в задаче векторной оптимизации. //Автоматика и телемеханика. 1976. - №6. — с.41-45.

25. Машунин Ю.К. Методы и модели векторной оптимизации. М.: Наука, 1986.139-141с.

26. Айзерман М.А., Алескеров Ф.И. Выбор вариантов. Основы теории. М.: Наука, 1990.-364с.

27. Макаров И.М. и др. Теория выбора и принятия решений. — М.: Наука, 1982. — 368с.

28. Дубов Ю.А. и др. Многокритериальные модели формирования и выбора вариантов систем. -М.: Наука, 1986. 198с.

29. Березовский Б.А., Гнедин А.В. Задача наилучшего выбора. М.: Наука, 1984. - 196с.

30. Березовский Б.А. и др. Многокритериальная оптимизация. Математические аспекты. М.: Наука, 1989. - 128с.

31. Кини Р., Райфа X. Принятие решений по многим критериям: предпочтения и замещения. — М.: Радио и связь, 1981.- 452с.

32. Фишберн П. Теория полезности для принятия решений. — М.: Мир, 1978. — 352с.

33. Бурков В.Н. Основы математической теории активных систем. М.: Изд. ИПУ АН СССР, 1977. - 347с.

34. Бурков В.Н., Новиков Д.А. Введение в теорию активных систем. — М.: Изд. ИПУ РАН, 1995.- 124с.

35. Бурков В.Н., Новиков Д.А. Теория активных систем: состояние и управление. -М.: Изд. ИПУ РАН, 1999.- 126с.

36. Философский энциклопедический словарь. 2-е изд. М.: Сов. энциклопедия, 1989.-815с.

37. Калихман И.Л. Линейная алгебра и программирование. -М.: Высшая школа, 1967.-216с.

38. Кузнецов Ю.Н. и др. Математическое программирование. — М.: Высшая школа, 1980. 346с.

39. Зайченко Ю.П. Исследование операций. Киев: Выща школа, 1988. - 552с.

40. Кузнецов А.В. и др. Высшая математика: Математическое программирование. Минск: Вышэйшая школа, 1994. - 397с.140

41. Елтаренко Е.А. Оценка и выбор решения по многим критериям. — М.: МИФИ, 1995.-95с.

42. Новиков П.С. Элементы математической логики. М.: Наука, 1973, -358с.

43. Arrow K.J. Rational choice functions and orderings. Econometrica, 1959, vol. 26, Pp. 121 - 127.

44. Arrow K.J., Hurwicz L. An optimally criterion for decision-making under ignorance. In: Uncertainty and expectation in economics/Ed. By C.F. Carter, J.L. Ford. Oxford: Blackwell and Mott, 1972. 299 p.

45. Milnor J. Games against nature. In: Decision processes/Ed. By R.M. Thrall and others. L.: Chapman and Hall, 1954. 332 p.

46. Sen A.K. Choice functions and revealed preference. Rev. Econ. Stud., 1971. vol. 38, Pp. 307-317.

47. Иванов Jl.H., Кириллов Ю.В. К вопросу о Парето-оптимальности решений задач векторной оптимизации. //Сборник научных трудов НГТУ. 2003. -№3(33).-стр. 61-70.

48. Карпелевич Ф.И., Садовский Л.Е. Элементы линейной алгебры и линейного программирования. -М.: Наука, 1965. -276с.

49. Наумов А.А., Мезенцев Ю.А. Оптимальное управление инвестиционным портфелем. — Новосибирск: ООО «Издательство Лада», 2002. — 192с.

50. Y. Nesterov and A. Nemirovsi: Interior Point Polynomial Algorithms in Convex Programming Theory and Application. SIAM, Philadelphia, 1994.

51. Липсиц И.В. Коммерческое ценообразование. M.: Инфра, 1998. — 258с.

52. Цены и ценообразование. / Под ред. Салимжанова И.К. М.: Дело, 1999. -312с.

53. Бокс Дж., Дженкинс Г. Анализ временных рядов. М.: Мир, 1974. - Вып. 1,2.

54. Четыркин Е.М. Финансовый анализ производственных инвестиций. М.: Дело, 1998.-256с.

55. Ковалев В.В. Методы оценки инвестиционных проектов. М.: Финансы и статистика, 1998.- 128с.

56. Грешилов А.А. Как принять наилучшее решение в реальных условиях. — М.: Радио и связь, 1991. 320с.

57. Мезенцев Ю.А., Кириллов Ю.В. Некоторые аспекты задач оптимального проектирования при нескольких критериях предпочтения. //Сборник научных трудов НГТУ. 2003. - №3(33). - стр. 21-40.

58. Кириллов Ю.В., Зенкова О.В. Моделирование инвестиционных потоков. //Управление экономикой: методы, модели, технологии: Сб. материалов российской научно-методической конференции с международным участием. — Уфа, 2002.-с. 36-38.

59. Кириллов Ю.В. Многокритериальное моделирование как основа информационных технологий поддержки .принятия решений. //Фундаментальные исследования. 2004. - №6. - стр. 114-116.

60. Кириллов Ю.В., Кудаев С.А. Задача оптимального обеспечения топливом предприятий энергетической промышленности с учетом качества энергоносителей. //Современные наукоемкие технологии. 2005. — №1. — стр. 122 — 126.