МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ ЛЕКСИКОГРАФИЧЕСКОЙ ОПТИМИЗАЦИИ С ЛИНЕЙНЫМИ ФУНКЦИЯМИ КРИТЕРИЕВ НА НЕЧЕТКОМ МНОЖЕСТВЕ АЛЬТЕРНАТИВ часть 2

МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ ЛЕКСИКОГРАФИЧЕСКОЙ ОПТИМИЗАЦИИ С ЛИНЕЙНЫМИ ФУНКЦИЯМИ КРИТЕРИЕВ НА НЕЧЕТКОМ МНОЖЕСТВЕ АЛЬТЕРНАТИВ часть 1
МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ ЛЕКСИКОГРАФИЧЕСКОЙ ОПТИМИЗАЦИИ С ЛИНЕЙНЫМИ ФУНКЦИЯМИ КРИТЕРИЕВ НА НЕЧЕТКОМ МНОЖЕСТВЕ АЛЬТЕРНАТИВ часть 2

Разработан подход к решению задачи Z (F, X ), основанный на методе последовательных уступок. При решении многокритериальной задачи этим методом вначале производится качественный анализ относительной важности частных критериев. Особенностью данного метода есть то, что критерии задачи должны быть предварительно упорядочены по убыванию их важности, так что главным является критерий f1( x), менее важен f2 ( x), затем следуют остальные частные критерии f3 ( x) ,…, fl ( x).
Максимизируется первый по важности критерий f1( x) и определяется его наибольшее значение f *.
Затем назначается величина допустимого снижения (уступки) ?1? 0 критерия f1( x) и ищется наибольшее значение f * второго критерия f2 ( x) при условии, что значение первого критерия должно быть не меньше, чем f * ??. Снова назначается величина уступки ?2? 0, но уже по второму критерию, которая вместе с первой используется при нахождении условного максимума третьего критерия, т.д. Наконец, максимизируется последний по важности критерий fl ( x) при условии, что значение каждого критерия fr ( x) из l ?1 предыдущих должно быть не меньше соответствующей величины f * ??, получаемые в итоге стратегии считаются оптимальными.
Таким образом, выбор решения задачи осуществляется путем выполнения многошаговой процедуры и состоит в последовательном включении ограничений задачи Z (F, X ) и учете структурных особенностей его допустимой области.
Следует отметить, что в случае, когда все ?r – нули, метод последовательных уступок выделяет только лексикографически оптимальные альтернативы; эти альтернативы доставляют наибольшее на множестве допустимых значений решение первому по важности критерию f1( x).
Поэтому величины уступок, назначенные для многокритериальной задачи, можно рассматривать как своеобразную меру отклонения приоритета (степени относительной важности) частных критериев от жесткого, лексикографического.
Опишем применение этого метода для получения лексикографически оптимальных решений при нечетко заданном допустимом комбинаторном множестве перестановок.
Суть метода заключается в выделении сначала множества альтернатив с наилучшей оценкой по наиболее важному критерию. Если такая альтернатива одна, то она считается лучшей. Если их несколько, то из подмножества альтернатив, выделенного на предыдущем шаге, выделяются те альтернативы, которые имеют лучшую оценку по следующему критерию в ряду упорядочения их по важности и т.д.
Обозначим fij = fi ( x j )? нечеткие оценки альтернатив x j, j? Nn, по критериям fi, i? Nl.
Применение метода при нечеткой исходной информации сводится к следующим действиям:
1.Критерии упорядочить по важности: f1( x), f2 ( x) ,…, fl ( x).
2.С согласия ЛПР назначить уровень?? [0,1], для которого определяется множество лучших альтернатив в соответствии с пунктами 3 – 5:
3. Определить нижнюю (l ) и верхнюю (u) границы ?? уровневых подмножеств для оценки альтернатив по рассматриваемому критерию: l ( fij ) = min x, u( fij ) = max x.
4. Для каждой пары альтернатив оценок hzy ( z > y) и hyz ( y > z):? fij ( x)??? fij ( x)? z, y? X’ вычислить показатели взаимного превышения критериальных
а) если оценки таковы, что f?? f?, то u( fiz )? u( fiy ) l ( fiy )? l ( fiz ) где z, y? X’; hzy = u( fiz )? l ( fiz ), hyz=u( fiz )? l ( fiz ) z y z y
б) если оценки не пересекаются и? f0? S fiz: ?f? S fiy f0 > f, то u( fiy )? l ( fiz ) hzy = 1?, hyz = 0, (6) max{r ( z), r ( y)} где r ( z) = u( fiz )? l ( fiz ), r ( y) = u( fiy )? l ( fiy );
в) если оценки не пересекаются и ?f z? S f, ?f y? S iz iy: f z > f y, то hzy = 1, hyz = 0. (7)
5. Вычислить показатели D принадлежности j -й альтернативы множеству лучших ( D -множеству) по i -му критерию альтернатив? D = sup{0, (max h? max h )}, где h jy, hyj ij jy yj y?X y?X y? j y? j вычислены по формулам (5) – (6) для i -го критерия.
6. Если множество лучших по рассматриваемому критерию альтернатив содержит ровно одну альтернативу с? D??, то она считается лучшей. Если это множество содержит более чем одну? D??, то выбирается следующий по важности критерий и повторяются пункты 3? 5.
Если все критерии просмотрены и множество лучших по рассматриваемому критерию альтернатив содержит более одной альтернативы и? <1, то? можно увеличить и перейти к пункту 3. Если? = 1, то окончательный выбор лучшей альтернативы предоставляется ЛПР.
Рассмотрим еще один простой метод решения задачи Z (F, X ), который является развитием метода идеальной точки на случай нечетко заданных альтернатив, при отсутствии информации о предпочтениях на множестве критериев.
Пусть заданы или вычислены нечеткие оценки fi ( x j ) альтернатив x j, j? Nn, по критериям fi, i? Nl.
Рассмотрим метод выбора альтернатив по обобщенному критерию пессимизма (максимина). Он состоит в выполнении следующих шагов:
1.Для каждого критерия вычислить нечеткую максимальную критериальную оценку fi max = m’ax { fi ( x j ) | x j? X, j? Nn }, i? Nl, по каждому из критериев оценки.
2.Вычислить приведенные нормализованные оценки альтернатив по критериям fij = fi ( x j ) / fi max, x j? X, j? Nn.
3.Вычислить минимальную критериальную оценку для каждой альтернативы f j min, определяемую как f j min = m’in { f * | i? Nl }, j? Nn.
4.Определить обобщенный максимум найденных минимальных оценок f0 max = m’ax { f j min | j? Nn }.
5.Оценить степень сходства f0 max с каждой из оценок f j min. В качестве показателя сходства j? f0 max f j min n нечетких чисел может быть использована величина? =? z?[0,1] ( z)?? ( z), j? N.
6.Выбираем альтернативу с максимальным индексом? j, j? Nn.
Если альтернатива выбирается по максимаксному принципу, то на шаге 3 следует вместо f j min вычислить f j max = m’ax { f * | i? Nl }, j? Nn, и использовать в остальных шагах алгоритма вместо f j min значения f j max.
Выводы
В данной работе в результате проведенного исследования векторной комбинаторной задачи, основанного на использовании информации о выпуклой оболочке допустимой области, изучении свойств многогранников, вершины которых определяют заданное комбинаторное множество перестановок, разработан и обоснован метод решения сложных многокритериальных задач на нечетко заданном комбинаторном множестве. Использование структурных свойств комбинаторных многогранников дает возможность разрабатывать эффективные алгоритмы решения новых классов векторных задач комбинаторной оптимизации.
  • +2
  • 4 ноября 2009, 13:29
  • yxom

Комментарии (0)

RSS свернуть / развернуть

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