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

– Признаётся право на все изменения, которые не приносят никому дополнительного вреда.

– Ситуация, когда достигнута эффективность по Парето — это ситуация, когда все выгоды от обмена исчерпаны.

Множество Парето – множество состояний системы, оптимальных по Парето.

Пусть имеется область D и задана функция f – целевая функция (критерий). Задача оптимизации имеет вид

(max)min f(X)

X?D

Точка X1?D называется оптимальной (недоминируемой, неулучшаемой), если не существует точки X2?D, для которой f(X1)>f(X2) (целевая функция минимизируется). Аналогично можно исключить из области D точки, которые заведомо не могут оказаться наилучшими.

Очевидно, что в обобщённом смысле определение оптимальности можно трактовать как описание (выделение) в подмножестве D некоторого нового подмножества D0, т. е. некоторое сужение D до D0 ?D. В зависимости от характера описания, подмножество D0 может оказаться пустым, состоять из одного элемента, содержать более одного элемента. Описание D0 можно проводить либо только с помощью критериев Fi, либо использовать дополнительные условия. Здесь мы рассмотрим направление, которое связано с определением оптимальности по Парето.

Отношение доминирования по Парето. Парето-оптимальность.

Как было сказано раньше для всякого решения X?D набор его оценок по всем критериям, т. е. набор (F1(X), F2(X), . . .,Fm(X)), есть векторная оценка решения X. Векторная оценка X содержит полную информацию о ценности (полезности) этого решения для ЛПР и сравнение любых двух решений заменяется сравнение их векторных оценок. Пусть в МЗО требуется получить меньшие значения каждого частного критерия (минимизировать частные критерии) Fi(X).

Опр. Пусть имеются два решения X1 и X2. Говорят, что решение X1 лучше (предпочтительнее, эффективнее, доминирует) решения X2, если Fi(X1)<=Fi(X2) для всех  i=1,m, и хотя бы для одного j - го критерия выполняется строгое неравенство Fi(X1)<Fi(X2).

Опр. Решение X2 называется доминируемым, если существует решение X1, не хуже чем X2, т. е. для любой оптимизируемой функции Fi, I=1, 2, …, m,

Fi(X2)?Fi(X1) при максимизации функции Fi, Fi(X2)?Fi(X1) при минимизации Fi.

В случае доминирования при переходе от X2 к X1 ничего не будет проиграно ни по одному из частных критериев, но в отношении j - го частного критерия точно будет получен выигрыш. Говорят, что решение  X1 лучше (предпочтительнее) решения X2.

Опр. Стратегия X1?D называется эффективной (оптимальной по Парето), если не существует стратегии X2?D такой, что Fi(X2) ?Fi(X1),

i=1, . . ., m, F(X2)?F(X1),

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

Очевидно, тогда в составе множества D нет смысла сохранять решение X2, оно вытесняется (или,  как говорят, “доминируется”) решением X1.  Выбросим решение X2 как неконкурентоспособное и перейдём к сравнению других решений по всем критериям. В результате такой процедуры отбрасывания заведомо непригодных, невыгодных решений множество D обычно сильно уменьшается: в нём сохраняются только так называемые эффективные (иначе “паретовские”) решения, характерные тем, что ни для одного из них не существует доминирующего решения. Множество таких точек и называется множеством точек оптимальных по Парето. Множество точек оптимальных по Парето лежат между точками оптимумов, полученных при решении задачи математического программирования для каждого частного критерия. В литературе множество точек оптимальных по Парето, как правило, обозначают буквой P (P?D).

Опр. Множество векторных оценок, соответствующих множеству эффективных точек, называют областью компромиссов (переговорным множеством) или множеством Парето в области критериев. Будем обозначать YP (YP ?YD).

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

В области Yc нет противоречия между частными критериями оптимальности, т. к. каждая точка X?D может быть изменена таким образом, что будет одновременно улучшены все частные критерии.

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

Проиллюстрируем приём выделения паретовских решений на примере задачи с двумя критериями F1 и F2. Множество D состоит из 11 возможных решений. Каждому решению соответствуют определённые значения показателей F1 и F2. Пусть имеются следующие векторные оценки: F(X1)=(2;4), F(X2)=(3;5), F(X3)=(3;3), F(X4)=(5;2), F(X5)=(4;3), F(X6)=(1;3), F(X7)=(2;3), F(X8)=(3;2), F(X9)=(2;2), F(X10)=(3;1), F(X11)=(2;1). Векторные оценки исходов представим точками координатной плоскости (по оси абсцисс откладываем значения критерия F1, а по оси ординат – значения критерия F2). Используем принцип оптимальности по Парето для выделения эффективных решений. Решение X1 вытесняется решением X2, решение X2 лучше решений X3, X7, X8, X9, X10 и X11. Решение X4 по первому критерию лучше решения X5, а по второму наоборот, т. е. имеем неулучшаемые решения, и т. д. После проведённого анализа у нас остались три решения X2,X4, X5 оптимальных по Парето.

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

  Множество Yk

Когда из множества возможных решений выделены эффективные, "переговоры" могут вестись уже в пределах этого "эффективного" множества. На рис. образуют три решения X2, X4, X5; из них X4 лучше по критерию F1, а решение X2 по критерию F2. Дело ЛПР, выбрать тот вариант, который для него предпочтителен и “приемлем” по обоим критериям.

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

Замечание. Для определения эффективных точек используют правило “уголка”. Уголок вида  L используется для определения компромиссных точек в критериальном пространстве, когда критерии максимизируются, а уголок  ¬когда критерии минимизируются.

В случае, когда множество допустимых исходов является непрерывным, их векторные оценки "заполняют" некоторую область YD на плоскости. В этом случае множество Парето-оптимальных оценок (представляет собой часть границы YD, образно говоря, её "юго-западную" границу (красная линия)). Если критерии максимизируются то – "северо-восточную" (синяя линия) границу области YD, без тех ее частей, которые параллельны одной из координатных осей или лежат в «глубоких» провалах.

Преимущества метода:

1) Критерии равнозначны;

2) Метод математически объективен.

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

ГлаваII

Практическая часть

Решение задач на МКО по методу оптимального выбора и по методу Парето.

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

С1: сложность предмета в соответствии с СанПиНами для общеобразовательных учреждений;

C2:  количество заданий по каждому предмету, в соответствии с демоверсиями.

Метод оптимального выбора.

Составим соответствующую таблицу, приняв наибольшие значения за 100% и вычислив остальные значения.

предметы	сложность предмета(С1)	кол-во заданий(С2)	сложность предмета	кол-во заданий
химия	12	22	0,92	0,61
физика	13	26	1	0,72
обществознание	9	31	0,69	0,86
биология	7	32	0,53	0,89
английский язык	9	36	0,69	1
география	5	23	0,38	0,64
история	10	35	0,77	0,97
литература	7	25	0,53	0,69
информатика	7	21	0,53	0,58
эталон	13-100%	36-100%	1	1

Найдем max для каждой альтернативы, из которых выберем минимальное, оно будет указывает на результат.

предметы	сложность предмета	кол-во заданий	mах
химия	0,92	0,61	0,92
физика	1	0,72	1
обществознание	0,69	0,86	0,86
биология	0,53	0,89	0,89
английский язык	0,69	1	1
география	0,38	0,64	0,64
история	0,77	0,97	0,97
литература	0,53	0,69	0,69
информатика	0,53	0,58	0,58

D = min{0,92/хим; 1/физ; 0,86/общ; 0,89/биол; 1/англ; 0,64/геогр; 0,97/ист; 0,69/лит; 0,58/инф } = = {0,64/геог;0,58/инф}