Green-sell.info

Новые технологии
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

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

Цель: научиться методам решения многокритериальных ЗЛП с помощью ЭВМ, используя метод последовательных уступок.

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

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

ПРИМЕР 4.1.Математическая модель трехкритериальной задачи имеет вид:

Решить задачу методом последовательных уступок, выбрав уступку по первому критерию d1=4, а по второму d2=5.

Открываем электронную книгу Excel и, как и для решения однокритериальной задачи определяем ячейки под переменные x1, x2, x3. Для этого в ячейку А1 вводим подпись «Переменные», а соседние три ячейки В1, С1 и D1 вводим значения переменных. Это могут быть произвольные числа, например единицы, далее они будут оптимизироваться. Во второй строке задаем целевые функции. В А2 вводим подпись «Целевые», а в В2 формулой «=2*B1+C1–3*D1» задаем первую целевую функцию 2x1+ x2–3x3. Аналогично в С2 и D2 вводим вторую и третью целевую функцию, вводя в С2 «=B1+3*C1–2*D1», а в D2 «= –B1+2*C1+4*D1». В третью строку вводим левые части ограничений. Для этого вводим в А3 подпись «Ограничения», в В3 формулу «=B1+3*C1+2*D1», в С3 формулу «=2*B1–C1+D1» и в D3 формулу «=B1+2*C1».

Предварительные действия завершены. Вызываем надстройку «Поиск решения» в меню «Сервис». На первом этапе оптимизируем первую целевую функцию.

После открытия окна «Поиск решения» в поле «Установить целевую» ставим курсор и делаем ссылку на ячейку В2, щелкая по ней мышью. В окне появится $B$2. В связи с тем, что целевая функция максимизируется, далее нужно проверить, что флажок ниже поля стоит напротив надписи «Равной максимальному значению». После ставим курсор в поле «Изменяя ячейки» и обводим ячейки с переменными В1, С1 и D1, выделяя ячейки с переменными. В поле появится $B$1:$D$1. В нижней части окна находится поле «Ограничения». Для того чтобы ввести ограничения, нажимают кнопку «Добавить», откроется окно «Добавление ограничения». В левом поле «Ссылка на ячейку» вводят ссылку на левую часть первого ограничения – ячейку В3, в центральном окне определяем знак ≥ и в правом «Ограничения» набираем правую часть ограничения – число 1. Нажимаем «ОК», видим, что ограничение появилось в окне. Нажимаем вновь «Добавить», вводим «С3» «≤» и «16». Вновь нажимаем «Добавить», вводим «D3» «≤» и «24». Для ввода дополнительных ограничений x1, x2, x30 вновь нажимаем «Добавить», ставим курсор в левое поле и обводим ячейки В1, С1 и D1 (результат $B$1:$D$1) в среднем окне ставим «≥» и в правом число 0. Результат на рис.4.1.

Рисунок 4.1 Окно «Поиск решения» первого этапа

Для запуска вычислений нажимаем кнопку «Выполнить». Появляется надпись, что решение найдено. Выбираем «Сохранить найденное решение» и нажимаем «ОК» – видим результат (рис. 4.2): в ячейках В1, С1 и D1 значения переменных x1, x2, x3, соответствующие оптимальному решению: 11,2; 6,4 и 0. В ячейки В2 – значение целевой функции 28,8.

Рисунок 4.2 Решение первого этапа примера 4.1

На втором этапе оптимизируется вторая целевая функция. При этом первую, в соответствие с методом последовательных уступок, можно ухудшить на величину не более чем d1=4. По этой причине, на втором шаге, значения в ячейке В2 (где хранится первая целевая функция, которая максимизируется) может быть не меньшее, чем 28,8–4=24,8. Вызываем надстройку «Сервис/Поиск решения», видим, что все прежние данные остались введенными. Меняем ссылку на целевую функцию. Ставим курсор в поле «Установить целевую» и щелкаем по ячейке С2, в которой находится ссылка на вторую целевую функцию. Так как вторая целевая функция минимизируется, то ставим флажок в поле напротив надписи «Равной минимальному значению». Вводим дополнительное ограничение, связанное с уступкой по первому критерию. Переводим курсор в поле «Ограничения» и нажимаем кнопку «Добавить». В появившемся окне «Добавление ограничения» в трех окнах (слева направо) вводим данные «В2», «≥», «24,8». Результат на рис.4.3.

Рисунок 4.3 Окно «Поиск решения» второго этапа

Для запуска вычислений нажимаем кнопку «Выполнить». Появляется надпись, что решение найдено. Выбираем «Сохранить найденное решение» и нажимаем «ОК» – видим результат (рис. 4.4): переменные x1, x2, x3равны 10,2; 4,4; 0. Вторая целевая функция равна 23,4 (ячейка В2). Первая равна своему минимальному значению 24,8 (ячейка С2).

Рисунок 4.4 Решение второго этапа примера 4.1

На третьем этапе делаем уступку по второму критерию. Величина уступки равна d2=5. Так, как вторая функция минимизируется, то ее значение не должно превышать 23,4+5=28,4. Вызываем надстройку «Сервис/Поиск решения». Меняем ссылку на целевую функцию. Ставим курсор в поле «Установить целевую» и щелкаем по ячейке D2, в которой находится ссылка на третью целевую функцию. Так как третья целевая максимизируется, то ставим флажок в поле напротив надписи «Равной максимальному значению». Вводим дополнительное ограничение, связанное с уступкой по второму критерию. Переводим курсор в поле «Ограничения» и нажимаем кнопку «Добавить». В появившемся окне «Добавление ограничения» вводим данные «С2», «≤», «28,4». Результат на рис.4.5.

Рисунок 4.5 Окно «Поиск решения» третьего этапа

Для запуска вычислений нажимаем кнопку «Выполнить». Появляется надпись, что решение найдено. Выбираем «Сохранить найденное решение» и нажимаем «ОК» – видим результат (рис. 4.6): переменные x1, x2, x3равны 10,76; 6,62; 1,11. Целевые функции равны, соответственно, 24,8; 28,4 и 6,93. Это окончательный ответ. Все дополнительные условия соблюдены.

Рисунок 4.6 Окончательное решение примера 4.1

Задание 4.1. Решить методом последовательных уступок двухкритериальную задачу, представленную математической моделью:

Уступка по первому критерию оптимизации d1=2.

Значение неизвестного параметра а взять равным номеру варианта.

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

Задание 4.2. Молочный комбинат, исследовав конъюнктуру местного рынка, решил выпускать новый вид йогурта, который был бы конкурентно способен. При этом необходимо разработать план организации производства для выпуска данного продукта. Основными затратами на разработку являются затраты на модернизацию оборудование х и затраты на научные исследования у. При исследовании установлено, что себестоимость единицы продукции при этом будет зависеть от затрат как F1(x, y) = 12 + ax + (31а)y, а качество продукции как F2 = 6 + (31а)x + аy. Ставится задача минимизировать себестоимость (цену) данного продукта и максимизировать качество выпускаемой продукции. Из двух целевых функций основной считается цена (себестоимость продукции). По фактору «цена» можно сделать уступку 3 денежные единицы. Решить задачу методом последовательных уступок и найти оптимальные значения факторов х и у, а также значения целевых функций, если на факторы наложены ограничения:

Значение неизвестного параметра а взять равным номеру варианта.

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

Задание 4.3. Решить методом последовательных уступок двухкритериальную задачу, представленную математической моделью:

Уступка по первому критерию оптимизации d1 равна номеру варианта а.

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

Задание 4.4. Решить методом последовательных уступок трехкритериальную задачу, представленную математической моделью:

Значение неизвестного параметра а взять равным номеру варианта.

Уступки по первому и второму критерию оптимизации равны d1=6,d2=4.

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

Задачи многокритериальной оптимизации;

Однокритериальные задачи

Методы принятия решений

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

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

  • поиска экстремума алгебраической функции-зависимости критерия от параметров системы К = ƒ(х). Для задачи с плавным изменением функции экстремум находится дифференцированием. Решение — конкретное численное значение;
  • вариационного исчисления, если критерий описывается функционалом, то есть интегралом от выражения, зависящего от параметров, их функции и производных. Решение имеет вид функциональной зависимости (аналитического уравнения), например, уравнения формы поверхности равнопрочного вала, закона нагружения;
  • линейного программирования, когда критерий и условия, накладываемые на решение задачи, являются линейными функциями параметров (равенства или неравенства). Решение — численное значение;
  • нелинейного программирования;
  • поиска вариантов решений методами полного или частичного перебора.
Читать еще:  Как отключить оптимизацию на телефоне

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

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

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

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

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

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

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

Область Парето — это область компромиссов: все решения здесь равнозначны, а окончательный выбор решения связан с введением дополнительного условия, часто — субъективного характера. Поиск решений, оптимальных по Парето, позволяет объективно сократить область возможного выбора, причем наибольшее усечение области допустимых решений достигается при назначении двух критериев. При увеличении числа критериев эффективность этого метода падает. Целесообразен одновременный учёт 2…5 критериев.

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

Например, задачу минимизации массы и потерь энергии изделия можно свести к задаче проектирования изделия, у которого потери не превысят, допустим, 5 % , а масса — 10 кг. Если в полученной области будет находиться несколько решений, то ограничения можно ужесточить (скажем, ограничить предельную массу 6 кг). Если же решений нет, то ограничения смягчают.

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

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

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

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

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

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

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

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

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

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

В качестве целевой функции ƒ часто используют:

  • аддитивную функцию, то есть функцию, подсчитываемую для каждого варианта (j=1,…, n) решения как сумму отдельных критериев К (i=1,…, m) с

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

Суть данного метода заключается в том, что частные критерии Fi (X), i = каким-либо образом объединяются в один интегральный критерий F (X) = Ф (F1 (X), F2 (X),…, Fn (X)) , а затем находится максимум или минимум данного критерия.

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

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

1) аддитивный критерий;

2) мультипликативный критерий;

3) максиминный (минимаксный) критерий.

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

,

где n – количество объединяемых частных критериев; Ci – весовой коэффициент i-го частного критерия; Fi (X) – числовое значение i-го частного критерия; Fi (0) (X) – i-й нормирующий делитель; fi (X) – нормированное значение i-го частного критерия.

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

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

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

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

Преимущество аддитивного критерия: как правило, всегда удается определить единственный оптимальный вариант решения.

— трудности (субъективизм) в определении весовых коэффициентов;

— аддитивный критерий не вытекает из объектной роли частных критериев и поэтому выступает как формальный математический прием;

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

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

Таблица 3.2 – Исходные данные для определения
оптимального варианта исполнения машины

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

.

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

Значения обобщенного аддитивного критерия рассчитываются для каждого варианта машины.

Читать еще:  Что значит оптимизировать приложения

Вариант 1. F (X) = 0,6(1000/4000) + 0,4(1500/1500) = 0,55.

Вариант 2. F (X) = 0,6(2000/4000) + 0,4(1000/1500) = 0,558.

Вариант 3. F (X) = 0,6(4000/4000) + 0,4(500/1500) = 0,732.

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

Один из недостатков этого метода заключается в том, что весовые коэффициенты назначает проектировщик. Разные проектировщики могут назначать разные весовые коэффициенты. Пусть, например, C1 = 0,4;
C
2 = 0,6. Определим теперь значения аддитивных критериев для вариантов машины.

Вариант 1. F (X) = 0,4 × 0,25 + 0,6 × 1 = 0,7.

Вариант 2. F (X) = 0,4 × 0,5 + 0,6 × 0,67 = 0,602.

Вариант 3. F (X) = 0,4 × 1 + 0,6 × 0,33 = 0,598.

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

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

,

где П – знак произведения; Сi – весовой коэффициент i-го частного критерия; Fi(X) – числовое значение i-го частного критерия.

Преимущества мультипликативного критерия:

— не требуется нормирование частных критериев;

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

— трудности (субъективизм) в определении весовых коэффициентов частных критериев;

— перемножение разных размерностей;

— взаимная компенсация значений частных критериев.

Максиминный (минимаксный) критерий. Эти критерии работают по принципу компромисса, который основывается на идее равномерности. Сущность принципа максимина заключается в следующем. При проектировании сложных систем, при наличии большого числа частных критериев установить между ними аналитическую взаимосвязь очень сложно. Поэтому стараются найти такие значения переменных (параметров) X = <x1, x2,…, xm>, при которых нормированные значения всех частных критериев равны между собой:

где Ci – весовой коэффициент i-го частного критерия; fi (X) – нормированное значение i-го частного критерия; K – константа.

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

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

Такой принцип выбора Х (0) иногда носит название гарантированного результата. Он заимствован из теории игр, где является основным принципом.

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

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

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

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

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

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

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

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

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

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

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

Область Парето — это область компромиссов: все решения здесь равнозначны, а окончательный выбор решения связан с введением дополнительного условия, часто — субъективного характера. Поиск решений, оптимальных по Парето, позволяет объективно сократить область возможного выбора, причем наибольшее усечение области допустимых решений достигается при назначении двух критериев. При увеличении числа критериев эффективность этого метода падает. Целесообразен одновременный учёт 2…5 критериев.

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

Например, задачу минимизации массы и потерь энергии изделия можно свести к задаче проектирования изделия, у которого потери не превысят, допустим, 5 % , а масса — 10 кг. Если в полученной области будет находиться несколько решений, то ограничения можно ужесточить (скажем, ограничить предельную массу 6 кг). Если же решений нет, то ограничения смягчают.

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

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

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

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

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

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

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

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

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

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

В качестве целевой функции ƒ часто используют:

  • аддитивную функцию, то есть функцию, подсчитываемую для каждого варианта (j=1,…, n) решения как сумму отдельных критериев К (i=1,…, m) с учётом их относительной важности λi, то есть ƒj = Σλi·Кij. Коэффициент λi называется весовым. Обычно принимают Σλi=1;
  • мультипликативную функцию, то есть функцию, подсчитываемую как произведение отдельных критериев с соответствующими степенями λi, то есть ƒj = П(Кij) λ i.
Читать еще:  Операционная система linux какую выбрать

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

В качестве примера рассмотрим такой показатель качества как компактность. Под ним обычно понимается совокупность минимизируемых критериев — габаритных размеров, допустим x, y, z. Тогда целевой функции компактности в аддитивной формулировке ƒа=x+y+z будет соответствовать периметр, а в мультипликативной ƒм=x·y·z — объём.

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

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

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

1 Основные группы методов

  • 2 Эвристические методы
    • 2.1 Метод итераций (последовательного приближения)
    • 2.2 Метод декомпозиции
    • 2.3 Метод контрольных вопросов
    • 2.4 Метод мозговой атаки (штурма)
      • 2.4.1 Метод синектики
    • 2.5 Теория решения изобретательских задач (ТРИЗ)
    • 2.6 Метод морфологического анализа
    • 2.7 Функционально-стоимостной анализ
    • 2.8 Методы конструирования
  • 3 Экспериментальные методы
    • 3.1 Цели и виды экспериментальных методов
    • 3.2 Планирование эксперимента
    • 3.3 Машинный эксперимент
    • 3.4 Мысленный эксперимент
  • 4 Формализованные методы
    • 4.1 Методы поиска вариантов решений
    • 4.2 Методы автоматизации процедур проектирования
    • 4.3 Методы оптимального проектирования
      • 4.3.1 Задачи оптимального проектирования
      • 4.3.2 Методы принятия решений
        • 4.3.2.1 Однокритериальные задачи
        • 4.3.2.2 Задачи многокритериальной оптимизации

4.3.3 Принятие решений в условиях неопределенности

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

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

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

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

Креативный подход в рекламе — это не свободное творчество, а расчет и здравый смысл. Именно поэтому креатив в рекламе — это не мода, а необходимость.

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

«Творчество» и «креативность» — далеко не синонимы. Творчес­кий процесс основывается на вдохновении автора, его опыте, спо­собностях, интуиции. При создании рекламы руководствоваться исключительно внутренними побуждениями нельзя. Здесь творческое пространство строго ограниченно векторами и рамками коммерческой деятельности. Его довольно жестко контролирует креативный бриф — документ, сжато определяющий ситуацию маркетинга и конкретные задачи рекламы.

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

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

Например, на символе сети магазинов «Рамстор» красуется зеленый кенгуру с красным галстуком-бабочкой и почему-то никто не спросит: «А почему кенгуру зеленый?». Креативный зверек нравится всем, и это самое главное.

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

Практические задания

Пр. задание №1

1. Изучить информацию «Эвристические методы» (см. из мет. «Орг. Проект деят»)

2. Определить (обосновать) применение изучаемых методов в предпроектных исследованиях. Результаты представить в таблице.

Задача многокритериальной оптимизации. Multiobjectivization

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

Постановка задачи [ править ]

Так как не существует единого решение, которое было бы максимальным для всех целевых функций, вместо него можно искать множество [math]X^* subseteq X [/math] множество Парето оптимальных значений.

Множество Парето оптимальных значений [ править ]

Выражение [math]x succ x^*[/math] означает, что [math]x[/math] доминирует над [math]x^*[/math] .

Говорят, что [math]x[/math] доминирует над [math]x^*[/math] . по Парето, если [math]x[/math] не хуже [math]x^*[/math] по всем критериям и хотя бы по одному критерию превосходит [math]x^*[/math] . В таком случае в выборе [math]x^*[/math] нет смысла, т.к. [math]x[/math] по всем параметрам не уступает, а по каким-то и превосхожит [math]x^*[/math] . Если рассматривать всего два критерия то на рис. 1 показана область пространства, доминируемая данным решением А. Эта область «замкнута»: элементы на ее границе также доминируемы А

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

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

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

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

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

Hill-Climbers [ править ]

[math]x’_1 leftarrow [/math] Mutate [math](P)[/math] , [math]x_2 leftarrow [/math] Mutate [math](P)[/math]
if [math](H(x_1,x’_1)+H(x_2,x’_2) gt H(x_1,x’_2)+H(x_2,x’_1))[/math]

[math]P leftarrow P cup x’_1 setminus x_1[/math]

[math]P leftarrow P cup x’_2 setminus x_2[/math]

Hierarchical-if-and-only-if function [ править ]

H-IIF – предназначена для моделирования проблемы с блочной структурой, каждый блок которой строго связан с остальными блоками.

[math] f(B)= begin1,& mbox |B| = 1, mbox < else>\|B|+f(B_L)+f(B_R),& mbox(forall i mbox < or >forall i ) \f(B_L) + f(B_R), & mbox end [/math] ,

где [math]B[/math] – блок бит [math], |B|[/math] – размер блока, а [math]B_L, B_R[/math] – левая и правая часть блока соответственно.

Применяя к этой задаче мультиобъективизацию, разобьём задачу [math]f[/math] на [math]k[/math] -задач.

Представим, как будет выглядеть [math]f(B)[/math] :

[math] f(B)= begin 0, & mbox |B| = 1 mbox< and >b_1 neq k, mbox < else>\1,& mbox |B| = 1 mbox< and >b_1 = k, mbox < else>\|B|+f_k(B_L)+f_k(B_R),& mbox(forall i ), \f_k(B_L) + f_k(B_R), & mbox end [/math]

где [math]f_0(x)[/math] – первая цель; [math]f_0(x)[/math] – вторая цель.

Данный подход помогает избежать проблему локальных максимумов (минимумов).

Задача коммивояжера [ править ]

Задача коммивояжера (TSP)является наиболее известно из всего класса [math]NP[/math] -сложных задач. Формулируется задача следующим образом:

Задано [math]C= [/math] – множество городов и для каждой пары [math][/math] задано расстояние. Наша цель – найти цепь из городов, минимизирующую величину:

Применяя к этой задаче мультиобъктивизацию, нужно разбить её на подзадачи. TSP – является [math]NP[/math] -сложной именно потому, что нет хорошего разложения этой задачи. Тем не менее задачу можно разбить на две или больше подтуров, каждый из которых мы можем минимизировать.

Представим подтуры в виде двух городов. Тогда наша задача примет вид:

где [math]a[/math] и [math]b[/math] – два города, указанных априори. Если [math]pi (a) lt pi (b)[/math] , меняем их местами.

Предполагается, что [math]a[/math] и [math]b[/math] выбраны произвольно.

Ссылка на основную публикацию
ВсеИнструменты
Adblock
detector