«Многокритериальная оптимизация» - Дипломная работа

Содержание

Введение 3

Глава I. Многокритериальная оптимизация 5

1.1. Постановка задачи многокритериальной оптимизации 5

1.2. Примеры задач 8

1.3. Множество Парето 10

1.4. Основные методы решения многокритериальных задач (метод обобщенного критерия, метод последовательных уступок) 31

Глава II. Реализация методов последовательных уступок и обобщенного критерия для линейных задач 35

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

2.2. Блок-схема метода последовательных уступок 42

2.3. Программное решение линейной задачи метода последовательных уступок с помощью Excel 58

2.4. Программное решение линейной задачи с помощью Pascal 61

2.5. Тестирование программы и решение задачи на ЭВМ 66

Заключение 69

Литература 71

Введение

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

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

Объектом исследования является задачи многокритериальной оптимизации.

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

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

Сформулированная цель предопределила совокупность решаемых задач:

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

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

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

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

5. Провести сравнительный анализ методов.

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

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

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

Выдержка из текста работы

Глава I. Многокритериальная оптимизация

1.1. Постановка задачи многокритериальной оптимизации

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

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

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

Задача со многими критериями может быть записана в таком виде:

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

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

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

Сравнение допустимых решений в многокритериальной задаче. Оценкой допустимого решения х X задачи (10.1.1) называется вектор

Смысл сравнения различных допустимых решений в многокритериальной задаче состоит в сравнивании их векторных оценок. То есть предпочтительность на множестве X можно заменить предпочтительностью оценок на множестве Rm. Однако, на множестве Rm элементы сравнимы далеко не всегда. Часто встречается ситуация, когда среди двух допустимых решений одно лучше по одному критерию, а второе — по другому критерию. Например, в задаче (Пример 1) векторная оценка решения (20; 0) имеет вид (200; 20), а векторная оценка решения (0; 40) — (160; 40). По этим оценкам видно, что рассматриваемые решения несравнимы.

3. Эффективные решения многокритериальных задач Математически отношения между объектами, когда некоторые из них можно сравнивать, а некоторые несравнимы, называются отношениями частичного порядка или отношениями строго частичного порядка. В задаче многокритериальной оптимизации (1.1) на множестве Х допустимых решений можно ввести отношение строго частичного порядка. Пусть х, у — два допустимых решения задачи (1.1), т.е. х X и у X . Говорят, что x строго предпочтительнее у, если решение х лучше решения по всем критериям. Такое отношение строгого предпочтения на множестве X записывают х у.

Отношение строгого предпочтения можно ослабить: говорят, что допустимое решение х доминирует допустимое решение у, если х не хуже у по всем критериям и строго лучше, хотя бы по одному из них. Такое отношение доминирования обозначается х =у у.

Отношение доминирования, введенное на множестве допустимых решений X, называется также доминированием по Парето.

Рассмотрим задачу (1.1) на нахождение максимума по всем критериям. Решение х0 е X называется оптимальным по Парею или эффективным, если не существует 'такого другого решения х X . что

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

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

Проиллюстрируем прием выделения эффективных решений на примере с двумя критериями: W1,. W2 (оба требуется максимизировать). Множество X состоит из конечного числа п возможных решений х1, х2,…хn. Каждому решению соответствуют определенные значения показателей W1, W2: будем изображать решение точкой на плоскости с координатами значений показателей W1, W2 и занумеруем точки соответственно решению (рис 1).

Очевидно, из всего множества X эффективными будут только х1,х2,х3,

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

Особенно удобным является случай, когда уже в результате предварительного анализа многокритериальной задачи выясняется, что можно допустить уступки лишь в пределах «инженерной» точности (5-10% от наибольшей величины критерия).

Список литературы

1. Алгоритмы и программы решения задач на графах и сетях. Отв. ред. М.И. Нечепуренко. – Новосибирск: Наука. Сиб. отделение, 1990. – 513 с.

2. Архангельский А.Я. Приемы программирования в Delphi. Версии 5 – 7. М.: ЗАО «Издательство БИНОМ», 2003.

3. Беляков Г.П. и др. Основы системотехники: Учеб. Пособие для вузов/ Г.П. Беляков, В.А. Сарычев, В.А. Сорокин, В.О. Чернышев. Под ред. В.О. Чернышева. – Томск: МГП «РАСКО», 1992. 312 с.: ил.

4. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем: Учеб. пособие. — 2-е изд., перераб. и доп. — М.: Финансы и статистика, 2006. – 432 с: ил.

5. Дискретная математика: логика, группы, графы/ О.Е. Акимов. – 2-е изд., доп. – М.: Лаборатория Базовых Знаний, 2003. – 376 с.: ил.

6. Дубов Ю.А., Травкин С.И., Якимец В.Н. Многокритериальные модели формирования и выбора вариантов систем. – М.: Наука. Гл. ред. физ.-мат. лит., 1986. – 296 с. – (Теория и методы системного анализа.)

7. Дегтярев Ю.И. Системный анализ и исследование операций.- М.:Высшая школа, 2006. - 335с.

8. Емельянов С.В., Ларичев О.И. Многокритериальные методы принятия решений. – М.: Знание, 1985. – 32 с. – (Новое в жизни, науке, технике. Сер. «Математика, кибернетика»; № 10).

9. Зыков А.А. Основы теории графов. – М.: Наука, 1987. – 381 с.

10. Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения: Пер. с англ./Под ред. И.Ф. Шахнова. – М.: Радио и связь, 1981. – 560 с. ил.

11. Клешков В.М. Модели и алгоритмы распределения общих ресурсов при управлении инновациями реструктурированного предприятия ВПК. –Дисс. канд. техн. наук. – Красноярск: НИИ СУВПТ, 2003, 165 с.

12. Кузменков В.А. Математические методы и модели исследования операций. Параметрическая, многокритериальная и целочисленное оптимизация: учеб. Пособие / В.А. Кузменков, В.Н. Юрьев. – 2-е изд., перераб. И доп. – СПб.: Изд-во Политехн. Ун-та, 2011. – 120 с.

13. Лекции по дискретной математике/ Ю.В. Капитонова, С.Л. Кривой, А.А. Летичевский и др. – СПб.: БХВ-Петербург, 2004. – 624 с.

14. Лекции по теории графов/ Емеличев В.А., Мельниченков О.И., Сарванов В.И., Тышкевич Р.И. – М.: Наука, Гл. ред. физ.-мат. лит., 1990. – 384 с.

15. Лекции по теории графов: Учебн. пособие. – М.: Наука, 1990. – 384 с.

16. Малыхина М.П. Программирование на языке высокого уровня Turbo Pascal. – Спб.: БХВ-Петербург, 2006. – 544 с.

17. Математическое программирование (с элементами информационных технологий): Учеб. пособие для студ. нематемат. спец. вузов/ В.Р. Кулян, Е.А. Юнькова, А.Б. Жильцов. – К.: МАУП, 2000. – 124 с.: ил.

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

19. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2004. – 302 с.: ил.

20. Перегудов Ф.И., Тарасенко Ф.П. Основы системного анализа: Учеб. 2-е изд., доп. – Томск: Изд-во НТЛ, 1997. – 369 с.: ил.

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

22. Программирование в среде Turbo Pascal: методичка/Ю.В. Псигин, О.Г. Крупенников: Ульяновск, 2008. – 95 с.

23. Розен. В.В.Математические модели принятия решений в экономике. Учебное пособие.– М.: Книжный дом "Университет", Высшая школа, 2002.– 288 с., ил.

24. Семенкин Е.С., Семенкина О.Э., Коробейников С.П. Оптимизация технических систем. Учебное пособие. – Красноярск: СИБУП, 1996. 284 с.

25. Семенкин, Е.С. Распределение ресурсов при управлении инновациями реструктурированного предприятия ВПК / Е.С. Семенкин, В.М. Клешков, К.В. Гупалов, А.В. Гуменникова // – Красноярск: СибГАУ, 2004, с. 124-134.

26. Таха, Хэмди А. Введение в исследование операций. – М.: Мир, 2001.

27. Теория графов и её применение: сборник научных трудов/ Институт математики им. С.Л. Соболева. – Новосибирск, 1996. – 106 с.

28. Хайниш С.В., Клешков В.М., Бородин А.Н. Российское предприятие ВПК: выжить и развиваться. (На примере реформирования и развития Химзавода – филиала ФГУП «КРАСМАШ»). – М.: Рохос, 2003. – 240 с., цв. вкл. (Из опыта управленческого консультирования.)

29. Шикин Е.В., Шикина Г.Е. Исследование операций : учеб. — М. : ТК Велби, Изд-во Проспект, 2006. – 280 с.

30. Юдин Д.Б. Вычислительные методы теории принятия решений. – М.: Наука. Гл. ред. физ.-мат. лит., 1989. – 320 с. (Теория и методы системного анализа.)

31. Яблонский С.В. Введение в дискретную митематику. – М.: Наука, 1986. – 384 с.

Примечания

К работе прилагается презентация.

К работе прилагается все исходники. Есть приложения.