Файл: Оптимизация решений по Парето.pdf

Структура модели отражает результат анализа ситуации принятия решения. 

Основные группы понятий метода анализа иерархий:

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

1.2. МЕТОД КУСОЧНО-ЛИНЕЙНОЙ АППРОКСИМАЦИИ

В тех случаях, когда ЛПР четко представляет себе "что за что он готов поменять"может быть использован метод кусочно-линейной аппроксимации. Метод позволяет осуществить линейное, а не групповое упорядочивание, но требует от ЛПР очень много информации. Тем не менее, в некоторых случаях, например при управлении очередями задач операционной системой ЭВМ, при решении задач численными методами, когда значение коэффициентов при неизвестных определяет эксперт или ЛПР, при принятии решений в чрезвычайных ситуациях и в некоторых других случаях метод может оказаться полезным. Пусть множество объектов А можно разбить на какие-то подмножества: А=u Bj которые можно рассортировать Bj=u Bji.J(-j пусть, далее, в каждом классе Bj выделяется некоторый представитель bB1(-Вi(-Вj(-А причем множество В°, состоящее из всех представителей также сортируемо и выбор лица, принимающего решение на любом наборе представителей соответствует охватывающей этот набор сортировке. Доказано, что в этом случае глобальная сортировка оказывается единственной для всех систем частичных сортировок. Этот метод реализует решение задачи классификации лицом, принимающим решение о состояниях объектов по совокупности качественных и/или количественных признаков. Приведем вначале алгоритм определения структуры предпочтения ЛПР путем построения поверхностей безразличия. Введем понятие кривой безразличия. Гиперповерхность уровня функции U(xi ,...,xm ) определяется как множество точек x=(xi , xz , ..., xm), для которых функция полезности U(x)=const. Гиперповерхности уровня функции полезности называются кривыми безразличия. Термин "кривая безразличия" связан с тем, что полезность альтернатив х и у, лежащих на одной кривой, одинакова U(x)=U(y). Норма замены между i-м и j-м критериями равна числу единиц по i-ому критерию, потеря которых может быть компенсирована одной единицей по j-ому критерию.

1.3. МЕТОД ПАРЕТО

Приведем соответствующее формальное определение. Решение ^*Х называется эффективным решением или оптимальным по Парето решением, если не существует другого решения X среди анализируемых альтернатив, такого, что g^(k)() g^(k)(^*), k=, причем хотя бы для одного k имеет место строгое неравенство. Другими словами, оптимальное по Парето решение ^*Х должно обладать следующим свойством. В множестве Х допустимых альтернативных решений не найдется ни одного другого решения, переход к которому (от ^*) позволит улучшить показатель хотя бы одного из частных критериев, чтобы при этом не ухудшились бы показатели других частных критериев. Если множество абсолютных решений не является пустым, то множество оптимальных по Парето решений совпадает с множеством абсолютных решений. Убедитесь в этом самостоятельно.

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

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

Графическая интерпретация. Понятие решения, оптимального по Парето имеет простую интерпретацию. Для графической интерпретации рассмотрим случай, когда задано только два частных критерия (N=2): G(g⁽¹⁾(), g⁽²⁾()). Кроме того, пусть каждый из указанных частных критериев будет представлен соответствующей функцией именно двух переменных. Для удобства изложения векторную переменную будем представлять как = (x, y), а частные критерии – как функции и , определенные в некоторой области D допустимых значений переменных. Итак, имеем следующий векторный критерий: G(g⁽¹⁾(), g⁽²⁾()) = G((x, y), (x, y)). Рассматриваем задачу оптимизации двух критериев:

(x, y)min

(x, y) min

при условии (x, y)D (см. рисунок 1.1).

Для интерпретации и графического представления множества решений, оптимальных по Парето, перейдем к двумерному пространству (U, V), в котором представим все возможные значения частных критериев (в формате анализируемых альтернатив). Такое пространство называют пространством значений частных критериев. Введем обозначения: U =(x, y), V=(x, y). На плоскости (U, V) изобразим все точки (для всех допустимых решений (x, y)D), координаты которых определяются по указанным формулам для U и V. Обозначим полученное множество через (см. рис. 1.2). Для представленного на рис. 1.2 множества всех возможных значений для частных критериев видно, что наименьшее значение первого частного критерия (значение U_min) и наименьшее значения второго частного критерия (значение V_min), вообще говоря, могут достигаться в разных точках пространства (U, V) и соответственно в разных точках пространства допустимых решений (x, y)D. При этом точка с координатами (U_min, V_min) лежит в пространстве значений частных критериев вне интересующего нас множества . Другими словами, для такой ситуации множество абсолютных решений будет пустым, а поставленная задача – неразрешима. Необходимо искать компромиссное решение. При этом множество Парето представляет собой такие точки (x, y)D, которым в пространстве (U, V) соответствует граничная область множества , обладающая следующим свойством. В указанном пространстве нельзя сдвинуться на «юг», на «запад» или на «юго-запад», чтобы при этом остаться в пределах множества .

УПРАЖНЕНИЕ. Рассмотрите самостоятельно интерпретацию множества оптимальных по Парето решений для случая, когда задача многокритериальной оптимизации является задачей максимизации соответствующих функций (x, y) и (x, y), причем менеджер не намерен использовать прием по замене знака критериальной функции для приведения таких частных критериев к оговоренному выше стандартному виду. Кроме того, рассмотрите также интерпретацию множества оптимальных по Парето решений для случая, когда задача многокритериальной оптимизации является задачей максимизации одной из этих функций и задачей минимизации другой из них.

УКАЗАНИЕ. Множеству оптимальных по Парето решений (x, y)D соответствуют в области значений частных критериев (при N=2) такие граничные точки, из которых:

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

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

• • на рис. 1.3 (а-б) они представлены применительно к задачам многокритериальной оптимизации, когда оба частных критерия минимизируются;
  • на рис. 1.4 (а-б) – применительно к задачам многокритериальной оптимизации, когда оба частных критерия максимизируются.

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

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

Сравнение альтернатив при многих критериях

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

ПРИМЕР 1

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

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

Табл. 1.3.

Атрибуты задачи оптимизации для примера 1

РЕШЕНИЕ. В частности, можно предпочесть альтернативу X₁, так как при этом решении суммарный показатель по всем частным критериям является наименьшим (он равен 150). Никакая другая альтернатива не дает такого результата (хотя в формате отдельных показателей частных критериев потери, соотносимые с X1, при других альтернативных решениях могут быть меньшими). Но можно предпочесть, например, альтернативное решение X₂ , обратив внимание на следующее. Только по одному из частных критериев (показатель критерия ) альтернатива X₂ уступает альтернативе X₁, а применительно ко всем остальным частным критериям не уступает. Более того, по критерию она даже является более предпочтительной. Можно также предпочесть, например, альтернативу X₄, заметив, например, что только по одному из частных критериев (показатель критерия ) она уступает альтернативе X₂, а применительно ко всем остальным частным критериям она не уступает ей.