Eng | Rus | Ukr
Исследование операций
29.09.2004

<< prev | ^up^ | next >>

9.6. ОБЩАЯ ЗАДАЧА НЕЧЕТКОГО МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ И МЕТОДЫ ЕЕ РЕШЕНИЯ НА ОСНОВЕ ПОДМНОЖЕСТВА НЕДОМИНИРуемЫХ АЛЬТЕРНАТИВ.

Рассмотрим общие задачи НМП, которые описываются моделями типа 5 согласно классификации, приведенной в разд. 9.3. Рассмотрим в качестве примера следующую практическую задачу планирования производства на фирме.

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

максимизировать                              (9.6.1)

при ограничениях ,                     (9.6.2)

             .

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

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

После такого уточнения приходим к следующей постановке задачи НМП [20].

Задана линейная форма вида:

                            (9.6.3)

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

                        (9.6.4)

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

Формулировка задачи и ее сведение к общей задаче НМП.

Пусть  - универсальное множество альтернатив. Подмножество допустимых альтернатив описывается неравенствами, вытекающими из (9.6.4):

 ,                       (9.6.5)

где - заданные функции , ; , ,- числовые параметры, значения которых описаны в форме нечетких множеств числовой оси.

Пусть - заданные функции принадлежности этих нечетких множеств.

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

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

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

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

 .

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

    (9.6.6)

В этих обозначениях получим

 .                                (9.6.7)

Каждой альтернативе  функция  ставит в соответствие степень ее допустимости с учетом нечеткой информации.

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

Пусть - некоторые конкретные числовые значения параметров функции (9.6.3), степени их принадлежности заданным нечетким множествам равны соответственно .

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

 ,                               (9.6.8)

где     .

Окончательно получаем, что исходная задача с нечетко описанными параметрами формулируется в виде следующей общей задачи НМП [20; 37]

максимизировать нечетко заданную целевую функцию

                            (9.6.9)

на нечетком множестве допустимых альтернатив

 ,                              (9.6.10)

где  и  задаются соответственно (9.6.8) и (9.6.6).

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

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

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

                (9.6.11)

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

 .                              (9.6.12)

Допустим противное: найдется такой , для которого                        

                                                                     ( 9.6.13)                                                                                                    

Это означает (см. (9.5.15)), что при любом  и любом

 выполняется неравенство                         (9.6.14)

Выберем произвольное число  из интервала  и пусть  таковы, что .

Получим

                               

Вместе с тем для  выполняется условие . Однако в силу выбора  неравенство (9.6.14) не выполняется для  и , следовательно, не выполняется неравенство (9.6.13).

Таким образом, если все заданные нечеткие множества таковы, что имеют , то выполняются все условия теоремы 9.4. и поэтому для нахождения альтернатив, степень недоминируемости которых не меньше, достаточно решить следующую задачу:

максимизировать                                    (9.6.15)

при условиях

                  (9.6.16)

Предположим, что множество  компактно, непрерывны на , функция  также непрерывна на произведении . Нетрудно показать, что при этих условиях задача (9.6.15), (9.6.16) эквивалентна следующей задаче [20]:

максимизировать             (9.6.17)

при ограничениях

                       (9.6.18)

Действительно, пусть пара  - решение задачи (9.6.15), (9.6.16). В принятых выше предположениях функция  непрерывна на , а множество  замкнуто в . Пусть вектор такой, что . Тогда по определению множества  получаем, что . Допустим, что  не является решением задачи (9.6.17), т.е. найдутся , удовлетворяющие (9.6.18), такие , что . Это означает, что  и , т.е. пара  удовлетворяет ограничениям (9.6.16). Но тогда не может быть , так как - решение задачи (9.6.15).

Аналогично можно показать, что любое решение задачи (9.6.17), (9.6.18) есть также решением задачи (9.6.15).

2. Рассмотрим общую задачу НМП, в которой нечетко заданы параметры  функции  и параметры ограничений (9.6.5). Как показано выше, эту задачу можно записать в виде (9.6.15), (9.6.16).

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

Как было показано в разд. 9.5, функция  и естественный порядок  на  индуцируют на  нечеткое отношение предпочтения вида

 .              (9.6.19)

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

Таким образом,

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

Пересечение отношений , имеет вид

 .                  (9.6.20)

Взвешенная сумма (критериев) при условии равенства весовых коэффициентов отношений ,

 .               (9.6.21)

Пусть , - нечеткие подмножества недоминируемых альтернатив множеств ,  соответственно. Тогда результирующее подмножество недоминируемых альтернатив имеет вид

 .                         (9.6.22)

Функция принадлежности  служит основой для выбора конкретных альтернатив в общей задаче НМП.

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

Итак, рассмотрим задачу определения ч.нд. альтернативы, для которой

Из (9.6.22) получаем, что для этого необходимо и достаточно выполнения условий , .

Выясним сначала условия, при которые  есть ч.нд. альтернатива во множестве , т.е. когда .

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

Отсюда из теоремы 9.2 следует, что н.о.п.  -сильно линейное отношение. Нетрудно видеть, что - также сильно линейное отношение . Однако их пересечение этим свойством в общем случае не обладает.

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

 .  (9.6.23)

Но, поскольку , а  то  и неравенство (9.6.23) невозможно, т.е. выполняется .

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

Покажем теперь, что если  - ч.нд. альтернатива во множестве (т.е. на множестве  по отношению ), то она является таковой и во множестве .

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

Пусть , тогда из того, что - ч.нд. альтернатива в множестве  и - сильно линейное н.о.п., получаем согласно теореме 9.3, что .

Кроме того, , поскольку . Отсюда, заключаем , что неравенство    невозможно.

Итак, если  выбрано описанным выше способом, то равенство  выполняется при любом , значит - ч.нд. альтернатива в множестве .

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

Пусть исходные нечеткие множества  таковы, что существуют , для которых . При этом множество  составляют альтернативы, которые удовлетворяют условиям

                   (9.6.24)

Задача нахождения ч.нд. альтернативы аналогична задаче, рассмотренной в п.1. данного раздела.

Если выполняются введенные в ней предположения (компактность множества , неперервность функции ), то приходим к следующей задаче для нахождения ч.нд. альтернативы в множестве [20;37]

максимизировать               (9.6.25)

при ограничениях

                 (9.6.26)

Любое решение  задачи (9.6.25), (9.6.26) есть ч.нд. альтернатива в множестве , и в то же время ч.нд. альтернатива в множествах  и . Покажем, что любое решение этой задачи есть ч.нд. альтернатива и в множестве .

Действительно, нечеткое подмножество недоминируемых альтернатив множества  с н.о.п.  имеет вид

 .      (9.6.27)

Пусть  решение задачи (9.6.25), (9.6.26). Тогда, поскольку - ч.нд. альтернатива в , то при любом  выполняется условие , или . Кроме того -ч.нд. альтернатива в множестве , и, следовательно, при любом  выполняется условие  или .

Из двух последних вариантов следует, что в (9.6.27)

       (9.6.28).

Итак, .

Таким образом, любое решение задачи (9.6.25), (9.6.26) удовлетворяет условиям, , т.е. -ч.нд. альтернатива для исходной общей задачи НМП.

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

Аналогичными рассуждениями можно прийти к выводу о том, что для нахождения альтернативы, имеющей степень недоминируемости не меньшую, чем (т.е.  ) достаточно решить следующую задачу математического программирования [20]

х,с

 
максимизировать                (9.6.29)

(9.6.30)

 
при ограничениях (9.6.30)

                 (9.6.31)

Решение задачи типа (9.6.29)-(9.6.31) позволяет определить лишь некоторые из недоминируемых альтернатив с соответствующей степенью  для исходной общей задачи НМП.

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

найти

                                (9.6.32)

при ограничениях (9.6.30), (9.6.31).

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

Пример 9.14. Пусть требуется

максимизировать                                       (1)

при условиях

 ,                                                     (2)

,                                                        (3)

причем переменные - нечеткие параметры с функциями принадлежности .

Требуется решить соответствующую задачу НМП, пользуясь соотношениями (9.6.18):

максимизировать                                      (4)

при условиях (2) и

 .                                          (5)

Ограничение (5) записывают в следующем эквивалентном виде:

 .                                (6)

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

Пример 9.15. Решить следующую задачу НМП:

максимизировать                                             (1)

при условиях

 ,                                                     (2)

,                                                              (3)

где переменные  - нечеткие параметры с функциями принадлежности  и , где

 .

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

Соответствующая задача МП записывается в виде (1)-(3) при дополнительных ограничениях вида

                                   (4)

                                                    (5)

После неложных преобразований ограничения (4), (5) приводятся к виду

                    (6)

                                                     (7)

Далее возможно выбрать любые значения  из интервалов (6), а  из интервалов (7).

Таким образом, данная задача, как и предыдущая, приводится к задаче ЛП с параметрами.

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004