|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
СПОСОБЫ СКАЛЯРИЗАЦИИ ВЕКТОРНОГО КРИТЕРИЯСтр 1 из 2Следующая ⇒
Поиск решений в задачах ИО. Одна из основных задач ИО заключается в поиске таких решений, которые отвечают наилучшим (экстремальным) значениям выбранного критерия эффективности операции W.
Различают два аспекта управления: оптимизация, т.е. поиск решений, доставляющих максимум или минимум выбранному критерию, и ранжирование, т.е. упорядочение решений в порядке убывания или возрастания значений критерия. Задача ранжирования носит более частный характер, так как решается, обычно, на ограниченном множестве решений. Как уже говорилось ранее, критерий эффективностиможет бытьскалярным, т.е. характеризоваться одним единственным числом, или векторным, характеризующимся совокупностью чисел. Это зависит от характера решаемой задачи. Например, при управлении перехватчиком естественно в качестве критерия принять вероятность поражения цели. Если же перед нами стоит задача оценки проекта пассажирского лайнера, то необходимо учитывать совокупность многих его свойств: надежность, скорость, дальность, комфортабельность, рыночную конкурентоспособность и т.п. В соответствии с характером выбранного критерия принято различать однокритериальныеимногокритериальныезадачи принятия решений.
С учетом разнообразия задач управления, критерий эффективности W, в общем виде может быть записан следующим образом W = Ф ( U, S, C ), где: Ф – некоторый функционал, U - вектор управления. U= f(u1, u2,...un), i=1..n, S - вектор, характеризующий внешнюю среду, C - вектор, характеризующий процесс ( систему). Вектор С, в свою очередь, можно представить в виде: С = Ф(К, Р), где вектор К={ki} характеризует структуру нашей системы, а вектор P={pi} является вектором параметров (конкретных числовых характеристик системы). Данное выражение можно рассматривать как математическую модель управляемого процесса (системы). C помощью этой модели можно искать оптимальное управление, оптимальную структуру и оптимальные параметры при заданной структуре.
U0=arg max/min Ф (U, S, C) оптимизация управления. u K0= arg max/min Ф (U, S, C) оптимизацияструктуры. k P0= arg max/min Ф (U, S, C) параметрическая оптимизация. p
Не снижая общности, зафиксируем значения факторов, действующих в ходе операции, и опустим их обозначения при поиске оптимальных решений, т.е. примем W = W(x), где xÎ X значение вектора управления – решения, приятого оперирующей стороной.
В теории принятия решений широко употребителен термин « альтернатива ». Этим термином обозначается каждое из несовместных возможных решений, определяемое в нашем случае значением вектора управления xÎ X. Каждой альтернативе будет соответствовать точка в критериальном пространстве. Совокупность всех решений представляет собой полное множество альтернатив. Оно содержит как реализуемые, так и не реализуемые решения. Понятие альтернативы удобно тем, что оно обобщает все типы решений независимо от их содержания. В нашем случае альтернативами являются как решения по выбору управления, так и решения по выбору структуры или параметров управляемой системы. В рамках этой терминологии основная задача принятия решений может быть сформулирована как задача поиска оптимальных альтернатив.
В общем случае W есть векторный критерий - Wn={w1, w2...wn}. Его можно рассматривать как n-мерный вектор, или как точку в n- мерном пространстве, где w1, w2... wn ее координаты. Образованное таким образом пространство принято называть критериальным, размерность его равна числу показателей (их часто называют локальными критериями, в отличие от глобального векторного). Область всех возможных значений векторного критерия, независимо от их реализуемости, составляет, при двухсторонних ограничениях, гиперкуб, ребра которого отображают область возможных значений соответствующих показателей wi. Существенным недостатком векторного критерия является то, что мы не можем решать оптимизационные задачи на его основе традиционными регулярными методами, т.к. современный математический аппарат не располагает универсальным способом сопоставления векторов.
В случае скалярного критерия эффективности под наилучшим будем понимать решение, обеспечивающее максимальное значение показателя W. Тогда задача поиска наилучшего решения может быть записана следующим образом: При заданном комплексе условий проведении операции, найти такое решение x = x° (xÎ X), которое обращает показатель эффективности операции W в максимум, т.е.
W° (x°) = мах W(x) xÎ X (см. Рисунок)
В случае минимизации показателя W, обуславливаемом его физическим смыслом (например, расходы на создание системы), задача сводится к задаче максимизации изменением знака показателя W на противоположный. Если число возможных вариантов решения, образующих множество X невелико, то для поиска оптимального решения необходимо, для каждого из возможных значений xÎ X (решая прямую задачу) определить значение показателя W. Сравнив их между собой, можно указать одно или несколько решений, при которых W достигает максимума. Такой способ называется простым перебором. В случае, если множество возможных вариантов решения X велико, то поиск среди них оптимального простым перебором бывает весьма затруднителен, а подчас просто невозможен. С формальной точки зрения задача поиска оптимального решения относятся к задаче математического программирования, где в качестве целевой функции используется критерий эффективности W(x). Термин программирование от английского programming – составление плана или программы действий, здесь следует понимать в смысле “поиска наилучших планов - решений”, а не в смысле разработки программного обеспечения для ЭВМ.
мax U = U( W(x) ), либо решение (одно из решений) x = x° (xÎ X), отвечающее условию, что нельзя найти другое решение, позволяющее улучшить любой из показателей Wi (i=1, к) не ухудшая при этом значения других показателей Wx (x¹ i) (хотя бы одно из них). Такие решения называются эффективными или паретовскими (xпÎ Xп ).
Рассмотрим задачу поиска оптимальных (рациональных) решений в общем случае (множество решений может быть ограничено и не ограничено) более подробно.
Пусть W векторный критерий - Wn={w1, w2...wn}. Его можно рассматривать как точку в n- мерном пространстве, где w1, w2... wn ее координаты. Для решения задачи поиска оптимального решения как скалярной используют, как мы уже говорили, различные методы свертки вектора в скаляр. Рассмотрим некоторые из них. Критерий «взвешенной суммы» B этом случае обобщенный показатель U представляется в виде суммы показателей с весовыми коэффициентами ai, которые также называются коэффициентами важности. Они отражают ценность i-ого показателя (его важность для обобщенного показателя) по сравнению с остальными. Наиболее употребителен следующий вид свертки: n U =å ai ui i=1 Здесь ui - нормированное значение показателя wi, равное его отношению к размеру области возможных значений. Чем ближе значение ui к 1, тем выше качество, достигнутое по этому показателю. Нормировка вводится потому, что все слагаемые суммы должны иметь одинаковую размерность, иначе их нельзя было бы складывать. В рассмотренном случае в качестве скаляризованного критерия используется среднее взвешенное значение показателей. Для весовых коэффициентов так же вводится условие нормировки в виде: å ai=1. Значения весовых коэффициентов ai назначаются экспертами или ЛПР, либо непосредственно, либо с помощью специальных процедур, которые позволяют учесть противоречия между весами различных показателей. Процедура непосредственного назначения экспертами или ЛПР хороша тем, что она прозрачна и наилучшим образом отражает систему ценностей лица ее осуществляющего. Однако она возможна только, если размерность векторного критерия невелика. В противном случае она может оказаться трудно выполнимой.
В качестве специальной процедуры назначения весовых коэффициентов часто используют так называемой “метод парных сравнений” (МПС). В основу МПС положена квадратная матрица, строки и столбцы которой отвечают упорядоченным последовательностям показателей wi. Элементы матрицы аij показывают - на сколько (для аддитивный свертки) или во сколько раз (для мультипликативной свертки) i-й показатель важнее j – го и назначаются экспертами или ЛПР для каждой пары показателей. При аддитивной свертке сумма весовых коэффициентов в каждой паре должна быть равна 1: (aij + aji = 1). При мультипликативной свертке произведение весовых коэффициентов в парах равно 1: (aij * aji = 1). Обработка заполненной матрицы позволяет получить искомые нормированные коэффициенты важности ai. При непосредственном назначении всех элементов матрицы парных сравнений эксперты или ЛПР могут проявить непоследовательность суждений при сопоставлении отдельных пар, что приведет к несогласованности элементов матрицы и нарушению транзитивности соответствующих коэффициентов. В этом случае необходима коррекция сделанных назначений. Однако, матрицу можно задать лишь первой строкой, и из условий симметрии и нормировки формально определить ее целиком.. Тогда она будет внутренне согласованной, но зато будет хуже отображать точку зрения ЛПР или эксперта. Следует заметить, что часто в результате свертки теряется содержательный смысл полученного обобщенного критерия и найденные на его основе оптимальные решения нужно анализировать по достигнутому значению векторного критерия.
Кроме этого, поскольку выбор оптимального (рационального) решения есть прерогатива ЛПР и носит субъективный характер, поэтому выбор метода свертки и его параметров необходимо проводить, также, им непосредственно (или под его контролем).
ВЫБОР ГЛАВНОГО КРИТЕРИЯ Относится к методам, не использующим свертку векторного критерия в скалярный при поиске оптимального решения. Пусть (w1, w2,..., wn)- множество показателей. В соответствии с этим способом лицо, принимающее решения (ЛПР) выбирает самый важный показатель wi. При этом остальные показатели wj при " j¹ i переводятся в ограничения. Для задачи оптимизации можно записать: х 0=arg max wi (х), при ограничениях: wj (х0) ³ (£ ) cj при " j¹ i. Этот способ по существу равносилен отказу от векторного критерия и переходу к скалярному. При этом происходит большая потеря информации, т.к. значения всех критериев, кроме главного, учитываются только в ограничительном смысле.
МЕТОД ПОСЛЕДОВАТЕЛЬНЫХ УСТУПОК. В этом случае поиск решения по векторному критерию осуществляют, оптимизируя решения поочередно по каждой компоненте векторного критерия, в порядке их предпочтения. Для этого показатели wi ранжируются по важности (предпочтительности). Но их упорядочение носит чисто качественный характер, т.е. никаких количественных оценок их важностей не производится. Затем выбирается первый, самый важный, показатель и находится оптимальная по нему альтернатива. После этого назначается уступка, т.е. интервал, в котором могут варьироваться значения первого показателя. Другими словами, определяется - насколько первый показатель может отличаться от своего оптимального значения. Затем производится оптимизация по второму показателю. При этом оптимальное значение второго показателя ищется при допустимой уступке первого. Далее определяется уступка по второму показателю и т.д. В качестве оптимальной по векторному критерию принимается альтернатива, вычисленная в конце многоэтапной оптимизации. В этом методе скаляризация векторного критерия непосредственно не производится. Возможность использования регулярных методов оптимизации обеспечивается за счет процедуры последовательного применения скалярных показателей (компонент wi ) в качестве критериев оптимизации. От оптимизации по главному критерию этот способ принципиально отличается тем, что в процессе оптимизации участвуют все компоненты векторного критерия.
ПОИСК ОПТИМАЛЬНОГО РЕШЕНИЯ МЕТОД «ВЗВЕШЕННОЙ СУММЫ» B этом случае обобщенный показатель U представляется в виде суммы показателей с весовыми коэффициентами ai, которые отражают ценность i-ого показателя (его важность для обобщенного показателя) по сравнению с остальными. n U =å ai ui i=1 Весовые коэффициенты ai представляют в этом случае компоненты вектора градиента целевой функции. Поиск решения сводится к задаче оптимизации с целевой функцией, линейной относительно компонент векторного критерия Wn(w1, w2...wn), но не вектора Х. Наилучшим будет решение, расположенное максимально далеко в критериальном пространстве от начала координат в направлении градиента (см. рис.).
Следует заметить, что при использовании методов, связанных с сопоставлением различных альтернатив по какой-либо компоненте векторного критерия понятие лучше (больше), в общем случае, не является монотонной функцией своего аргумента (напр. Температура воды для плавания в бассейне).
Основные достоинства и недостатки различных методов скаляризации векторного критерия. Критерий среднего взвешенного. Достоинства 1. Простота формализации 2. Ясный физический смысл 3. Учет индивидуальных представлений ЛПР о задаче при назначении весовых коэффициентов (важностей) 4. Наличие простой формальной процедуры (метод парных сравнений), облегчающей процесс назначения весовых коэффициентов Недостатки: 1. Неявная взаимная компенсация показателей, которая становится неконтролируемой при большом их числе. Не учет нелинейной зависимости весовых коэффициентов от значений показателей: важности вводятся один раз и остаются постоянными величинами. Метод идеальной точки. Достоинства: 1. Компоненты векторного критерия рассматриваются в совокупности (без применения сверток) 2. Четкая формальная постановка Недостатки: 1. Неявная взаимная компенсация показателей, которая становится неконтролируемой при большом их числе. 2. Произвольный выбор метрики 3. Непредставимость, в содержательном смысле, расстояния между двумя точками в n-мерном пространстве (при n> 3). Метод последовательных уступок. Достоинства: 1. Содержательная простота 2. Учет всех компонент векторного критерия Недостатки: 1. Необходимость предварительного ранжирования показателей по важности 2 Трудность определения величин уступок 3. Практическая не реализуемость при большом числе показателей Оптимальность по Парето. Достоинства: 1. Метод математически строг и понятен пользователю. 2. Выделяет множество допустимых решений., 3. Дает возможность ЛПР сосредоточить анализ решений на более узком множестве и выбрать субъективно оптимальное решение. Недостатки: 1. Применимость метода ограничена мощностью Парето-оптимального множества (для непосредственного выбора решения количество его элементов не должно превышать 7-10). Если у недоминируемого множества большая мощность, то метод трудно выполним без привлечения одного из рассмотренных выше способов. Свертка по полезности, свертка по предпочтениям.Хотя оба метода можно рассматривать как способ скаляризации векторного критерия, по существу это способы выявления неформальной информации, которой обладает ЛПР. Информации основанной на знаниях, опыте, интуиции и сложившейся на этой основе системе ценностей ЛПР. Внешне они просты для пользователя, однако это далеко не так. Выявление и формализация системы ценностей ЛПР, выражаемой в виде предпочтений или полезностей требует организации достаточно сложных процедур. Одна из таких процедур будет рассмотрена ниже на примере СППР DSS/UTES. (см. лекции по ИО Бомас В.В.).
Поиск решений в задачах ИО. Одна из основных задач ИО заключается в поиске таких решений, которые отвечают наилучшим (экстремальным) значениям выбранного критерия эффективности операции W.
Различают два аспекта управления: оптимизация, т.е. поиск решений, доставляющих максимум или минимум выбранному критерию, и ранжирование, т.е. упорядочение решений в порядке убывания или возрастания значений критерия. Задача ранжирования носит более частный характер, так как решается, обычно, на ограниченном множестве решений. Как уже говорилось ранее, критерий эффективностиможет бытьскалярным, т.е. характеризоваться одним единственным числом, или векторным, характеризующимся совокупностью чисел. Это зависит от характера решаемой задачи. Например, при управлении перехватчиком естественно в качестве критерия принять вероятность поражения цели. Если же перед нами стоит задача оценки проекта пассажирского лайнера, то необходимо учитывать совокупность многих его свойств: надежность, скорость, дальность, комфортабельность, рыночную конкурентоспособность и т.п. В соответствии с характером выбранного критерия принято различать однокритериальныеимногокритериальныезадачи принятия решений.
С учетом разнообразия задач управления, критерий эффективности W, в общем виде может быть записан следующим образом W = Ф ( U, S, C ), где: Ф – некоторый функционал, U - вектор управления. U= f(u1, u2,...un), i=1..n, S - вектор, характеризующий внешнюю среду, C - вектор, характеризующий процесс ( систему). Вектор С, в свою очередь, можно представить в виде: С = Ф(К, Р), где вектор К={ki} характеризует структуру нашей системы, а вектор P={pi} является вектором параметров (конкретных числовых характеристик системы). Данное выражение можно рассматривать как математическую модель управляемого процесса (системы). C помощью этой модели можно искать оптимальное управление, оптимальную структуру и оптимальные параметры при заданной структуре.
U0=arg max/min Ф (U, S, C) оптимизация управления. u K0= arg max/min Ф (U, S, C) оптимизацияструктуры. k P0= arg max/min Ф (U, S, C) параметрическая оптимизация. p
Не снижая общности, зафиксируем значения факторов, действующих в ходе операции, и опустим их обозначения при поиске оптимальных решений, т.е. примем W = W(x), где xÎ X значение вектора управления – решения, приятого оперирующей стороной.
В теории принятия решений широко употребителен термин « альтернатива ». Этим термином обозначается каждое из несовместных возможных решений, определяемое в нашем случае значением вектора управления xÎ X. Каждой альтернативе будет соответствовать точка в критериальном пространстве. Совокупность всех решений представляет собой полное множество альтернатив. Оно содержит как реализуемые, так и не реализуемые решения. Понятие альтернативы удобно тем, что оно обобщает все типы решений независимо от их содержания. В нашем случае альтернативами являются как решения по выбору управления, так и решения по выбору структуры или параметров управляемой системы. В рамках этой терминологии основная задача принятия решений может быть сформулирована как задача поиска оптимальных альтернатив.
В общем случае W есть векторный критерий - Wn={w1, w2...wn}. Его можно рассматривать как n-мерный вектор, или как точку в n- мерном пространстве, где w1, w2... wn ее координаты. Образованное таким образом пространство принято называть критериальным, размерность его равна числу показателей (их часто называют локальными критериями, в отличие от глобального векторного). Область всех возможных значений векторного критерия, независимо от их реализуемости, составляет, при двухсторонних ограничениях, гиперкуб, ребра которого отображают область возможных значений соответствующих показателей wi. Существенным недостатком векторного критерия является то, что мы не можем решать оптимизационные задачи на его основе традиционными регулярными методами, т.к. современный математический аппарат не располагает универсальным способом сопоставления векторов.
В случае скалярного критерия эффективности под наилучшим будем понимать решение, обеспечивающее максимальное значение показателя W. Тогда задача поиска наилучшего решения может быть записана следующим образом: При заданном комплексе условий проведении операции, найти такое решение x = x° (xÎ X), которое обращает показатель эффективности операции W в максимум, т.е.
W° (x°) = мах W(x) xÎ X (см. Рисунок)
В случае минимизации показателя W, обуславливаемом его физическим смыслом (например, расходы на создание системы), задача сводится к задаче максимизации изменением знака показателя W на противоположный. Если число возможных вариантов решения, образующих множество X невелико, то для поиска оптимального решения необходимо, для каждого из возможных значений xÎ X (решая прямую задачу) определить значение показателя W. Сравнив их между собой, можно указать одно или несколько решений, при которых W достигает максимума. Такой способ называется простым перебором. В случае, если множество возможных вариантов решения X велико, то поиск среди них оптимального простым перебором бывает весьма затруднителен, а подчас просто невозможен. С формальной точки зрения задача поиска оптимального решения относятся к задаче математического программирования, где в качестве целевой функции используется критерий эффективности W(x). Термин программирование от английского programming – составление плана или программы действий, здесь следует понимать в смысле “поиска наилучших планов - решений”, а не в смысле разработки программного обеспечения для ЭВМ.
мax U = U( W(x) ), либо решение (одно из решений) x = x° (xÎ X), отвечающее условию, что нельзя найти другое решение, позволяющее улучшить любой из показателей Wi (i=1, к) не ухудшая при этом значения других показателей Wx (x¹ i) (хотя бы одно из них). Такие решения называются эффективными или паретовскими (xпÎ Xп ).
Рассмотрим задачу поиска оптимальных (рациональных) решений в общем случае (множество решений может быть ограничено и не ограничено) более подробно.
Пусть W векторный критерий - Wn={w1, w2...wn}. Его можно рассматривать как точку в n- мерном пространстве, где w1, w2... wn ее координаты. Для решения задачи поиска оптимального решения как скалярной используют, как мы уже говорили, различные методы свертки вектора в скаляр. Рассмотрим некоторые из них. СПОСОБЫ СКАЛЯРИЗАЦИИ ВЕКТОРНОГО КРИТЕРИЯ Существуют два подхода к скаляризации векторного критерия - формализованная и неформализованная свертка. В первом случае (формализованная свертка) для получения обобщенного показателя (обозначим его как U ) используется некоторое формальное выражение, позволяющее по заданному значению вектора Wn={w1, w2...wn} вычислить соответствующее ему значение обобщенного показателя U=F (Wn)= F (w1, w2...wn), где F некоторая заданная функция. Во втором случае (неформализованная свертка) различным значениям вектора Wn={w1, w2...wn} ставится в соответствиезначение обобщенного показателя без использования функциональных (формализованных) зависимостей. U=Y(Wn) = Y(w1, w2...wn). В дальнейшем, не снижая общности, будем обозначать сверткувекторного критерия в скаляр как U=U(Wn)=U(w1, w2...wn).
На практике наиболее употребительны два метода свертки показателей: аддитивная и мультипликативная. В аддитивной свертке обобщенный показатель эффективности представляется в виде взвешенной суммы показателей. В мультипликативной свертке обобщенный критерий представляю в форме некоторого произведения (отношения) показателей. Рассмотрим эти способы свертки более подробно.
Критерий «взвешенной суммы» B этом случае обобщенный показатель U представляется в виде суммы показателей с весовыми коэффициентами ai, которые также называются коэффициентами важности. Они отражают ценность i-ого показателя (его важность для обобщенного показателя) по сравнению с остальными. Наиболее употребителен следующий вид свертки: n U =å ai ui i=1 Здесь ui - нормированное значение показателя wi, равное его отношению к размеру области возможных значений. Чем ближе значение ui к 1, тем выше качество, достигнутое по этому показателю. Нормировка вводится потому, что все слагаемые суммы должны иметь одинаковую размерность, иначе их нельзя было бы складывать. В рассмотренном случае в качестве скаляризованного критерия используется среднее взвешенное значение показателей. Для весовых коэффициентов так же вводится условие нормировки в виде: å ai=1. Значения весовых коэффициентов ai назначаются экспертами или ЛПР, либо непосредственно, либо с помощью специальных процедур, которые позволяют учесть противоречия между весами различных показателей. Процедура непосредственного назначения экспертами или ЛПР хороша тем, что она прозрачна и наилучшим образом отражает систему ценностей лица ее осуществляющего. Однако она возможна только, если размерность векторного критерия невелика. В противном случае она может оказаться трудно выполнимой.
В качестве специальной процедуры назначения весовых коэффициентов часто используют так называемой “метод парных сравнений” (МПС). В основу МПС положена квадратная матрица, строки и столбцы которой отвечают упорядоченным последовательностям показателей wi. Элементы матрицы аij показывают - на сколько (для аддитивный свертки) или во сколько раз (для мультипликативной свертки) i-й показатель важнее j – го и назначаются экспертами или ЛПР для каждой пары показателей. При аддитивной свертке сумма весовых коэффициентов в каждой паре должна быть равна 1: (aij + aji = 1). При мультипликативной свертке произведение весовых коэффициентов в парах равно 1: (aij * aji = 1). Обработка заполненной матрицы позволяет получить искомые нормированные коэффициенты важности ai. При непосредственном назначении всех элементов матрицы парных сравнений эксперты или ЛПР могут проявить непоследовательность суждений при сопоставлении отдельных пар, что приведет к несогласованности элементов матрицы и нарушению транзитивности соответствующих коэффициентов. В этом случае необходима коррекция сделанных назначений. Однако, матрицу можно задать лишь первой строкой, и из условий симметрии и нормировки формально определить ее целиком.. Тогда она будет внутренне согласованной, но зато будет хуже отображать точку зрения ЛПР или эксперта. Популярное:
|
Последнее изменение этой страницы: 2016-03-25; Просмотров: 1951; Нарушение авторского права страницы
В случае векторного критерия эффективности под наилучшим (иногда говорят рациональным) обычно понимается решение x = x° (xÎ X), обеспечивающее максимальное (минимальное) значение некоторого обобщенного показателя U, который представляет собой результат формализованной (неформализованной) свертки векторного критерия в скалярный 