Нахождение множества Парето

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

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

Возникает вопрос, как можно провести сравнение и оценку отдельных альтернатив, т.е. провести композицию альтернатив. Для иллюстрации возможных подходов воспользуемся, как всегда, удобной графической интерпретацией критериального пространства при n = 2. Точками изобразим все имеющиеся альтернативы. Наилучшей альтернативой (рис. 5) будет та, что изображена точкой выше и правее других. Исключить все улучшаемые альтернативы, а также проверить неулучшаемость альтернатив паретовского множества, можно следующим образом: из каждой точки–альтернативы провести лучи, параллельные положительному направлению обеих осей, и если в угле, образуемом этими лучами, оказываются другие точки, данная альтернативы отбрасывается. Нетрудно видеть, что если лучи проведены из точки, соответствующей неулучшаемой альтернативе, то в образованном углу других альтернатив нет (рис. 5а).

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

Примером множества Парето может служить диаграмма «грузоподъемность-дальность» для транспортных средств (рис.6).

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

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

* уменьшение количества воды в речной системе ухудшает условия рыболовства и судоходства;

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

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

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

f_i(x)®max, i=1,2,.......n.

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

Однако, помимо критериев f_i(х) в распоряжении проектировщика достаточно часто есть еще и некоторый общий критерий F(х). Иногда бывает возможно формализовать его, записать в явном виде. Например, таким критерием может быть стоимость проекта. В этом случае «исследователю операций» предоставляется возможность решить задачу до конца. Для этого достаточно определить вектор х, который дает решение задачи: F(x) ® max при xÎP_G(f₁,f₂,...f_n), где P_G(f₁,f₂,...f_n) - множество Парето для функций f₁,f₂,...f_n на множестве G допустимых векторов х. Например, в случае водохозяйственного комплекса множество G определяется таким распределением воды по объектам х_i, при котором ее количество не превосходит притока Q_{i ­.}

Важно отметить, что введение «общего» критерия F(x) и максимизация его значений на множестве Парето также является некоторой гипотезой, поскольку из совокупности критерие в f₁, f₂,....,f_n, F один из критериев мы специальным образом выделяем.

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

Дата добавления: 2014-01-07