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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

СОДЕРЖАНИЕ:

ВВЕДЕНИЕ

1. Вспомогательные сведения из интервального анализа и многокритериальной оптимизации

1.1 Многокритериальная оптимизация: сущность и подходы к её решению

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

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

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

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

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

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

3. Модель «Планирование заработной платы сотрудникам на предприятии»

3.1 Формальная постановка

3.2 Интервальная модель задачи

3.3 Сведение задачи к однокритериальной методом направленных уступок

3.4 Решение задачи линейного программирования на примере автомагазина «ДетальДВ»

4. Численные эксперименты

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ 
 
 

ВВЕДЕНИЕ

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

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

     США (модель Уортонской ассоциации эконометрических прогнозов) – 207 уравнений;

     Канада (модель “Трейс” Торонтского университета) – 183 уравнения;

     Франция (модель “ПОМ-ПОМ” Независимого университета) – 32 уравнения;

     Великобритания (модель Лондонской школы бизнеса) – 226 уравнений;

     Япония (модель Института экономических  исследований Киото) – 78 уравнений;

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

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

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

      Планирование  производства:

суммарный чистый доход,

минимальный чистый доход за любой период,

число невыполненных заказов,

сверхурочное  время,

запасы  готовой продукции.

      Выбор портфеля ценных бумаг:

доход,

риск,

дивиденды,

отклонения  от желаемого уровня разнообразия бумаг.

      Транспортировка:

стоимость,

среднее время доставки грузов приоритетным клиентам,

производство  по заданной технологии,

расход  топлива.

      Составление сметы капиталовложений:

наличие средств,

спрос на капитальные вложения,

ежегодные эксплуатационные расходы,

инвестиции  в проекты, связанные с охраной окружающей среды,

инвестиция  в проекты в заданном регионе,

инвестиции  в проекты по заданной товарной специализации.

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

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

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

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

      Выбор принципа оптимальности. В задачах оптимизации принцип оптимальности определяет свойство оптимального решения и дает ответ на главный вопрос – в каком смысле оптимальное решение превосходит все остальные допустимые решения и дает правило поиска этого оптимального решения. Принцип оптимальности – это основная проблема задач оптимизации. Она непосредственно связана с проблемой нормализации критериев. Если не стоит проблемы нормализации критериев, то выбор принципа оптимальности ставится на первое место.

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

      Вычисление  оптимума задачи оптимизации. Сейчас достигнуты определенные успехи в области решения задач математического программирования как линейного, так и нелинейного. Но имеется много примеров, когда вычислительные схемы и алгоритмы становятся непригодными для решения задач математического программирования в результате небольших изменений и добавлений к первоначальной задаче, поэтому встает проблема – вычисление оптимума построенной задачи оптимизации. Добавим, что перечисленные проблемы так или иначе сводят многокритериальную задачу к однокритериальной, т.е. сводят к проблеме вычисления оптимума.

      Решение перечисленных  проблем и развитие методов решения задач многокритериальной оптимизации идет в нескольких направлениях. Выделим из этих направлений основные:

      - методы, основанные на свертывании  критериев;

      - методы, построенные на наложении  ограничений на критерии;

      - методы целевого программирования;

      - методы, основанные на отыскании  компромиссного решения;

      Цель  данной работы – показать механизм многокритериальной интервальной оптимизации и методы её решения.

      Задачи:

      - рассмотреть вспомогательные сведения  по интервальному анализу и  многокритериальной оптимизации;

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

      - показать методы решения интервальных задач оптимизации;

      - описать экономико-математическую  модель планирования заработной  платы сотрудникам на предприятии;

      - изучить данную модель на примере автомагазина «ДетальДВ».

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

1. Вспомогательные  сведения из интервального  анализа и многокритериальной оптимизации

      1.1 Многокритериальная оптимизация: сущность и подход к ее решению

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

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

                                           

                                             (1.1) 

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

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

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

                                                                   (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*.