WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 | 2 || 4 | 5 |   ...   | 11 |

В некоторых задачах связи могут отсутствовать, тогда требуется найти такое u* U, что Q (u*) = min Q (u), при выполнении ограничения i (u) 0, i = 1, k.

uU Управляющие переменные, удовлетворяющие требованиям u U и i (u) 0, называются допустимым решением. Все остальные решения недопустимы.

Допустимые решения u*, при котором целевая функция минимальна, называется оптимальным решением.

Основной задачей теории принятия решения является нахождение оптимального решения. Для этого необходимо: построить модель у = f (u), определить целевую функцию Q (y, u), определить область допустимых управлений U, определить технологические ограничения.

На практике встречаются задачи нахождения не оптимального, а допустимого решения, т.е. решения, удовлетворяющего системе ограничений. В этом случае задача ставится следующим образом: найти такие u* U, при которых i (u) 0, i = 1, k. Такие задачи могут иметь не единственное решение.

Некоторые задачи теории принятия решения пассивны, для них характерно, что входные управляющие параметры u не влияют на целевую функцию, они не являются рулями. В таких задачах только проверяют допустима полученная система или нет, и решением является "да" или "нет". Если у = f (u), то проверяется у Y, и задача заключается в том, чтобы по построенной модели проверить при всех ли u показатели у хорошие, и на основании этого сделать вывод о пригодности системы или ее непригодности.

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

2 КЛАССИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ ПРИНЯТИЯ РЕШЕНИЙ Математическая формулировка задачи принятия решения часто эквивалентна задаче отыскания экстремума функции одной или многих переменных. Поэтому для решения подобных задач могут быть использованы различные методы исследования функций классического анализа, в частности, методы поиска экстремума. Эти методы применяют в тех случаях, когда известен аналитический вид зависимости оптимизируемой функции Q от независимых переменных u.

2.1 ЭКСТРЕМУМ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ Большинство простейших задач принятия решений эквивалентно задачам отыскания экстремума функции одной переменной.

Пусть требуется найти экстремум функции одной переменной Q (u) при отсутствии ограничений на диапазон изменения переменной u.

Необходимым условием существования экстремума непрерывной функции Q (u) является равенство нулю первой производной (dQ / du = 0) или ее отсутствие. Графически равенство нулю производной означает, что касательная к кривой Q (u) в этой точке параллельна оси абсцисс (рис. 2.1, а), на рис. 2.1, б изображен случай, когда производные в точках экстремума не существуют.

Q а) Q б) µµµµ u2 u u2 u u1 uРис. 2.1 Различные типы экстремума функции одной переменной:

а – производная в точке экстремума существует;

б – производная в точке экстремума не существует а) б) в) Q Q Q u1 u1 uu u u Рис. 2.2 Функции Q(u), удовлетворяющие необходимым условиям экстремума:

а – производная равна нулю; б – производная не существует;

в – производная равна бесконечности Названные условия являются лишь необходимыми условиями. Их выполнение не означает еще, что в данных точках функция имеет экстремум (рис. 2.2).

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

1 Сравнение значений функций. Этот способ сводится к определению значений функции в точках, расположенных слева и справа в достаточной близости от исследуемой точки, т.е. в точках (u1 – ), (u1 + ), где – малая положительная величина. Если Q(u1) > Q(u1 – ) и Q(u1) > Q(u1 + ), то в точке u1 существует максимум (рис. 2.3). Если Q(u1) < Q(u1 – ) и Q(u1) < Q(u1 + ), то в точке u1 существует минимум (рис. 2.3, б). Если же Q(u1) будет занимать промежуточное положение между Q(u1 – ) и Q(u1 + ), например, Q(u1) > Q(u1 – ) и Q(u1) < Q(u1 – ), то в точке u1 экстремума не будет (рис. 2.3, в).

2 Сравнение знаков производной. При этом способе определяется знак первой производной функdQ ции Q(u) - в точках (u1 – ) и du (u1 + ). Если знаки производных различны, то в точке u1 имеется экстремум функции Q(u), причем, если при переходе от точки (u1 – ) к точке (u1 + ) знак производной изменяется с "+" на "–", то в точке u1 – максимум (рис. 2.3, а). Если же знак меняется с "–" на "+", то в точке u1 – минимум (рис. 2.3, б).

Если же знаки производных в точках (u1 – ) и (u1 + ) одинаковы, то в точке u1 экстремума нет (рис.

2.3, в).

3 Исследование знаков высших производных. Этот способ применяется в тех случаях, когда исследуемая функция имеет производные высших порядков. Если в точке u1 выполняется необходимое dQ d2Q условие экстремума, т.е. = 0 и существует вторая производная –, значение которой вычисляdu duud2Q ется в "подозреваемой" точке u1, то точка u1 является точкой максимума, если < 0, и точкой миduuнимума, d2Q если > 0.

duu а) б) в) Q Q Q (+) (+) (+) (–) (–) (+) u– u+ u– u+ u– u+ u u u u u u Рис. 2.3 Проверка достаточных условий экстремума:

а – максимум; б – минимум; в – экстремума нет d2Q d3Q d4Q Если же = 0, то для дальнейших исследований вычисляются, и т.д.

du2 du3 du uПри решении практических задач, как правило, приходится исследовать функции, имеющие несколько экстремумов. В этом случае говорят о нахождении наибольшего и наименьшего значения функции, которые называют глобальными экстремумами. Остальные экстремумы называются локальными. Также в практических задачах диапазон изменения переменной u часто бывает ограничен заданным интервалом [a, b], поэтому в число "подозреваемых" точек должны быть включены и крайние точки этого интервала, так как в них может достигаться глобальный экстремум.



2.2 ЭКСТРЕМУМЫ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ В большинстве задач оптимизации критерий оптимальности является функцией нескольких независимых переменных – Q(u1, u2,..., un). Если он является непрерывной функцией, имеющей непрерывные частные производные первого и второго порядка по всем переменным u ( = 1, n), то необходимым условием экстремума в точке {u*} является равенство нулю в этой точке первых производных по всем переменным, т.е. точки, в которой функция Q(u1, u2,..., un) может достигать экстремума, определяются решением системы уравнений Q(u1, u2,..., un ) = 0, = (1, n). (2.1) u u* Достаточные условия существования экстремума определяются в результате анализа знака квадраn n тичной формы B= xi x, коэффициенты которой определяются соотношениями ai j j i=1 j=2Q(u1, u2,..., un ) 2Q(u1, u2,..., un ) aij = = = a, i, j =1, n.

ji ui u u ui j j Квадратичная форма может быть положительно определенной и отрицательно определенной. Ответ о знаке квадратичной формы дает теорема, которая формулируется следующим образом: для положительной определенности квадратичной формы необходимо и достаточно, чтобы были выполнены условия Сильвестра 1 = a11>0;

a11 a = > 0;

a21 a...

(2.2) a11 a12... a1n a21 a22... a2n n = > 0,............

an1 an2... ann т.е. все главные миноры матрицы a11 a12... a1n a21 a22... a2n A =............

an1 an2... ann должны быть строго положительны.

Квадратичная форма будет отрицательно определенной, если все главные миноры матрицы A, имеющие нечетный порядок, отрицательны, а, имеющие четный порядок, положительны, т.е. 1 < 0, < 0,..., 2 > 0, 4 > 0.

Если квадратичная форма является положительно определенной, то исследуемая точка является точкой минимума, если же квадратичная форма будет отрицательно определенной, то в точке {u} имеет место максимум.

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

П р и м е р 2.1.

Пусть в реакторе идеального смешения протекает реакция первого порядка (A P). Требуется определить оптимальные условия – время пребывания и температуру, при которой себестоимость продукта P будет минимальной.

Критерий оптимальности – себестоимость задается функцией Cq 1 Cv Q (u1, u2) = + +1 + (u1u2 +1), CA UxA0 u1u2 u2xA где u1 – время пребывания, u2 – константа скорости химической реакции, связанная с температурой уравнением Аррениуса u2 = exp(– E / RT), E и R – константы; СА – стоимость единицы расходуемого сырья;

Сq – стоимость дополнительного оборудования реактора, исчисляемая с учетом амортизации; Сv – стоимость единицы объема реактора, исчисляемая с учетом его амортизации; U – нагрузка реактора по исходному сырью; xA0 – начальная концентрация вещества А.

Необходимые условия экстремума функции Q(u1, u2) дают систему уравнений:

Cq 1 Cv Q = - + + = 0;

u1 CA UxA0 2 xAu1 u Cq 1 Cv Q = - + - = 0.

u2 CA UxA0 2 u1u2 u2 xA Последнее уравнение не удовлетворяет ни каким значениям u1, u2, поэтому разумно выдерживать максимально возможную температуру ведения процесса, что определит значение u2. Оптимальное значение времени пребывания, соответствующее принятому значению температуры в этом случае определится как CAUxA0 + Cq 0, u1опт =.

CvUu Минимальная себестоимость составит 0, Cv CAUxA0 + Cq Qопт = 1+ u2.

u2xA0 CvUu П р и м е р 2.2.

4 Найти экстремум функции Q (u1, u2) = u1 + u2 - 4u1u2.

Необходимые условия экстремума записываются в виде системы:

Q(u1u2 ) 4u1 - 4u2 = 0;

= u (u1u2) Q = 4u2 - 4u1 = 0.

u Решение полученной системы уравнений дает три подозрительные точки на экстремум: (0, 0); (1, 1);

(–1, –1). Для определения существования экстремума в найденных точках требуется проверить достаточные условия. С этой целью составляется матрица 2 Q Q u1 u1u 12u - A = =.

2 Q Q - 4 12u u2u1 u В найденных точках - 4 -, A(1,1) = A(-1, -1) = A(0, 0) =.

- 4 0 - 4 Матрица А(0, 0) – знаконеопределена, следовательно, точка (0, 0) не является экстремальной. Матрицы А(1, 1) и А(–1, –1) положительно определенные (1 = 12 > 0, 2 = 128 > 0), поэтому в точках (1, 1) и (–1, –1) будет минимум – Qmin = –2.

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





Для решения таких задач в классическом анализе используется метод неопределенных множителей Лагранжа. Сами задачи получили название задач на условный экстремум.

2.3.1 ОСНОВНЫЕ ПОЛОЖЕНИЯ Пусть требуется найти экстремум функции, например, минимум Q (u1, u2,..., un) min (2.3) при условии (u1, u2,..., un) = 0, = 1, k. (2.4) Согласно методу Лагранжа для решения задач на условный экстремум функции составляется вспомогательная функция Лагранжа, которая определяется соотношением k Q (u1, u2,..., un1,..., k ) = Q (u1,..., un ) + (u1,..., un ), (2.5) =где, = 1, k – неопределенные множители Лагранжа.

Таким образом, задача нахождения условного экстремума функции (2.3) сводится к задаче нахождения безусловного экстремума функции (2.5), но число неизвестных в ней n + k (u, = 1, n ; j, j = 1, k ).

Как известно из п. 2.2 необходимым условием безусловного экстремума функции является равенство нулю частных производных, которые для данного конкретного случая записываются в виде Q(u1,..., un ) 1(u1,..., un ) k (u1, un ) + 1 +...+ k = 0; =1, n.

u u u (2.6) и дает n уравнений для определения неизвестных. Эта система уравнений дополняется к уравнениям (2.4) и, следовательно, получается (n + k) неизвестных и (n + k) уравнений.

Метод множителей Лагранжа дает лишь необходимые условия существования условного экстремума для непрерывных функций, имеющих также непрерывные производные, поэтому найденные значения переменных могут и не давать экстремума функции Q (u1,..., un), их надо проверить с использованием достаточных условий экстремума функции многих переменных.

В окончательном решении задачи фактически множители Лагранжа не известны, поэтому задача совместного решения системы (2.4), (2.6) иногда ставится как задача исключения "k" неизвестных переменных u с последующим решением остающейся системы n уравнений с n неизвестными.

Задача Лагранжа имеет "n – k" степеней свободы.

2.3.2 ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ МЕТОДА МНОЖИТЕЛЕЙ ЛАГРАНЖА Интерес представляют геометрический смысл множителей Лагранжа. Для такой интерпретации лучше рассмотреть задачу с двумя неизвестными и одним ограничением.

Пусть требуется найти минимум функции Q = Q(u1, u2) min при условии (u1, u2) = 0. Если минимум существует, то в пространстве функция Q должна иметь вид воронки, а условие связи – это некоторая поверхность (рис. 2.4).

На рис. 2.4, б изображены на плоскости переменных u1, u2 линии уровня функции Q (u1, u2) и ограничение (u1, u2) = 0, представляю- щее собой линию. Составляется вспомогательная функция Q (u1, u2) = = Q (u1, u2) + (u1, u2). Необходимое условие экстремума дает:

а) б) Q u(u1, u2) = A Q u Q = const u u uРис. 2.4 Геометрический смысл множителей Лагранжа:

а – пространственное изображение;

б – изображение проекции на плоскость u2 – uQ Q Q u = + = 0;

u = - ;

u1 u1 u1 или. (2.7) Q Q Q u = + = 0; u2 = -.

uu2 u В точке А (рис. 2.4) – точке касания линии (u1, u2) = 0 с линией равного уровня функции (u1, u2) и Q (u1, u2) имеют общую касательную и необходимое условие (2.7) минимума представляет собой ус Q Q ловие пропорциональности двух векторов: вектора Q =, – градиента функции Q (u1, u2) и векu u тора =, – градиента функции (u1, u2).

u u Два вектора пропорциональны друг другу лишь в том случае, если они коллинеарные. Так как градиент функции перпендикулярен касательной к линии уровня, то в точке А выполняется условие (2.7), и множитель является коэффициентом пропорциональности между векторами Q и.

2.3.3 ЭКОНОМИЧЕСКАЯ ТРАКТОВКА МЕТОДА МНОЖИТЕЛЕЙ ЛАГРАНЖА В некоторых задачах множители Лагранжа допускают и экономическое толкование. Если толковать целевую функцию Q (u1,..., un) как прибыль, получаемую некоторым предприятием при использовании ресурсов, а условия (u1,..., un) = 0, = 1, k ограничения на дефицит ресурсов, то при (u1,..., un) < прибыль, то максимум целевой функции будет расти.

Экономист такую задачу будет решать следующим образом. Он назначит некоторые цены на единицы ресурсов и предложит потребителю купить их по этой цене. Последний, максимизируя чисk тую прибыль Q (u1,..., un ) = Q (u1,..., un ) - (u1,..., un ), найдет (u1,..., un) и скажет, сколько ресурсов он хо =тел бы купить. В экономике почти всегда бывает так, что чем больше, тем меньше (u1,..., un), и чем меньше, тем больше (u1,..., un). Если окажется, что (u1,..., un) > 0, то экономист повысит цену, если (u1,..., un) < 0 – понизит. Так будет происходить до тех пор, пока при некоторой цене, называемой равновесной, потребителю будет выгодно, чтобы дефицит ресурсов (u1,..., un) был равен нулю, при этом чистая прибыль будет максимальна, т.е. будут выполняться условия k Q (u1,..., un ) (u1,..., un ) - = 0.

u u =Таким образом, равновесная цена с точностью до знака равна множителю Лагранжа.

2.3.4 ОСОБЫЕ СЛУЧАИ В заключение следует отметить особые случаи, когда градиент функции Q (u1,..., un) равен нулю (Q = 0) и когда градиент (u1,..., un) равен нулю ( = 0).

В первом случае решение может достигаться в точке экстремума функции Q (u1,..., un), множители равны нулю, и задача сводится к задаче безусловного экстремума и условия (u1,..., un) = 0 роли не играют. Во втором случае подозрительные на экстремум точки находятся из уравнений (u1,..., un) = 0, в которых затем вычисляется значение критерия Q (u1,..., un).

Pages:     | 1 | 2 || 4 | 5 |   ...   | 11 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.