Шпаргалка по "Экономико-математическому моделированию"

 

 

 

29. ПОНЯТИЕ  О МНОЖЕСТВЕ ПАРЕТО

 

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

r1(x1,x2)→max

r2(x1,x2)→max

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

 

 

27. СОКРАЩЕНИЕ  ЧИСЛА КРИТЕРИЕВ В МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧАХ.

 

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

Задается пороговое  значение коэффициента корреляции r₀, с помощью которого производится построение срезов корреляционного цилиндра, из которых формируется последовательность подграфов, принимаемых в качестве "плеяд". Узлами этих подграфов являются все рассматриваемые признаки, а ребрами – корреляционные связи по абсолютной величине больше r₀. При последовательном уменьшении критического уровня, количество ребер увеличивается, плеяды становятся крупнее и начинают сливаться друг с другом. Окончательно выбирается порог r₀, скорее отвечающий эстетическим вкусам исследователя, чем каким-то формальным правилам.

 

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

Чем ближе к 1 коэффициент  корелляции, тем теснее связь и  тме разброс более приближен к функциональной связи.поскольку коэффициенты корелляции являются случайными(они получены по случайным данным) они могут быть статистически незначимы. 0≤‌‌‌ r≤1

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

 

28. ОСОБЕННОСТИ  И СПОСОБЫ РЕШЕНИЯ МНОГОКРИТЕРИАЛЬНЫХ  ЭКСТРЕМАЛЬНЫХ ЗАДАЧ

 

Далее рассмотрим многокритериальные задачи с уже проведенным сокращением критериев. Есть 3 основных метода решения: 1. преобразование(свертка) всех частных критериев в один обобщенный. 2. выбор из всех частных критериев одного самого важного с переводом остальных в ограничения, чтобы были не хуже наперед заданных значений. Задаваемые в качестве ограничения заданные значения субъективны и повлияют на возможное достижение экстремума по основному показателю. 3. назначение уступок, которое заключается в том, что мы соглашаемся несколько уступить по одним критериям, за счет чего произвести улучшение по другим.

 

 

 

 

 

 

30. ВИДЫ СВЕРТКИ  КРИТЕРИЕВ

 

1)близость к идеалу. Лучшим решением считают такое, которое наиболее близко к идеалу.

R=√(r₁(x₁x₂)-r₁^идеал)² + (r₂(x₁x₂)-r₂^идеал)²

R→min

На практике часто  возникают субъективные предпочтения того или иного критерия, он для  нас более важен. Относительную  важность можно учесть с помощью  весового коэффициента. R=√β(r₁(x₁x₂)-r₁^идеал)² + r₂(x₁x₂)-r₂^идеал)²

Если β близок к  нулю, то min R будет достигаться тогда когда r2→max.

2. взвешенная сумма(каждый  критерий со своим весовым  коэф-том). R=∑α_ir_i Особенности применения метода: типы всех частных критериев должны быть одинаковы (все max или min) Величины весовых коэф-тов учитывают: 1.относительную важность частных критериев 2.устраняют разные размерности 3. величину значения критерия надо выбирать так, чтобы диапазон изменчивости были примерно одинаковы. Весовые коэф-ты одновременно выполняют 3 функции, что очень неудобно в общем случае. Поэтому такой способ свертки критериев целесообразно применять тогда, когда частные критерии одинаковы. Разные критерии: R = ∑ α_ir_i^норм=∑ αi ·r_i-r_imin/r_imax-r_imin(∑ α_i=1)

3.использование функции  желательности. Если мы вводим  качественную оценку для частного  критерия, то для перехода к количественной вспомогательной переменной у нужно сформировать для каждого участка линейную связь между у и х. у=а+br_i. а и b находятся из известных соответствующих границах r и у. Т.о. на 1 шаге каждому ri ставится в соответствие частная функция желательности di, с учетом желаемых оценок. Приведенная зависимость частной функции желательности обладает след. св-ми:1. в области оч.хороших или оч.плохих оценок крутизна функций маленькая, т.е. маленькая чувствительность. 2.в средней части крутизна высокая, т.е. высокая чувствительность.

После построения частной  функции желательности вводится обобщенная функция желательности. D=^m√d1d2…d m

Данная зависимость  обладает след.св-ми:1.если хотя бы один критерий имеет полностью неприемлимое значение d≈ 0, то и D будет неприемлемо. 2.для того, чтобы D было близко к 1 нужно, чтобы все частные функции желательности были близкими к 1.

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

 

32. ГРАДИЕНТНЫЕ МЕТОДЫ ОРГАНИЗАЦИИ ЭКСТРЕМАЛЬНЫХ ЭКСПЕРИМЕНТОВ. МЕТОД ГРАДИЕНТА.

 

Метод градиента  в чистом виде формирует шаг по переменным как функцию от градиента R(x) в текущей точке поиска. Простейший алгоритм поиска min R(х) записывается в векторной форме следующим образом:

xⁱ⁺¹=xⁱ – h grad R(xⁱ)

или в скалярном  виде:

x_jⁱ⁺¹=x_jⁱ – h dR/d x_jⁱ   j=1,…,n

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

Поиск каждой новой  точки состоит из двух этапов:

1)  оценка  градиента R(x)  путем вычисления частных производных от R(x) по каждой переменной х_j

2) рабочий шаг  по всем переменным одновременно.

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

x_jⁱ⁺¹=x_jⁱ-h Cos φ_j    где Cos φ_j = (dR/d x_j) / Igrad R(x)I

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

Наибольшее распространение получили следующие алгоритмы:

hⁱ = соnst=h (без коррекции);  

hⁱ = h^i-1 /2, если R(xⁱ)< R(x^i-1);   hⁱ = h^i-1, если  R(xⁱ)> R(x^i-1)

hⁱ = h^i-1, если α₁≤α≤α₂; hⁱ = 2h^i-1, если α_1> α; hⁱ = h^i-1/3, если  α₂< α,

где α  — угол между градиентами на предыдущем и текущем шаге; α₁ и α₂ — заданные пороговые значения выбираются субъективно (например, α₁= π/6, α₂=π/3).

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

Для оценки частных производных используются разностные

методы.

1 . Алгоритм с центральной пробой

dR/d x_i ≈ R(x₁,…,x_i+g_i,…,x_n) – R(x₁,…,x_i,…,x_n) / g_i

2. Алгоритм с  парными пробами

dR/d x_i ≈ R(x₁,…,x_i+g_i,…,x_n) – R(x₁,…,x_i- g_i,…,x_n) / g_i

где g_i  — пробный шаг по i-й переменной, выбираемый достаточно малым для разностной оценки производной.

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

На рис.  приведена одна из возможных траекторий поиска минимума двумерной функции  градиентным методом (наряду с другими  ниже рассматриваемыми методами).

2 – метод градиента

Условием  окончания поиска может являться малость модуля градиента R(x), т.е. |gradR(x)|< ε

 

33. ГРАДИЕНТНЫЕ МЕТОДЫ ОРГАНИЗАЦИИ ЭКСТРЕМАЛЬНЫХ ЭКСПЕРИМЕНТОВ. МЕТОД КРУТОГО ВОСХОЖДЕНИЯ.

 

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

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

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

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

 

 

37. МЕТОДЫ СЛУЧАЙНОГО ПОИСКА ПРИ ОРГАНИЗАЦИИ ЭКСТРЕМАЛЬНЫХ ЭКСПЕРИМЕНТОВ.

 

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

Сгенерируем случайный  вектор и будем использовать его  вместо градиента. Этот метод использует одномерную оптимизацию – подбор шага

В этом методе есть два параметра, задаваемых пользователем.

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

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

 

34. БЕЗГРАДИЕНТНЫЕ МЕТОДЫ ОРГАНИЗАЦИИ ЭКСТРЕМАЛЬНЫХ ЭКСПЕРИМЕНТОВ. МЕТОД ГАУССА-ЗАЙДЕЛЯ.

 

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

В ряде случаев (для сепарабельных критериев  оптимальности, т.е. таких R(x₁,x₂,…,x_i,…,x_n), которые можно представить в виде

   R(x)=f(x₁)+f(x₂)+…+f(x_i)+…+f(x_n)

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

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