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

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

1.2 Характеристика типовых задач математического моделирования и подходов к их решению.

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

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

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

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

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

Их можно разделить на:

принятие решений в условиях определенности - исходные данные - детерминированные; принятие решений в условиях неопределенности - исходные данные - случайные величины.

Классификация задач оптимизации

Исходные данные	Переменные	Зависимости	Задача
Детерминированные	Непрерывные	Линейные	Линейного программирования
Целочисленные	Линейные	Целочисленного программирования
Непрерывные, целочисленные	Нелинейные	Нелинейного программирования
Случайные	Непрерывные	Линейные	Стохастическое программирование

А по критерию эффективности:

одноцелевое принятие решений (один критерий эффективности); многоцелевое принятие решений (несколько критериев эффективности).

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

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

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

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

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

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

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

1.3 Компоненты принятия решений.

1. Варьируемые параметры -

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

• Варьируемые параметры (варьируемые переменные) – то, что ЛПР может назначать произвольно при принятии решения.

• Выбор значений параметров при принятии решения и есть задача ЛПР.

• Оптимальное значение параметров – это значит наилучшее в каком-то смысле.

  2. Область допустимых значений параметров определяет 

параметры принятия решения.

– Описывается одним или несколькими ограничениями

– ЛПР в процессе принятия решения может менять ОДЗ и рассматривать другие возможные варианты.

• Внешние и внутренние ограничения

– Внешние ограничения (ограничения среды – экзогенные)

– Внутренние ограничения (ограничения модели – эндогенные)

• ОДЗ задается набором ограничений на варьируемые параметры:

– Частные ограничения на переменные;

– Ограничения общего вида (линейные и нелинейные).

• Ограничения для варьируемых параметров ???? из n-мерного пространства: ???????? ? ???????? ? ???????? , ???? = 1, … , ????.

– Данный тип ограничений в практическом применении существует почти всегда.

• Ограничения общего вида для вектора варьируемых параметров ???? из n-мерного евклидового пространства: ????(????) = ????(????1, … , ????????) ? 0.

– Данные ограничения могут быть легко преобразованы в ограничения типа равенств.

  3. Цель и критерий оптимальности.

Цель характеризует поведение ЛПР в процессе принятия решения. Критерий оптимальности – характеристика (или одна их характеристик) варианта решения.

  – Критерий обязательно должен быть выражен в числовой форме.

  – Большее (меньшее) значение означает лучшую (худшую) 

  характеристику с точки зрения ЛПР.

  – По данному критерию можно сравнить любые два варианта (лучше,  хуже или эквивалентно)

Частный критерий – объективная характеристика.

  – При условии, что значение характеризует качество (вес, размеры, стоимость, калорийность и т. д. )

Наличие/отсутствие возможности.

  – Приводит к бинарным значениям характеристик качества (1/0).

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

  – Такая характеристика указывает, какое значение лучше, но не 

  указывает, на сколько.

Экспертная оценка.

  – Результат субъективного оценивания эксперта и/или ЛПР.

  4. Принцип оптимальности и роль ЛПР

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

  – ЛПР выбирает «наилучшее» с его точки зрения решение;

  – Оптимальное решение в многокритериальном случае чаще всего не  существует;

– Рациональное решение – решение, принятие которого можно объективно объяснить.

• Роль ЛПР в процессе принятия решения:

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

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

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

Пусть имеется множество из k альтернатив А = {а1,а2,..аk}.

Тогда для критерия С может быть рассмотрено нечеткое множество

С= {с1/а1, с2)/а2,. . , сk)/ак}, где сi/аi – значение из промежутка [0, 1].

Оценка альтернативы аi по критерию С, характеризует степень соответствия альтернативы понятию, определяемому критерием С.

Если имеется n критериев: С1, С2,... ,Сn, то лучшей считается альтернатива, удовлетворяющая и критерию C1, и С2, и..., и Сn. Тогда правило для выбора наилучшей альтернативы может быть записано в виде; пересечения соответствующих нечетких множеств:

D = C1 ?C2 ?...?Cn

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

1.5 Теория метода многокритериальной оптимизации по Парето

Вильфредо Парето

(1848 – 1923)

Итальянский математик, инженер, экономист и социолог

• Диссертация «Фундаментальные принципы равновесия в твердых телах»

• Длительная работа инженером в ж/д отрасли и в металлургии

• С 1893 – профессор политической экономии Лозаннского университета в Швейцарии

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

Закон Парето, или принцип Парето, или принцип 20/80

– Эмпирическое правило: «20% усилий дают 80% результата, а остальные 80% усилий — лишь 20% результата».

– Может использоваться как базовая установка в анализе факторов эффективности какой-либо деятельности и оптимизации её результатов:

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

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

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