Механизм многокритериальной интервальной оптимизации

                                                                   (1.2)

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

                                           

                                          (1.3) 

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

      1.2 Метод решения задачи многокритериальной оптимизации, основанный на свертывании критериев

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

                             

                               (1.4) 

Рис 1. Графическое изображение методики решения задачи (1.4)

                                         

     Область значений ЗМО (1.1) будет определяться как множество всех возможных значений целевых функций, которые мы получаем при всех допустимых значениях аргумента  x X: 

                   

                       (1.5) 

      В результате решения, получившейся после  свертывания критериев, однокритериальной задачи (1.4), мы получили точку оптимума x*.

      Основным  достоинством свертки (1.4) является то, что с ней связаны классические, достаточные и необходимые условия оптимальности по Парето.

      Теорема 1.1 (Карлин С.)

      В выпуклой ЗМО (1.1) точка  оптимальна по Парето, если существует вектор весовых коэффициентов , , для которого выполняется соотношение  

 

      Теорема 1.2 (Карлин С.)

      Если  в выпуклой ЗМО (1.1) точка оптимальна по Парето, если существует вектор весовых коэффициентов , , для которого выполняется соотношение  

 

      1.3 Метод направленных уступок для решения задачи многокритериальной оптимизации

      При решении ЗМО (1.1) методом последовательных уступок вначале вводится общий параметр λ и каждому из критериев присваивается своя константа (k_1,,...,k_m), задающая направление, при условии, что k₁>0, k₁>0,…, k_m>0. Произведения параметра λ на коэффициент k₁ будет определять минимальную границу области, в которой будет находиться область значений рассматриваемого критерия, для второго критерия минимальную границу будет определять произведение параметра λ на коэффициент k₂ и так соответственно для всех остальных критериев. После этого максимизируем все по параметру λ в рассматриваемых областях. Таким образом, получается задача однокритериальной оптимизации с m ограничениями (1.6):  

                                                     

                                             (1.6) 

      Область значений ЗМО (1.1) выглядит как (1.5).

Решив задачу однокритериальной оптимизации (1.6) мы получим точку оптимума x*.

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

 

      После преобразований получим однокритериальную  задачу: 

                                                      

                                                (1.7) 

Рис 2. Графическое изображение методики решения задачи (1.7)  
 
 
 
 

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

2.1 Постановка задачи

      В ЗМО (1.1) все m критериев определенны точно, теперь задачу сформулируем для случая многокритериальной оптимизации, когда все её критерии определенны на интервалах. Задача многокритериальной интервальной оптимизации (ЗМИО) будет выглядеть следующим образом:  

                                  

                                (2.2)                                                     

где – множество значений переменных x, ”max” – символ, означающий, что данный критерий нужно максимизировать. Также каждый критерий можно представить в таком виде: 

        

       (2.3) 

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

2.2 Метод свертывания векторного критерия в суперкритерий

     Рассмотрим задачу многокритериальной интервальной оптимизации (ЗМИО) (2.2).

      Для начала определим область значений ЗМИО (2.2) как множество всех возможных  значений интервальных целевых функций, которые мы получаем при всех допустимых значениях аргумента x X: 

     

 

     В пункте 1.2 была применена аддитивная свертка для задачи ЗМО (1.1), теперь аналогично ей применим аддитивную свертку для ЗМИО (2.2) и получим задачу однокритериальной интервальной оптимизации (3.1): 

                                    

                           (3.1) 

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

                                      

                             (3.2) 

     Тогда задача (3.1) будет являться задачей  однокритериальной интервальной оптимизации  с нормировкой критериев (3.3): 

                      

          (3.3) 

           Для упрощения задачи (3.1) произведем небольшие преобразования: 

     

 
 

где

 

Таким образом, после этих преобразований мы получили задачу (3.4): 

                                   (3.4) 

     Определение: Точка является точкой локального ρ-максимума функции l(α,x) на множестве X, если найдется такая её окрестность C, что для всех справедливо неравенство: 

     

                      (3.5) 

     Число r является нижней оценкой показателей интервальных неравенств в окрестности точки x*. Так как неравенство (3.5) должно выполняться и при х = х*, то  . Если , то каждая точка локального 0-минимума функции l является точкой обычного локального минимума функции - её центра. Перепишем неравенство (3.5) в виде:  

           

                           (3.6) 

где радиусы интервалов >0.

      Множество точек локального ρ- минимума будет выглядеть так: 

 

      Теорема 3.1 В области множество X*(ρ) точек локального ρ- минимума монотонно по включению при , т.е. если , то .

Доказательство:

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

    

.                   (*) 

Т.к. по условию неравенство  , то

,

а из определения  и соотношения (3.6) следует, что 

,

где

.

Мы показали, что условие (*) выполняется, а это  значит, что  . Теорема доказана.

      Таким образом, точка x* является решением ЗМИО (2.2), если она удовлетворяет неравенству (3.6). 

2.3 Метод направленных уступок

     Рассмотрим задачу многокритериальной интервальной оптимизации (ЗМИО) (2.2). Но каждый критерий задачи запишем в виде (2.3). Т.е. ЗМИО будет выглядеть так:  

            

                 (3.7) 

      Определим область значений ЗМИО (3.7) как множество  всех возможных значений интервальных целевых функций, которые мы получаем при всех допустимых значениях аргумента x X: 

     

. 

     Выпишем для ЗМИО (3.7) однокритериальную задачу оптимизации с помощью метода направленных уступок:  

                                    

                                          (3.8) 

Воспользуемся определением показателя интервального  неравенства: 

 

Радиусы интервалов , значит мы можем переписать задачу (3.8) в следующем виде: 

                                        

                                        (3.9) 

Таким образом мы привели ЗМИО (3.7) к  неинтервальной задаче однокритериальной  оптимизации с m ограничениями (3.9), которую можно решить и найти искомое значение x*.