Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Многоцелевая оптимизация Чаще всего многоцелевую задачу пытаются свести к одноцелевой. Эта процедура. - презентация

1 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Многоцелевая оптимизация Чаще всего многоцелевую задачу пытаются свести к одноцелевой. Эта процедура в большинстве случаев приводит к серьезному искажению существа проблемы и, следовательно, к неоправданной замене одной задачи другой. Многомерные цели могут находиться друг с другом в следующих отношениях: Цели взаимно нейтральны (система рассматривается независимо). Цели кооперируются (система рассматривается применительно к одной цели, а остальные достигаются одновременно). Цели конкурируют. В этом случае одну из целей можно достигнуть лишь за счет другой. Если цели частично нейтральны, частично кооперированы и частично конкурируют между собой, то задача формулируется таким образом, что нужно принимать во внимание только конкурирующие цели. Рассмотрение нейтральных или кооперативных целей не представляет особых трудностей, так что проблемы, ориентированные на множество целей, прежде всего должны быть рассмотрены в части конкурирующих целей, коль скоро все они вместе не могут быть выражены одномерным параметром. Rev /

2 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Классификация задач МЦО По методу использования информации Априорные (все явно или неявно задается в условии) Апостериорные (после решения задачи формулируются субъективные доп. требования, которые позволяют ее ограничить и перевести к скалярному виду) Адаптивные (подстройка условий задачи на основе решения, итеративный процесс) По характеру использованной информации а) детерминированныеб) вероятностные По методу принятия решения а) Скалярная постановка метод главной компоненты метод уступок метод комплексного критерия метод Гермейера метод справедливого компромисса метод условного центра масс метод идеальной точки б) Векторная постановка графоаналитический метод Н.Н.Моисеева метод зондирования с помощью ЛП последовательностей

3 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Априорные методы МЦО Метод главной компоненты Заключается в том, что критерий качества связывается с одним из показателем, выбранных в роли основного (главного). На остальные показатели накладываются ограничения. В этом случае по главному показателю реализуется критерий оптимальности, по остальным - пригодности. Например, если имеется вектор полезного эффекта в виде W =, где W i (i=1,2...k) - компоненты вектора, например, для оборудования: производительность, экологичность, надежность, себестоимость и т.д., то метод главной компоненты заключается в произвольном выборе одного из компонентов в качестве главного, по которому производится оптимизация и выбирается решение. При этом остальные компоненты переводятся в разряд ограничений. Этот метод прост, нагляден и часто применяется в машиностроительной практике, однако принципиальным его недостатком является произвол в выборе главного критерия. Можно привести много примеров из истории науки и техники, когда произвольный и неверный выбор этого критерия приводит к трагическим последствиям или, по меньшей мере, к малоэффективным результатам.

4 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Априорные методы МЦО Последствия студенческих работ...

5 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Априорные методы МЦО Метод уступок Применяется для задач, критерии которых неравнозначны. Прежде чем решать поставленную задачу по методу уступок, необходимо: I. расположить критерии по их значимости (наиболее важный считается первым); II. отыскать оптимальное значение W 1 * целевой функции W 1 ; III. сделать уступку по первому показателю эффективности, т.е. ухудшить величину W 1 * до значения W 1 **=k 1 W 1 *; IV. ввести в задачу дополнительное ограничение W 1 W 1 **; V. отыскать оптимальное значение W 2 * целевой функции W 2 ; VI. сделать уступку по второму показателю эффективности, т.е. ухудшить величину W 2 * до значения W 2 **=k 2 W 2 *; VII. ввести в задачу дополнительное ограничение W 2 W 2 **; VIII. новую задачу с двумя дополнительными ограничениями решить по третьему показателю эффективности и т.д.; IX. процесс решения задачи заканчивается, когда решение будет получено по всем показателям. Окончательный план и будет наиболее рациональным - получено оптимальное значение наименее важного критерия при условии гарантированных значений предшествующих показателей эффективности.

6 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Априорные методы МЦО Метод уступок Пример Решить задачу по двум критериям, считая первый наиболее предпочтительным. Его отклонение от максимального значения составляет 10%: W 1 = x 1 + 2x 2 max; W 2 = x 1 + 3x 2 min; x 1 4; x 2 5; x 1 0; x 2 0. Решая задачу линейного программирования по первому показателю эффективности W 1, например, в среде пакета EXCEL или графически, получаем, что максимальное значение целевой функции W 1 *=14 достигается при x 1 =4 и x 2 =5. Делаем уступку на 10%, т.е. уменьшаем величину W 1 *=14 до значения W 1 ** =14*0,9=12,6. Вносим в задачу дополнительное ограничение x 1 + 2x 2 12,6. Далее, решая задачу линейного программирования при минимизации второго показателя эффективности, имеем W 2 *=17,6 при x 1 =2,6 и x 2 =5. При этом значение показателя эффективности W 1 не изменилось и равно 12,6.

7 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Априорные методы МЦО Метод комплексного критерия Применяется редко. Заключается в переходе от комплексного критерия к скалярному путем образования суммарного показателя. Чаще всего этот показатель реализуется в виде дроби, где в числителе стоят величины, которые необходимо максимизировать, а в знаменателе – те, которые надо сделать минимальными. Например, (привлекательность)=(производительность)/(стоимость). Метод Гермейера Целевые функции образуют единый показатель, в котором разным слагаемым приписаны разные веса, пронормированные на 1. Q= i W i (u) i =1 i – коэффициент значимости i-го показателя качества. Обычно i определяются с помощью метода экспертных оценок или на основании хорошо апробированных статистических данных. Этой моделью пользуются в задачах, в которых критерии имеют одну и ту же единицу измерения (как правило, стоимостную). Если критерии W i (u) не выражаются в одних и тех же единицах измерения, то их приводят к безразмерному виду.

8 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Априорные методы МЦО Метод справедливого компромисса Для метода Гермейера характерно то, что "сильная целевая функция даст намного больший вклад в общий критерий, а слабая (даже если ее значения будут приближаться к 0), вообще не будет влиять на результат (таким образом можно спроектировать экскаватор с нулевой грузоподъемностью). Q= W i (u) Методы компромиссов лишены этого недостатка (общая целевая функция Q(u) будет стремиться к нулю, если одна из входящих в нее целевых функций W i принимает небольшие значения). Метод идеальной точки Для всех целевых функций в отдельности определяют W i (x)*. Понятно, что одна из этих точек x i * обладает оптимальностью не только для W i, но и для других W j, ij. Поэтому после решения отдельных задач по каждой целевой функции и получения координат n оптимальных точек (n – количество целевых функций) производят расчет других целевых функций для всех значений промежуточных оптимальных точек. И уже из набора x i * определяют x*.

9 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Априорные методы МЦО Метод условного центра масс Пусть последовательно найдены значения экстремумов для каждого показателя W i (u), что соответствует точкам в пространстве параметров с координатами {x 1 i *,x 2 i *,...,x n i *}. "Условная масса" точки выражается - значение i-го показателя эффективности при совокупности управляемых параметров, обеспечивающих экстремальное его значение. Будем полагать, что компромиссному решению будет удовлетворять набор параметров, соответствующих точке с координатами "условного центра масс": Найденные по этому методу средневзвешенные значения параметров x i ** учитывают не только интересы всех показателей качества, но и чувствительность каждого по отношению к данному параметру.

10 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Априорные методы МЦО Векторная постановка В отличие от предыдущей группы методов, где решение чаще всего сводится к одной целевой функции, методы векторной постановки задачи основаны на принципе компромисса, то есть принятия взвешенного решения, в котором фигурируют в определенной пропорции все действующие факторы. При этом, в некоторых методах предлагается не однозначный ответ, а лишь область разумных (рациональных) решений. Принятие же однозначного решения остается прерогативой лица принимающего решение (ЛПР). Основная идея метода Парето заключается в выделении Парето-области – области наиболее целесообразных решений: 1.Множество решений, где с изменением какого- либо из них критерии меняются противоречиво. 2.В Парето-область (при поиске максимума) включаются только те решения x*, для которых не существует такого x**, чтобы для всех критериев удовлетворялось неравенство W i (x**) W i (x*). Пример. Пусть W 1 max, W 2 max. cd – возрастает W 1 и W 2, для bc есть cd. W1W1 W2W2 Парето-область a b c d e

11 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Априорные методы МЦО Графоаналитический метод Н.Н.Моисеева Заключается в последовательном итеративном процессе решения простейших оптимизационных задач. При этом сначала задаются начальными произвольными значениями критериев: W 1 (o) =C 1 ; W 2 (o) =C 2. Затем решаются две оптимизационные задачи: W 1 (o) max, при W 2 (o) =C 2 ; W 2 (o) max, при W 1 (o) =C 1 ; Решив эти две задачи находят точки a и b. Прямая, соединяющая эти две точки является областью Парето в первом приближении. Далее решаются две аналогичные задачи. При этом задаются значениями критериев: W 1 (1) =C 3 ; W 2 (1) =C 4. Затем решаются две оптимизационные задачи: W 1 (1) max, при W 2 (1) =C 4 ; W 2 (1) max, при W 1 (1) =C 3 ; Через полученные точки снова проводят прямые. После соединения точек c и d получают ломаную acdb, которая является областью Парето второго приближения. В большинстве случаев второе приближение является достаточным. W1W1 W2W2 Парето-области 1 и 2 порядка a b c d C1C1 C3C3 C4C4 C2C2