Курсовая  на тему «Многокритериальная  оптимизация в  ИО».

Оглавление

Введение

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

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

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

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

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

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

      Задачи  работы.

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

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

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

    .

Глава 1. Многокритериальная оптимизация в  ИО: сущность и постановка задачи

      Успехи  использования математических подходов и стиля мышления в естественных науках не сразу привели к мысли  о том, чтобы включить в сферу математических приложений принятие управленческих решений и попытаться тем самым превратить древнее искусство управления в науку или ремесло. Уже ранние работы (XVIII-XIX вв.) явились важным этапом разработки и становления научного управления организациями. Усилия А. Смита (A. Smith), Ч. Бэббиджа (Ch. Babbage), Ф. Тейлора (F. Taylor), Г. Ганта (H. Gantt) и др. привели к эффективному решению ряда конкретных задач в области организации труда и производства, учета человеческого фактора в промышленности. Дальнейшие достижения в разработке математических подходов к решению задач управления в 40-50-е годы ознаменовались признанием новой научной дисциплины, названной Исследованием операций (ИО). С этого момента и по сегодняшний день ИО развивается с целью помочь руководителю научно определить свою политику и действия среди возможных путей достижения поставленной цели. [4, c. 24]

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

1.1. Исследование операций: становление как  науки

      Активное  использование достижений математики в различных областях, связанных с принятием управленческих решений, привело к становлению дисциплины, называемой «Исследования операций» (ИО). Формальные истоки ИО связывают с инициативой Алекса Питера Роу (Alex Piter Rowe), суперинтенданта Bawdsey Research Station, который использовал в 1937 г. знания британских ученых для повышения эффективности работы персонала новейшей радарной станции.

      Затем исследование операций получило развитие. Для управления … 
 
 
 
 

      ….

      Другим  стимулятором популяризации ИО был … 
 
 
 
 
 
 

      … было сформировано 26 групп. [3, c. 54-56]

      А в начале 1950-х ИО стало активно  применяться и в американской промышленности. Появление компьютера повысило осведомленность руководства о широте проблем и возможностях для их решения.

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

      В России [2, c. 64-65] становление ИО как отдельной области знаний происходило с сильным отставанием. Это было вызвано и гонениями на кибернетику в целом, и общей технической отсталостью страны.

      Формальное  рождение ИО в России связывают с  … 
 
 
 

      ...

      Рост  популярности ИО в те годы связывается с именами Гермейера Ю. Б., Бусленко Н. П., Канторовича Л. В., Моисеева Н. Н., Репьева Ю. М. и многих других ученых и руководителей крупных проектов.

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

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

1.2. Многокритериальная  оптимизация: сущность и постановка задачи

      Задача  многокритериального математического  программирования имеет вид: [1, c. 41-43]

max{f1(x)=F1}, 
max{f2(x)=F2}, 
... 
max{fk(x)=Fk}, при xєX, где

      X – множество допустимых значений  переменных х;

      k – число целевых функций (критериев);

      Fi – значение i-го критерия (целевой  функции),

      “max”  – означает, что данный критерий нужно максимизировать.

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

      При наличии в многокритериальной задаче критериев с разной размерностью с целью устранения данной проблемы используют нормализацию критериев. Способы нормализации представлены в таблице 1.1.

      Таблица 1.1.

      Способы нормализации

      В данной таблице y – элемент пространства G. G – пространство элементов произвольной природы, называемых целевыми термами (в конкретных интерпретациях это совокупность, перечень или нумерация качественных свойств) элементов xєX.

      Сверткой  компонент многоцелевого показателя fєF называется отображение gє{F->R1}, которое преобразует совокупность компонент многоцелевого показателя f, соответствующих целевым термам yєY, в скалярный целевой показатель g(f(x|y)= g[{f(x|y}yєY]єR1. Основными видами сверток являются линейные, минимизационные, максимизационные, произведения и функции Кобба-Дугласа вида:

      … 
 
 

      …

      Проблемы  получения и обоснования выбора сверток составляют основное направление теории полезности.

      К настоящему времени сформулированы основные принципы выбора, приведенные в таблице 1.2. (приложение 1)

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

      Вектор  называется оптимальным по Парето решением, если не существует хєХ такого, что выполнены неравенства

      …

      …

      Областью  компромиссов Гх называется подмножество допустимого множества решений Х, обладающего тем свойством, что все принадлежащие ему решения не могут быть улучшены одновременно по всем локальным критериям — компонентам вектора эффективности. Следовательно, для любых двух решений, принадлежащих области Гх(х', x''єГх ), обязательно имеет место противоречие хотя бы с одним из локальных критериев. Это автоматически приводит к необходимости проводить выбор решения в Гх на основе некоторой схемы компромисса, что и послужило причиной для названия этого подмножества областью компромиссов.

      Оптимальное решение, выбираемое на основе многокритериального  подхода независимо от … 
 
 
 
 

      … областью компромиссов Гх, которая, как правило, значительно уже всей области возможных решений Х.  Рассмотрим теперь некоторые методы многокритериальной оптимизации.

Глава 2. Некоторые методы многокритериальной оптимизации

2.1. Принцип справедливого  компромисса

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

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

      Этому принципу можно дать следующую математическую интерпретацию. [6] Пусть в области компромиссов Гх даны два решения х’ и х’’, качество которых оценивается критериями F1(х) и F2(х). Решение х' превосходит решение х’’ по критерию F1, но уступает ему по критерию F2. Необходимо сравнить эти решения и выбрать наилучшие на основе принципа справедливого компромисса. Для сравнения этих решений на основе принципа справедливого компромисса введем меру относительного снижения качества решения по каждому из критериев – цену уступки x:

      … 
 
 

      …           (1)

      где  DF₁ и DF₂ — абсолютные снижения уровня критериев при переходе от решения х' к решению х'' (для критерия F1) и при обратном переходе (для критерия F2).

      Если  относительное снижение критерия F1 больше, чем критерия F2, то следует  отдать предпочтение решению х'. Это  следует из сравнения цены уступки  по каждому критерию.

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

      Шаг 0. Выбираем х' и х’’є Dx.

      Шаг 1. Вычисляем по формулам (1) х1 и х2.

      Шаг 2. …

      Шаг 3. Если не существует вектора хєX предпочтительнее xI или xII, то решение останавливается, иначе выбираем новый вектор xIII и переходим к шагу 1.

      Модель  определения области компромиссов, а также модель … 
 
 
 
 
 

      … нормализацию критериев, т. е. искусственно приводить их к единой мере.

      Большинство принципов нормализации основывается на введении идеального решения, т. е. решения, обладающего идеальным вектором эффективности Fи. Это идеальное решение можно априорно предположить исходя из информации об объекте, а можно решить задачу оптимизации для каждого локального критерия и соответствующее этим решениям значение вектора эффективности принять за идеальный вектор эффективности Fи. Тогда выбор оптимального решения становится равнозначным наилучшему приближению к этому идеальному вектору Fи = (Fи , … , Fиn) В этом случае вместо действительного значения критериев рассматриваются или их отклонение от идеального значения

      …           (2)

      или их безразмерное относительное значение

      …           (3)

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

      После нормализации критериев эффективности  задача выбора решения приобретает  … 
 
 
 
 

      … Это дает возможность проводить  обоснованный выбор принципов оптимальности и выявлять их логический смысл.

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

2.2. Принцип слабой  оптимальности по Парето

    Вектор  х1єХ называется слабо оптимальным  по Парето решением (оптимальным по Слейтеру), если не существует вектора х1єХ, такого, что

    …

    Пусть xoj (i=1,m) есть оптимальные решения  для обычных скалярных оптимизационных  задач, каждая из которых максимизирует компоненту Fi(х) вектора F (х):

    …           (4)

    Если  они являются максимальными решениями  для каждой i, то считаем, что Fj(xoj) >Fi(xj) (i=1,m), где xoj — оптимальное решение задачи (4).

    Положим, что Soj изображает множество решений, каждое из которых соответствует компоненту Fj, и Soj = …       (5)

где aj представляет допустимое количество ограничений  соответствующей области по отношению  к Fj. Тогда оптимальное достаточное  решение это такое решение, при котором минимальный компонент (наихудший компонент) максимизируется на множестве, удовлетворяющем достаточному условию хєХ и хєSo1nSo2n…,Som. Оно может быть сформулировано как

…             (6)

х, z при

…             (7)

…             (8)

хєХ.             (9)

    Здесь задача (6) – (9) неразрешима, если аj не настолько  велико, что пересечение {S°j} непусто. Величины аj должны быть определены на основе значений Fj(xoj) или анализа точности. Можно доказать, что оптимальное решение задачи (6) – (9) есть оптимальное решение по Парето.

    Алгоритм  решения задачи имеет следующие  этапы.

    Шаг 1. Полагаем l=1 и решаем задачу

    max z            (10)

    х, z при

    Fj(x)>=z;

    Fi(x)>=Fj(x)oj—aj, i=1,m; хєХ.

    Вызываем  исходное решение x1 и оцениваем целевую  функцию F(x1).

     Шаг 2. Когда хl задано, разлагаем F(хl) на удовлетворительные и неудовлетворительные компоненты. Обозначим их соответственно через Sl и Sl.

     Если Sl, тогда эта задача считается  неразрешимой, а если Sl ºÆ, то х1 — оптимальное, отвечающее требованиям решение. Если S <> Æ и Sl <> Æ, то для jєSl определяется аlj>0, допустимое по отношению к Fj(xl) [аlj=0 означает, что j-я целевая функция fj(x) не может принимать значение, отличное от fj (xl)].

    Ш а г 3. Решаем задачу

    max z

    х, z

    при условии

     Fj(x)єz, jє Sl;

    Fi(x)>=Fj(x)oj—aj, jєSl; хєХ. 

    Вызываем  исходное решение xl+l. Если xl+1=xl, то задача будет неразрешимой;  если xl+1<>xl, то полагаем 1 = 1+1 и возвращаемся к шагу 2. При этом алгоритм заканчивается.

2.3. Принцип приближения  по всем локальным  критериям к идеальному решению

    В основу данного подхода положена идея приближения по всем критериям. [7]

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

    max{f1(x)=F1},

    max{f2(x)=F2},          (11)

    :

    max{fk(x)=Fk}, xєX,

     и заданы граничные условия

     …        

                       (13)

    …           (14)

    Среди решений системы (11) – (14) требуется  отыскать такое значение вектора  х*(х*1, … , х*n), при котором локальные  критерии примут по возможности максимальное (минимальное) значение одновременно.

    Рассмотрим  каждую отдельную функцию fi(x) и допустим, что для каждого фиксированного i (i=1,m) решена задача максимизации. Пусть соответствующие оптимальные планы характеризуются векторами

    … i=1,m           (15)

    На  этих оптимальных планах определим  значения критериев соответственно

    …            (16)

    Естественно, что векторы (15), определяющие векторы  точки в пространстве переменных (x1, x2,…, xn)є W, будут разными: некоторые из них могут совпадать друг с другом.

    Рассмотрим  вектор F(х) с компонентами F(x)|Foi из (15) и составим квадрат евклидовой нормы

    …           (17)

     вектора F(x) - Fo, определенного для всех xєW .

    Заметим, что Fo будет представлять собой единичный  вектор в пространстве вектора F(x). Назовем его идеальным значением вектора F(x). Поставленная задача теперь сформулируется так: дана система целевых функций (11) и даны условия задачи (12) – (14). Требуется определить точку xєW, в которой функция R(x) достигает минимума.

    Таким образом, отыскание векторно-оптимального плана xєW в данной задаче сведено к оптимизации выражения (17) на решениях системы линейных неравенств (12) – (14). Поскольку выражение (17) представляет собой квадратичную функцию переменных х1, …, хп, то задача отыскания векторно-оптимального плана свелась к задаче выпуклого программирования:

    Задана  выпуклая функция R(x), определенная на множестве xєW. Требуется отыскать точку xєW, обеспечивающую выполнение условия R(x*) = minR(x), xєW.

    Таким образом, алгоритм решения задачи (11) – (14) состоит из двух основных этапов:

    этап 1: maxFi(x), i=1, m;

    этап 2: min R(x).

2.4. Метод квазиоптимизации  локальных критериев  (метод последовательных уступок)

    В этом случае осуществляется поиск не единственного точного оптимума, а некоторой области решений, близких к оптимальному, – квазиоптимального множества. При этом уровень допустимого отклонения от точного оптимума определяется с учетом точности постановки задачи (например, в зависимости от точности вычисления величины критериев), а также некоторых практических соображений (например, требований точности решения задачи). [7]

    Вначале производится качественный анализ относительной  важности критериев; на основании такого анализа критерии располагаются  и нумеруются в порядке убывания важности, так что главным считается критерий F1, менее важен F2, затем следуют остальные локальные критерии F3, F4,.. ., Fm. Максимизируется первый по важности критерий F1 и определяется его наибольшее значение M1. Затем назначается … 
 

    …           (18)

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

    После этого находим наибольшее значение М2 второго критерия F2 на множестве X(1), т. е. при условии, что значение первого критерия должно быть не меньше, чем M1-d1. Снова назначается значение уступки d2>=0, но уже по второму критерию, которое вместе с первым используется при нахождении условного максимума третьего критерия, и т. д. Наконец, максимизируется последний по важности критерий Fm при условии, что значение каждого критерия Fr из m—1 предыдущих должно быть не меньше соответствующей величины Мr - dг; получаемые стратегии считаются оптимальными:

    …

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

1. найти M1= …
2. найти M2= …          (19)
3. …

m) найти  Mm= …

    Если  критерий Fm на множестве стратегий, удовлетворяющих ограничениям задачи m) из (19) не достигает своего наибольшего значения Мm, то решением многокритериальной задачи считают максимизирующую последовательность {xk} из последовательности множеств

Xm-1ÌXm-2Ì … ÌX1Ì X

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

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

    Шаг 1. Пусть х01 — решение задачи (19)

    max Fl(x), xєX

    Шаг 2. Пусть xok - решение задачи

    max Fk(x), xєX(k-1)

    где Xk определяется из (19).

    Шаг 3. Если k<m, то устанавливаем k=k+1 и повторяем шаг 2. Если k = m, то

    хom считаем оптимальным решением.