Основы теории нечетких множеств

Алгоритмы нечеткой оптимизации

Разбить на страницы
Показывать лекцию целиком

Нечеткие цели, ограничения и решения

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

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

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

В традиционном подходе главными элементами процесса принятия решения являются:

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

    Под нечеткой целью подразумевается цель, которую можно описать как нечеткое множество в соответствующем пространстве. Пусть $$X$$ — заданное множество альтернатив. Тогда нечеткая цель, или просто цель, $$G$$ будет определяться фиксированным нечетким множеством $$G$$ в $$X$$.

    При обычном подходе функция предпочтительности, используемая в процессе принятия решения, служит для установления линейной упорядоченности на множестве альтернатив. Очевидно, что функция принадлежности $$\(\mu _G (x)\)$$ нечеткой цели выполняет ту же задачу и может быть получена из функции предпочтительности с помощью нормализации, сохраняющей установленную линейную упорядоченность.

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

    Решение — это по существу выбор одной или нескольких из имеющихся альтернатив. Проблема принятия решения в нечетких условиях интерпретируется тогда как комплексное влияние нечеткой цели $$G$$ и нечеткого ограничения $$C$$ на выбор альтернатив и характеризуется пересечением $$G\cap C$$, которое и образует нечеткое множество решений $$D$$, т.е.$$D = G\cap C.$$

    Функция принадлежности для множества решений задается соотношением$$\mu _D (x) = \mu _G (x) \wedge \mu _C (x).$$

    В общем случае, если имеется $$n$$ нечетких целей и $$m$$ нечетких ограничений, то результирующее решение определяется пересечением всех заданных целей и ограничений, т.е.$$D = G_1 \cap \ldots \cap G_n \cap C_1 \cap \ldots \cap C_m$$ и, соответственно,$$\mu _D (x) = \mu _{G_1 } (x) \wedge ... \wedge \mu _{G_n } (x) \wedge \mu _{C_1 } (x) \wedge ... \wedge \mu _{C_m } (x).$$

    В приведенном определении нечеткие цели и нечеткие ограничения входят в выражение $$D$$ совершенно одинаковым образом. Такое определение решения как нечеткого множества в пространстве альтернатив может показаться несколько искусственным. На самом деле оно совершенно естественно, поскольку нечеткое решение может рассматриваться как некоторая "инструкция", неформальность которой является следствием неточности формулировки поставленных целей и ограничений.

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

    Для практики интересен более общий случай, когда нечеткие цели и нечеткие ограничения — нечеткие множества в разных пространствах.

    Пусть $$f$$ — отображение из $$X$$ в $$Y$$, причем переменная $$x$$ обозначает входное воздействие, а $$y$$ — соответствующий выход.

    Предположим, что нечеткая цель задана как нечеткое множество $$G$$ в $$Y$$, в то время как нечеткое ограничениенечеткое множество $$C$$ в пространстве $$X$$. Имея нечеткое множество $$G$$ в $$Y$$, можно найти нечеткое множество $$\(\bar G\)$$ в $$X$$, которое индуцирует $$G$$ в $$Y$$. Функция принадлежности $$\(\bar G\)$$ в $$Y$$ задается равенством$$\mu _{\bar G} (x) = \mu _G (f(x)).$$

    После этого решение $$D$$ может быть выражено пересечением множеств $$\(\bar G\)$$ и $$C$$. Используя предыдущее соотношение, можно записать$$\mu _D (x) = \mu _G (f(x)) \wedge \mu _C (x).$$

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

    Задачи нечеткого математического программирования

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

    Стандартная задача нечеткого математического программирования формулируется обычно как задача максимизации (или минимизации) заданной функции на заданном множестве допустимых альтернатив, которое описывается системой равенств или неравенств. Например:$$f(x) \to \max ,\;\t{\char239}\t{\char240}\t{\char232}\;\varphi _i (x) \leqslant 0,\quad \quad i = 1,...,m,\;x \in X,$$ где $$X$$ — заданное множество альтернатив, $$f\colon X\to R$$ — заданная функция, которую нужно максимизировать, и $$\varphi_{i}\colon X\to R$$ — заданные функции ограничений.

    При моделировании в нечеткой форме реальных задач принятия решений в распоряжении исследователя-математика могут оказаться лишь нечеткие описания функции $$f$$ и $$\varphi_{i}$$, параметров, от которых зависят эти функции, и самого множества $$X$$. Таким образом, задача стандартного математического программирования превратится в задачу нечеткого математического программирования.

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

    Перечислим некоторые из таких формулировок.

    Задача 1. Максимизация заданной обычной функции $$f\colon X\to R$$ на заданном нечетком множестве допустимых альтернатив $$\(\mu\colon {{X}} \to {{R}}\)$$.

    Задача 2. Нечеткий вариант стандартной задачи математического программирования. Пусть определена следующая задача:$$f(x) \to \max ,\;\t{\char239}\t{\char240}\t{\char232}\;\varphi _i (x) \leqslant 0, \quad i = 1,...,m,\;x \in X.$$

    Нечеткий вариант этой задачи получается, если "смягчить" ограничения, т.е. допустить возможность их нарушения с той или иной степенью. Кроме того, вместо максимизации функции $$f(x)$$ можно стремиться к достижению некоторого заданного значения этой функции, причем различным отклонениям значения функции от этой величины приписывать разные степени допустимости.

    Задача 3. Нечетко описана "максимизируемая" функция, т.е. задано отображение $$\(\mu _\varphi ;X \times R \to [0,1]\)$$, где $$X$$ — универсальное множество альтернатив, $$R$$ — числовая ось.

    В этом случае функция $$\(\mu _\varphi ({{x}}_{{0}}^{}{{,r}})\)$$ при каждом фиксированном $$x_{0}\in X$$ представляет собой нечеткое описание оценки результата выбора альтернативы $$x_{0}$$ (нечеткую оценку альтернативы $$x_{0}$$ ) или нечетко известную реакцию управляемой системы на управление $$x_{0}$$. Задано также нечеткое множество допустимых альтернатив $$\(\mu _C \); \(X \to [0,1]\)$$.

    Задача 4. Заданы обычная максимизируемая функция $$f\colon X\to R$$ и система ограничений вида $$\(\varphi _{{i}} {{(x)}} \leqslant {{b}}_{{i}}^{} {{,}}\quad {{i}} = {{1}},\ldots,{{m}}\)$$, причем параметры в описаниях функций $$\(\varphi _{{i}} {{(x)}}\)$$ заданы в форме нечетких множеств.

    Задача 5. Нечетко описаны как параметры функций, определяющих ограничения задачи, так и самой максимизируемой функции.

    Рассмотрим, например, подробнее задачу линейного программирования с нечёткими коэффициентами. Нечеткость в постановке задачи нечеткого математического программирования может содержаться как в описании множества альтернатив, так и в описании целевой функции.$$\begin{equation} f(x) \to \max ,\;\quad g(x) \leqslant 0,\quad \quad x \in X. \end{equation}$$

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

    Нечеткую обстановку можно рассматривать как множество $$X$$ альтернатив вместе с его нечеткими подмножествами, представляющими собой нечетко сформулированные критерии (цели и ограничения), т.е. как систему $$(X, f_{0}, f_{1}, \ldots ,f_{n})$$. Принять во внимание по возможности все критерии в такой задаче означает построить функцию$$\begin{equation} D = f_{0}\cap f_{1}\cap \ldots\cap f_{n}, \end{equation}$$ в которую цели и ограничения входят одинаковым образом.

    Решение можно определить как нечеткое подмножество универсального множества альтернатив. Оптимум соответствует той области $$X$$, элементы которой максимизируют $$D$$. Это и есть случай нечеткого математического программирования.

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

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

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

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

    Нечеткий вариант стандартной задачи математического программирования получается, если "смягчить" ограничения, т.е. допустить возможность их нарушения с той или иной степенью. Кроме того, вместо максимизации целевой функции $$f(x)$$ можно стремиться к достижению некоторого заданного ее значения, причем различным отклонениям значения $$f(x)$$ от этой величины приписывать различные степени допустимости (например, чем больше отклонение, тем меньше степень его допустимости).

    Пусть $$a$$ — заданная величина функции цели $$f(x)$$, достижение которой считается достаточным для выполнения цели принятия решений, и пусть имеется пороговый уровень $$b$$, такой, что неравенство $$f(x)<a-b$$ означает сильное нарушение неравенства $$f(x)\ge a$$. Тогда функцию принадлежности для нечеткой функции цели можно определить следующим образом:$$\begin{equation} \mu _G (x) = \left\{ {\begin{array}{*{20}c} {0,} {\t{\char229}\t{\char241}\t{\char235}\t{\char232}} {f(x) \leqslant a - b,} \\ {\mu _a (x),} {\t{\char229}\t{\char241}\t{\char235}\t{\char232}} {a - b < f(x) < a,} \\ {1,} {\t{\char229}\t{\char241}\t{\char235}\t{\char232}} {f(x) \geqslant a,} \\ \end{array} } \right. \end{equation}$$ где $$\mu_{a}$$ — функция принадлежности, описывающая степени выполнения соответствующего неравенства с точки зрения лица, принимающего решения.

    Аналогично определяется функция принадлежности $$\mu_{C}(x)$$ для нечетких ограничений. В результате исходная задача оказывается сформулированной в форме задачи выполнения нечетко определенной цели, к которой применим подход Беллмана-Заде (2).

    При моделировании ситуации в форме задачи линейного программирования$$\begin{equation} \min \{ cx\;|\;Ax \leqslant b,\;x \geqslant 0\} \end{equation}$$ о коэффициентах $$a_{ij}$$, $$b_{i}$$ и $$c_{i}$$ известно лишь то, что они находятся в некотором множестве, отражающем все реальные возможности.

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

    Рассмотрим задачу нахождения минимума на заданной области. Пусть задана область вида$$\begin{equation} P = \left\{ {x \in R_ + ^n \;|\;a_{i1} x_1 + \ldots + a_{in} x_n \subseteq b_i ,\; i = 1,\ldots,m} \right\}, \end{equation}$$ где $$a_{ij}, b_{i}$$ — нечеткие подмножества множества $$R$$, а бинарная операция $$+$$ обозначает сложение нечетких множеств. Требуется найти $$\(\mathop {\min }\limits_{x \in P} \;\{ c,x\}\)$$ на заданной области.

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

    Сведем решение исходной задачи к решению ряда задач линейного программирования. Для этого введем дискретные $$\alpha$$ -уровни. В результате нечеткие ограничения принимают следующий интервальный вид:$$\begin{equation} P = \left\{ {\begin{array}{*{20}c} {\sigma _\alpha (a_{i1} )x_1 + \ldots + \sigma _\alpha (a_{in} )x_n ,} {i = 1,\ldots,m,\;\alpha = 1,\ldots,p,} \\ {x_j \geqslant 0,} {j = 1,\ldots,n.} \\ \end{array} } \right. \end{equation}$$

    Таким образом, мы перешли от нечетких множеств к четко определенным и теперь, зная, что $$\alpha$$ — обычный интервал, можем записать нашу задачу в следующем виде:$$\begin{equation} \begin{gathered} (a_{11} , a_{12}) x_{1} + (c_{11}, c_{12}) x_{2}\subseteq (b_{11} , b_{12}),\\ (a_{21} , a_{22}) x_{1} + (c_{21}, c_{22}) x_{2} \subseteq (b_{21} , b_{22}). \end{gathered} \end{equation}$$

    Теперь, чтобы привести задачу к виду обычной задачи линейного программирования, нам достаточно записать неравенства отдельно по левому и правому краям интервалов, с учетом знаков неравенства. Т.е., мы приведем систему к следующему виду:$$\begin{equation} \begin{gathered} a _{11}x_{1} + c_{11}x_{2}\ge b_{11},\\ a _{12}x_{1} + c_{12}x_{2}\le b_{12},\\ a_{21}x_{1} + c_{21}x_{2}\ge b_{21},\\ a_{2}x_{1} + c_{22}x_{2}\le b_{22}. \end{gathered} \end{equation}$$

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

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

  • Исходная задача.
  • Вводим дискретные $$\alpha$$ -уровни.
  • Ограничения принимают интервальный вид.
  • Записываем неравенства отдельно по левому и правому краям с учетом знаков неравенства (при этом размерность увеличивается).
  • Получаем задачу ЛП с четкими коэффициентами.
  • Решаем полученную задачу симплекс-методом.
  • Как видим, исходная задача нечеткого математического программирования представляется в виде совокупности обычных задач линейного программирования на всевозможных множествах уровня множества допустимых альтернатив. Если альтернатива $$x_{0}$$ есть решение задачи $$\(\mathop {\min }\limits_{x\in P} \;\{ c,x\}\)$$ на множестве уровня $$\alpha$$, то можно считать, что число $$\alpha$$ есть степень принадлежности альтернативы $$x_{0}$$ нечеткому множеству решений исходной задачи.

    Перебрав, таким образом, всевозможные значения $$\alpha$$, получаем функцию принадлежности нечеткого решения.

    Если же и компоненты целевой функции $$c_{i}$$ являются нечеткими, то необходимо выбирать для каждого уровня $$\alpha$$ соответствующие границы множеств $$\sigma_{\alpha}(c_{J})$$, $$J=1,\ldots,n$$ в соответствии с правилами интервальной арифметики, минимизируя предварительно таким образом: $$\{c,x\}$$.

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

    Модели нечеткой ожидаемой полезности

    При описании индивидуального принятия решения в рамках классического подхода, наряду с моделями математического программирования, широко применяются теория статистических решений и теория ожидаемой полезности. Последняя предназначена для анализа решений, когда неопределенность обусловлена отсутствием объективной физической шкалы для оценки предпочтительности альтернатив. В этих случаях используется субъективная шкала полезности лица, принимающего решение (ЛПР). В реальных ситуациях исходы, соответствующие принятым решениям (состояниям системы), являются подчас неточными, что влечет за собой размытость соответствующих им оценок функции полезности. Размытый вариант ожидаемой полезности формулируется, например, в модели, где выделяются и одновременно учитываются как случайные, так и нечеткие составляющие неопределенности. Выбор происходит на основе максимизации нечеткой ожидаемой полезности$$ER_j = \sum\limits_{i = 1}^n {\tilde p_i F(s_i ,a_j ,b_k )} ,$$ где $$\(\tilde p_i\)$$ — размытая вероятность состояния $$s_{i}$$ из множества состояний мира $$\(S,\;F:\quad S \times A \times B \to \wp (R)\)$$, $$A=\{a\}$$ — множество альтернатив, $$B=\{b\}$$ — множество критериев, $$R$$ — множество оценок, а $$\(\wp (R) = \{ \mu _R \;|\;\mu _R :\;R \to [0,1]\}\)$$ — класс всех нечетких подмножеств на множестве оценок $$R$$.

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

    Например, задача анализа решений формулируется следующим образом. Пусть имеются две обычные вероятности лотереи: $$A = \left[ {pu_{A_1 } ,\;(1 - p)u_{A_2 } } \right]$$, где $$p$$ — вероятность исхода с ожидаемой полезностью $$\(u_{A_1 }\)$$ и $$(1-p)$$ — вероятность исхода с ожидаемой полезностью $$\(u_{A_2 }\)$$, а $$\(B = \left[ {qu_{B_1 } ,\;(1 - q)u_{B_2 } } \right]\)$$, где $$q$$ — вероятность исхода с ожидаемой полезностью $$\(u_{B_1 }\)$$, $$(1-q)$$ — вероятность исхода с ожидаемой полезностью $$\(u_{B_2 }\)$$. Из теории ожидаемой полезности следует, что $$\(A \succ B\)$$, если$$pu_{A_1 } , + (1 - p)u_{A_2 } > qu_{B_1 } + \;(1 - q)u_{B_2 } .$$

    Будем считать, что вероятности $$p$$ и $$q$$ и ожидаемые полезности $$\(u_{A_1 } ,\;u_{A_2 } ,\;u_{B_1 } ,\;u_{B_2 }\)$$ точно не известны, т.е. введем$$\mu _P :\;P \to [0,1],\quad \mu _Q :\;Q \to [0,1],\quad \mu _U :\;U \to [0,1].$$

    Тогда, в соответствии с принципом обобщения, степени принадлежности альтернатив $$a$$ и $$b$$ множествам нечетких ожидаемых полезностей в нечетких лотереях $$A$$ и $$B$$ соответственно вычисляются$$\begin{gathered} \mu _A (a) = \mathop {\max }\limits_{pu_{A1} + (1 - p)u_{A2} = a} \;\left[ {\min \{ \mu _P (p),\;\mu _{A_1 } (u_{A_1 } ),\;\mu _{A_2 } (u_{A_2 } )\} } \right], \\ \mu _B (b) = \mathop {\max }\limits_{qu_{B1} + (1 - q)u_{B2} = b} \;\left[ {\min \{ \mu _P (p),\;\mu _{B_1 } (u_{B_1 } ),\;\mu _{B_2 } (u_{B_2 } )\} } \right]. \\ \end{gathered}$$

    В случае лотереи с $$n$$ исходами также для каждого ребра дерева решений подсчитывается значение нечеткой ожидаемой полезности.

    Страницы:

    Нечеткие цели, ограничения и решения

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

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

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

    В традиционном подходе главными элементами процесса принятия решения являются:

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

    Под нечеткой целью подразумевается цель, которую можно описать как нечеткое множество в соответствующем пространстве. Пусть $$X$$ — заданное множество альтернатив. Тогда нечеткая цель, или просто цель, $$G$$ будет определяться фиксированным нечетким множеством $$G$$ в $$X$$.

    При обычном подходе функция предпочтительности, используемая в процессе принятия решения, служит для установления линейной упорядоченности на множестве альтернатив. Очевидно, что функция принадлежности $$\(\mu _G (x)\)$$ нечеткой цели выполняет ту же задачу и может быть получена из функции предпочтительности с помощью нормализации, сохраняющей установленную линейную упорядоченность.

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

    Решение — это по существу выбор одной или нескольких из имеющихся альтернатив. Проблема принятия решения в нечетких условиях интерпретируется тогда как комплексное влияние нечеткой цели $$G$$ и нечеткого ограничения $$C$$ на выбор альтернатив и характеризуется пересечением $$G\cap C$$, которое и образует нечеткое множество решений $$D$$, т.е.$$D = G\cap C.$$

    Функция принадлежности для множества решений задается соотношением$$\mu _D (x) = \mu _G (x) \wedge \mu _C (x).$$

    В общем случае, если имеется $$n$$ нечетких целей и $$m$$ нечетких ограничений, то результирующее решение определяется пересечением всех заданных целей и ограничений, т.е.$$D = G_1 \cap \ldots \cap G_n \cap C_1 \cap \ldots \cap C_m$$ и, соответственно,$$\mu _D (x) = \mu _{G_1 } (x) \wedge ... \wedge \mu _{G_n } (x) \wedge \mu _{C_1 } (x) \wedge ... \wedge \mu _{C_m } (x).$$

    В приведенном определении нечеткие цели и нечеткие ограничения входят в выражение $$D$$ совершенно одинаковым образом. Такое определение решения как нечеткого множества в пространстве альтернатив может показаться несколько искусственным. На самом деле оно совершенно естественно, поскольку нечеткое решение может рассматриваться как некоторая "инструкция", неформальность которой является следствием неточности формулировки поставленных целей и ограничений.

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

    Для практики интересен более общий случай, когда нечеткие цели и нечеткие ограничения — нечеткие множества в разных пространствах.

    Пусть $$f$$ — отображение из $$X$$ в $$Y$$, причем переменная $$x$$ обозначает входное воздействие, а $$y$$ — соответствующий выход.

    Предположим, что нечеткая цель задана как нечеткое множество $$G$$ в $$Y$$, в то время как нечеткое ограничениенечеткое множество $$C$$ в пространстве $$X$$. Имея нечеткое множество $$G$$ в $$Y$$, можно найти нечеткое множество $$\(\bar G\)$$ в $$X$$, которое индуцирует $$G$$ в $$Y$$. Функция принадлежности $$\(\bar G\)$$ в $$Y$$ задается равенством$$\mu _{\bar G} (x) = \mu _G (f(x)).$$

    После этого решение $$D$$ может быть выражено пересечением множеств $$\(\bar G\)$$ и $$C$$. Используя предыдущее соотношение, можно записать$$\mu _D (x) = \mu _G (f(x)) \wedge \mu _C (x).$$

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

    Задачи нечеткого математического программирования

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

    Стандартная задача нечеткого математического программирования формулируется обычно как задача максимизации (или минимизации) заданной функции на заданном множестве допустимых альтернатив, которое описывается системой равенств или неравенств. Например:$$f(x) \to \max ,\;\t{\char239}\t{\char240}\t{\char232}\;\varphi _i (x) \leqslant 0,\quad \quad i = 1,...,m,\;x \in X,$$ где $$X$$ — заданное множество альтернатив, $$f\colon X\to R$$ — заданная функция, которую нужно максимизировать, и $$\varphi_{i}\colon X\to R$$ — заданные функции ограничений.

    При моделировании в нечеткой форме реальных задач принятия решений в распоряжении исследователя-математика могут оказаться лишь нечеткие описания функции $$f$$ и $$\varphi_{i}$$, параметров, от которых зависят эти функции, и самого множества $$X$$. Таким образом, задача стандартного математического программирования превратится в задачу нечеткого математического программирования.

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

    Перечислим некоторые из таких формулировок.

    Задача 1. Максимизация заданной обычной функции $$f\colon X\to R$$ на заданном нечетком множестве допустимых альтернатив $$\(\mu\colon {{X}} \to {{R}}\)$$.

    Задача 2. Нечеткий вариант стандартной задачи математического программирования. Пусть определена следующая задача:$$f(x) \to \max ,\;\t{\char239}\t{\char240}\t{\char232}\;\varphi _i (x) \leqslant 0, \quad i = 1,...,m,\;x \in X.$$

    Нечеткий вариант этой задачи получается, если "смягчить" ограничения, т.е. допустить возможность их нарушения с той или иной степенью. Кроме того, вместо максимизации функции $$f(x)$$ можно стремиться к достижению некоторого заданного значения этой функции, причем различным отклонениям значения функции от этой величины приписывать разные степени допустимости.

    Задача 3. Нечетко описана "максимизируемая" функция, т.е. задано отображение $$\(\mu _\varphi ;X \times R \to [0,1]\)$$, где $$X$$ — универсальное множество альтернатив, $$R$$ — числовая ось.

    В этом случае функция $$\(\mu _\varphi ({{x}}_{{0}}^{}{{,r}})\)$$ при каждом фиксированном $$x_{0}\in X$$ представляет собой нечеткое описание оценки результата выбора альтернативы $$x_{0}$$ (нечеткую оценку альтернативы $$x_{0}$$ ) или нечетко известную реакцию управляемой системы на управление $$x_{0}$$. Задано также нечеткое множество допустимых альтернатив $$\(\mu _C \); \(X \to [0,1]\)$$.

    Задача 4. Заданы обычная максимизируемая функция $$f\colon X\to R$$ и система ограничений вида $$\(\varphi _{{i}} {{(x)}} \leqslant {{b}}_{{i}}^{} {{,}}\quad {{i}} = {{1}},\ldots,{{m}}\)$$, причем параметры в описаниях функций $$\(\varphi _{{i}} {{(x)}}\)$$ заданы в форме нечетких множеств.

    Задача 5. Нечетко описаны как параметры функций, определяющих ограничения задачи, так и самой максимизируемой функции.

    Рассмотрим, например, подробнее задачу линейного программирования с нечёткими коэффициентами. Нечеткость в постановке задачи нечеткого математического программирования может содержаться как в описании множества альтернатив, так и в описании целевой функции.$$\begin{equation} f(x) \to \max ,\;\quad g(x) \leqslant 0,\quad \quad x \in X. \end{equation}$$

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

    Нечеткую обстановку можно рассматривать как множество $$X$$ альтернатив вместе с его нечеткими подмножествами, представляющими собой нечетко сформулированные критерии (цели и ограничения), т.е. как систему $$(X, f_{0}, f_{1}, \ldots ,f_{n})$$. Принять во внимание по возможности все критерии в такой задаче означает построить функцию$$\begin{equation} D = f_{0}\cap f_{1}\cap \ldots\cap f_{n}, \end{equation}$$ в которую цели и ограничения входят одинаковым образом.

    Решение можно определить как нечеткое подмножество универсального множества альтернатив. Оптимум соответствует той области $$X$$, элементы которой максимизируют $$D$$. Это и есть случай нечеткого математического программирования.

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

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

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

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

    Нечеткий вариант стандартной задачи математического программирования получается, если "смягчить" ограничения, т.е. допустить возможность их нарушения с той или иной степенью. Кроме того, вместо максимизации целевой функции $$f(x)$$ можно стремиться к достижению некоторого заданного ее значения, причем различным отклонениям значения $$f(x)$$ от этой величины приписывать различные степени допустимости (например, чем больше отклонение, тем меньше степень его допустимости).

    Пусть $$a$$ — заданная величина функции цели $$f(x)$$, достижение которой считается достаточным для выполнения цели принятия решений, и пусть имеется пороговый уровень $$b$$, такой, что неравенство $$f(x)<a-b$$ означает сильное нарушение неравенства $$f(x)\ge a$$. Тогда функцию принадлежности для нечеткой функции цели можно определить следующим образом:$$\begin{equation} \mu _G (x) = \left\{ {\begin{array}{*{20}c} {0,} {\t{\char229}\t{\char241}\t{\char235}\t{\char232}} {f(x) \leqslant a - b,} \\ {\mu _a (x),} {\t{\char229}\t{\char241}\t{\char235}\t{\char232}} {a - b < f(x) < a,} \\ {1,} {\t{\char229}\t{\char241}\t{\char235}\t{\char232}} {f(x) \geqslant a,} \\ \end{array} } \right. \end{equation}$$ где $$\mu_{a}$$ — функция принадлежности, описывающая степени выполнения соответствующего неравенства с точки зрения лица, принимающего решения.

    Аналогично определяется функция принадлежности $$\mu_{C}(x)$$ для нечетких ограничений. В результате исходная задача оказывается сформулированной в форме задачи выполнения нечетко определенной цели, к которой применим подход Беллмана-Заде (2).

    При моделировании ситуации в форме задачи линейного программирования$$\begin{equation} \min \{ cx\;|\;Ax \leqslant b,\;x \geqslant 0\} \end{equation}$$ о коэффициентах $$a_{ij}$$, $$b_{i}$$ и $$c_{i}$$ известно лишь то, что они находятся в некотором множестве, отражающем все реальные возможности.

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

    Рассмотрим задачу нахождения минимума на заданной области. Пусть задана область вида$$\begin{equation} P = \left\{ {x \in R_ + ^n \;|\;a_{i1} x_1 + \ldots + a_{in} x_n \subseteq b_i ,\; i = 1,\ldots,m} \right\}, \end{equation}$$ где $$a_{ij}, b_{i}$$ — нечеткие подмножества множества $$R$$, а бинарная операция $$+$$ обозначает сложение нечетких множеств. Требуется найти $$\(\mathop {\min }\limits_{x \in P} \;\{ c,x\}\)$$ на заданной области.

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

    Сведем решение исходной задачи к решению ряда задач линейного программирования. Для этого введем дискретные $$\alpha$$ -уровни. В результате нечеткие ограничения принимают следующий интервальный вид:$$\begin{equation} P = \left\{ {\begin{array}{*{20}c} {\sigma _\alpha (a_{i1} )x_1 + \ldots + \sigma _\alpha (a_{in} )x_n ,} {i = 1,\ldots,m,\;\alpha = 1,\ldots,p,} \\ {x_j \geqslant 0,} {j = 1,\ldots,n.} \\ \end{array} } \right. \end{equation}$$

    Таким образом, мы перешли от нечетких множеств к четко определенным и теперь, зная, что $$\alpha$$ — обычный интервал, можем записать нашу задачу в следующем виде:$$\begin{equation} \begin{gathered} (a_{11} , a_{12}) x_{1} + (c_{11}, c_{12}) x_{2}\subseteq (b_{11} , b_{12}),\\ (a_{21} , a_{22}) x_{1} + (c_{21}, c_{22}) x_{2} \subseteq (b_{21} , b_{22}). \end{gathered} \end{equation}$$

    Теперь, чтобы привести задачу к виду обычной задачи линейного программирования, нам достаточно записать неравенства отдельно по левому и правому краям интервалов, с учетом знаков неравенства. Т.е., мы приведем систему к следующему виду:$$\begin{equation} \begin{gathered} a _{11}x_{1} + c_{11}x_{2}\ge b_{11},\\ a _{12}x_{1} + c_{12}x_{2}\le b_{12},\\ a_{21}x_{1} + c_{21}x_{2}\ge b_{21},\\ a_{2}x_{1} + c_{22}x_{2}\le b_{22}. \end{gathered} \end{equation}$$

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

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

  • Исходная задача.
  • Вводим дискретные $$\alpha$$ -уровни.
  • Ограничения принимают интервальный вид.
  • Записываем неравенства отдельно по левому и правому краям с учетом знаков неравенства (при этом размерность увеличивается).
  • Получаем задачу ЛП с четкими коэффициентами.
  • Решаем полученную задачу симплекс-методом.
  • Как видим, исходная задача нечеткого математического программирования представляется в виде совокупности обычных задач линейного программирования на всевозможных множествах уровня множества допустимых альтернатив. Если альтернатива $$x_{0}$$ есть решение задачи $$\(\mathop {\min }\limits_{x\in P} \;\{ c,x\}\)$$ на множестве уровня $$\alpha$$, то можно считать, что число $$\alpha$$ есть степень принадлежности альтернативы $$x_{0}$$ нечеткому множеству решений исходной задачи.

    Перебрав, таким образом, всевозможные значения $$\alpha$$, получаем функцию принадлежности нечеткого решения.

    Если же и компоненты целевой функции $$c_{i}$$ являются нечеткими, то необходимо выбирать для каждого уровня $$\alpha$$ соответствующие границы множеств $$\sigma_{\alpha}(c_{J})$$, $$J=1,\ldots,n$$ в соответствии с правилами интервальной арифметики, минимизируя предварительно таким образом: $$\{c,x\}$$.

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

    Модели нечеткой ожидаемой полезности

    При описании индивидуального принятия решения в рамках классического подхода, наряду с моделями математического программирования, широко применяются теория статистических решений и теория ожидаемой полезности. Последняя предназначена для анализа решений, когда неопределенность обусловлена отсутствием объективной физической шкалы для оценки предпочтительности альтернатив. В этих случаях используется субъективная шкала полезности лица, принимающего решение (ЛПР). В реальных ситуациях исходы, соответствующие принятым решениям (состояниям системы), являются подчас неточными, что влечет за собой размытость соответствующих им оценок функции полезности. Размытый вариант ожидаемой полезности формулируется, например, в модели, где выделяются и одновременно учитываются как случайные, так и нечеткие составляющие неопределенности. Выбор происходит на основе максимизации нечеткой ожидаемой полезности$$ER_j = \sum\limits_{i = 1}^n {\tilde p_i F(s_i ,a_j ,b_k )} ,$$ где $$\(\tilde p_i\)$$ — размытая вероятность состояния $$s_{i}$$ из множества состояний мира $$\(S,\;F:\quad S \times A \times B \to \wp (R)\)$$, $$A=\{a\}$$ — множество альтернатив, $$B=\{b\}$$ — множество критериев, $$R$$ — множество оценок, а $$\(\wp (R) = \{ \mu _R \;|\;\mu _R :\;R \to [0,1]\}\)$$ — класс всех нечетких подмножеств на множестве оценок $$R$$.

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

    Например, задача анализа решений формулируется следующим образом. Пусть имеются две обычные вероятности лотереи: $$A = \left[ {pu_{A_1 } ,\;(1 - p)u_{A_2 } } \right]$$, где $$p$$ — вероятность исхода с ожидаемой полезностью $$\(u_{A_1 }\)$$ и $$(1-p)$$ — вероятность исхода с ожидаемой полезностью $$\(u_{A_2 }\)$$, а $$\(B = \left[ {qu_{B_1 } ,\;(1 - q)u_{B_2 } } \right]\)$$, где $$q$$ — вероятность исхода с ожидаемой полезностью $$\(u_{B_1 }\)$$, $$(1-q)$$ — вероятность исхода с ожидаемой полезностью $$\(u_{B_2 }\)$$. Из теории ожидаемой полезности следует, что $$\(A \succ B\)$$, если$$pu_{A_1 } , + (1 - p)u_{A_2 } > qu_{B_1 } + \;(1 - q)u_{B_2 } .$$

    Будем считать, что вероятности $$p$$ и $$q$$ и ожидаемые полезности $$\(u_{A_1 } ,\;u_{A_2 } ,\;u_{B_1 } ,\;u_{B_2 }\)$$ точно не известны, т.е. введем$$\mu _P :\;P \to [0,1],\quad \mu _Q :\;Q \to [0,1],\quad \mu _U :\;U \to [0,1].$$

    Тогда, в соответствии с принципом обобщения, степени принадлежности альтернатив $$a$$ и $$b$$ множествам нечетких ожидаемых полезностей в нечетких лотереях $$A$$ и $$B$$ соответственно вычисляются$$\begin{gathered} \mu _A (a) = \mathop {\max }\limits_{pu_{A1} + (1 - p)u_{A2} = a} \;\left[ {\min \{ \mu _P (p),\;\mu _{A_1 } (u_{A_1 } ),\;\mu _{A_2 } (u_{A_2 } )\} } \right], \\ \mu _B (b) = \mathop {\max }\limits_{qu_{B1} + (1 - q)u_{B2} = b} \;\left[ {\min \{ \mu _P (p),\;\mu _{B_1 } (u_{B_1 } ),\;\mu _{B_2 } (u_{B_2 } )\} } \right]. \\ \end{gathered}$$

    В случае лотереи с $$n$$ исходами также для каждого ребра дерева решений подсчитывается значение нечеткой ожидаемой полезности.

    Вернуться к учебному плану