Многокритериальные задачи. Парето-оптимальность

Министерство образования и науки  российской федерации

(минобрнауки россии)

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Санкт-Петербургский государственный политехнический университет» (ФГБОУ ВПО «СПбГПУ»)

 

Институт менеджмента и информационных технологий

(филиал)федерального государственного  бюджетного образовательного учреждения  высшего профессионального образования

«Санкт-Петербургский государственный политехнический университет» в г. Череповце (ИМИТ «СПбГПУ»)

Кафедра экономики

 

 

 

 

 

 

 

 

 

кантрольная работа

Дисциплина: «Методы оптимальных решений»

 

 

 

 

 

 

 

Выполнил студент группы з.623 т   Жохов Артем Валерьевич

№ варианта  4       № зачетной книжки з.6120305 т

Руководитель                                          Лысова Наталия Викторовна   

 

          «_______» _________________________20___ г.

        __________   __________________

отметка о зачете           подпись преподавателя

 

 

г. Череповец

2015

Содержание

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.Многокритериальные задачи. Парето-оптимальность.

 

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

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

Определение

Задача многокритериальной оптимизации формулируется следующим образом:

где  это k (  ) целевых функций. Векторы решений  относятся к не пустой области определения S.

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

Эталонные точки

Для возможности оценки качества найденных решений, обычно рассматривают такие точки в области значения целевой функции:

идеальная точка, Y I,

утопическая точка, Y U,

надир ( надир ), Y N.

В некоторых случаях эти точки могут быть решениями.

Идеальная точка определяется как вектор, каждая из координат которого имеет оптимальное значение соответствующей составляющей целевой функции:

Точка надир   определяется как вектор:

Утопическую точку Y U вычисляют на основе идеальной:

где ?> 0, U - единичный вектор. 

 

Критерии оптимальности

Критерий Парето

 

Вектор решения   называется оптимальным по Парето если не существует   такого, что   для всех   и   для хотя бы одного i. Множество оптимальных по Парето решений можно обозначить как P ( S ). Целевой вектор является оптимальным по Парето, если соответствующий ему вектор из области определения также оптимальный по Парето. Множество оптимальных по Парето целевых векторов можно обозначить как P ( Z ).

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

Диапазон значений оптимальных по Парето решений в области допустимых значений дает полезную информацию об исследуемой задачу если целевые функции ограничены областью определения. Нижние границы оптимальной по Парето множества представлено в «идеальном целевом векторе». Его компоненты Z и полученные путем минимазации каждой целевой функции в пределах области определения.

Множество оптимальных по Парето решений также называют Парето-фронтом ( англ. Pareto-frontier ).

Лексикографический порядок

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

 

Отношение лексикографического порядка <lex между векторами  и  выполняется, если A Q < B Q, где. То есть, первые q компонент вектора   меньше компоненты вектора, а компоненты q + 1 - уровни (если есть). Лексикографический порядок для случая действительных чисел является линейным.

Вектор  является лексикографическим решением, если не существует вектора   такого, что  .

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

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

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

Скаляризация

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

Пусть F - функция скаляризации, что превращает векторную функцию  на скалярную. Если F сохраняет упорядоченность по Парето, то есть, если для произвольных   выполняется:

тогда решение, что минимизирует F на X является решением по Парето.

Если F сохраняет отношение порядка < в, то есть, если для произвольных   выполняется:

тогда решение, что минимизирует F на X является слабым по Парето. Если Fнепрерывнана, и  единственная точка минимума F на X, тогда  является решением по Парето.

Взвешенная сумма

Приведенная функция F 1 сохраняет упорядоченность по Парето для w > 0. Поэтому решения, минимизирующие F 1 на X для произвольных w > 0 являются оптимальными по Парето. Однако F 1 не сохраняет упорядоченность по Парето для  а сохраняет лишь отношение < и поэтому решения, минимизирующие F 1 наX для   являются слабыми по Парето.

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

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

 

Функция скаляризации Чебышева

Взвешенная функция скаляризации Чебышева сохраняет отношения < и поэтому минимум   является слабым по Парето.

 

Метод изменения ограничений (?-ограничения)

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

при условиях: 

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

 

Методы решения

Интерактивность

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

Эволюционные методы

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.Марковские процессы  принятия решений.

 

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

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

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

Как указывалось, марковские случайные процессы относятся к частным случаям случайных процессов (СП). В свою очередь, случайные процессы основаны на понятии случайной функции (СФ).

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

Такими примерами СФ являются: колебания напряжения в электрической цепи, скорость движения автомобиля на участке дороги с ограничением скорости, шероховатость поверхности детали на определенном участке и т.д.

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

Нетрудно заметить, что если обозначить состояние   и изобразить зависимость  , то такая зависимость и будет случайной функцией.

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

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

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

 (1)

Рис. 1. Схема процесса без последействия

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

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

Выше мы совершили незаметный терминологический переход от понятия СП к “марковской цепи”. Теперь эту неясность следует устранить. Отметим, во-первых, что случайный процесс с дискретными состояниями и временем называется случайной последовательностью.

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

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

Марковский СП называется однородным, если переходные вероятности   остаются постоянными в ходе процесса.

Цепь Маркова считается заданной, если заданы два условия.

1. Имеется совокупность переходных  вероятностей в виде матрицы:

. (2)

2. Имеется вектор начальных вероятностей

, ….. (3)

описывающий начальное состояние системы.

Матрица (2) называется переходной матрицей (матрицей перехода). Элементами матрицы являются вероятности перехода из i-го в j-е состояние за один шаг процесса. Переходная матрица (2) обладает следующими свойствами:

a)  , (3a)

б)  .

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

Рис. 2. Ориентированный взвешенный граф

Вершины графа обозначают состояние  , а дуги- переходные вероятности.