Главная | Обратная связь
МегаЛекции

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





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

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

Рис 2.2

 

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

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

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

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

Φ(x, α) = f(x) + αТ s((g(x)) (2.10)

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

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

s((g(x)) = (2.11)

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



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

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

Φ(x, αi ) = [ f(x) + αi s((g(x))] = x*i безусл (2.12)

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

x*i безуслi ) = x* усл Φ(x*i безуслi ), αi ) = f(x* усл) (2.13)

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

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

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

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

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

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

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

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

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

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

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

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

Задание исходных данных (параметров, коэффициентов и др.)
вход

Рис 2.3

 

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

s((g(x)) = (2.14)

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

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

Φ(x, αi) = f(x) + αij sj((gj(x)) (2.15)

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

Φ(x, αi) = f(x) + (2.16)

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

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

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





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:
©2015- 2020 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.