Раздел 2. Методы решения задачи многокритериальной оптимизации. Методы многокритериальной оптимизации


10.2. Методы многокритериальной оптимизации

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

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

  1. основаны на том, что ЛПР может выразить свои предпочтения до начала процесса многокритериальной оптимизации;

  2. интерактивные (диалоговые) методы;

  3. методы построения множества эффективных решений с последующим представлением его ЛПР.

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

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

10.2.1. Методы первой группы

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

10.2.1.1.Функция полезности

В XIX веке экономисты высказали предположение о существовании у каждого индивидуума определённого количественного измерителя счастья или полезности –“пользометра”. Единицы измерения этого прибора назвали“утилями”(от английскогоutility – полезность ). Согласно этой модели потребительского поведения каждый потребитель выбирает так товары и услуги, чтобы максимизировать свою полезность в пределах средств, которыми он располагает. Эта идея перенесена на многокритериальные задачи и интенсивно разрабатывается в теории полезности, ставшей самостоятельным направлением прикладной математики.

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

Приведём строгое определение этого понятия. Функция U,которая каждой точкеY критериального пространства ставит в соответствие действительное числоU(Y),называется функцией полезности (ценности) ЛПР, если

Y~Y"U(Y')=U(Y"),

Y'Y"U(Y')>U(Y").

Таким образом, функция полезности представляет собой математическую модель предпочтений ЛПР. Если функция полезности известна, то многокритериальная задача сводится к стандартной задаче оптимизации: найти вектор XD, максимизирующийU[Y(X)]. Множество точек критериального пространства, одинаковых по предпочтительности (для которыхU(Y)=Const), образует гиперповерхность равного уровня функции полезности. Гиперповерхности равного уровняU(Y) называются кривыми безразличия, а семейство всех кривых безразличия – картой безразличия. Такая терминология связана с тем, что для любых двух альтернативY' иY", лежащих на одной кривой безразличия, U(Y')=U(Y"), т.е. ЛПР всё равно, достигнет он Y' илиY". Пример карты безразличия некоторой функции полезности и нахождение по ней оптимального решения показаны на рис. 10.4.

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

Ч

G

тобы построитьU(Y), прежде всего необходимо установить её вид, который определяется структурой предпочтения ЛПР. Выявление структуры предпочтений – самый ответственный этап построения функции полезности. Следует однако заметить, что если функцияU однозначно определяет всю структуру предпочтений, то обратное неверно. Это значит, что одна и та же структура может быть представлена разными функциями полезности, которые являются стратегически эквивалентными. Функции полезностиU1(Y) иU2(Y) стратегически эквивалентны, если они приводят к одинаковому упорядочению по предпочтению. Так любыеU1 и U2, связанные какой-либо монотонно возрастающей функциейТ(),являются эквивалентными. Действительно, максимизацияU1(Y) иU2(Y)=T[U1(Y)] приведет к одному результату, т.е. обе функции одинаково отражают структуру предпочтений ЛПР.

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

U(y1,y2,...,ym)=F[U1(y1),U2(y2),...,Um(ym)], (10.7)

т.е. многомерная функция определяется через одномерные функции полезности значений одного отдельно взятого критерия. Типичные примеры таких функций для m=2:

U(Y)=C1y1+ С2у2, С1>0, С2>0,

, >0,>0.

Формализация структуры предпочтений основана на исследовании возможности взаимной компенсации значений различных критериев. Это проблема замещения по полезности. Возможные замещения на наборе критериев может дать только ЛПР, а выявить их у ЛПР и формально описать - задача аналитика. Далее будем предполагать, что критерии независимы по предпочтению (см. раздел 10.1.3), и рассмотрим простейшие случаи построенияU(Y) для m=2.

Предельный коэффициент замещения критерия y1 на критерийу2в точке (,

) равен, если ЛПР согласен уступитьединиц критерияy1 заединиц критерияу2, где- достаточно малая величина (строго говоря, при0). В общем случае предельные коэффициенты замещения зависят от значенийy1 иу2.Возвращаясь к рис.10.4 нетрудно понять, что предельный коэффициент есть тангенс угла наклона касательной к кривой безразличия в точке (,), взятый с обратным знаком. Отсюда ясно, что определение коэффициентов замещения дает представление о карте безразличия, а следовательно, и о виде функции полезности.

Если коэффициент замещения не зависит от значений y1 иу2, то это означает, что кривые безразличия – прямые, имеющие вид

y1+

y2=Const,

а предпочтения ЛПР могут быть представлены функцией

U(Y)=y1+ y2. (10.8)

Если предельный коэффициент замещения зависит от значения у2, но не зависит отy1, то подходящей составной функцией полезности может быть

U(Y)=y1+ U2(y2). (10.9)

Возможный путь полученияU2(y2) состоит в следующем. Примем произвольноU2()=0, что дает точку отсчета значенийU2. Тогда U2() есть сумма в единицахy1, которую ЛПР согласен "заплатить" за переход отк. Выявив у ЛПР эти суммы для ряда значений у2, получим график функцииU2(y2) как, например, на рис.10.5.

Карта безразличия, соответствующая структуре предпочтений (10.9), имеет вид семейства кривых, которые получаются простым сдвигом по горизонтали (по осиу1) одной из них. Аналогичный подход применяется и в случае, когда

зависит отy1, но не зависит оту2.

Из ситуаций, когда коэффициент замещения зависит от значений обоих критериев, рассмотрим самую простую: структура предпочтений ЛПР аддитивна. Обратимся к рис 10.6. Если вместо знака вопроса (?) ЛПР поставитd, т.е. он согласен заплатить d единицу1за увеличениеу2на с в точкеD и это остается в силе при любых значениях а, b, с и d и в любых точках А, В, С иD, образующих прямоугольник, то имеет место условие соответственных замещений.

Доказано, что структура предпочтений аддитивна и, следовательно, описывается функцией полезности вида

U(Y)=U1(y1)+ U2(y2) (10.10)

тогда и только тогда, когда выполняется условие соответственных замещений.

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

), где<и <, если для любого исходного значения критерияу2ЛПР согласен "заплатить" одно и то же количество единицу2за увеличениеy1 как отдо, так и отдо . Средней по полезности точкойинтервала[] значений критерияyi называется точка, которая образует эквивалентные по разности полезности пары [] и[]. Заметим, что из условия соответственных замещений следует независимость значения средней точки для данного интервалаy1 от значений критерияу2, хотя "плата" за изменениеуi(в единицах у2) будет зависеть от уровняу2.

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

U(y1,y2)=1U1(y1)+2U2(y2), (10.11)

где

Ui()=0, Ui()=1, (10.12)

>0, 2>0 и 1+2=1. (10.13)

В процедуре отыскания Uв виде (10.11), приводимой ниже, одинаковость пар и значения средних точек определяет ЛПР в диалоге с аналитиком.

I.СтроимU1 в следующей последовательности:

-находим среднюю по полезности точку уинтервала []и полагаемU1(y)=0,5;

-находим среднюю по полезности точку уинтервала [у,] и полагаемU1(y)=0.75;

-находим среднюю по полезности точку уинтервала[] и принимаемU1(y)=0,25;

-проверяем согласованность результатов: является ли усредней по полезности точкой интервала [у]? Если нет, то придется корректировать эти точки до достижения согласованности .

-по пяти определенным точкам (или большему числу, если продолжить дробление интервалов) строится график функции U1(y1).

2. Таким же образом находим U2(у2).

3. Определяем коэффициенты шкалирования и2. Для этого выбираем любые две одинаковые по предпочтительности пары (y1,y2). Пусть, например, это пары() и (). Тогда

U()=U()

или

. (10.14)

Значения U1 и U2 в точкахиопределяются по построенным графикам. Добавив к (10.14) равенство (10.13), находим значения и.

Соответствие полученной функции полезности структуре предпочтений ЛПР можно дополнительно проверить, предложив ему несколько пар значений критериев (отличных оти) с одним значениемU. Если ЛПР сочтет их примерно одинаковыми по предпочтительности, то построенная функция приемлема. В противном случае следует повторить 3-й этап процедуры с тем, чтобы уточнить значения и(их можно получить более надежно усреднением по нескольким парам с равной предпочтительностью).

С увеличением размерности критериального пространства трудоемкость построения функции полезности даже в аддитивном виде резко возрастает. А при более сложной структуре предпочтений ЛПР отыскание адекватнойU(Y) становится весьма проблематичным.

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

studfiles.net

Методы многокритериальной оптимизации — КиберПедия

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

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

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

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

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

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

4. Задачи оптимизации на множестве этапов функционирования – рассматривается функционирование объекта на некотором интервале времени, разбитом на несколько этапов; качество управления на каждом этапе оценивается частным критерием, а на множестве этапов – общим векторным критерием.

В задачах 2, 3, 4-го типа частные критерии имеют обычно единую размерность.

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

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

для критериев, которые стремятся увеличивать, и

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

Таким образом, после нормировки вместо матрицы , в который элементы столбцов имели различную размерность, получается матрица , размерность элементов которой от 0 до 1: .

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

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

критерий справедливости абсолютной уступки

;

критерий справедливой относительной уступки

,

где – нормированное значение p-го критерия оптимальности ; λp – коэффициент важности свертки p-го критерия.

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

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

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

Укрупненный алгоритм модифицированной процедуры следующий.

1.Ввод исходной информации для расчета значений критериев и ограничений математической модели.

2. Присвоение начальных значений коэффициентам важности для свертки критериев оптимальности в единую целевую функцию вида (max и min в зависимости от смысла решаемой задачи). При этом должно выполняться условие . Для первой итерации допустимо задавать равные значения коэффициентов .

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

. (3.9)

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

Например, при наличии трех критериев оптимальности возможно формирование трех вариантов ( ), близких к базовому по критериям

,

если предполагается увеличение на величину е первого критерия;

 

 

,

если увеличивается второй критерий, и

 

при увеличении третьего критерия.

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

6. Анализ базового или близких к нему вариантов решения ЛПР и ввод парных предпочтений для каждого из вариантов решений по отношению к базовому («+» – вариант более предпочтителен, чем базовое решения; «-» – вариант менее предпочтителен, чем базовое решение).

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

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

. (3.10)

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

а) для каждого k-го варианта, который признан ЛПР более предпочтительным, чем базовый,

, (3.11)

где ξ – некое достаточно малое число, например, ξ =0,001; – значение p-го критерия для k- го и базового вариантов соответственно;

б) для каждого k-го варианта, который признан ЛПР менее предпочтительным, чем базовый, записываются ограничения вида

; (3.12)

В) получивший набор значений должен соответствовать условию

. (3.13)

10. Получение новых значений коэффициентов свертки критериев ( ) при решении математической модели (3.10) – (3.13) с помощью симплекс-метода и переход к блоку 3.

При минимизации единой целевой функции (3.9) ограничения (3.11) и (3.12) меняются местами.

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

 

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

2. Раскройте основные положения и содержание этапов исследования при помощи численных методов в процессе поиска оптимальных решений для однокритериальных моделей.

3. Раскройте основные положения и содержание этапов экспериментальной оптимизации на ЭВМ при поиске оптимальных решений для однокритериальных моделей.

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

5. В чем заключается суть сведения стохастической задачи к детерминированной?

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

7. Опишите основные методы и подходы при реализации процедур принятия решений при наличии в модели неопределенных факторов

8. Что такое платежная матрица? Опишите ее структуру и назначение.

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

10. Что такое многокритериальная оптимизация? Приведите классификацию типов задач многокритериальной оптимизации. Опишите основную суть методов многокритериальной оптимизации.

Глава 4. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ СИСТЕМ

4.1. Особенности и принципы построения имитационныхмоделей

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

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

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

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

Имитационные модели как подкласс математических моделей можно классифицировать на: статические и динамические; детерминированные и стохастические; дискретные и непрерывные.

Класс задачи предъявляет определенные требования к имитационной модели. Так, например, при статической имитации расчет повторяется несколько раз в различных условиях проведения эксперимента – исследование поведения «в определенный короткий период времени». При динамической имитации моделируется поведение системы «в течение продолжительного периода времени» без изменений условий. При стохастической имитации в модель включаются случайные величины с известными законами распределения; при детерминированной имитации эти возмущения отсутствуют, т.е. их влияние не учитывается.

Порядок построения имитационной модели и ее исследования в целом соответствует схеме построения и исследования аналитических моделей. Однако специфика имитационного моделирования приводит к ряду специфических особенностей выполнения тех или иных этапов. В литературе приводится следующий перечень основных этапов имитации:

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

2. Формулирование модели – переход от реальной системы к некоторой логической схеме (абстрагирование).

3. Подготовка данных – отбор данных, необходимых для построение модели и представления их в соответствующей форме.

4. Трансляция модели – описание модели на языке, применяемом для используемой ЭВМ.

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

6. Стратегическое планирование – планирование эксперимента, который должен дать необходимую информацию.

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

8. Экспериментирование – процесс осуществления имитации с целью получения желаемых данных и анализа чувствительности.

9. Интерпретация – построение выводов по данным, полученным путем имитации.

10. Реализация – практическое использование модели и (или) результатов моделировании.

11. Документирование – регистрация хода осуществление проекта и его результатов, а также документирование процесса создания и использования модели

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

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

 

cyberpedia.su

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

      1. Метод "обобщенного критерия".

        1. Основные виды сверток.

Определение.

Сверткой критериев называется преобразование векторного критерияв скалярный:

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

(11.2.0 )

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

Предварительно необходимо все критерии привести к сопоставимому безразмерному виду, то есть произвести их нормализацию. О наиболее распространенных способах нормализации было сказано в главе 1.

Итак, как и выше, исходная задача ( 11.1 .0 ) заменяется задачей ( 11.2 .0 ), поэтому возникает справедливый вопрос: как соотносятся решения этих задач ?

У постановщика задачи здесь могут быть два принципиально различных подхода:

  1. переход от постановки ( 11.1 .0 ) к ( 11.2 .0 ) производится путем тщательного анализа, в результате которого постановка ( 11.2 .0 ) полностью заменяет исходную постановку, получением решения задачи ( 11.2 .0 ) завершается работа;

  2. признается, что постановка ( 11.2 .0 ) не полностью заменяет постановку ( 11.1 .0 ), поэтому решение задачи ( 11.2 .0 ) анализируется в первую очередь на эффективность.

Для этой цели применяется критерий эффективности, о наиболее употребляемом критерии упоминается в разделе 11.2.2.1

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

Наиболее распространенными свертками являются :

1)

при имеем наиболее употребительную из всех линейную свертку:

2)

3)

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

        1. Линейная свертка и ее свойства.

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

В выпуклой задаче ( 11.1 .0 ) оптимальна по Парето, если существует вектор,

такой, что

(11.2.0 )

и обратно, если оптимальная по Парето, то найдется вектор, удовлетворяющий ( 11.2 .0 ).

Конструктивность этой теоремы можно рассматривать с двух позиций:

  1. найти , решив задачу однокритериальной оптимизации:

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

Замечание.

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

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

Поучительным будет рассмотрение с этих позиций нашего примера ( 11.1 .0 ) :

Применим свертку: .

Решим задачу однокритериальной оптимизации:

Здесь удается применить классический метод, приводящий к простой системе уравнений:

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

Решением будет , откуда видим, что взяв любое, получаем.

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

Эффективным решением будет :

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

Эффективным решением будет :

Получили , как и следовало бы ожидать, существенно ближе к точке минимума, чем, во втором случае наоборот:существенно ближе к точке минимума, чем.

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

studfiles.net

Раздел 2. Методы решения задачи многокритериальной оптимизации

Чтобы получить более полную характеристику достоинств и недостатков проектируемого объекта, нужно ввести больше критериев качества в рассмотрение. Как результат, задачи проектирования сложных систем всегда многокритериальные, так как при выборе наилучшего варианта приходится учитывать много различных требований, предъявленных к системе [28].

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

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

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

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

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

Ниже, рассмотрим подробно этих методов решения задачи многокритериальной оптимизации [33,46,48,51].

2.1. Метод последовательных уступок

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

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

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

Существенным недостатком метода последовательных уступок является то, что решение, полученное этим методом, может оказаться неоптимальным по Парето [37].

Рассмотрим пример, математическая модель трехкритериальной задачи имеет вид [51]:

Уступка по первому критерию , а по второму.

Решение:

Открываем электронную книгу Excel и, как и для решения однокритериальной задачи определяем ячейки под переменные . Для этого в ячейку А2 вводим подпись «Переменные», а соседние три ячейки В2, С2 и D2 вводим значения переменных. Это могут быть произвольные числа, например единицы или нули, далее они будут оптимизироваться.

рис. 2.1. Определение переменных значений

В третьей строке задаем целевые функции. В А3 вводим подпись «Целевые», а в В3 формулой «=2*B2+C2-3*D2» задаем первую целевую функцию . Аналогично в С3 и D3 вводим вторуюи третьюцелевую функцию, вводя в С3 «=B2+3*C2-2*D2», а в D3 «=-B2+2*C2+4*D2».

рис.2.2. Определение целевых значений

Ячейка А5 будем называть «Ограничения».

Левые части ограничений распишем от B5:D7, правые части записываем в диапазонF5:F7. Вводим в Е5 формулу «=B5*$B$2+C5*$C$2+D5*$D$2», номера столбцов и номера строк ряда переменных зафиксировано, далее воспользуемся автозаполнением, чтобы заполнить ячейки Е6 и Е7.

рис.2.3. Определение ограничений

Предварительные действия завершены. Вызываем надстройку «Поиск решения» в меню «Данные».

На первом этапе оптимизируем первую целевую функцию. После открытия окна «Поиск решения» в поле «Оптимизировать целевую функцию» ставим курсор и делаем ссылку на ячейку «В3», щелкая по ней мышью. В окне появится $B$3. В связи с тем, что целевая функция максимизируется, далее нужно проверить, что флажок ниже поля стоит напротив надписи «Максимум».

После ставим курсор в поле «Изменяя ячейки переменных» и обводим ячейки с переменными В2, С2 и D2, выделяя ячейки с переменными. В поле появиться $B$2:$D$2.

В нижней части окна находится поле «Ограничения». Для того, чтобы ввести ограничения, нажимаем кнопку «Добавить», откроется окно «Добавление ограничения». В левом поле «Ссылка на ячейки» вводят ссылку на левую часть первого ограничения – ячейку «Е5», в центральном окне определяем знак«»и в правом «Ограничения» выбираем соответствующую правую часть первого ограничения –«F5». Нажимаем «ОК», видим, что ограничение появилось в окне. Нажимаем вновь «Добавить», вводим «E6» «» и «F6». Вновь нажимаем «Добавить», вводим «E7» «≤» и «F7».

Для ввода дополнительных ограничений вновь нажимаем «Добавить», ставим курсор в левое поле и обводим ячейки В2, С2 и D2 (результат $B$2:$D$2) в среднем окне ставим «» и в правом число 0.

рис. 2.4. Параметры поиска решения

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

Выбираем «Сохранить найденное решение» и «ОК» видим результат. В ячейках В2, С2 и D2 видны значения переменных соответствующие оптимальному решению: 11,2; 6,4 и 0. В ячейки В3 – значение целевой функции 28,8.

рис.2.5. Результат полученного решения

На втором этапе оптимизируется вторая целевая функция. Однако, первую, в соответствие с методом последовательных уступок, можно ухудшить первый критерий на величину не более, чем . По этой причине, на втором шаге, значения в ячейке В3 (где хранится первая целевая функция, которая максимизируется) может быть значение, не меньшее, чем 24,8 (=28,8-4). Для удобства, можно записать «Уступок» в сторонке.

Вызываем надстройку «Поиск решения», видно, что все прежние данные остались введенными. Меняем ссылку на целевую функцию. Ставим курсор в поле «Оптимизировать целевую функцию» и щелкаем по ячейке С3, в которой находится ссылка на вторую целевую функцию. Так, как вторая целевая минимизируется, то ставим флажок в поле напротив надписи «Минимум». Вводим дополнительное ограничение, связанное с уступкой по первому критерию. Переводим курсор в поле «Ограничения» и нажимаем кнопку «Добавить», правее поля. В появившемся окне «Добавление ограничения» в трех окнах (слева на право) вводим данные «В3», «≥», «С9».

Результат – переменные равны 10,2; 4,4; 0. Вторая целевая функция равна 23,4 (ячейка С3). Первая равна своему минимальному значению 24,8 (ячейка В3).

рис.2.6. Определение уступка

На третьем этапе делаем уступку по второму критерию. Величина уступки равна . Так, как вторая функция минимизируется, то ее значение не должно превышать 23,4+5=28,4. Вызываем надстройку «Поиск решения». Меняем ссылку на целевую функцию. Ставим курсор в поле «Оптимизировать целевую функцию» и щелкаем по ячейке D3, в которой находится ссылка на третью целевую функцию. Так, как третья целевая максимизируется, то ставим флажок в поле напротив надписи «Максимум». Вводим дополнительное ограничение, связанное с уступкой по второму критерию. Переводим курсор в поле «Ограничения» и нажимаем кнопку «Добавить». В появившемся окне «Добавление ограничения», вводим данные «С3», «≤», «С10».

Результат – переменные равны 10,76; 6,62; 1,11. Целевые функции равны, соответственно, 24,8; 28,4 и 6,93. Это окончательный ответ. Все дополнительные условия соблюдены.

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

studfiles.net

4. Методы многокритериальной оптимизации

Рассматривается задача X— множество сравниваемых альтернатив (объектов),R— бинарное отношение на множествеX. Пусть задано множество, состоящее изQкритериев, имеющих шкалы оценки альтернатив;n— номер оценки по шкалеq-го критерия— множество оценокq-го критерия, расположенных в порядке возрастания их качества (шкалаq-го критерия):. — множество векторных оценок; качество каждого объектаоценивается вектором ,,.

Каждому критерию ставится в соответствие число wq, (удельный вес) характеризующее важность критерия. Веса критериев определяются с помощью ЛПР или экспертов.

Системы предпочтений на множестве альтернатив , заданные с помощью векторного отображенияF:Y→EQможет быть представлены на языке бинарных отношений,, либо отношением Слейтера, либо отношением Парето:

, , (4.1)

, , (4.2)

где — отношение Слейтера,— отношение Парето.

Цель многокритериальной задачи оптимизации— построение ядра (подмножества максимальных, доминируемых элементов):

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

4.1. Аксиоматическая теория полезности

Целью многокритериальной теории полезности отразить предпочтения ЛПР в числовом виде при выборе из некоторого множества элементов. Выбор вариантов в условиях определенности на основе теории полезности состоит в построении некоторого функционала U(x), определенного на множестве оценок альтернатив. Такой функционал позволяет формально свести многокритериальную задачу к однокритериальной. Будем называть функционалU(x)функцией полезности.

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

1. Аксиома связности, когда для ,илиили.

2. Аксиома транзитивности, когда для таких, чтои.

3. Для соотношений между полезностями альтернатив , имеющими вид:

где U(x) — функция полезности альтернативы, можно найти такие числа,, что:

4. Аксиома рефлексивности: для которыхи.

5. Аксиома эквивалентности: , тогда на подмножестве эквивалентных элементов отношение симметрично.

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

Для построения функции полезности предполагаются условия независимости альтернатив:

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

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

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

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

либо мультипликативной:

где ,— функции полезности, изменяющиеся от 0 до 1;— веса критериев,; коэффициентk> – 1.

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

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

studfiles.net

Многокритериальная оптимизация - это... Что такое Многокритериальная оптимизация?

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

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

Определение

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

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

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

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

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

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

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

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

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

где ,  — единичный вектор.

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

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

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

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

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

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

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

Отношение лексикографического порядка между векторами и выполняется, если , где . То есть, первая компонента вектора меньше компоненты вектора , а компоненты  — уровни (если есть). Лексикографический порядок для случая действительных чисел является линейным.

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

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

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

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

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

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

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

тогда решение , что минимизирует до , является решением по Парето.[7] Если сохраняет отношение порядка в , то есть, если для произвольных выполняется:

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

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

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

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

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

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

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

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

при условиях

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

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

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

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

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

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

Примечания

  1. ↑ Steuer R.E. Multiple Criteria Optimization: Theory, Computations, and Application. — New York: John Wiley & Sons, Inc. — ISBN 047188846X
  2. ↑ Sawaragi Y. Theory of Multiobjective Optimization (vol. 176 of Mathematics in Science and Engineering). — Orlando, FL: Academic Press Inc. — ISBN 0126203709
  3. ↑ 1 2 Jürgen Branke, Kalyanmoy Deb, Kaisa Miettinen та Roman Slowinski Multiobjective Optimization: Interactive and Evolutionary Approaches (Lecture Notes in Computer Science). — Springer. — ISBN 3-540-88907-8
  4. ↑ A. Osyzka. «Multicriteria optimization for engineering design». Design Optimization (Academic Press): 193-227.
  5. ↑ (Ehrgott, c. 34)
  6. ↑ (Jürgen et al, с. XI)
  7. ↑ 1 2 3 Sequential Approximate Multiobjective Optimization Using Computational Intelligence (Vector Optimization). — Springer. — ISBN 978-3-540-88909-0
  8. ↑ R. S. Rosenberg Simulation of genetic populations with biochemical properties. — University of Michigan, 1967.

См. также

Литература

Ресурсы интернета

biograf.academic.ru

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

Суть данного метода заключается в том, что частные критерии Fi (X), i = каким-либо образом объединяются в один интегральный критерий F (X) = Ф (F1 (X), F2 (X),…, Fn (X)) , а затем находится максимум или минимум данного критерия.

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

В зависимости от того, каким образом частные критерии объединяются в обобщенный критерий различают следующие виды обобщенных критериев:

1) аддитивный критерий;

2) мультипликативный критерий;

3) максиминный (минимаксный) критерий.

 

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

,

где n – количество объединяемых частных критериев; Ci – весовой коэффициент i-го частного критерия; Fi (X) – числовое значение i-го частного критерия; Fi(0) (X) – i-й нормирующий делитель; fi (X) – нормированное значение i-го частного критерия.

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

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

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

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

Преимущество аддитивного критерия: как правило, всегда удается определить единственный оптимальный вариант решения.

Недостатки:

- трудности (субъективизм) в определении весовых коэффициентов;

- аддитивный критерий не вытекает из объектной роли частных критериев и поэтому выступает как формальный математический прием;

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

Пример. Определить оптимальный вариант машины с использованием обобщенного (интегрального) аддитивного критерия. Частными критериями, с помощью которых оценены варианты машины, являются ее производительность и надежность (наработка на отказ). Оба критерия «работают» на максимум, т. е. наилучшими вариантами машины являются те из них, которые обеспечивают наибольшую ее производительность и надежность. Исходные данные для решения задачи приведены в таблице 3.2.

 

Таблица 3.2 – Исходные данные для определения оптимального варианта исполнения машины

Критерий Fi Весовой коэффициент Сi Значения критериев для вариантов исполнения машины
Вариант 1 Вариант 2 Вариант 3
Производительность F1, шт/ч 0,6
Надежность (наработка на отказ) F2, ч 0,4

 

Целевая функция на основе аддитивного критерия запишется следующим образом:

.

В качестве нормирующих делителей в данной задаче примем наилучшие (максимальные) значения частных критериев:

F1(0) (X) = 4000 шт/ч, F2(0) (X) = 1500 шт/ч.

Значения обобщенного аддитивного критерия рассчитываются для каждого варианта машины.

Вариант 1. F (X) = 0,6(1000/4000) + 0,4(1500/1500) = 0,55.

Вариант 2. F (X) = 0,6(2000/4000) + 0,4(1000/1500) = 0,558.

Вариант 3. F (X) = 0,6(4000/4000) + 0,4(500/1500) = 0,732.

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

Один из недостатков этого метода заключается в том, что весовые коэффициенты назначает проектировщик. Разные проектировщики могут назначать разные весовые коэффициенты. Пусть, например, C1 = 0,4; C2 = 0,6. Определим теперь значения аддитивных критериев для вариантов машины.

Вариант 1. F (X) = 0,4 × 0,25 + 0,6 × 1 = 0,7.

Вариант 2. F (X) = 0,4 × 0,5 + 0,6 × 0,67 = 0,602.

Вариант 3. F (X) = 0,4 × 1 + 0,6 × 0,33 = 0,598.

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

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

,

где П – знак произведения; Сi – весовой коэффициент i-го частного критерия; Fi(X) – числовое значение i-го частного критерия.

Преимущества мультипликативного критерия:

- не требуется нормирование частных критериев;

- практически всегда определяется одно оптимальное решение.

Недостатки:

- трудности (субъективизм) в определении весовых коэффициентов частных критериев;

- перемножение разных размерностей;

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

Максиминный (минимаксный) критерий. Эти критерии работают по принципу компромисса, который основывается на идее равномерности. Сущность принципа максимина заключается в следующем. При проектировании сложных систем, при наличии большого числа частных критериев установить между ними аналитическую взаимосвязь очень сложно. Поэтому стараются найти такие значения переменных (параметров) X = {x1, x2,…, xm}, при которых нормированные значения всех частных критериев равны между собой:

Cifi (X) = K,

где Ci – весовой коэффициент i-го частного критерия; fi (X) – нормированное значение i-го частного критерия; K – константа.

При большом количестве частных критериев из-за сложных взаимосвязей добиться выполнения указанного выше соотношения очень сложно. Поэтому на практике так варьируют значениями переменных проектирования x1, x2,…, xm, при которых последовательно «подтягиваются» те нормированные критерии, численные значения которых в исходном решении оказались наименьшими. Т. к. эта операция производится в области компромисса, подтягивание «отстающего» критерия неизбежно приводит к снижению значений части остальных критериев. Но при проведении ряда шагов можно добиться определенной степени уравновешивания противоречивых частных критериев, что и является целью принципа максимина.

Формально принцип максимина формулируется следующим образом: выбрать такой набор переменных Х(0) Î Х, при котором реализуется максимум из минимальных нормированных значений частных критериев,

т. е. F (X(0)) = max min fi (X).

Такой принцип выбора Х(0) иногда носит название гарантированного результата. Он заимствован из теории игр, где является основным принципом.

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

F (X(0)) = min max fi (X)

cyberpedia.su


Prostoy-Site | Все права защищены © 2018 | Карта сайта