§ 9.1. Модели нечеткого математического программирования

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

альтерпатив: ценность, полезность, стоимость, качество и т. п. Нечеткость в постановке задачи математического программирова- Дия может содержаться как в описании множества альтернатив, так и в описании целевой функции. Различные формы описания исходпой информации обусловливают существование различных формулировок задач нечеткого математического программирования (НМП): а) задача достижения нечетко поставленной целн при нечетких ограничениях; б) задача НМП при нечетком множестве допустимых альтернатив; в) нечеткий вариант стандартной задачи математического программировання со «смягчением» целевой функции и/или ограничений, где вместо задачи оптимизации решается задача удовлетворения цели и соответствующие неравенства для целевой функции и ограничений могут нарушаться; г) задача программирования с нечеткими коэффициентами и др.

По Веллману — Заде [82, 23] задача достижения нечетко поставленной цели при нечетком ограничении решается на основе принципа слияния. Нечеткая цель G и нечеткое ограничение С описываются нечеткими подмножествами универсального множества альтернатив X, т. е. соответственно функциями (іа: X-*■ [О, 1] и (іс: X ^ [О, 1] из = X ^ [О, 1]}. При этом нечеткое

решение определяется как нечеткое подмножество Z) множества X, получающееся в результате слияния нечетких целей и нечетких ограничений ЛПР, * f^c, где * — некоторая бинарная операция, вводимая в 9~(Х). В общем случае, когда у ЛПР имеется п нечетких целей и т нечетких ограничений, нечеткое решение записывается в виде fij) = ... *    * • • • * Конкретно, нечеткое решение D определяется [82] как результат операции:

1)   пересечения I (взятия минимума) нечетких множеств целей и ограничений ficf = HCj Л • • • Л Л Л • • • Л

2)   пересечения II (перемножения) нечетких множеств целей и ограничений •. • •(см. табл. 1.1);

3)   линеііной комбинации нечетких множеств целей и ограничений

Отметим, что цсп (^) ^ FIdj (•^) ^ (•^) ѴжеХ.

В [117] при определении нечеткого решения используется формула

откуда пересечение II получается как частный случай, когда параметр ^ = 1- Для учета различной значимости целей и ограничений нечеткое решение можно сформулировать не только как их выпуклую комбинацию с весовыми коэффициентами а,-, Р,-, і = 1, га; 7 = 1, т, т. е. как JIDjji», но также в виде =

“п

= * ... » , где * — пересечение типа I или II нечетких множеств, а а,- (і=1, ..га) — коэффициенты важности, отражающие вес в решении [159]. Рациональную шкалу важности можно получить, применяя основанную на попарных сравнениях процедуру Саати (см. гл. 10).

Как пример рассмотрим задачу выбора варианта проектного решения, когда цели и ограничения выражены следуюпщм образом:

G: спроектировать конструкцию, радиус R которой должен быть «приблизительно 300 330 мм»,

С: согласно ограничениям по технологичности, должен быть «не менее 310 мм».

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

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

На практике чаще встречаются ситуации, когда цели и ограничения — нечеткие подмножества в разных пространствах альтернатив и результатов (причин и следствий) — соответственно X я Y. Пусть нечеткие цели заданы на множестве результатов Y: HGjS^(y), і = 1, ..га, а нечеткие ограничения — на множестве альтернатив X: ^ {X)t / = 1, ..., т. Если известно отображение ф: Х^ Y, то используя понятие прообраза fio

нечеткого множества целей Цс при отображении ф: |.ів(а:) = = (гс(ф(а:)) ѴжеХ, легко сводим данную задачу к предыдущей, в которой цели и ограничения находятся в одном и том жѳ пространстве. Решение можно записать в виде

[Id (х) = fiGj (ф (х)) * ... * (Ф (х)) * ncj (а:) * ... * \іСт (х) Ѵж е X.

Наиболее общим является случай, когда само отобран?ение

нечеткое, т. е. ф;Х->У или |.ц: ХХУ->-[0, 1]. Это означает, что каждая конкретная альтернатива х^Х может привести к нечеткому подмножеству последствий на множестве результатов Y. В [50] решение этой задачи определяется в виде максимального по отношению вложенности нечеткого множества, удовлетворяющего условиям: а) допустимости решения [Лі)^\іср j == і, ..тп и б) достижения поставленных целей ф (\іо) ^ і = 1, ..., п.

Модели решения задачи нечеткого математического программирования при нечетком множестве допустимых альтернатив предложены в работах [47, 48, 53, 74, 117, 130, 131, 134, 139— 141, 152, 156, 160]. В [74, 133, 152] нечеткая цель рассматривается как обобщенная форма заданного критерия качества, причем ее функция принадлежности вводится на основе нормализации этого (ограниченного) критерия качества с сохранением линейного порядка. Далее применяется принцип слияния, и с помощью четких множеств уровня Ca^=^ {х ^Х\\іс{х)'^ at е [О, 1] для нечетких ограничений |.іс рассматриваемая задача нечеткой оптимизации — найти

— сводится к семейству обычных четких задач оптимизации вида

Однако, поскольку работать с семействами множеств трудно, естественно стремиться к аппроксимации нечеткого множества четким. В [134] для оценки точности такой аппроксимации вводится чебышевская норма | ||: (X) -> [0,1], || || = sup | (гл(з;)

xsX

= sup (х) и считается, что обычное множество А ^ X анпрок-

симирует нечеткое множество {.іл ^ 9~(Х) с точностью е > О, т. е.

если І}ІА —/а1<6, где /а — характеристическая функция множества А.

В [139] предлагается другой подход к решению задачи НМП с нечетким множеством допустимых альтернатив; изложены два варианта решения этой задачи. Первый вариант опирается на разложение нечеткого множества ограничений на множества

уровня и представлении задачи НМП в виде семейства обычных задач оптимизации целевоіі функции ф на множествах уровня Са- Но в отличие от вышеприведенной методики здесь вводится подмножество таких элементов множества Са, где функция ф(а:) достигает своего максимума;

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

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

Этому нечеткому решению, определенному в X, соответствует нечеткое значение целевой функции ф(а:) в Я, которое есть образ нечеткого множества альтернатив при отображении ф,

где ф-1 (г) = {а: е XI ф {х) = г}.

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

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

Стандартная задача математического программирования — это отыскание тахф(а:) при ограничениях i|3(a;)<0, х^Х. Нечеткий вариант этой задачи означает, что ограничения смягчаются, т. е. допускается возможность их нарушения с той или иной степенью. Более того, вместо задачи максимизации можно поставить задачу достижения некоторого наперед заданного значения функции ф(а;), соответствующего удовлетворению исходной цели. Тогда общая задача гибкого математического программирования формулируется следующим образом: сделать (f{x)^Zg при ограничениях 'ф (а;) § О, а; е X, где ~ означает, что неравенства могут нарушаться. Согласно подходу, развиваемому в [117, 172], вводятся пороги аж Ь такие, что неравенства ф(а;)<го — а ж ■ф(а:)> > Ь означают сильное нарушение исходных неравенств if (х) ^ Zq и 'ф(а:)=^0 соответственно. Функции принадлежности нечетких целей и ограничений определяются в виде:

где [Л, ѵ: X-> [О, 1] — функции, характеризующие степени выполнения соответствующих неравенств. Далее применяется принцип слияния целей и ограничений и для случая линейного программирования: найти ф(х) == сх ^ Zg при Ах ^Ь,х>0 (где с — вектор коэффициентов целевой функции, Ъ — вектор ограничений, а А — матрица коэффициентов) доказывается, что эта задача сводится к решению обычной задачи векторной оптимизации. В [136] этот вывод обобщается для функций принадлежности произвольного вида.

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

П

ствами вида S ^ Ьі или в матричной форме Ах < Ь, выра^ г=1

жается с помощью конечной суммы непустых выпуклых мно-

жеств, вложенных в заданное множество XiAt + х2А2 +...+ хпАп s si [148]. Когда Aj (/=1, . •п) — выпуклые нечеткие множества, А — также нечеткое множество, т. е.   ^”*->[0,1], цА: &т -*■ [0, 1], а операция + означает сложение нечетких множеств (см. гл. 1), то, переходя к множествам сильного уровня, легко решаем задачу их представления с помощью обычных множеств с ограничениями по включению [47]. Рассмотрим вариант линейного программирования с нечеткими коэффициентами [131, 132]. Здесь при формулировании ограничений вместо чисел (коэффициентов Ьі) используются интервалы [Ь,-, 5,]. Таким образом, учитывается, что в реальных задачах планирования требуется выбрать такое число {},• из [Ь„ 5(], чтобы неравенства

П

2    аахі ^ Рг задавали допустимую область, а {$« (например, ана-

5=1

лизируемая стоимость) была по возможности близкой к Ь{ (минимальная возможная для данного проекта стоимость). Степень близости р,- к Ьі удобно представить с помощью нечетких множеств ц,: &п ->• [0, 1] с носителем [Ъі, 23*] (і = 1, ..., т), где Рі^[Ь,-, 5і] означает, что ^(^^О. Тогда задача нечеткого линейного программирования (НЛП) формулируется так: найти вектор х = (хі, ..., хп)<^Яп такой, что для любого і (і = 1, ...

П    П

т.) 2 anxi s [bj, ВД и разность 2 anxj — мала. Если j=1 ^’=1

Bi~ Pi

взять функцию принадлежности вида [i (Р;) = и обозна-

і    г

чить тіпЦі(а:) через жп+1, то приходим к несложной задаче: найти max хп+1 при 2 аИх) + О^і — &і) хп+і < Віш

В [102] неточно известные коэффициенты моделируются с помощью нечетких чисел (L — R)-типа; задача робастного*) программирования принимает вид: определить тах(с1х1 +... 4- спхп) при

Сі(х„ ..., хп)> Ьі (і = 1, ..., т); (с}, Xj)^&2, х,>0.

Здесь Сі = (С;, Сі, Сі), где С, — вектор средних значениіі, а С,- и Сі соответственно левый и правый параметры нечеткости. Из определения нечеткого ограничения видно, что исходная задача с т нечеткими коэффициентами преобразуется в классическую задачу линейного программирования с 3т ограничениями, которую можно решить обычным симплекс-методом.