Нелинейная условная оптимизация

Сентябрь 7, 2022

Главная
Алгебра
Нелинейная условная оптимизация

Содержание

2. Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Нелинейная условная оптим-я Постановка задачи Показатель эффективности: прибыль предприятия
3. Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Нелинейная условная оптим-я Группы методов НУО: методы штрафных функций
4. Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Методы штрафных функций С помощью штрафных функций исходная задача
5. Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Методы штрафных функций
6. Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Методы штрафных функций Методы штрафных функций классифицируются в соответствии
7. Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Методы штрафных функций Для учета ограничений-неравенств используют следующие штрафы:
8. Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Методы штрафных функций Штраф квадрата срезки Ω = R*
9. Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Методы штрафных функций Алгоритм МШФ Шаг 1. Задать значения
10. Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Методы штрафных функций Пример решения задачи с использованием МШФ
11. Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Методы штрафных функций Этап 1 P(А1,Ro)=(x1-4)2+(x2-4)2 + 10/(-x1-x2+5) ?
12. Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Методы прямого поиска Ограничения учитываются в явном виде, необязателен
13. Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Методы прямого поиска Метод комплексов Заданы границы значений всех
14. Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Методы прямого поиска Шаг 3. Корректировка для обеспечения допустимости:
15. Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Методы прямого поиска Метод случайного поиска Задаются заранее большие
17. Скачать презентацию

Слайд 2

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Нелинейная условная оптим-я
Постановка задачи
Показатель эффективности: прибыль

предприятия
Управляемые переменные: x1 и x2 – количество комплектов корпусной мебели 1 и 2 вида
Целевая функция:
W=[7-(5+0.1x1)]x1 + [13-(10+0.1x2)]x2 или
W=2x1 - 0.1x12 + 3x2 - 0.1x22
Ограничения:
по использованию сосны (10+x1)x1+(20+x2)x2 ≤ 100
по использованию березы (20+x1)x1+(10+x2)x2 ≤ 120
по использованию дуба (20+x1)x1+(15+x2)x2 ≤ 150
обязательства по контракту x1≥2, x2≥2

Слайд 3

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

функций
методы прямого поиска
методы линеаризации

Слайд 4

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Методы штрафных функций
С помощью штрафных функций

исходная задача условной оптимизации преобразуется в последовательность задач безусловной оптимизации.
P(x,R) = W(x) + Ω(R,g(x),h(x)),
где R - набор штрафных параметров; Ω - штрафная функция, в которую включаются ограничения-равенства и ограничения-неравенства.

Штраф Ω определяется так, чтобы допустимые точки задачи имели преимущество перед недопустимыми в отношении безусловной оптимизации штрафной функции. Здесь штраф как бы создает вдоль границы допустимой области барьер из бесконечно больших значений функции P.
К штрафу выдвигаются следующие требования:
решение подзадач должны стремиться к решению исходной задачи нелинейного программирования;
сложность оптимизации P(x,R) и Ω должна быть такого же порядка, что и W(x).

Слайд 5

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Методы штрафных функций

Слайд 6

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Методы штрафных функций
Методы штрафных функций классифицируются

в соответствии со способами учета ограничений-неравенств g(x), так как ограничения-равенства h(x) учитываются во всех методах одинаково с помощью квадратичного штрафа.
Квадратичный штраф
Ω = R*(h(x))2
P(x,R) = W(x) + R*(h(x))2
При рассмотрении любой штрафной функции требуется выбрать начальное значение R и изменять его после решения каждой подзадачи безусловной оптимизации с тем, чтобы обеспечить сходимость. Для квадратичного штрафа, учитывающего ограничения-равенства, представляется целесообразным начинать с R=0, а затем последовательно увеличивать R на некоторое ΔR или использовать возрастающие степени какого-либо числа, например 10. В результате получаемые точки будут все точнее и точнее удовлетворять ограничениям.

Слайд 7

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

следующие штрафы:
P(x,R) = W(x) + Ω
"Бесконечный" штраф
(для поиска минимума)
Ω = 1020k, k=
Логарифмический штраф
Ω = -R*ln(g(x))
Отрицательный штраф исключают положив Ω=0 для таких x, что g(x)>1. Логарифмический штраф - барьерная функция, имеющая большие по модулю значения функции в недопустимых точках.
Итерационный процесс следует начинать из допустимой начальной точки при положительном начальном значении R (R=10 или R=100). После решения каждой подзадачи условной оптимизации параметр R следует уменьшать и в пределе устремить к нулю.
Штраф обратной функцией
Ω =-R*[1/g(x)]
Итерации следует начинать с начальной допустимой точки при положительном R, значения которого в пределе должно стремиться к нулю.

1, g(x)<=0
0, g(x)>0

Слайд 8

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Методы штрафных функций
Штраф квадрата срезки
Ω =

R* (g(x))2, g(x)=
В данном методе недопустимые точки не создают проблем (в отличие от предыдущих), поэтому он весьма удобен. Кроме того функция P(x,R) определена и непрерывна всюду. Вычисления следует проводить с положительными Ri; после решения очередной подзадачи безусловной оптимизации R необходимо увеличивать.

g(x), g(x)≤0
0, g(x)>0

Слайд 9

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Методы штрафных функций
Алгоритм МШФ
Шаг 1. Задать

значения e1, e2, e3, xo, Ro,
где e1, e2, e3 - соответственно, параметры окончания процедур одномерного и многомерного поиска безусловной оптимизации, а также работы алгоритма штрафных функций;
xo - начальное приближение для x*;
Ro - начальный выбор штрафных параметров.
Шаг 2. Построить P(x,R) = W(x) + Ω(R,g(x),h(x)).
Шаг 3. Найти xt+1 минимизирующее значение P(xt+1,Rt) при фиксированном Rt. В качестве начальной точки использовать xt, а в качестве параметра окончания шага - константу e2 (возможно и e1).
Шаг 4. Проверить, выполняется ли условие
| P(xt+1,Rt)-P(xt,Rt-1) | < e3.
если "да" - положить xt+1=xT и закончить процесс решения;
если "нет" - перейти к следующему шагу.
Шаг 5. Положить Rt+1=Rt+ΔRt в соответствии с используемым правилом пересчета, после чего вернуться к шагу 2.

Слайд 10

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

использованием МШФ
W(x)=(x1-4)2+(x2-4)2 ? min
x1+x2≤5
при e1=0.2, e2=0.4, e3=0.1, Ao=(x1o,x2o)=(1,1), Ro=10, с=10 - коэффициент изменения штрафного параметра (Rt+1=Rt/c).
Понятно, что если бы не было ограничения, функция W(x) имела бы минимум в точке (4,4).
Решение.
Преобразуем неравенство к виду g(x)≤0.
g(x)=x1+x2-5 ≤ 0,
при подстановке в данное ограничение координат начальной точки xo=(1,1), выясняем, что она является допустимой (g(1,1)≤0).
Выбираем штрафную функцию в виде обратной.
P(x,R)=W(x) – R/g(x)

Слайд 11

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Методы штрафных функций
Этап 1
P(А1,Ro)=(x1-4)2+(x2-4)2 + 10/(-x1-x2+5)

? min,
решив задачу многопараметрического безусловного поиска, находим корни минимума данной функции А1=(1.75,1.75) и значение самой функции P(А1,Ro)≈16.79. Проверка на окончание итераций (напр., А1-А0Уменьшаем R: R1=Ro/c=1 и переходим ко второму этапу.
Этап 2
P(А2,R1)=(x1-4)2+(x2-4)2 + 1/(5-x1-x2) ? min,
решив задачу многопараметрического безусловного поиска, находим корни минимума данной функции А2=(2.23,2.23) и значение самой функции P(А2,R1)≈8.12. Проверка на окончание итераций (напр., А2-А1Уменьшаем R: R2=R1/c=0.1 и переходим к следующему этапу.
Этап 3
P(А3,R2)=(x1-4)2+(x2-4)2 + 0.1/(5-x1-x2) ? min,
решив задачу многопараметрического безусловного поиска, находим корни минимума данной функции А3=(2.41,2.41) и значение самой функции P(А3,R2)≈5.61. И так далее до тех пор, пока изменение целевой функции или приращения по всем координатам не станут меньше соответствующих параметров e1, e2, e3.

Слайд 12

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

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

Слайд 13

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

всех переменных xiL, xiU, i=1,2,..., N (размерность задачи), допустимая точка xo, параметр отображения α (рекомендуется α=1.3) и параметры окончания вычислений ε и δ.
Шаг 1. Построение начального комплекса, состоящего из P допустимых точек (рекомендуется P=2N). Для каждой точки p=1,2,...,P-1 случайным образом определить координаты xp;
если xp - недопустимая точка (не удовлетворяет ограничениям-неравенствам), то найти центр тяжести xцт уже найденных точек и положить xp = xp + α(xцт - xp); повторять процедуру до тех пор, пока xp не станет допустимой; если xp - допустимая точка, повторять выбросы следующих точек до тех пор, пока p<>P; вычислить W(xp) для p=0,1,...,P-1.
Шаг 2. Отражение комплекса: выбрать точку xR, для которой W(xR)=max(W(xp))=Wmax (решается задача минимизации);
найти центр тяжести xцт и новую точку xm=xцт+α(xцт-xR);
если xm - допустимая точка и W(xm)≥Wmax, уменьшить в два раза расстояние между xm и центром тяжести xцт, продолжать поиск, пока W(xm)если xm - допустимая точка и W(xm)если xm - недопустимая точка, то перейти к шагу 3.

Слайд 14

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Методы прямого поиска
Шаг 3. Корректировка для

обеспечения допустимости:
если ximесли xim>xiU (верхняя граница допускаемой области), то положить xim = xiU;
если xm - недопустимая точка, то уменьшить в два раза расстояние до центра тяжести; продолжать до тех пор, пока xm не станет допустимой точкой.
Шаг 4. Проверка условий окончания вычислений:
положить и ;
если и ,
то вычисления прекратить; в противном случае перейти к шагу 2.

Слайд 15

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

большие границы значений всех переменных xiL, xiU, i=1,2,...,n (размерность задачи)
В каждой серии с помощью генератора случайных чисел образуется массив из N точек значений функции F(xi), xi∈[xiL,xiU] (N>100). Если точка принадлежит пространству недопустимых точек, то необходимо еще раз повторить вбрасывание.
Среди элементов этого массива значений функции находится оптимальное значение (Wmin|Wmax), а также соответствующее ему значение переменной (xmin|xmax).
По каждой координате рассчитывается новый промежуток, в пределах которого будет производиться последующий выбор из N значений.
Например, для уменьшения промежутка процентов на 10%,
L=0.9*(b-a);
a_new=x_optimal – L/2; if a_newb_new=x_optimal + L/2; if b_new>b then b_new=b;

Нелинейная условная оптимизация

Содержание

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г.Нелинейная условная оптим-яПостановка задачиПоказатель эффективности: прибыль

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

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г.Методы штрафных функцийС помощью штрафных функций

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г.Методы штрафных функций

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г.Методы штрафных функцийМетоды штрафных функций классифицируются

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

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г.Методы штрафных функцийШтраф квадрата срезкиΩ =

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г.Методы штрафных функцийАлгоритм МШФШаг 1. Задать

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

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г.Методы штрафных функцийЭтап 1P(А1,Ro)=(x1-4)2+(x2-4)2 + 10/(-x1-x2+5)

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

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

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г.Методы прямого поискаШаг 3. Корректировка для

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

Похожие презентации