Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

и когда количество активных ограничений, то есть количество элементов множества I₁ равно размерности вектора х – [n1] (так называемые «угловые» точки), тогда эта точка фиксируется активными ограничениями и не допускает вариации целевой функции (имеется ввиду корректная постановка задачи (1.1, 1.2)).

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

3. Исключение всех стационарных точек, не удовлетворяющих пассивным ограничениям.

То есть:

4. Исключение стационарных точек, не удовлетворяющих условиям неотрицательности множителей Лагранжа.

Из оставшегося числа вариантов стационарных точек необходимо исключить все точки, не удовлетворяющие условиям неотрицательности соответствующих множителей Лагранжа - , в которых согласно НУ не могут находиться условные локальные минимумы целевой функции.

5. Проверка оставшихся стационарных точек на достаточные условия локального минимума функции.

Все оставшиеся стационарные точки, за исключением «угловых» точек, должны быть проверены с помощью достаточных условий (ДУ), подтверждающих или опровергающих наличие в них условного локального минимума.

Одним из широко распространенных вариантов ДУ нахождения в исследуемой стационарной точке условного локального минимума является положительная определенность матрицы Гессе, размера [nn] (матрицы вторых частных производных) для функции Лагранжа F(х, ) по вектору х – [n1].

Известно, что матрица положительно определена, если составленная с ее помощью квадратичная форма положительно определена [1], то есть:

Где H(x)(х, ) - матрица Гессе (Гессиан) по вектору х; y – любой вектор с фиксированными значениями , размера [n1].

Для проверки положительной определенности квадратичной формы (2.6) предлагается применить критерий Сильвестра [2, 4]. Суть его заключается в следующем.

Для того, чтобы квадратичная форма (2.6) была положительно определенной, необходимо и достаточно, чтобы матрица H(x)(х, ) имела все положительные угловые миноры, нарастающие вдоль главной ее диагонали, то есть были бы положительными определители матриц:

Где h_ij – элементы матрицы Гессе H(x)(х, ) .

Таким образом, при подтверждении положительной определенности матрицы Гессе в стационарных точках, в которых согласно НУ возможно было нахождение условного локального минимума, то есть при > 0 , такие стационарные точки переводятся в число точек условного локального минимума целевой функции f(x) при условиях gj(x) ≤ 0, j=1,…,m :

6. Определение условного глобального минимума.

Сравнение значений целевой функции f(x) в точках условного локального минимума и в «угловых» точках позволяет выявить условный глобальный минимум:

Где x^угл – координаты «угловых» точек, определяемых n активными ограничениями из числа j1,…,m (см. пункт 2).

Таким образом условный глобальный минимум целевой функции равняется f(x_min ).

В соответствии с требованиями к КР (см. раздел 1.2) полученный результат необходимо представить графически и прокомментировать его с помощью поясняющих подписей и отдельных пояснений, следующих после рисунка (масштаб рисунка должен выбираться из соображений его наглядности). Пример графического представления результата аналитического решения задачи типа (1.1, 1.2) изображен на рис. 2.1.

В частности, на рис. 2.1 изображены: целевая функция f(x) с помощью линий уровня C₁, C₂, C₃, …., причем C₁ < C₂ < C₃ и т.д.; ограничения g_j ≤ 0, j =1,2,3 , выделяющие множество допустимых аргументов (параметров) - Х (запретные области условно заштрихованы); точки условного локального минимума определены номерами №1, №2, №3, №4, причем на рисунке видно, что точки №1 и №3 не удовлетворяют всем ограничениям g_j ≤ 0 ; «угловые» точки: №5, №6, №7.

Как следует из рассмотренной выше методики в результате сравнения значений функций в точках условного локального минимума №2, №4 и в «угловых» точках №5, №6, №7 определяются координаты условного глобального минимума, которые на рисунке обозначены №2.

2.2.Методические рекомендации по численному решению задачи условной оптимизации с ограничениями типа неравенств

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

Выбор и фиксация вариантов численных методов безусловной оптимизации осуществляется исходя из их классификации (см. рис. 2.2).

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

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

Для численного поиска условного минимума целевой функции (1.1) при условиях (1.2) предлагается применить метод «Штрафных функций» [1, 2], позволяющий свести задачу условной минимизации к последовательности итеративно решаемых задач безусловной минимизации. Суть этого метода заключается в следующем.

На основе целевой функции формируется функция вида:

Где s(g(x)) – сложная функция вектора х, называемая функцией «штрафа» (или «штрафной» функцией), α – вектор коэффициентов «штрафа», размера [m1].

Функция s(g(x)) должна иметь следующие свойства.

То есть, если ограничения типа неравенств не нарушаются (g(x) < 0) , то функция «штрафа» не должна никак себя проявлять в функции (2.10), и если это ограничение нарушено, то с ростом этого нарушения должен расти «штраф» за него, вплоть до бесконечности. При этом в точках g(x) = 0 функция «штрафа» должна быть непрерывной справа.

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

Предполагается, что последовательность аргументов решений задач безусловной оптимизации {x^*_{i безусл}}, i = 1, 2,….., а именно:

стремится к решению задачи условной оптимизации (1.1, 1.2) при неограниченном росте последовательности коэффициентов «штрафа» {a_i} , то есть:

Где x^*_{i безусл} – вектор безусловного минимума функции Φ(x, α_i) , зависящий от конкретного значения коэффициента «штрафа» α_i, x^*_усл - вектор координат условного минимума, соответствующего поставленной задачи.

Таким образом, согласно приведенной гипотезе алгоритм приближенного численного решения задачи (1.1, 1.2) должен включать следующие операции.

1. Ввод в программу: конкретных целевой функции - f(x) и ограничений - g(x) < 0 .

2. Определение и ввод в программу конкретной функции «штрафа» - s(g(x)) .

3. Фиксация исходных значений коэффициентов «штрафа» - α₀ и сопутствующих параметров (например, параметра итеративного роста коэффициентов «штрафа» и параметра допустимого числа итераций).

4. Определение метода безусловной оптимизации.

5. Фиксация параметров выбранного метода.

6. Задание начального приближения вектора аргументов x⁽⁰⁾ .

7. Организацию с помощью программных средств «охватывающего» цикла перебора коэффициентов «штрафа» - α_i , i = 1, 2, …. (с нарастанием до определенного значения).

8. Организацию с помощью программных средств и в соответствии с выбранным методом безусловной оптимизации «внутреннего» цикла поиска минимума функции Φ(x, α_i) для текущего значения α_i и определение промежуточного значения x^*_{i безусл} (α_i ). В случае применения в рамках заданного численного метода конкретной процедуры одномерной оптимизации, необходимо «внутри» этого цикла организовать еще один цикл - минимизации функции в заданном направлении.

9. Проверка условий окончания процедуры поиска условного минимума целевой функции и в случае их выполнения – прекращение процедуры, в противном случае – назначение новых значений α_i и x⁽⁰_i⁾ и переход к пункту 6 алгоритма (рекомендуется в качестве новых значений x⁽⁰_i⁾ выбирать последние значения этого вектора на предыдущей итерации «внутреннего» цикла, то есть - x^(p)_i-1 ).

Этот алгоритм может быть представлен в виде укрупненной блок-схемы (см. рис. 2.3).

В качестве функции «штрафа» предлагается использовать следующую составную функцию.

Где g_j(x) одна из m функций ограничений.

В общем случае для каждой функции g_j(x) должна быть определена своя функции «штрафа» - s_j((g_j(x)) типа (2.14). В результате функция Φ(x, α) приобретет более конкретный вид:

Коэффициенты «штрафа» α_ij могут быть различны для каждого ограничения g_j(x), однако, имея в виду абстрактность рассматриваемой задачи, они могут определяться одинаковой последовательностью значений {a_i}, i = 1,2,…. Тогда (2.14) с учетом этого и (2.15) будет иметь вид:

Таким образом, в случае правильного подбора параметров используемых методов и рационального выбора последовательности коэффициентов «штрафа» {a_i}, i = 1,2,…., значение которых увеличиваются с ростом номера последовательности i , каждое новое решение задачи на безусловный минимум функции Φ(x, α_i), должно приближаться к решению задачи условной минимизации (1.1, 1.2).

3.Варианты Заданий к курсовой работе

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

3.1.Задания по аналитической части курсовой работы

Каждый вариант задания по аналитической части курсовой работы имеет индивидуальную постановку задачи типа (1.1, 1.2), включающую:

• конкретный вид целевой функции – f(x₁, x₂) ;

• несколько конкретных ограничений типа неравенств – g_i (x₁, x₂) ≤ 0, i = 1,m.

вариант № 1

вариант № 2

Характеристики

Список файлов учебной работы