Многокритериальные задачи: постановка, проблемы, осн. понятия, методы

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

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

Многокритериальность может быть обусловлена одной из трех причин:

1. Цель не может быть адекватно представлена (покрыта) одним критерием.

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

3. Решения принимаются группой лиц с несовпадающими интересами.

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

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

Многокритериальная задача математического

Программирования

В формальном представлении критерии (целевые функции), по которым оценивается решение Х, будет записываться в виде f_i (Х), .

Критерий f_i называют также частными. Для удобства рассуждений примем, что для всех i чем больше значение критерия, тем лучше. Тогда задача многокритериального математического программирования запишется в виде:

max{ f ₁(X)= y ₁},

max{ f ₂(X)= y ₂},

.......

max{ f_m (X)= y_m },

Х D,

где D – множество допустимых решений. Иначе говоря, задача состоит в максимизации вектора критериев f (X)=Y по X D.

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

Допустимое множество D строится в n -мерном пространстве переменных. Каждое решение X D полностью характеризуется соответствующими значениями всех частных критериев, т.е. вектором Y. Числовое m -мерное пространство E ^m, координатами которого являются y_i=f_i (X), называется критериальным пространством. Очевидно, что каждому Х можно поставить в соответствие точку в критериальном пространстве. Если же решение Х допустимо, то соответствующая точка в E ^m, определяемая вектором Y, является достижимой. Множество таких точек в критериальном пространстве называется множеством достижимости (достижимых векторов). Таким образом, векторная функция f (X) отображает допустимое множество D на множестве достижимости G:

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

В общем случае построение множества G для реальных задач весьма проблематично, но для задач с «хорошими» свойствами, например, линейных, множество достижимости может быть построено.