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

<< prev | ^up^ | next >>

9.8. многокритериальное НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
С НЕЧЕТКИМИ ПАРАМЕТРАМИ

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

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

Парето- оптимальность -уровня.

В общем случае задачу МКНП можно записать в виде следующей задачи векторной оптимизации:

минимизировать               (9.8.1)

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

где - -мерный вектор переменных решения;

 -  различных целевых функций;

 - множество допустимых решений (МДР).

Фундаментальным понятием для задач многокритериальной оптимизации является понятие Парето- оптимального решения.

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

Text Box: 
Рис. 9.15
 Во многих случаях на практике в значениях параметров целевых функций и ограничений имеются неоднозначности, которые отражают неполноту знаний экспертов о реальной среде. Тогда целесообразно рассмотреть МКНП с нечеткими параметрами в описании целевых функций и ограничений:

минимизировать  (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.

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

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

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

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004