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

Оглавление

 

Введение

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

      Методы  решения задач математического  программирования с одним критерием интенсивно разрабатывались последние 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: