Информационные технологии решения задач векторной оптимизации. Задача векторной оптимизации может включать

30 Информационные технологии решения задач векторной оптимизации » СтудИзба

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

Лекция 7. Информационные технологии решения задач векторной оптимизации

Основные понятия, включенные в систему тренинг-тестирования:

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

Введение

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

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

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

где - альтернативы; - векторный критерий; - символ отношения нестрогого предпочтения.

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

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

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

Среди множества многокритериальных задач можно выделить задачи четырех типов.

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

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

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

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

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

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

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

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

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

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

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

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

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

· Если известны максимально возможные значения показателей, то

· Если известны диапазоны изменения показателей, то или .

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

studizba.com

Многоцелевая (векторная) оптимизация

2.5. Многоцелевая (векторная) оптимизация

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

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

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

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

Эффективные решения (оптимум по Парето). Вариант будем называть эффективным, если не существует какого-либо другого варианта X, для которого значения всех функций fi(X) не меньше , а значение хотя бы одной функции строго больше[1]. Иначе говоря, не существует такого X, что .

Множество эффективных вариантов обозначим . Такое множество называют множеством Парето, а элемент этого множества — оптимумом по Парето (по имени известного итальянского экономиста-математика конца XIX — начала XX вв.).

Любое из решений не может быть улучшено ни по одной частичной целевой функции fi(X) без ухудшения по какой-либо другой из них. Например, если из множества возьмем два таких варианта XAи XB, что fi1(XA)> fi1(XB), то обязательно найдется какая-нибудь i-я функция, по которой fi2(XA)> fi2(XB).

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

Решить указанную задачу в полном виде, как правило, трудно. Ситуация облегчается, если множество замкнуто и выпукло, а максимизируемые функции fi(X) — вогнутые (т.е. задачи субоптимизации есть задачи выпуклого программирования).

При выполнении указанных условий справедливы следующие утверждения:

1) для любого X существует такой полуположительный вектор L=(li) с компонентами, удовлетворяющими равенству

, что достигается для X=.

2) если задан векторL=(li)>0, где, то задача дает эффективные варианты (один или несколько) X .

Иначе говоря, любое решение задачи векторной оптимизации является решением задачи скалярной оптимизации с целевой функцией, которая представляет собой взвешенную (или средневзвешенную) сумму частичных целевых функций. Второе утверждение указывает конструктивный метод определения эффективных вариантов: необходимо решать задачу скалярной оптимизации с целевой функцией Fs(X), рассматривая liкак меняющиеся параметры, на которые наложены условия li>0 и . В случаях когда L- орт (имеет только одну положительную компоненту, равную единице), получаем субоптимальные решения.

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

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

vunivere.ru

Постановка задачи векторной оптимизации

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

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

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

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

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

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

Указанные выше числовые функции (они могут быть названы частными критериями оптимизации) образуют векторный критерий

(1)

который принимает значения в -мерном арифметическом пространстве .

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

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

Изучению свойств таких задач посвящена многочисленная литература (см., например, [1]).

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

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

Эти цели одновременно, как правило, достигнуты быть не могут, и поэтому речь может идти о компромиссном решении.

Задачу векторной оптимизации сформулируем следующим образом: найти

- минимум целевых функций ,

- максимум целевых функций

по поисковым переменным при наличии ограничений:

- на поисковые переменные:

, l=1(1)L; L-число поисковых переменных.

- на поисковые переменные в виде функциональных неравенств : , j=1(1)J; J- число функциональных неравенств.

- на поисковые переменные в виде функциональных равенств :

, i=1(1)I. I- число функциональных равенств.

Для сравнения критериев ,имеющих разный физический смысл (и естественно разные размерности),проведем нормализацию критериев в следующем виде:

для целевых функций ,

, i=1,……..m,

для целевых функций

i=m+1,…,M.

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

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

Найти минимум целевых функций

по поисковым переменным при наличии ограничений:

- на поисковые переменные:

, l=1(1)L; L-число поисковых переменных.

- на поисковые переменные в виде функциональных неравенств : , j=1(1)J; J- число функциональных неравенств.

- на поисковые переменные в виде функциональных равенств :

, i=1(1)I. I- число функциональных равенств.

(Вильфредо Парето (1848-1923) – итальянский социолог и экономист)

mm.lti-gti.ru

Постановка задачи векторной оптимизации

Постановка задачи векторной оптимизации

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

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

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

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

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

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

, (5.1)

где D - множество допустимых решений. F(x) – векторная функция векторного аргумента x, которую можно представить как F(x)={f1(x), f2(x), … , fk(x) }, где f1(x), f2(x), … , fk(x) – скалярные функции векторного аргумента x, каждая их которых является математическим выражением одного критерия оптимальности. Так как в данной модели используется векторная целевая функция, ее зачастую называют задачей векторной оптимизации. Очевидно, что задача (5.1) не принадлежит классу задач математического программирования, т.к.модели этого класса задач содержат всегда только одну целевую функцию векторного аргумента.

Иначе задачу (5.1) можно переписать в виде:

Сущность поставленной задачи состоит в нахождеии такого ее допустимого решения, т.е. }, которое в том или ином смысле максимизирует (минимизирует) значения всех целевых функций fi(x), i=1,k. Существование решения, буквально максимизирующего все целевые функции, является редким исключением. (Если вспомнить пример о поиске одновременно очень качественной и очень дешевой покупки, то становится понятным, что нахождение такого решения – редкая удача, но, гораздо более часто, это неразрешимая задача).

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

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

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

Введем несколько определений.

Пусть решается задача (6.1) и есть x', x'' - допустимые решения данной задачи. Говорят, что x' более предпочтительное решение по сравнению с x'', если f i (x') ≥ f i (x'') i=1,k), причем i0, такой, что f i (x') > f i (x''). Другими словами, будем считать, что решение x' более предпочтительно по сравнению с решением x'' , если оно не хуже x'' по всем рассматриваемым критериям, причем среди всех критериев есть хотя бы один критерий с номером i0, для которого решение x' лучше, чем x''

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

Множество эффективных решений называется множеством Парето и обозначается P(D). Очевидно, множество Парето является подмножеством множества допустимых решений, которое, в свою очередь принадлежит n-мерному векторному пространству, т.е. P(D) D En.

Вектор значений критериев, вычисленных для эффективного решения F(x*), называется эффективной оценкой. Совокупность всех эффективных оценок, т.е. образ множества Парето в пространстве критериев, называется множеством эффективных оценок и, как правило, обозначается как F (P). Множество эффективных оценок является подмножеством образа множества допустимых решений в пространстве критериев F(D), которое, в свою очередь, является подмножеством k-мерного векторного пространства, т.е. F(P) F(D) Ek. Т.е. можно сказать, что множеству Парето P, принадлежащему множеству допустимых решений D, с помощью векторной функции F сопоставлется множество эффективных оценок F(P)

Решение xl называется слабоэффективным решением задачи (6.1), если для него не существует решения xll такого, что i=1,k f(xl) > f(xll), другими словами, слабоэффективное решение – решение, которое не может быть улучшено одновременно по всем критериям.

P(D)En.

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

^ (по критерию fi(x) – оптимальное решение многокритериальной задачи, найденное по какому-либо одному критерию (i-ому) без учета остальных критериев.

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

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

Рассмотрим введенные понятия на примере.

Пример 5.1.

F(x) ={3x1-x2 ; x2}->max , т.е. f1(x)= 3x1-x2->maxf2(x)= x2->maxx1≤2 x2≤4 2x1+x2≤6xj≥0

С помощью графического метода найдем субоптимальные решения (см рис. 5.1). По критерию f1 - это точка Е(2,0), f1(Е)=6.

По критерию f2 субоптимальные точки - это точки отрезка, соединяющего точки С(0,4) и В(1,4),], при этом f2(С) = f2(В)=4

Таблица 5.1 – Анализ точек множества D примера 6.1 на принадлежность множеству Парето

XD	f1(x)	f2(x)	Примечание	Свойство решения
A(2,2)	4	2	Не улучшаемые точки	P(D)
B(1,4)	-1	4	-“-	P(D)
G(1,5, 3)	1,5	3	-“-	P(D)
E(2,0)	6	0	-“-	P(D)
C(0,4)	-4	4	Улучшаемая по 1-му критерию	S(D) P(D)
K(0,0)	0	0	Одновременно улучшаемая по обоим критериям	P(D), S(D)
L(1,1)	2	1	Одновременно улучшаемая по обоим критериям	P(D), S(D)

В таблице 5.1 приведены значения целевых функций f1(x)= 3x1-x2 и f2(x)= x2 для всех точек, обозначенных на рис. 5.1. На основании этих данных построен рис. 5.2. Полученный многоугольник F(C) F(K) F(E) F(A) F(G) F(B) является отображением многоугольника допустимых решений примера C K E A G B в пространсте критериев.

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

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

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

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

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

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

Если принять преобразование для нормализации критериев вида:

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

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

Второй нормализованный критерий получается в виде: . А значение второго нормализованного критерия в наилучшей и наихудшей точках по критерию f2:

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

Рисунок 5.3- Иллюстрация процесса решения примера 5.1 в пространстве нормализованных критериев.

Решение многокритериальных задач методом ограничений. Компромиссное решение

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

Естественно, следует считать наилучшим такое решение, при котором величина отклонений от оптимальных значений по каждой целевой функции достигает своего минимального значения, т.е. для преобразованных функций – такое решение, при котором . Но наименьшие значения величин или (x) , как правило, не достигаются одновременно ни для какого решения из D (т.е. нельзя подобрать x, чтобы (x) max или min min .

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

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

Метод ограничений основан на теореме: если x0 – эффективное решение для данного вектора предпочтений , то ему соответствует наименьшее значение , при котором система равенств

= выполняется для всех i=1,k (5.2)

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

Например, если принять и , то это означает, что по информации ЛПР первый критерий в 2 раза значимее по сравнению со вторым.

Тогда в качестве решения задачи (5.1) можно принять компромиссное решение с заданным вектором предпочтений. Очевидно, что компромиссное решение – это такое эффективное решение x0, которое обеспечивает одинаковые минимальные значения параметра , при котором система (5.2) совместна.

Таким образом, компромиссное решение может быть найдено как единственное решение системы неравенств вида

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

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

(5.3)

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

(5.4)

Если исходная задача (5.1) является задачей представлена с помощью линейных целевых функций и функций-ограничений , то вспомогательная задача (5.4)является задачей ЛП:

(5.5).

Пример 5.1 (продолжение 2)

Выше были построены нормализованные критерии для целевых функций примера 5.1: 1(x)=0.6-0.3+0.1, 2(x)=1-0.25. Тогда система вновь введенных ограничений вспомогательной задачи (5.5) при будет выглядеть как:

Вспомогательная задача для этого примера представляет собой задачей ЛП с тремя неизвестными и функциональными ограничениями:

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

^ Оптимальное решение вспомогательной задачи: (см рис.5.1) ,* = 0.175. Так как коэффициенты предпочтений были выбраны как для , то не трудно убедиться, что полученное решение x* эффективное (что и должно было получиться по теории метода ограничений - можно сказать, что это решение эффективно по построению). Это иллюстрируется графиком на рис. 5.1. Можно показать, что полученное решение x* также и компромиссное, а именно относительные взвешенные потери по всем критериям равны между собой, действительно:

Предположим, что критерии оптимальности расположены в порядке убывающей важности; сначала основной f1, затем другие, вспомогательные: f2, f3, … . Для простоты будем считать, что каждый из них нужно обратить в максимум (если это не так, достаточно изменить знак показателя). Процедура построения наиболее предпочтительного решения сводится к следующему. Сначала ищется решение, обращающее в максимум главный критерий оптимальности f1. Затем назначается, исходя из практических соображений и точности, с какой известны исходные данные (а часто она бывает небольшой), некоторая «уступка» Δ f1, которую ЛПР согласно допустить для того, чтобы обратить в максимум второй показатель f2,. Налагаем на критерий f1ограничение, чтобы он был не меньше, чем f1 * – Δ* f1, где f1* – максимально возможное значение f1, и при этом ограничении ищем решение, обращающее в максимум f2. Далее снова назначается «уступка» в показателе f2, ценой которой можно максимизировать f3, и т. д.

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

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

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

f1(x)= 3x1-x2->max

x1≤2

x2≤4

2x1+x2≤6

xj≥0 , j=1,2.

Выше в п.5.2. с помощью графического метода уже найдено субоптимальные решения (см рис. 5.1). По критерию f1 - это точка Е(2,0), f1(Е)=6. Отметим, что значение второго критерия в данной точке, равное 0, далеко от наилучшего значения этого критерия, равного 4. Т.е. с точки зрения второго критерия, полученное решение явно проигрышное.

Предположим, что ЛПР согласно на уступку по первому критерию в размере 50% от максимального значения критерия, т.е. на уступку в размере 3 единиц.

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

f2(x)= x2->max

f1(x)= 3x1-x2≥ f*1 - Δ* f1 = 6 – 3 = 3

x1≤2

x2≤4

2x1+x2≤6

xj≥0 , j=1,2.

Решение полученной задачи – вектор x* = (1,8; 2,4). Значения критериев в данной точке: f1(x)= 3x1-x2= 3; f2(x)= x2= 2,4.

Если посчитать относительные потери для найденного решения, т.е. значения нормализованных критериев в точке x*:

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

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

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

Рассмотрим метод более подробно. В качестве свертки для получения единой целевой функции, как правило, используется преобразование вида:

, (5.7)

где = 1,2., а - коэффициенты предпочтения. (Вместо функций fi(x) в преобразовании (5.6) можно использовать нормализованные критерии ).

Вспомогательная задача в этом случае выглядит как:

Если в преобразовании (5.7) принято, что =1, то получается вспомогательная задача с линейной сверткой:

Если исходная задача является задачей ЛП, то вспомогательная задача с линейной сверткой также является задачей ЛП и решается методами ЛП:

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

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

zanny.ru

Информационные технологии решения задач векторной оптимизации

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

План:Введение

Принцип оптимальности Парето. Неулучшаемые (оптимальные по Парето) решения

Принцип равновесия по Нэшу

Конфликты, переговоры и компромиссы

Краткий обзор методов решения задачи векторной оптимизации

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ситуация равновесия может оказаться не единственной.

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

Ситуации равновесия могут совпадать или не совпадать с ситуациями оптимальными по Парето.Конфликты, переговоры и компромиссы

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

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

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

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

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

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

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

Методы, основанные на свертывании системы показателей эффективности;

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

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

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

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

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

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

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

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

оптимальность парето векторный многокритериальный

Б. Методы, использующие ограничения на критерии, включают два подхода: метод ведущего критерия и метод последовательных уступок.

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

Алгоритм метода последовательных уступок состоит в следующем:

Критерии нумеруются в порядке убывания важности;

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

Решается задача по критерию с дополнительным ограничением ;

Пункты 2 и 3 повторяются последовательно для критериев .

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

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

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

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

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

ua.coolreferat.com