Помощь в написании студенческих работ
Антистрессовый сервис

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

КурсоваяПомощь в написанииУзнать стоимостьмоей работы

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

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования

«Брестский государственный университет имени А. С. Пушкина»

Юридический факультет

Кафедра экономики и управления

Курсовая работа

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

Выполнила: Савчук Е. Н.

Проверила: Сендер Л. М.

Брест 2011

СОДЕРЖАНИЕ ВВЕДЕНИЕ

1. МНОГОКРИТЕРИАЛЬНАЯ ОПТИМИЗАЦИЯ И МЕТОД РАВНЫХ НАИМЕНЬШИХ ОТКЛОНЕНИЙ

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

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

2. ИСПОЛЬЗОВАНИЕ МЕТОДА РАВНЫХ И НАИМЕНЬШИХ ОТКЛОНЕНИЙ

2.1 Решение задачи линейного программирования по двум критериям

2.2 Решение задачи линейного программирования по трем критериям ЗАКЛЮЧЕНИЕ СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

· дать определение «многокритериальной оптимизации», выделить ее особенности и возможности;

· определить существующие проблемы многокритериальной оптимизации и пути их решения;

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

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

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

1 МНОГОКРИТЕРИАЛЬНАЯ ОПТИМИЗАЦИЯ И МЕТОД РАВНЫХ НАИМЕНЬШИХ ОТКЛОНЕНИЙ

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

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

Решения, в которых значения всех критериев являются наилучшими одновременно, называют наиболее эффективными, компромиссными и субоптимальными, а проблему нахождения оптимальных решений по нескольким критериям — векторной (многокритериальной) оптимизацией. [1, с. 389] многокритериальный оптимизация равный отклонение

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

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

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

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

Задачи оптимизации на множестве этапов функционирования. Рассматривается функционирование объектов на некотором интервале времени, разбитом на несколько этапов. Качество управления на каждом этапе оценивается частным критерием, а на множестве этапов — общим векторным критерием.

Многокритериальные задачи можно также классифицировать по другим признакам: по вариантам оптимизации, по числу критериев, по типам критериев, по соотношениям между критериями, по уровню структуризации, наличию фактора неопределенности.

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

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

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

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

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

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

Решение перечисленных проблем идет в нескольких направлениям:

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

· методы, использующие ограничения на критерии;

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

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

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

Варианты решений характеризуются различными показателями эффективности, называемыми критериями. Один критерий C выдвигается тогда, когда цель действий единственна. На практике часто встречается ситуация, когда эффективность приходится оценивать не по одному, а сразу по нескольким показателям C1, C2,…, Ck. Одни из этих показателей желательно сделать больше, другие — меньше. При этом экстремальное значение критерия должно быть не хуже допустимого, устанавливаемого требованиями по эффективности.

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

Критерий можно представить:

* скалярной, векторной функцией и системой ограничений,

* одним лишь набором ограничений,

* качественными требованиями,

* предпочтениями, задаваемыми ЛПР на множестве возможных способов или вариантов действий и т. д.

Решения, принимаемые по одному критерию или предпочтению, называют простыми; решения, принимаемые по нескольким критериям и/или предпочтениями, — сложными.

Примеры критериев:

* прибыль о реализации продукции предприятия;

* рентабельность капитальных вложений;

* производительность труда при условии обеспечения заданного качества изделий;

* вероятность обнаружения неисправности электронной схемы в течение установленного времени;

* среднее время ожидания в очереди на прием к врачу;

* вероятность правильного обнаружения сигнала или распознавания объекта.

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

В общем случае не существует решения, которое обращало бы в максимум один критерий C1 и одновременно в максимум (или минимум) другой критерий C2. Тем более такого решения не существует для нескольких критериев. Компромисс между критериями может быть найден только на основе предпочтений ЛПР. Средством решения многокритериальных задач с объективными моделями являются процедуры, которые представляют собой процесс взаимодействия ЛПР и компьютера. Каждый шаг такой процедуры состоит из фазы анализа выполняемой ЛПР, и фазы расчета, выполняемой компьютером.

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

Математическая модель. Пусть D - произвольное множество, элементы которого называются допустимыми решениями или альтернативами, C1, …, Cт - числовые функции (целевые функции, критерии), заданные на множестве D. Требуется найти оптимальное решение из множества D, максимизирующее функции C1, …, Cт на множестве D:

Нормирование критериев. При решении многокритериальной задачи довольно часто выполняется нормирование - приведение критериев к единому масштабу и безразмерному виду. Для этого используется замена абсолютных значений критериев их:

1) безразмерными относительными величинами

2) относительными значениями отклонений от оптимальных значений критериев

[3 с. 72−73]

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

полнота (использование любых дополнительных критериев не меняет результатов решения, а отбрасывание хотя бы одного из выбранных критериев меняет результат);

· операциональность (каждый критерий должен иметь понятную для ЛПР формулировку, ясный и однозначный смысл, характеризовать определенный аспект решения);

· декомпозируемость (набор критериев должен позволять упрощать оценивание предпочтений путем разбиения первоначальной задачи на отдельные более простые подзадачи);

· неизбыточность (разные критерии не должны учитывать один и тот же аспект решения);

· минимальность (аспект решения должен содержать как можно меньшее число критериев);

· измеримость (каждый критерий должен допускать возможность количественной или качественной оценки степени достижения соответствующей цели).

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

Планирование очистки нефти

min {затраты}

min {количество импортируемой сырой нефти}

min {количество сырья с высоким содержанием серы}

min {отклонения от заданного состава}

min {сгорание газов}

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

max {суммарный чистый доход}

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

min {число невыполненных заказов}

min {сверхурочное время}

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

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

max {доход}

min {риск}

max {дивиденды}

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

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

min {стоимость}

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

min {расход топлива}

max {производство по заданной технологии}.

1.2 Метод равных и наименьших отклонений в многокритериальной оптимизации Метод равных и наименьших отклонений применяется, когда все критерии равнозначны и в компромиссном плане относительные отклонения всех критериев от своих оптимальных значений должны быть равны и минимальны. [5, с. 40]

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

Условие равенства отклонений запишем в виде

где — экстремальное значение целевой функции

Если некоторым критериям отдается предпочтение, то в условие равенства отклонений вводятся соответствующие коэффициенты (коэффициент считается равным единице). В этом случае соотношение примет вид

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

Или

где m — число критериев задачи.

Для случая, когда один критерий максимизируется, а второй минимизируется, условие равенства отклонений запишется так:

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

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

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

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

В качестве целевой функции можно взять любое из следующих выражений:

Тогда все остальные требования выполняются автоматически.

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

где оптимизируемые критерии включены в число неизвестных.

Общий алгоритм метода равных и наименьших отклонений

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

2. Составить замещающую задачу.

3. Найти решение замещающей задачи.

Этот метод относится к компромиссным методам.

Алгоритм метода:

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

и

и добавляются еще ограничения вида:

где — дополнительные неизвестные.

Например:

1) ;

2) ;

3)

4)

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

при ограничениях

Запишем условие равенства относительных отклонений значений критериев от их экстремальных значений для к' критериев:

Рассмотрим четыре первых критерия (к' > 4).

Пусnь в условии задачи критерии f1, и f2 максимизируются, а f3 и f4 минимизируются. Осуществим анализ числителей относительных отклонений первых двух критериев. Оба числителя fкf/к* положительны при fк < 0 и отрицательны при fк > 0(k=1, 2). Поэтому в равенстве относительных отклонений этих критериев скобки абсолютных величин можно опустить, т. е. для первых двух критериев справедливо выражение

Обозначив

и подставив в предыдущую формулу, получим

Если рассмотреть третий и четвертый критерии, то для них получим точно такое же уравнение, так как направления их оптимизации совпадают:

Возьмем теперь критерии f1, f3 с разными направлениями оптимизации. Для них при

а при

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

или с учетом обозначения

Имеем

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

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

Отметим, что дополнительных ограничений расширенной задачи вида (14.11) на одно меньше числа критериев.

Если необходимо улучшить значения каких-то критериев, то улучшение оценивается количественно и в условие (14.2) вводятся весовые коэффициенты а2, а3,…, ак. (а, = 1). Условие равенства относительных отклонений в этом случае будет иметь вид

Заключение

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

Среди частных и типичных пробел в анализе многокритериальных задач принятия решений можно назвать:

· нет полного списка допустимых вариантов решений;

· нет полного списка критериев, характеризующих качество решений;

· не построены все или некоторые шкалы критериев;

· нет оценок вариантов решений по шкалам критериев;

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Костевич, Л. С. Математическое программирование: Информационные технологии оптимальных решений: Учеб. пособие / Л. С. Костевич. - Мн.: Новое знание, 2003. — 424 с.: ил.

2. Экономико-математические методы и модели: Учеб. пособие / Н. И. Холод, А. В. Кузнецов, Я. Н. Жихар и др.; Под общ. ред. А. В Кузнецова. — Мн.: БГЭУ, 1999. — 413 с.

3. Степанова, М. Д. Прикладные интеллектуальные системы и системы принятия решений. Конспект лекций: Учеб. пособие / М. Д. Степанова, С. А. Самодумкин; Под науч. ред. В. В. Голенкова. — Мн.: БГУИР, 2007. — 119 с.

4. Штойер, Р. Многокритериальная оптимизация. Теория, вычисления и приложения: Пер. с англ. — М.: Радио и связь, 1992. — 504 с.: ил.

5. Математическое моделирование социально-экономических процессов: практический курс для студентов специальностей «Менеджмент организации» и «Государственное и муниципальное управление / В. П. Василенков, И. Б. Болотин — Смоленск: Изд-во СмолГУ, 2009. — Ч.2. — 100 с.

6. Сборник задач и упражнений по высшей математике: Математическое программирование: Учеб. пособие/А. В. Кузнецов, Сакович В. А, Н. И. Холод и др.; Под общ. ред. А. В. Кузнецова. — Мн.: Выш. шк., 1995. — 382 с.: ил.

Показать весь текст
Заполнить форму текущей работой