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

1 Теория принятия решенийПетрГУ, А.П.Мощевикин, 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 /

2 Теория принятия решенийПетрГУ, А.П.Мощевикин, 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

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

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

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

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) + "Бесконечный" штраф (для поиска минимума) = 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 1. Логарифмический штраф - барьерная функция, имеющая большие по модулю значения функции в недопустимых точках. Итерационный процесс следует начинать из допустимой начальной точки при положительном начальном значении R (R=10 или R=100). После решения каждой подзадачи условной оптимизации параметр R следует уменьшать и в пределе устремить к нулю. Штраф обратной функцией =-R*[1/g(x)] Итерации следует начинать с начальной допустимой точки при положительном R, значения которого в пределе должно стремиться к нулю. 1, g(x)0">

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

9 Теория принятия решенийПетрГУ, А.П.Мощевикин, 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.

10 Теория принятия решенийПетрГУ, А.П.Мощевикин, 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)

11 Теория принятия решенийПетрГУ, А.П.Мощевикин, 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

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

13 Теория принятия решенийПетрГУ, А.П.Мощевикин, 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 )

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

15 Теория принятия решенийПетрГУ, А.П.Мощевикин, 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;

16 Теория принятия решенийПетрГУ, А.П.Мощевикин, 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