 |
Методические рекомендации по численному решению задачи условной оптимизации с ограничениями типа неравенств
|
|
|
|
Численное решение задачи условной оптимизации с ограничениями типа неравенств должно осуществляться посредством нескольких методов с цель последующего сравнительного анализа соответствующих реализаций решения. Сравнение должно осуществляться как с точки зрения эвристических оценок показателей сходимости методов, так и с точки зрения затрат машинного времени на реализацию численного решения конкретной задачи с заданной точностью.
Выбор и фиксация вариантов численных методов безусловной оптимизации осуществляется исходя из их классификации (см. рис. 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).
Варианты Заданий к курсовой работе
|
|
|
Поскольку курсовая работа включает две части: аналитическую и численную оптимизацию, варианты заданий и их выдача разделены на два этапа, которые выполняются поочередно, причём задание на второй этап выдается только после выполнения первого.
|
|
|
