Методы оптимизации

Размещено на http://www.allbest.ru/

Введение

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

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

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

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

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

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

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

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

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

min{затраты},

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

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

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

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

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

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

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

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

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

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

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

mах{доход},

min{риск},

mах{дивиденды},

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

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

mах {наличие средств},

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

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

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

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

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

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

max {устойчивый урожай древесины},

max {человеко-дни отдыха в лесу},

max {человеко-дни охоты в лесу},

max {ареал распространения диких животных},

max {число месяцев выпаса домашних животных},

min {превышения бюджета}.

Управление попусками водохранилищ

max {выгоды от рекреации на водохранилище №1},

max {выгоды от зарегулирования стока ниже водохранилища №1},

max {количество энергии, вырабатываемой в бассейне реки},

min {недопоставки воды на коммунальные нужды в бассейне реки},

max {выгоды от рекреации на водохранилище №2},

max {прибыль от орошения земель ниже водохранилища №2}.

Формирование ревизионной службы в фирме

max{доход},

min {рост численности персонала службы},

min {уменьшение численности персонала службы},

min {избыточные сверхурочные},

min {недоиспользование квалификации кадров},

max {время, отведенное на профессиональный рост}.

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

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

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

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

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

Изготовление смеси для сосисок, копченой колбасы и салями

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

min{жирность},

min {отклонение от требуемого цвета},

max{протеин},

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

min {отклонения от требуемой пропорции свинины и говядины}.

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

1. Постановка многокритериальной задачи

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

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

Многокритериальная задача имеет вид

(1)

где D - область допустимых решений.

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

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

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

Если отношение предпочтительности на множестве D обозначить символом <, то для любых означает, что на множестве .

Сложность состоит в том, что и на множестве элементы сравнимы далеко не всегда. Часто встречается ситуация, когда среди двух допустимых решений одно лучше по одному критерию, а второе - по другому.

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

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

3. Эффективные решения многокритериальных задач. Различные виды эффективности

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

Однако иногда можно сравнивать по качеству некоторые исходы (допустимые решения), удовлетворяющие наложенным ограничениям независимо от предпочтений ЛПР. Например, если одно из двух возможных решений лучше другого по всем рассматриваемым критериям, то ему, конечно, следует отдать предпочтение.

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

Пусть - два допустимых решения задачи (1) т.е. . Будем говорить, что строго предпочтительнее , если решение лучше решения по всем критериям. Такое отношение строгого предпочтения на множестве D будем записывать следующим образом: строго.

Если считать, что все целевые функции задачи (1) максимизируются, то: строго, если для всякого

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

1. Для всякого справедливо неравенство

2. :

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

Таким образом, на множестве D допустимых решений задачи (1) введены два различных отношения 1) строгого предпочтения и 2) доминирования по Парето. С практической точки зрения каждое из них имеет свои преимущества и недостатки. Отношение строгого предпочтения является бесспорным, однако слишком много объектов являются несравнимыми. Поэтому отношение доминирования по Парето получило большое распространение в экономических исследованиях.

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

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

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

1. для всякого ;

2. существует такое что .

Эффективное решение задачи (1) называется так же решением, оптимальным по Парето, или Парето-оптимальным решением.

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

.

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

4. Построение Парето-эффективной границы

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

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

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

Векторные оценки исходов представим точками координатной плоскости .

5. Процедуры решения многокритериальных задач

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

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

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

Для заданной многокритериальной задачи нахождения решения (ЗНР) находится множество решений, а выбор конкретного решения из множество Парето-оптимальных решений предоставляется ЛПР.

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

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

,

где - позитивные критерии, .

При указании нижних границ критериев дополнительная информация имеет вид:

где - нижняя граница по j - му критерию;

- оптимальный исход,

Очевидно, что при увеличении значений , , Парето-оптимальное множество «сокращается».

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

Список литературы

1. Под редакцией д-ра экон. наук, проф. В.А. Колемаева. Математические методы и модели исследования операций. Издательство ЮНИТИ-ДАНА. 2008 г.

2. В.В. Подиновский, В.М. Гаврилов. Оптимизация по последовательно применяемым критериям. М. Советское радио. 1975 г.

Размещено на Allbest.ru