ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 2, с. 207-212
УДК 519.658
АЛГОРИТМ ПЕРЕСЧЕТА ОБРАЗУЮЩИХ КОНЕЧНОПОРОЖДЕННОГО НЕЧЕТКОГО КОНУСА ПРИ ДОБАВЛЕНИИ ОБРАЗУЮЩЕЙ К ЕГО ДВОЙСТВЕННОМУ КОНУСУ1
© 2015 г. О. В. Басков
(199034 Санкт-Петербург, Университетская наб., 7-9, Санкт-Петербургский гос. ун-т)
e-mail: ov.japh@gmail.com Поступила в редакцию 08.11.2013 г.
Исследуется задача о нахождении образующих нечеткого конуса, двойственного к заданному конечнопорожденному нечеткому конусу. Рассматривается случай, в котором изначально известны образующие пары нечетких взаимодвойственных конусов, а затем к одному из них добавляется одна или несколько образующих. Приводится алгоритм нахождения образующих двойственного к нему нечеткого конуса. Алгоритм может найти применение в задачах многокритериальной оптимизации. Библ. 5.
Ключевые слова: теория нечетких множеств, нечеткий конус, алгоритм нахождения образующих двойственного к нему нечеткого конуса, многокритериальная оптимизация.
DOI: 10.7868/S0044466915020040
1. ВВЕДЕНИЕ
В последние десятилетия в связи с развитием теории нечетких множеств много работ посвящается обобщениям известных результатов на нечеткий случай. В данной статье рассматривается обобщение на нечеткий случай задачи, решаемой алгоритмом Моцкина—Бургера (см. [1]), а именно задачи построения образующих двойственного конуса по известным образующим исходного конуса.
Эта задача относится к чисто математической области выпуклой геометрии, однако алгоритм широко применяется на практике. Так, например, при сужении множества Парето в многокритериальной задаче принятия решений с помощью определенного рода информации об отношении предпочтения лица, принимающего решение, возникает отношение двойственности между конусом отношения предпочтения и конусом, порожденным критериями. В [2] предложены алгоритмы учета информации об отношении предпочтения, опирающиеся как раз на построение образующих двойственного конуса. При переходе к нечеткой информации об отношении предпочтения возникает задача построения нечеткого двойственного конуса. В данной статье приводится алгоритм, который разработан для решения именно такой задачи.
В литературе, посвященной теории нечетких множеств, достаточно хорошо исследованы конусы, выпуклые и замкнутые множества (см., например, [3], [4]). Однако вопрос о двойственности нечетких конусов, по всей видимости, еще не получил достаточного освещения.
В четком случае алгоритм Моцкина—Бургера описывает, как изменяются образующие конуса C, если к его двойственному конусу D добавить одну образующую. Пусть исходный конус задан своими образующими a1, ..., ap и требуется построить двойственный к нему конус. Для этого полагают C = Rm, D = {0}, а затем последовательно добавляют к D образующие а1, ..., ap. Послеp итераций алгоритма C дает искомый двойственный конус. В нечетком случае применим этот же подход.
2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
Нечеткое множество А задается функцией принадлежности А, которая каждому вектору х е Ят ставит в соответствие число из [0; 1], характеризующее степень принадлежности вектора х этому множеству (см. [5]). Если А,А(х) = 0, говорят, что х £ А.
1) Работа выполнена при финансовой поддержке РФФИ (код проекта 11-07-00449).
Определение (см. [3]). Нечеткое множество A называется выпуклым, если Vx, y е Rm, Va е е (0; 1) ^ ^A(ax + (1 — a)y) > min{^A(x); ^A(y)}.
Определение (см. [4]). Замыканием нечеткого множества A называется нечеткое множество clA с функцией принадлежности
^clA (X) = sup {a е [ 0, 1 ]\x е cl {z е Rm\XA (z) > a}}.
Определение (см. [3]). Нечеткое множество A называется конусом, если Vx е Rm, Va > 0 ^ ^ XA(ax) = ^A(x).
Условимся, что в данной статье степень принадлежности нулевого вектора любому конусу считается равной единице.
Среди выпуклых нечетких конусов следует выделить класс конечнопорожденных нечетких конусов, т.е. конусов, представимых в виде конической комбинации конечного числа векторов, называемых образующими. В отличие от четкого случая для полного задания нечеткого конеч-нопорожденного конуса помимо образующих необходимо указывать и степень принадлежности их порождаемому конусу.
Определение. Нечеткая коническая комбинация векторов а1, ..., ap со степенями принадлежности a1, ..., ap — наименьший выпуклый нечеткий конус, содержащий эти векторы с не менее чем заданными степенями принадлежности.
Другими словами, функция принадлежности нечеткой конической оболочки С векторов а1, ..., ap со степенями принадлежности a1, ..., ap удовлетворяет условию Vk ^ ^c(ak) > ak, и, кроме того, для любого нечеткого выпуклого конуса D, удовлетворяющего этому условию, Vx е е Rm ^ A,c(x) < XD(x).
Более конструктивно функцию принадлежности нечеткого конечнопорожденного конуса задает следующее
Утверждение 1. Функция принадлежности нечеткой конической комбинации векторов а1, ..., ap со степенями принадлежности a1 > a2 > ... > ap задается равенством X(x) = max(ak : x е cone{a1, ..., ak}}. Здесь cone{a1, ..., ak} обозначает четкую коническую комбинацию векторов a1, ..., ak, a максимум по пустому множеству считается равным 0, так что X(x) = 0 в случае x £ cone{a1, ..., ap}.
Отсюда видно, что нечеткий конечнопорожденный конус представляет собой "наслоение" четких конусов с различными степенями принадлежности.
Наконец, введем понятие двойственного нечеткого конуса. В четком случае двойственный ко множеству С конус определяется как D = {x е Rm : 3y е C ^ xy > 0}, т.е. в D не входят векторы x е е Rm : 3y е C : xy < 0. В такой форме это определение несложно обобщить на нечеткий случай.
Определение. Нечеткий конус D, двойственный к заданному нечеткому множеству C, задается функцией принадлежности XD(x) = inf (1 - XC(y)).
y e R : xy < 0
Можно показать (см. утверждение 2 в приложении), что двойственный нечеткий конус действительно является нечетким конусом, причем всегда выпуклым и замкнутым.
3. ПОСТАНОВКА ЗАДАЧИ
Рассмотрим формальную постановку задачи пересчета образующих нечеткого конуса С при добавлении образующей к его двойственному конусу Б. Пусть взаимодвойственные нечеткие конусы С и Б заданы своими образующими: С есть нечеткая коническая оболочка векторов Ь1,..., Ьр со степенями принадлежности р1, ..., рр, а Б есть нечеткая коническая оболочка векторов и1, ..., И со степенями принадлежности v1, ..., Vq. Добавим к Б образующую п со степенью принадлежности V и обозначим получившуюся нечеткую коническую оболочку векторов и1, ..., п11, п со степенями принадлежности v1, ..., Vq, V через Б. Поставим задачу нахождения образующих нечеткого конуса С', двойственного к Б'.
В четком случае известно, что образующие конуса являются нормалями к граням двойственного конуса, поэтому добавление образующей равносильно пересечению двойственного конуса с полупространством. В нечетком случае справедливо аналогичное
Утверждение 3. Пусть
Г1, пх > 0, у(х) = <|
[ 1 - V, пх < 0.
Тогда Ух е Ят ^ ^С-(х) = ш1п{^С(х); у(х)}.
Таким образом, С' есть пересечение С с полупространством, задаваемым функцией принадлежности у. Поставленная задача тогда сводится к нахождению образующих нечеткого конуса, получающегося после пересечения исходного конечнопорожденного нечеткого конуса с заданным полупространством.
4. АЛГОРИТМ
Основываясь на структуре конечнопорожденного конуса, проведем следующие рассуждения. Структура конуса в неотрицательном полупространстве не изменится, поэтому все образующие Ьк : Ькп > 0 включаются в С'. В отрицательном полупространстве все слои должны иметь степень принадлежности не выше 1 — V, значит, если некоторая образующая Ьк : Ькп < 0 имеет степень принадлежности рк > 1 — V, ее следует уменьшить. Образующие расположены на границе слоев, поэтому новые могут появиться только в полуплоскости, нормальной к п.
Формально алгоритм описывается следующим утверждением.
Утверждение 4. Нечеткий конус С' может быть представлен в виде нечеткой конической оболочки следующих векторов:
1. Ь' со степенью принадлежности р' для ' : пЬ' > 0;
2. Ь1 со степенью принадлежности ш1п{ру-; 1 — V} для ] : пЬ1 < 0;
3. (пЬ')Ь1 — (пЬ)Ь' со степенью принадлежности шт{р;; ру} для ] : пЬ1 < 0 < пЬ'.
5. ПРИМЕР
Проиллюстрируем данный алгоритм примером его применения. Начнем с самодвойственного конуса С = Б, порожденного естественным базисом пространства Я3: (1; 0; 0), (0; 1; 0), (0; 0; 1). Степень принадлежности каждого вектора считаем равной единице, так что конус четкий. Добавим теперь к Б образующую (1; —1; 0) со степенью принадлежности 0.2 и обозначим получившийся конус за Б'. Образующие С тогда разделяются на три группы: лежащая в положительном полупространстве (1; 0; 0), в отрицательном полупространстве (0; 1; 0) и в нормальной полуплоскости (0; 0; 1). В соответствии с алгоритмом С" задается следующими образующими: (1; 0; 0), (0; 0; 1), (1; 1; 0) со степенью принадлежности 1 и (0; 1; 0) со степенью принадлежности 0.8.
Процесс добавления образующих можно продолжать. Пусть Б" есть нечеткий конус, получающийся из Б' добавлением образующей (1; 1; —1) со степенью принадлежности 0.2. Алгоритм тогда дает двойственный к Б" конус в виде нечеткой конической оболочки векторов: (1; 0; 0), (1; 1; 0), (1; 0; 1), (1; 1; 2) со степенью принадлежности 1 и (0; 0; 1), (0; 1; 0) со степенью принадлежности 0.8.
Если теперь добавить образующую (2; 1; —3) со степенью принадлежности 0.1, то новый двойственный конус по алгоритму будет задаваться следующими образующими: (1; 0; 0), (1; 1; 0), (3; 0; 2), (5; 2; 4), (4; 1; 3), (6; 6; 6) со степенью принадлежности 1, (1; 0; 1), (1; 1; 2) со степенью принадлежности 0.9 и (0; 0; 1), (0; 1; 0) со степенью принадлежности 0.8. Однако видно, что векторы (4; 1; 3) и (5; 2; 4) могут быть получены конической комбинацией векторов (3; 0; 2) и (6; 6; 6), поэтому их включение в список образующих излишне.
6. ВЫВОДЫ
Приведенный алгоритм позволяет найти образующие нечеткого конуса при добавлении образующей к двойственному конусу. Если добавляется не одна, а несколько образующих, алгоритм можно применять последовательно.
К недостаткам можно отнести тот ф
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.