Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Нелинейная условная оптим-я Пример задачи нелинейной условной оптимизации Предприятие может выпускать два вида корпусной мебели. На их изготовление идет древесина трех видов. Запасы древесины на предприятии, нормы их расхода a ij (i=1,2,3; j=1,2), себестоимость с j и оптовые цены указаны в таблице. Из-за брака в процессе производства расход древесины зависит от объема x j производства изделий и в первом приближении выражается линейной функцией a ij +x j, а себестоимость продукции - функцией c j +0.1x j. Предприятие обязано с целью изучения спроса населения выпустить не менее двух комплектов мебели каждого вида. Составить план выпуска изделий, максимизирующий прибыль. ПородаЗапас сырья, м 3 Нормы расхода на изделие вида 12 сосна береза дуб себестоимость c j, тыс.руб.510 цена, тыс.руб.713 Rev /

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Нелинейная условная оптим-я Постановка задачи Показатель эффективности: прибыль предприятия Управляемые переменные: x 1 и x 2 – количество комплектов корпусной мебели 1 и 2 вида Целевая функция: W=[7-(5+0.1x 1 )]x 1 + [13-(10+0.1x 2 )]x 2 или W=2x x x x 2 2 Ограничения: по использованиюсосны(10+x 1 )x 1 +(20+x 2 )x по использованиюберезы(20+x 1 )x 1 +(10+x 2 )x по использованиюдуба(20+x 1 )x 1 +(15+x 2 )x обязательства по контрактуx 1 2, x 2 2

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

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Методы штрафных функций С помощью штрафных функций исходная задача условной оптимизации преобразуется в последовательность задач безусловной оптимизации. P(x,R) = W(x) + (R,g(x),h(x)), где R - набор штрафных параметров; - штрафная функция, в которую включаются ограничения-равенства и ограничения-неравенства. Штраф определяется так, чтобы допустимые точки задачи имели преимущество перед недопустимыми в отношении безусловной оптимизации штрафной функции. Здесь штраф как бы создает вдоль границы допустимой области барьер из бесконечно больших значений функции P. К штрафу выдвигаются следующие требования: решение подзадач должны стремиться к решению исходной задачи нелинейного программирования; сложность оптимизации P(x,R) и должна быть такого же порядка, что и W(x).

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

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

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Методы штрафных функций Для учета ограничений-неравенств используют следующие штрафы: P(x,R) = W(x) + "Бесконечный" штраф (для поиска минимума) = k, 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

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Методы штрафных функций Штраф квадрата срезки = R* (g(x)) 2,g(x)= В данном методе недопустимые точки не создают проблем (в отличие от предыдущих), поэтому он весьма удобен. Кроме того функция P(x,R) определена и непрерывна всюду. Вычисления следует проводить с положительными R i ; после решения очередной подзадачи безусловной оптимизации R необходимо увеличивать. g(x), g(x) 0 0, g(x)>0

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Методы штрафных функций Алгоритм МШФ Шаг 1. Задать значения e 1, e 2, e 3, x o, R o, где e 1, e 2, e 3 - соответственно, параметры окончания процедур одномерного и многомерного поиска безусловной оптимизации, а также работы алгоритма штрафных функций; x o - начальное приближение для x*; R o - начальный выбор штрафных параметров. Шаг 2. Построить P(x,R) = W(x) + (R,g(x),h(x)). Шаг 3. Найти x t+1 минимизирующее значение P(x t+1,R t ) при фиксированном R t. В качестве начальной точки использовать x t, а в качестве параметра окончания шага - константу e 2 (возможно и e 1 ). Шаг 4. Проверить, выполняется ли условие | P(x t+1,R t )-P(x t,R t-1 ) | < e 3. если "да" - положить x t+1 =x T и закончить процесс решения; если "нет" - перейти к следующему шагу. Шаг 5. Положить R t+1 =R t + R t в соответствии с используемым правилом пересчета, после чего вернуться к шагу 2.

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Методы штрафных функций Пример решения задачи с использованием МШФ W(x)=(x 1 -4) 2 +(x 2 -4) 2 min x 1 +x 2 5 при e 1 =0.2, e 2 =0.4, e 3 =0.1, A o =(x 1 o,x 2 o )=(1,1), R o =10, с=10 - коэффициент изменения штрафного параметра (R t+1 =R t /c). Понятно, что если бы не было ограничения, функция W(x) имела бы минимум в точке (4,4). Решение. Преобразуем неравенство к виду g(x) 0. g(x)=x 1 +x , при подстановке в данное ограничение координат начальной точки x o =(1,1), выясняем, что она является допустимой (g(1,1) 0). Выбираем штрафную функцию в виде обратной. P(x,R)=W(x) – R/g(x)

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Методы штрафных функций Этап 1 P(А 1,R o )=(x 1 -4) 2 +(x 2 -4) /(-x 1 -x 2 +5) min, решив задачу многопараметрического безусловного поиска, находим корни минимума данной функции А 1 =(1.75,1.75) и значение самой функции P(А 1,R o ) Проверка на окончание итераций (напр., А 1 -А 0

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

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Методы прямого поиска Метод комплексов Заданы границы значений всех переменных x iL, x iU, i=1,2,..., N (размерность задачи), допустимая точка x o, параметр отображения (рекомендуется =1.3) и параметры окончания вычислений и. Шаг 1. Построение начального комплекса, состоящего из P допустимых точек (рекомендуется P=2N). Для каждой точки p=1,2,...,P-1 случайным образом определить координаты x p ; если x p - недопустимая точка (не удовлетворяет ограничениям- неравенствам), то найти центр тяжести x цт уже найденных точек и положить x p = x p + (x цт - x p ); повторять процедуру до тех пор, пока x p не станет допустимой; если x p - допустимая точка, повторять выбросы следующих точек до тех пор, пока pP; вычислить W(x p ) для p=0,1,...,P-1. Шаг 2. Отражение комплекса: выбрать точку x R, для которой W(x R )=max(W(x p ))=W max (решается задача минимизации); найти центр тяжести x цт и новую точку x m =x цт + (x цт -x R ); если x m - допустимая точка и W(x m ) W max, уменьшить в два раза расстояние между x m и центром тяжести x цт, продолжать поиск, пока W(x m )

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Методы прямого поиска Шаг 3. Корректировка для обеспечения допустимости: если x i m x iU (верхняя граница допускаемой области), то положить x i m = x iU ; если x m - недопустимая точка, то уменьшить в два раза расстояние до центра тяжести; продолжать до тех пор, пока x m не станет допустимой точкой. Шаг 4. Проверка условий окончания вычислений: положить и; если и, то вычисления прекратить; в противном случае перейти к шагу 2.

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Методы прямого поиска Метод случайного поиска Задаются заранее большие границы значений всех переменных x iL, x iU, i=1,2,...,n (размерность задачи) 1) В каждой серии с помощью генератора случайных чисел образуется массив из N точек значений функции F(x i ), x i [x iL,x iU ] (N>100). Если точка принадлежит пространству недопустимых точек, то необходимо еще раз повторить вбрасывание. 2) Среди элементов этого массива значений функции находится оптимальное значение (W min |W max ), а также соответствующее ему значение переменной (x min |x max ). 3) По каждой координате рассчитывается новый промежуток, в пределах которого будет производиться последующий выбор из N значений. Например, для уменьшения промежутка процентов на 10%, L=0.9*(b-a); a_new=x_optimal – L/2; if a_newb then b_new=b;

Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Методы линеаризации Идея методов заключается в сведении задачи нелинейного программирования к задаче линейного программирования. С этой целью нелинейные функции целевой функции W(x) и ограничений g(x), h(x) в ряд Тейлора до членов первого порядка в окрестности точки линеаризации x t, что позволяет W(x), g(x), h(x) аппроксимировать линейными функциями и свести общую задачу нелинейного программирования к следующей задаче линейного программирования. W(x) min (max) g j (x) 0, j=1..J h k (x)=0, k=1..K x iL