9.8. многокритериальное НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
С НЕЧЕТКИМИ ПАРАМЕТРАМИ
В разд. 9.7. рассмотрена проблема многокритериальной оптимизации в ЛП и описан подход, позволяющий решить ее с использованием аппарата нечетких множеств.
Рассмотрим более общий случай задач многокритериального нелинейного программирования (МКНП) с нечеткими параметрами. Предлагаемый подход к их решению использует понятие Парето- оптимальности 
- уровня.
Парето- оптимальность -уровня.
В общем случае задачу МКНП можно записать в виде следующей задачи векторной оптимизации:
минимизировать 
(9.8.1)
при условиях 
(9.8.2)
где 
- 
-мерный вектор переменных решения;
- 
различных целевых функций;
- множество допустимых решений (МДР).
Фундаментальным понятием для задач многокритериальной оптимизации является понятие Парето- оптимального решения.
Напомним, что вектор 
называется Парето- оптимальным решением задачи МКНП тогда и только тогда, когда не существует другого вектора 
такого, что 
для всех 
, причем хотя бы для одного 
это ограничение выполняется строго.
Во многих случаях на практике в значениях параметров целевых функций и ограничений имеются неоднозначности, которые отражают неполноту знаний экспертов о реальной среде. Тогда целесообразно рассмотреть МКНП с нечеткими параметрами в описании целевых функций и ограничений:
минимизировать 
(9.8.3)
при условиях 
,
где 
- вектор нечетких параметров, включенных в целевую функцию 
и ограничения 
соответственно.
Эти нечеткие параметры предполагаются нечеткими числами, которые введены Дюбуа и Прэйдом.
Определение 9.26. Нечеткое число 
- это выпуклое непрерывное нечеткое подмножество числовой оси, функция принадлежности 
которого определяется следующим образом [20]:
1) 
2) 
для всех 
3) - строго возрастающая функция на интервале 
4) 
для всех 
5) - строго убывающая функция на интервале 
6) для всех 
где 
- действительные числа такие, что 
Возможный вид функции принадлежности для нечеткого числа приведен на рис. 9.15.
Предположим далее, что 
в нечетком МКНП являются нечеткими числами с функциями принадлежности 
соответственно. Для простоты обозначений определим следующие векторы и матрицы
Тогда можно ввести множество уровня или - сечение нечетких чисел 
и 
.
Определение 9.27. Множеством уровня 
нечетких чисел 
и 
называется множество 
, для которого степень принадлежности всех элементов превышает величину , т.е.
. (9.8.4)
Множества уровня обладают следующим свойством: 
тогда и только тогда, когда 
.
Итак, для некоторого заданного значения -задача нечеткого МКНП может трактоваться как следующая - МКНП задача вида:
минимизировать 
(9.8.5)
при условии
. (9.8.6)
Следует подчеркнуть, что в - МКНП задаче параметры 
рассматриваются как переменные, а не как константы. Используя множества уровня нечетких чисел, введем понятия Парето- оптимальных решений для нечетких - МКНП задач [62].
Определение 9.28. Вектор 
называют -Парето- оптимальным решением задачи (9.8.5), (9.8.6) тогда и только тогда, когда не существует другого 
такого, что
(9.8.7)
и строгое неравенство выполняется, по крайней мере, для одного 
, где соответствующие величины параметров 
называются оптимальными параметрами уровня .
Из свойств множества уровня вытекает следующее утверждение.
Пусть 
- Парето- оптимальные решения уровней 
и 
соответственно, 
,
- соответствующие оптимальные параметры уровня 
и задачи МКНП. Если
, то существуют 
и такие, что 
для любого 
и . Как следует из данного определения, обычно - Парето- оптимальные решения состоят из бесконечного множества точек и ЛПР должен выбрать свой компромисс или удовлетворительное решение среди - Парето- оптимальных решений, основанных на его субъективных суждениях.
Чтобы отыскать 'кандидата' на удовлетворительное решение (которое является также и Парето- оптимальным) ЛПР просят определить степень для множества - уровня, а также эталонные уровни достижения значений ц.ф., которые называются 'эталонными' уровнями.
Для указанных ЛПР степени и эталонных уровней 
соответствующее - Парето- оптимальное решение, которое отвечает требованиям ЛПР (или лучше их при условии, что эталонные уровни достижимы), получается путем решения следующей минимаксной задачи (в предположении, что разности 
имеют одинаковую важность для ЛПР):
найти 
(9.8.7)
или эквивалентно:
минимизировать 
(9.8.8)
при условиях
(9.8.9)
. (9.8.10)
Следует подчеркнуть, что минимаксная задача используется как средство генерации - Парето- оптимальных решений и, если ЛПР не удовлетворен текущим - Парето- оптимальным решением, то возможно улучшить это решение путем корректировки его эталонных уровней.
Взаимосвязи между оптимальными решениями минимаксной задачи и понятием - Парето- оптимальных решений задачи МКНП описываются следующими теоремами [62;63].
Теорема 9.6. Если 
-единственное оптимальное решение минимаксной задачи для некоторого 
, то тогда 
- - Парето- оптимальное решение для - МКНП задачи.
Доказательство. Предположим, что не является - Парето- оптимальным решением задачи МКНП. Тогда существует 
(причем 
) такой, что
.
Отсюда следует, 
, что противоречит предположению, что - единственное оптимальное решение минимаксной задачи. Отсюда - - Парето- оптимальное решение - МКНП задачи.
Теорема 9.7. Если - - Парето- оптимальное решение и 
- оптимальные параметры - уровня в - МКНП задаче, то существует вектор такой, что - оптимальное решение минимаксной задачи.
Доказательство. Предположим, что -не оптимальное решение минимаксной задачи для любого 
, удовлетворяющего условию
.
Тогда существуют 
и 
такие, что
.
Отсюда следует, 
Если любая разность 
положительна или равна 0, то это неравенство не будет выполняться. Отсюда должно выполняться 
, что противоречит допущению, что - - Парето- оптимальное решение и - оптимальные параметры - уровня. Итак, теорема доказана.
Если же оптимальное решение минимаксной задачи не однозначно, то можно проверить - Парето- оптимальность для , решив следующую задачу:
найти 
(9.8.11)
при условиях
(9.8.12)
Пусть 
- оптимальное решение задачи (9.8.11), (9.8.12). Если все 
, то - - Парето- оптимальное решение. Если же хотя бы одно 
, то можно легко показать, что 
является - Парето- оптимальным.
Уровни компромисса.
Определив - Парето- оптимальное решение для заданных величин и эталонных уровней путем решения соответствующей минимаксной задачи, ЛПР может быть либо удовлетворен текущим - Парето- оптимальным решением, либо подкорректировать его. Чтобы помочь ЛПР выразить степень его предпочтения, используется информация о компромиссе между текущей целевой функцией 
и любой другой 
, а также между степенью и значениями .
Такая информация о компромиссах может быть легко получена,так как она тесно связана со строго положительными множителями Лагранжа минимаксной задачи.
Чтобы получить эту информацию о компромиссах (замещении), определим сначала функцию Лагранжа для минимаксной задачи (9.8.7)-(9.8.10) в виде:
В дальнейшем для удобства компоненты решения в минимаксной задаче (9.8.7)-(9.8.10) будем обозначать 
. Предположим, что минимаксная задача имеет одно единственное локально - оптимальное решение, которое удовлетворяет следующим допущениям [63].
Допущение 1. 
- регулярная точка ограничений минимаксной задачи.
Допущение 2. В точке удовлетворяются достаточные условия второго порядка.
Допущение 3. В точке нет вырожденных ограничений.
Тогда справедлива следующая теорема существования [62].
Теорема 9.8. Пусть = - единственное оптимальное решение минимаксной задачи (9.8.8)-(9.8.10), удовлетворяющее допущениям 1-3. Пусть 
обозначает множители Лагранжа, соответствующие ограничениям (9.8.9), (9.8.10). Тогда существуют неперервно дифференцируемые вектор - функции 
и 
, определенные в некоторой окрестности 
такие, что 
, где 
- единственное локально оптимальное решение минимаксной задачи (9.8.8)-(9.8.10) для любого 
, удовлетворяющего допущениям 1-3 и 
- вектор множителей Лагранжа, удовлетворяющий ограничениям (9.8.9), (9.8.10).
В теореме 9.8 величина
(9.8.13)
может рассматриваться как оптимальное значение целевой функции в минимаксной задаче (9.8.8)-(9.8.10) для любого 
. Поэтому следующая теорема выполняется при тех же самых ограничениях, что и теорема 9.8.
Теорема 9.9. Если все допущения теоремы 9.8 удовлетворяются, то выполняется следующее соотношение в некоторой окрестности
. (9.8.14)
Если все ограничения (9.8.9) минимаксной задачи активные, а именно, если 
для всех , то справедлива также и следующая теорема [62;63].
Теорема 9.10. Пусть все допущения теоремы 9.8 выполняются. Предположим также, что все ограничения (9.8.9) минимаксной задачи активны. Тогда выполняется соотношение
(9.8.15)
Рассматривая уровень замещения между 
и 
для всех 
, можно доказать справедливость следующей теоремы 63.
Теорема 9.11. Пусть все допущения теоремы 9.8 выполняются. Предположим, также, что ограничения (9.8.9) активны. Тогда справедливо следующее соотношение
. (9.8.16)
Для того, чтобы можно было получить информацию о замещении выражений (9.8.15), (9.8.16), все ограничения (9.8.9) минимаксной задачи должны быть активными. Поэтому, если есть неактивные ограничения, то необходимо заменить 
для неактивного ограничения на 
и решить соответствующую минимаксную проблему для нахождения множителей Лагранжа.
Интерактивный алгоритм поиска Парето- оптимальных решений задачи МКНП.
Опишем интерактивный алгоритм для поиска решений из множества - Парето- оптимальных решений, удовлетворяющих ЛПР.
Шаг 1. Вычислить индивидуальный минимум и максимум для каждой ц.ф. 
при заданных ограничениях для 
и 
.
Шаг 2. Попросить ЛПР выбрать начальное значение (
)и начальные эталонные уровни 
.
Шаг 3. Для выбранных значений ,{ } решить минимаксную задачу и выполнить тест на проверку - Парето- оптимальности.
Шаг 4. Сообщить ЛПР соответствующее - Парето- оптимальное решение и уровни замещения (обмена) между ц.ф. и степенью . Если ЛПР удовлетворен текущими значениями ц.ф. и , то конец. Иначе - ЛПР может скорректировать эталонные уровни и (или) значение , рассмотрев текущие значения ц.ф. и вместе с уровнями (величинами) замещения между ц.ф. и , и возвратиться к шагу 3.
Следует подчеркнуть для ЛПР, что:
1) любое улучшение одной ц.ф. может быть достигнуто только за счет ухудшения, по крайней мере, одной из других ц.ф. для некоторого фиксированного
2) увеличение уровня приводит к ухудшению (уменьшению) значений ц.ф. при некоторых фиксированных значениях эталонных уровней .
Экспериментальные исследования алгоритма
решения задач МКНП.
Для экспериментального исследования интерактивного алгоритма решения задачи МКНП была выбрана следующая задача :
(9.8.17)
(9.8.18)
при ограничении
(9.8.19)
где 
- нечеткие числа с функциями принадлежности (ФП) треугольного вида с параметрами 
и 
, значения которых приводятся в табл. 9.19
Таблица 9.19.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Для нахождения решения минимаксной задачи вида (9.8.8)- (9.8.10) используется метод барьерных поверхностей (МБП), для применения которого строится барьерная функция вида:
, (9.8.20)
где - номер текущей итерации,
,
Условия остановки алгоритма такие:
(9.8.21)
где 
- оптимальное решение после - ой итерации. При оптимизации барьерной функции используется градиентный метод с переменным шагом. Эксперименты проводились при различных уровнях . Как эталонные уровни использовались значения 
та 
, заданные ЛПР. В табл.9.20 приводятся результаты экспериментальных исследований в зависимости от вариаций и значений эталонных уровней 
,
. Здесь 
и 
- достигнутые значения критериев , , -
число итераций оптимизации.
Таблица 9.20.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В следующих экспериментах было исследовано влияние выбора нечетких параметров 
из интервала 
на область допустимых решений (ОДР) и достигнутые значения критериев при 
. Конечно, что при 
получим максимальную ОДР, а при 
- минимальную.
Соответствующие результаты приведены в табл. 9.21.
Таблица 9.21.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Проанализировав приведенные экспериментальные результаты, приходим к следующим выводам.
Увеличение уровня приводит к ухудшению достигнутых значений критериев та , так как сокращается интервал 
, на котором отыскиваем 
.
Увеличение ОДР приводит к улучшению значений критериев, а уменьшение наоборот - к обратному эффекту. Уменьшая заданные значения эталонных уровней 
и 
, можно достичь улучшения значения соответствующего критерия вследствие оптимизации.
