2 Многокритериальная оптимизация. Методы сведения многокритериальной задачи к однокритериальной. Однокритериальная и многокритериальная оптимизация

Многокритериальная оптимизация Векторная интерпретация задачи. Место эвристики

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

Данный класс задач предполагает сравнение вариантов решения одновременно по нескольким параметрам, где каждый n–ый вариант характеризуетсяm-ым числом параметров:

n, n=1,N

m, m=1,M

(qnm,n=1,N,m=1,M– в общем случае некая функция)

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

Это мультипликативная и аддитивная свертка.

Фn = П qnm – мультипликативная

m=1

Yn = ∑ qnm - аддитивная

n=1

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

В связи с этим на практике широкое применение нашла аддитивная свертка. Для ее применения необходимо решить два вопроса:

Как учесть разный физический смысл (природу) различных параметров.
Как учесть различную относительную важность разнородных параметров.

Дадим векторную интерпретацию задачи. Рассмотрим данную задачу на плоскости:

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

|Xn|→max

→ Xno=Xncosαno

αno→min

Т.е., в предположении, что задан некоторый идеальный вектор качества (qn=0), лучший вариант можно определить по длине вектора и углу вектора с идеальным. Или сводя задачу к однокритериальной по длине проекции вектора качества на идеальный вектор. Ранее мы показывали, что в ортонормированном базисе данная длина определяется следующей функцией:

Xm= (1/√M)*∑qnm=Yn= ∑qnm

m=1 n=1

а это ни что иное, как аддитивная свертка.

Таким образом, аддитивный критерий оптимальности может интерпретироваться как приведенная (умноженная на коэффициент 1/√M) длина проекции вектора качества варианта на идеальный вектор качества.

Возникают 2 вопроса:

Как задать идеальный вектор (соответственно, как нормировать параметры).
Как учесть относительную важность разнородных параметров.

Рассмотрим альтернативные варианты решения.

Объективный способ нормирования параметров.

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

Нормирование же параметров реализуется следующим образом:

qnm=qnm/qnmax, если лучшее значение качества определяется, какmax(например, производительность)

qnm=qnmin/qnm, если лучшее значение качества определяется, какmin(например, стоимость)

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

Достоинства:

Недостатки:

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

Данная задача решается вводом весовых коэффициентов.

qnm = ∑αm* qnm

m=1

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

Однако вернемся к интерпретации. Что с этой позиции означает задание весового коэффициента в ортонормированном базисе - поворот в пространстве идеального вектора (это нам далее пригодится). А идеальный вектор в данном случае определяется лучшими значения параметров на сравниваемом множестве вариантов (в ортонормированном базисе эти значения равны «1»).

Субъективный способ нормирования параметров.

При проектировании любой системы требуется достижение некоторых качеств (в противном случае речь не может идти о проектировании, а тогда что и зачем сравнивать), совокупность данных требуемых качеств и определяет идеальный вектор, то есть параметры qnmaxиqnmin- формируются субъективно разработчиком, исходя из условий задач. Действительно, как выбирать, как назначать какие-либо весовые коэффициенты, пока не определился с тем, что необходимо получить в результате. Исходя из этого посыла, предполагаем, что задать подобные значенияqnmaxиqnminвозможно всегда. А теперь очень важный момент, следующий из представленной выше интерпретации. Задавqnmaxиqnmin, мы тем самым задаем идеальный вектор, причем не только его величину, но и расположение в пространстве. Напомним, что, следуя интерпретации, расположение вектора в пространстве задается назначением весовых коэффициентов. В данном случае, задавqnmaxиqnmin, мы тем самым задаем и весовые коэффициенты – относительную важность параметров. Т.е. при таком подходе к решению задачи снимаются все неопределенности – выбирается вариант, наиболее подходящий сформулированным требованиям.

Замечание:

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

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

Yn= ∑qnm

n=1

а нормированные значения параметров вариантов определяются соответствующим образом:

qnm=qnm/qnmax, если лучшее значение качества определяется, какmax(например, производительность)

qnm=qnmin/qnm, если лучшее значение качества определяется, какmin(например, стоимость)

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

Достоинства:

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

studfiles.net

Однокритериальная, многокритериальная оптимизация и другие методы

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

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

Однокритериальная оптимизация

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

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

Многокритериальная оптимизация с ограничениями

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

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

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

Оптимизация на основе метамоделей (суррогатных моделей)

Оптимизация на основе суррогатных моделей (также называемых аппроксимационными или метамоделями, SBO) реализована с использованием другого модуля pSeven Core — GT Approx. Это пример сочетания возможностей различных модулей pSeven Core: модули оптимизации и аппроксимации используются совместно и в результате предоставляют пользователю эффективную методологию глобальной оптимизации. Метод основан на методе установления наиболее вероятного лучшего решения, однако во многом превосходит известные реализации этого подхода. В частности, в рамках одного метода удалось достичь как хорошей глобализации поиска решения, так и сохранить свойства локальной сходимости обычных оптимизационных методов. Заметим, что алгоритм прекрасно справляется и с многоэкстремальными многокритериальными задачами при наличии ограничений благодаря использованию современных методов адаптивной фильтрации.

www.datadvance.net

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

Транскрипт

1 Однокритериальные и многокритериальные задачи в управленческой деятельности. Задачи однокритериальной оптимизации Существует значительное число экономических систем, в частности из области управленческой деятельности, моделируя которые мы приходим к различным формам задач оптимизации. Рассмотрим задачу однокритериальной оптимизации. В общей форме она запишется следующим образом: f x ax n, x X. Т.е. на некотором допустимом множестве X максимизируется либо минимизируется функция от вектора переменных x R n. Действительно, практически любая задача управления состоит в оптимизации заданной целевой функции при некоторых бюджетных ограничениях. Мы либо максимизируем прибыль (объем производства, функцию полезности, заданную в произвольной форму, или любой прочий эквивалент счастья ), либо минимизируем затраты (риск при инвестировании, объем перевозок и т.д.). При этом в различных задачах нас ограничивают объем имеющихся денежных средств, объем ресурсов (сырьевых либо каких-то иных) и любые другие соображения. Подобные ограничения обычно записываются в виде равенств и неравенств. Таким образом, получаем следующую формулировку задачи оптимизации f ( x) ax, g ( x) = 0, =,...,, h x 0, =,..., k. Очевидно, что задача минимизации может быть превращена в задачу максимизации путем замены функции f ( x ) на f ( x ). В частном случае, когда все функции f( x), g( x) и h( x ) являются линейными, задача называется задачей линейного программирования. 2. Примеры задач однокритериальной оптимизации Рассмотрим несколько примеров задач однокритериальной оптимизации.

2 2.. Производственная задача. Пусть некоторое предприятие способно выпускать n видов продукции (A, A 2,... A n ). При этом используется видов ресурсов B, B 2,... B, n <. Под ресурсами подразумеваются денежные средства, виды сырья, рабочая сила, производственные мощности, площади, технологии. Прибыль от реализации единицы продукции составляет. Затраты - ресурса на производство одной единицы - вида продукции составляет a A c (сколько требуется денег, сырья, человеко-часов рабочей силы, часов работы оборудования и т.д., чтобы произвести единицу продукции). Имеющийся объем - ресурса равен. Нужно составить такой план производства, при котором мы получим максимальную прибыль. Пусть производится единиц продукции. Прибыль при этом будет равна n cx x ax. () Суммарные затраты по - виду ресурса составят a x. Зная, каков имеющийся объем ресурса, составим ограничения n a x b, =,...,. (2) И последним видом ограничений будут очевидная неотрицательность объемов производимой продукции x 0, =,...,n. (3) Мы получили задачу линейного программирования ()-(3). Наиболее распространенным методом ее решения является симплекс-метод, хотя существует и значительное число других подходов. b A n 2.2. Транспортная задача. Пусть у нас имеется пунктов производства однородного продукта:,,... ) и n пунктов его потребления (A A 2 A B, B 2,... B n. В каждом из пунктов A производится a единиц продукта, а в каждом из пунктов B потребляется соответственно b единиц. Необходимо составить оптимальный план перевозок (при котором достигается их минимальная суммарная 2

3 стоимость), если известно, что удельная стоимость перевозки из пункта B в пункт составляет. c Составим математическую модель. Пусть A A B - объем продукта, перевозимого из в. Тогда общая стоимость перевозок, которую мы минимизируем, будет равна n = cx n. (4) Суммарный объем груза, вывозимого из пункта, составит, а он по условию равен. Суммарный объем груза, привозимого в, равный по b a x = условию, составит. Получим ограничения n x = a, =,...,, (5) x = b, =,...,n. (6) = Также здесь присутствуют ограничения неотрицательности всех объемов перевозок x 0, =,...,, =,..., n. (7) x A n x B Задача (4)-(7) называется транспортной. Начальный допустимый план можно получить методом северо-западного угла. Затем проводится последовательное улучшение плана методом потенциалов Модель оптимизации инвестиционного портфеля. Пусть в нашем распоряжении имеется некоторая денежная сумма S. Имеются n различных инвестиционных проектов (n эмитентов, работающих на рынке ценных бумаг, в акции которых можно вкладывать средства). Математическое ожидание дохода, полученного при вложении рубля в - проект, составляет рублей,. Однако доходность, разумеется, не может служить единственной интересующей нас характеристикой: существуют достаточно доходные, но крайне рисковые проекты, очень ярким примером здесь является построенная несколько лет назад пирамида АО МММ. С другой стороны, имеются абсолютно (по крайней мере, почти) надежные проекты, которые так же абсолютно надежно не приносят при 3

4 были: можно просто держать деньги наличными (этот выбор можно считать (n + ) - проектом), никуда их не вкладывая, при этом мат.ожидание дохода составит n+ =. Нужно найти компромисс между данными двумя крайностями. За меру рискованности инвестиционного портфеля можно принять его дисперсию (т.е. меру разброса доходности относительно среднего значения). Итак будем вкладывать в - проект объем средств. Тогда мат.ожидание полученного дохода, которое и максимизируется, составит M x = n+ x ax. (8) Поскольку мы располагаемым фиксированным объемом средств S, то получим первое ограничение n+ x = S. (9) Дисперсия портфеля составит n+ n+ = D x = K x x. В случае, когда корреляцией между отдельными проектами можно пренебречь, т.е. K = n+ 2 0,, дисперсию можно записать в форме D( x ) = D x. Одним из подходов к формированию оптимального портфеля будет ограничение его дисперсии заданной фиксированной величиной D. В упрощенной форме ограничение запишется в следующем виде: D x = n+ D x 2 D. (0) x И последним видом ограничений снова будет неотрицательность величин - объемов средств, вкладываемых в - проект. Хотя существуют модификации модели, в которых это ограничение отсутствует - в них отрицательность означает необходимость не покупки, а продажи акций. Тем не x менее, в исходной версии модели оно присутствуют x 0, =,..., n. () Получили задачу квадратичного программирования (8)-(). Однако фиксирование верхней границы D для дисперсии (ограничение (0)) и последующее решение задачи однокритериальной оптимизации не является единственно возможным подходом как к задаче выбора опти- x 4

5 мального инвестиционного портфеля, так и к любым другим задачам, в которых предполагается оптимизация по нескольким противоречащим друг другу критериям. Мы переходим к рассмотрению более общей задачи: задачи многокритериальной оптимизации. 3. Задачи многокритериальной оптимизации Пусть у нас имеется несколько целевых функций, которые для упрощения записи нам нужно максимизировать (как уже говорилось, задача на минимум преобразуется заменой знака функции на противоположный). В рассмотренной модели ими являются доходность и минус-дисперсия, в других задачах, разумеется, могут возникать любые другие варианты целевых функций. По прежнему имеется набор ограничений, задающих область допустимых значений задачи. Получаем задачу многокритериальной оптимизации, которая в общей форме формулируется следующим образом: f ax, =,...,, (2) x X. Главная возникающая здесь сложность в неоднозначности оптимального решения: в точке, где один из критериев достигает своего максимума, другой может быть очень далек не только от максимума, но и даже от какойлибо приемлемой величины. Продемонстрируем возможную ситуацию на рисунке x f, f2, f3 f 2 a f b x f 3 5

6 Видим, что максимум функций f и f 2 достигается в точке b, однако она же является точкой минимума третьей функции, максимум которой достигается в точке a. Каким образом можно прийти к компромиссу? Существует множество подобных способов. Рассмотрим их поочередно. 4. Сведение многокритериальной задачи к однокритериальной f Способ. Выделение главного критерия (условная максимизация). Применение данного подхода на модели оптимизации портфеля ценных бумаг привело к рассмотренной выше задаче однокритериальной оптимизации (8)-(). Его суть достаточно проста: выбирается наиболее важный из всего набора критерий и проводится его оптимизация при условии того, что значения остальных критериев не хуже наперед заданных фиксированных значений, считающихся удовлетворительными. В рассмотренной модели была выбрана предельная величина риска портфеля, превосходить которую мы не можем, какова бы при этом ни была доходность портфеля. Формализуем этот подход для задачи (2). Пусть выбран наиболее важный для нас критерий (перенумеруем критерии так, чтобы самый важный оказался первым). Пусть заданы числа f f n, = 2,..., - удовлетворяющие нас значения соответствующих критериев. Будем решать следующую однокритериальную задачу: f x ax, n f x f, = 2,...,, x X. Главное в этом подходе избежать двух крайних случаев: когда множество точек x, при которых выполняются все неравенства f( x) f n, совпадает с самим множеством X (тогда непонятно, для чего нужны остальные критерии) и когда подобное пересечение с множеством X пусто (относясь слишком привередливо к побочным критериям, мы задали такие значения, при которых не осталось ни одной допустимой точки). f n 6

7 4.2. Способ 2. Линейная свертка. Наиболее простым и часто используемым способом сведения многокритериальной задачи к однокритериальной является линейная свертка. Задаются весовые неотрицательные коэффициенты, обозначающие степень важности каждого критерия, и максимизируется линейная комбинация целевых функций, т.е. решается задача g ( x) = c f ( x) x X, = c 0, =,...,, c =., = c (3) В крайнем случае, когда какой-то из коэффициентов c =, а все остальные c = 0,, мы приходим к однокритериальной задаче максимизации - целевой функции. f Способ 3. Максиминная свертка. В этом способе заранее задаются масштабирующие коэффициенты (в частном случае все значения можно принять равными = ) и решается задача максиминной оптимизации g ( x) x X. Коэффициенты ( x) f = n ax, =,..., n 0 f f 0 здесь используются для приведения всех целевых функций к примерно одному масштабу, либо наоборот, для выделения какого-либо из критериев. Основным недостатком данного подхода является возможная потеря гладкости полученной целевой функции, однако в некоторых случаях применение такого способа свертки является достаточно удобным Способ 4. Приведем еще один способ, который выдает достаточно точное с точки зрения экономической интерпретации решение. Поскольку мы предполагаем, что умеем легко решать задачи однокритериальной оптимизации, то вычислим сначала максимальные и минимальные значения, кото- f 0 7

8 рые может принимать на допустимом множестве каждая из целевых функций: ax f = ax f x, x X, =,...,, n f = n f x, x X, =,...,. В этом случае разность этих значений ax n f f будет интерпретироваться как амплитуда, разность значений f ax f( x ) - как абсолютное отклонение от максимума - целевой функции в точке x, а их частное ax f f( x) ax n f f - как относительное отклонение от максимума - целевой функции (в точке максимума оно равно нулю, а в точке минимума - единице). Способ свертки состоит в решении задачи минимизации линейной комбинации с неотрицательными весовыми коэффициентами c, обозначающими важность - критерия, относительных отклонений, определенных выше: g c f ax f x x = n, ax n = f f x X, c 0, =,..., c =. = Существенным недостатков данного подхода является большой объем вычислений, необходимых для получения решения Способ 5. Метод идеальной точки. Последний подход к получению однозначного решения задачи многокритериальной оптимизации несколько отличается от предложенных выше. Определим множество достижимости многокритериальной задачи как множество всех возможных значений целевых функций, которые мы получаем при всех допустимых значениях x : 8

9 { : f, } Y = y R y = x x X Идеальной точкой назовем вектор, состоящий из максимальных значений всех целевых функций: f* = ax f x x x, ax f 2,..., ax f x X x X x X Продемонстрируем это на рисунке: y 2 f* Y Y f opt y Основным исследуемым случаем здесь, конечно, является вариант, когда f* Y. В противном случае имеется точка, в которой достигается максимум по всем критериям, она и является оптимальной. Решением задачи многокритериальной оптимизации будем считать точку, вектор значений целевых функций в которой минимально по норме отличается от идеальной точки: fx f* n, x X. Подобное решение изображено на рисунке. Можно использовать как стандартную евклидову норму f opt * ( f( x) f ) = 2 n, x X, так и Чебышевскую норму (максимальное по модулю отклонение) * ax f =,..., n x f n, x X, так и любой другой вид нормы Способ 6. Решения, оптимальные по Парето и по Слейтеру. Рассмотрим наиболее общий подход к решению задач многокритериальной оптимизации. Назовем решение x X оптимальным по Парето, если не существует такого y X, что ( y) ( x) f f, =,..., 9

10 и при этом хотя бы для одного решение выполняется в строгой форме, т.е. если нельзя улучшить решение хотя бы по одному критерию, не ухудшив его по остальным. Решение x X - оптимально по Слейтеру, если не существует такого y X, что ( y) ( x) f > f, =,...,, т.е. если нельзя улучшить решение одновременно по всем критериям. Понятие оптимальности по Слейтеру более широкое, чем оптимальности по Парето. Любая точка, оптимальная по Парето будет оптимальной по Слейтеру, но не наоборот. Продемонстрируем это на следующем рисунке: y 2 Решения оптимальные и по Парето, и по Слейтеру Y Решения, оптимальные только по Слейтеру y Однако и Парето-оптимальные решения дают нам весь спектр оптимальных решений многокритериальной задачи. Заметим также интересный факт: подставляя различные весовые коэффициенты при решении задачи (3), мы всегда получаем Парето- c оптимальное решение. Более того, любое Парето-оптимальное решение является решением задачи (3) при некотором наборе весов. В этом смысле, линейная свертка является самодостаточной. Можно также использовать это свойство следующим образом. Среди набора целевых функций часто имеется экономический критерий (например, максимизация прибыли), а также другие, не приводимые в явном виде к стоимостной форме. Например, при выборе вариантов развития производства наряду со стоимостными показателями в качестве критериев могут использоваться показатели различных вредных выбросов в природную среду или показатели экологического риска для населения. Каждому полу- c 0

11 ченному Парето-оптимальному решению данной задачи можно поставить в соответствие весовые коэффициенты, при которых данное решение c будет решением и однокритериальной задачи (3). При умножении всех коэффициентов на одно и то же число решение задачи (3) не изменится. Поэтому можно при стоимостном критерии задать единичный весовой коэффициент. Тогда коэффициенты при остальных критериях можно интерпретировать как параметры перевода измеряемых ими показателей в стоимостную форму - например, как удельные ущербы от вредных выбросов или от повышения риска для здоровья населения. c Литература. Воробьев Н.Н. Теория игр. Лекции для экономистов-кибернетиков. - Л., Тятюшкин А.И. Решение и анализ задач линейного программирования: Учебное пособие. - Иркутск: ИГЭА, Зоркальцев В.И. Модели рыночной экономики: Учебное пособие. - Иркутск: ИГУ, 993.

12 Содержание. Задачи однокритериальной оптимизации... 2 Примеры задач однокритериальной оптимизации Производственная задача Транспортная задача Модель оптимизации инвестиционного портфеля Задачи многокритериальной оптимизации Сведение многокритериальной задачи к однокритериальной Способ. Выделение главного критерия (условная максимиза6 ция) Способ 2. Линейная свертка Способ 3. Максиминная свертка Способ Способ 5. Метод идеальной точки Способ 6. Решения, оптимальные по Парето и по Слейтеру...9 Литература... Содержание

docplayer.ru

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

Однокритериальная и многокритериальная

Оптимизация

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

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

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

Рассмотрим задачу многокритериальной оптимизации следующего вида:

fi(x) → max, fi ׃ D → R, i = 1, … , m; D Í Rn. (6.1) xÎD

Таким образом, задано m функций или функционалов fi, отображающих множество D – допустимых решений n-мерных векторов x =(х1, … , хn) во множество вещественных чисел R. Предполагается, что выбор оптимальных значений x производится не во всем n-мерном пространстве Rn, а лишь в пределах некоторого его подмножества D. Например, можно интерпретировать задачу (6.1) как задачу оптимального выбора параметров х1, … , хn некоторой системы, качество функционирования которой оценивается показателями f1, … , fm. В этом случае ограничение x ÎD отражает технологические и иные возможности реализации тех или иных значений хi. Кроме того, часть ограничений может формироваться на основе имеющейся априорной информации, позволяющей исключить из рассмотрения заведомо неудачные варианты x.

Важнейшее значение при исследовании задач (6.1) имеет принцип Парето и связанные с ним понятия эффективного (Парето-оптимального) и слабо эффективного решения. Для сведения задачи многокритериальной оптимизации (6.1) к некоторой ее однокритериальной версии можно использовать следующие традиционные «инженерные» методы [13].

Метод главного критерия

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

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

fi(x) → max; D′ Í D Í Rn; xÎD′ D′ = {x ÎD | fi(x) ≥ ti, i = 2, … , m}. (6.2)

В результате получили более простую задачу поиска максимума функционала f1 на новом допустимом множестве D′ при ограничениях вида fi(x) ≥ ti, показывающих, что согласны не добиваться максимальных значений для функционалов f2, … , fm, сохраняя требование их ограниченности снизу на приемлемых уровнях. Однако, переход от задачи (6.1) к задаче (6.2) не есть переход от одной эквивалентной задачи к другой. Произошло существенное изменение исходной постановки задачи, которое в каждой конкретной ситуации требует отдельного обоснования. Применение этого метода на интуитивном уровне обычно наталкивается на трудности, связанные с возможным наличием нескольких «главных» критериев, находящихся в противоречии друг с другом. Кроме того, не всегда ясен алгоритм выбора нижних границ ti. Их необоснованное задание может привести, в частности, к пустому множеству D′.

Метод линейной свертки

Это наиболее часто применяемый метод «скаляризации» (свертки) задачи (6.1), позволяющий заменить векторный критерий оптимальности f = (f1, … , fm) на скалярный J׃ D → R. Он основан на линейном объединении всех частных целевых функционалов f1, … , fm в один:

m m J(x) =åaifi(x) → max; ai > 0, åai =1. (6.3) i=1 x ÎD i=1

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

Метод максиминной свертки

Этот метод обычно применяется в форме:

J(x)= min fi(x) → max. (6.4) i xÎD

В отличие от метода линейной свертки на целевой функционал J(x)оказывает влияние только тот частный критерий оптимальности, которому в данной точке x соответствует наименьшее значение соответствующей функции fi(x). И если в случае (6.3) возможны «плохие» значения некоторых fi за счет достаточно «хороших» значений остальных целевых функционалов, то в случае максиминного критерия производится расчет «на наихудший случай» и по значению J(x)можно определить гарантированную нижнюю оценку для всех функционаловfi(x). Этот факт расценивается как преимущество максиминного критерия перед методом линейной свертки.

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

J(x)= min ai fi(x) → max, (6.5) i xÎD

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

Критерии оптимизации ТПШИ

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

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

4-i-5.ru

Однокритериальная и многокритериальная

Оптимизация

Рассмотрим задачу многокритериальной оптимизации следующего вида:

fi(x) → max, fi ׃ D → R, i = 1, … , m; D Í Rn. (6.1) xÎD

Таким образом, задано m функций или функционалов fi, отображающих множество D – допустимых решений n-мерных векторов x = (х1, … , хn) во множество вещественных чисел R. Предполагается, что выбор оптимальных значений x производится не во всем n-мерном пространстве Rn, а лишь в пределах некоторого его подмножества D. Например, можно интерпретировать задачу (6.1) как задачу оптимального выбора параметров х1, … , хn некоторой системы, качество функционирования которой оценивается показателями f1, … , fm. В этом случае ограничение x Î D отражает технологические и иные возможности реализации тех или иных значений хi. Кроме того, часть ограничений может формироваться на основе имеющейся априорной информации, позволяющей исключить из рассмотрения заведомо неудачные варианты x.

Метод главного критерия

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

fi(x) → max; D′ Í D Í Rn; xÎD′ D′ = {x ÎD | fi(x) ≥ ti, i = 2, … , m}. (6.2)

В результате получили более простую задачу поиска максимума функционала f1 на новом допустимом множестве D′ при ограничениях вида fi(x ) ≥ ti, показывающих, что согласны не добиваться максимальных значений для функционалов f2, … , fm, сохраняя требование их ограниченности снизу на приемлемых уровнях. Однако, переход от задачи (6.1) к задаче (6.2) не есть переход от одной эквивалентной задачи к другой. Произошло существенное изменение исходной постановки задачи, которое в каждой конкретной ситуации требует отдельного обоснования. Применение этого метода на интуитивном уровне обычно наталкивается на трудности, связанные с возможным наличием нескольких «главных» критериев, находящихся в противоречии друг с другом. Кроме того, не всегда ясен алгоритм выбора нижних границ ti. Их необоснованное задание может привести, в частности, к пустому множеству D′.

Метод линейной свертки

Это наиболее часто применяемый метод «скаляризации» (свертки) задачи (6.1), позволяющий заменить векторный критерий оптимальности f= (f1, … , fm) на скалярный J ׃ D → R. Он основан на линейном объединении всех частных целевых функционалов f1, … , fm в один:

m m J(x) =åaifi(x) → max; ai > 0, åai =1. (6.3) i=1 x ÎD i=1

Метод максиминной свертки

Этот метод обычно применяется в форме:

J(x)= min fi(x) → max. (6.4) i xÎD

В отличие от метода линейной свертки на целевой функционал J(x) оказывает влияние только тот частный критерий оптимальности, которому в данной точке x соответствует наименьшее значение соответствующей функции fi(x). И если в случае (6.3) возможны «плохие» значения некоторых fi за счет достаточно «хороших» значений остальных целевых функционалов, то в случае максиминного критерия производится расчет «на наихудший случай» и по значению J(x) можно определить гарантированную нижнюю оценку для всех функционаловfi(x). Этот факт расценивается как преимущество максиминного критерия перед методом линейной свертки.

J(x)= min ai fi(x) → max, (6.5) i xÎD

Критерии оптимизации ТПШИ

studlib.info

2 Многокритериальная оптимизация. Методы сведения многокритериальной задачи к однокритериальной. Однокритериальная и многокритериальная оптимизация

Многокритериальная оптимизация Векторная интерпретация задачи. Место эвристики

Однокритериальная, многокритериальная оптимизация и другие методы

Однокритериальная оптимизация

Многокритериальная оптимизация с ограничениями

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

Оптимизация на основе метамоделей (суррогатных моделей)

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

Транскрипт

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

Похожие главы из других работ:

3. Краткие сведения о методе решения задачи

1.1 Методы решения задачи календарного планирования

1.4 Задачи и методы экономического анализа при применении бюджетной системы управления

1.2 Оптимизация плана транспортной задачи с использованием метода потенциалов на сети

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

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

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

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

1.1 Теоретические сведения и алгоритм решения задачи

1.2 Методы составления опорного плана транспортной задачи

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

3. Методы решения задачи

1 Творческие задачи и методы их решений

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

3. Предмет и задачи дисциплины «Экономико-математические методы и модели».

Однокритериальная и многокритериальная

Однокритериальная и многокритериальная