|
-
Сделаем проверку:
Подставим точку  в
ограничения.
Ограничения выполняются: 
Этап 2:
Решаем основную задачу:
Выделим базисные переменные и уберем их из
целевой функции:
Тогда целевая функция примет вид:
Записываем симплекс-таблицу и повторяем тот же
алгоритм:
|
БП
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x7
|
ПЧ
|
СО
|
|
x5
|
-5
|
1
|
-1
|
0
|
1
|
-2
|
0
|
5
|
-1
|
|
x4
|
2/5
|
1/5
|
1/5
|
1
|
0
|
1/5
|
0
|
2
|
5
|
|
x7
|
12
|
3
|
3
|
0
|
0
|
1
|
1
|
36
|
3
|
|
|
2
|
-1
|
-8
|
0
|
0
|
-3
|
0
|
-30
|
-
|
|
БП
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x7
|
ПЧ
|
СО
|
|
x5
|
0
|
9/4
|
1/4
|
0
|
1
|
-19/12
|
5/12
|
20
|
-
|
|
x4
|
0
|
1/10
|
1/10
|
1
|
0
|
1/6
|
-1/30
|
4/5
|
-
|
|
x1
|
1
|
1/4
|
1/4
|
0
|
0
|
1/12
|
1/12
|
3
|
-
|
|
|
0
|
-3/2
|
-17/2
|
0
|
0
|
-19/6
|
-1/6
|
-36
|
-
|
Получаем решение:
Сделаем проверку:
Подставляя решение
в ограничения получаем:
Т.о. найдено допустимое базисное решение
исходной задачи.
4. Исследование множества на выпуклость
Постановка задачи:
Доказать, что множество Х решений произвольной
системы линейных уравнений и неравенств выпукло.
Теоретические сведения:
Определение 4.1.
Множество называется выпуклым, если любые две
точки  можно
соединить прямой, принадлежащей этому множеству.
Графически это выглядит так:
Математически данное свойство выражается, как:
Данных сведений достаточно, что бы решить
поставленную задачу.
Решение:
Пусть произвольная системы линейных уравнений и
неравенств имеет вид:
Это ее матричная запись., которая является более
удобной.
Так же пусть существуют решения данной системы,
т.е.  и
число  .
Тогда два решения этой системы можно записать
так:
В силу линейности каждого уравнения произвольная
системы линейных уравнений и неравенств имеем:
Объединяя две системы, получим:
В силу дистрибутивности свойств умножения матриц
уравнение переписывается в виде:
Т.е. при заданных решениях произвольной системы
линейных уравнений и неравенств и числе вектор
 -
тоже решение.
Отсюда следует выпуклость множества Х - решений
произвольной системы линейных уравнений и неравенств.
5. Исследование функции на выпуклость
Постановка задачи:
Показать, что произведение выпуклых функций
необязательно выпукло. Существуют ли подклассы выпуклых функций, замкнутые по
отношению к умножению?
Теоретические сведения:
Определение 5.1
Функция  где
 -
выпуклое множество, называется выпуклой функцией на этом множестве, если
Теорема 5.1
Пусть функция  определена
на интервале  и  -некоторая
точка этого интервала. При всех  определено
разностное отношение - функция :
Тогда функция выпукла
на интервале в
том и только том случае, когда функция
 не убывает на
множестве  .
Теорема 5.2
Пусть функция дифференцируема на интервале и
 ,
при всех  .
Тогда возрастает
на .
Если же  при
всех ,
то не
убывает на .
Аналогично, если  ,
при всех ,
то убывает
на ,
а если  ,
при всех ,
то
не
возрастает на .
Теорема 5.3
Пусть функция имеет
на производную
 .
Функция выпукла
на тогда
и только тогда, когда производная не
убывает на .
Замечание 5.1
Дифференцируемая функция вогнута
на интервале тогда и только
тогда, когда её производная не возрастает.
Если функция имеет во всех точках интервала
вторую производную  ,
то для исследования выпуклости можно воспользоваться следующим утверждением.
Теорема 5.4
Пусть на интервале функция
имеет
вторую производную . Функция
выпукла
на тогда
и только тогда, когда  , при всех ,
и
вогнута тогда и только тогда, когда  при
всех .
Решение:
Согласно теореме 5.4, если функция
выпуклая и имеет вторую производную,то:  при всех  .
Например возьмем выпуклые функции  , а их произведение уже не будет
выпуклой функцией:  так как   Это наглядно представлено на рисунке:
Чтобы произведение функций было
выпукло, требуется что функции принадлежали к подклассу выпуклые
неотрицательные неубывающие функции.
Тогда их произведение будет
положительно :
Производная произведения не убывает
:
6. Исследование функции на
овражность
Постановка задачи:
Требуется исследовать на овражность
функцию :
Теоретические сведения:
Определение 6.1
Матрицей Гессе  дважды
дифференцируемой в точке  функции называется
матрица частных
производных второго порядка,
вычисляемых в данной точке:
Определение 6.2
Собственные значения  матрицы размера  находятся
как корни характеристического уравнения (алгебраического уравнения n-й степени):
Определение 6.3
Пусть ограниченная снизу функция:
обладает той особенностью, что в
исследуемой области собственные значения матрицы Гессе , упорядоченные
в любой точке  , удовлетворяют неравенствам:
В этом случае поверхности уровня  имеют структуру, сильно
отличающуюся от сферической.
Такие функции называются овражными.
Определение 6.4
Степень овражности характеризуется
числом:
Обычно при k>10
функция приобретает овражную структуру.
Определение 6.5
Если собственные значения матрицы
Гессе удовлетворяют неравенствам:
а отношение:
невелико ,то число  называется размерностью оврага.
Решение:
Составим матрицу Гессе:
Найдем собственные значения матрицы
Гессе:
Степень и размерность овражности  ,
следовательно, функция имеет овражную структуру.
График функции и линии
уровней построим в среде MathCAD 14
Линии уровней:
Как видно из рисунка, лини уровней
сильно вытянуты, что указывает на овражность данной функции.
7. Безусловная оптимизация неквадратичной
функции овражной структуры
Метод Дэвидона-Флетчера-Пауэлла
Постановка задачи
В курсовой работы предложено написать реализацию
метода Дэвидона-Флетчера-Пауэлла на любом алгоритмическом языке. Произвести
минимизацию неквадратичной функции двух переменных
а так же отладить функцию на квадратичной
овражной функции, взятой из пункта 6.
В курсовой работы предложено написать реализацию
метода Дэвидона-Флетчера-Пауэлла на любом алгоритмическом языке.
Метод Давидона - Флетчера - Пауэла.
Первоначально метод был предложен Дэвидоном
(Davidon [1959] ), а затем развит Флетчером и Пауэллом (Fletcher, Powell [1963]
). Метод Дэвидона-Флетчера-Пауэлла называют также и методом переменной метрики.
Он попадает в общий класс квазиньютоновских процедур, в которых направления
поиска задаются в виде -Dj f(y). Направление градиента является, таким образом,
отклоненным в результате умножения на -Dj , где Dj - положительно определенная
симметрическая матрица порядка n х n, аппроксимирующая обратную матрицу Гессе.
На следующем шаге матрица Dj+1 представляется в виде суммы Dj и двух симметрических
матриц ранга один каждая. В связи с этим схема иногда называется схемой
коррекции ранга два.
Среди алгоритмов многомерной минимизации следует
выделить группу алгоритмов, которые объединяют достоинства метода наискорейшего
спуска и метода Ньютона. Такие алгоритмы принято относить к так называемым
квазиньютоновским методам. Особенность этих алгоритмов состоит в том, что при
их применении нет необходимости вычислять и обращать матрицу Гессе целевой
функции f(x) и в то же время удается сохранить высокую скорость сходимости
алгоритмов, присущую методу Ньютона и его модификациям.
Алгоритм метода
) Ввод начальных данных с клавиатуры:
) Проверка условия:
А) Если утверждение верно, то 5);
Б) Если утверждение ложно, то 3).
3) Нахождение значения  :
Где 
) Переопределение значений:
 Увеличиваем счетчик
итераций и переходим к Шаг2);
5) Минимум найден: 
Решение задачи
График и линии уровня заданной функции
представлены на рисунках:
 
Рис.7.1
Функция определена при:
если условия не выполняются, то программа
прекращает свою работу. Данной условие осуществлено за счет проверки знака
определителя матрицы Гессе.
При нахождении минимума
целесообразно брать точки недалекие от значения минимума функции. Как видно из
рисунка 7.1 , резко
возрастает точки должны быть близкими к  иначе функция резко увеличивает
количество итераций для, требуемых для нахождения минимума, из-за непрерывного
увеличения степени овражности, при отклонении от точки  (рис 7.2).
Результат работы программы:
Рис. 4.3
 - начальная точка
Программа нашла минимум исходной
функции за 2 итерации.
Значение функции 1.90263 1.903.
Выполним проверку при помощи пакета Mathcad 14:
8. Сведение задачи условной
оптимизации к безусловной задаче оптимизации.
.1 Метод внешних штрафных функций
Постановка задачи:
Требуется найти решение задачи:
Теоретические сведения:
Задача условной оптимизации:
Этот метод основан на сведении к
последовательности задач, минимизации дополнительной функции:
 - штрафная функция, зависящая от
двух параметров,
 - параметр штрафа.
С ростом номера k , штраф за
невыполнение ограничений увеличивается
Штрафная функция записывается в
виде:
 - квадрат срезки (для ограничений
типа неравенств).
 - квадратичная функция.
На каждой k-ой итерации
ищется точка  - точка
минимума вспомогательной функции  .
Найденная точка используется как
начальная точка на следующей итерации, выполняемой при большем значении
параметра штрафа .
Теорема 8.2.1 (о сходимости метода
штрафных функций)
Пусть  - точка локального минимума задачи
условной минимизации
 - непрерывные, дифференцируемые
функции в окрестности точки .
Тогда последовательность точек  ,
полученных на каждой итерации, сходится к точке условного минимума .
Алгоритм метода
Шаг№1
Задается начальное приближение  , начальный
штраф  , его обычно
берут равным {0,01;0,1;1}.
Задается некоторая константа для
увеличения  .
Задается точность  .
Шаг№2
Находим точку минимума функции,
разработанным методом многомерной минимизации, в нашем случае методом
Дэвидона-Флетчера-Пауэлла.
Вычисляем величину штрафа  , что есть
критерий остановки поиска условного минимума.
Шаг№3
Проверка условия окончания поиска:
а) если  ,то в
качестве оптимальной точки выбираем  .
б) иначе  и в
качестве нового приближения выбирается начальная точка в безусловной
минимизации:
 , k=k+1 =>
Шаг№1.
Результат работы программы:
Для разных точек, не принадлежащих допустимому
множеству, минимум функции находится и он одинаков для разных точек, что
говорит о правильности реализуемой программы.
В чистом виде исходная функция не имеет
минимума, но т.к. вспомогательная функция квадратичная, то минимум находится.
Для точек, принадлежащих допустимому множеству,
минимум функции не находится, т.к. функция не выпукла, т.е. не имеет минимума.
Этот факт определяется по виду градиента этой функции и значению определителя
матрицы Гессе.
.2 Метод возможных направлений Зойтендейка
Постановка задачи:
Требуется найти решение задачи:
В общем виде она выглядит так:
Стратегия поиска:
Метод основан на построении последовательности
точек  ,
таких, что  .
Правило построения точек последовательности :
Выбор направления  осуществляется
следующим образом:
) 
) 
А) Вектор направляется
внутрь области 
Б) Вектор должен
составлять с направление убывания наименьший угол
Определим множество индексов:
Если точка множество активных ограничений  не
пусто, то решается задача:
-Шаг  определяется
как:
Алгоритм:
) Выбирается начальная точка из множества
допустимых решений  . Находим  и,
если  ,
то  ,
иначе 2)
) Определяем элементы множеств  ,
) Если  ,
иначе:
)
Если  ,
то завершаем, иначе 5)
) Определяем шаг и
находим следующую точку 
Решение:
Итерация 0:
) Выбираем точку  ,которая
принадлежит допустимому множеству
Вычисляем градиент целевой функции  в
начальной точке:
) Множество активных ограничений и
индексов, для которых координаты направления положительны пусты, т.е.  .
) Т.к. указанные в (2) множества пусты,
то направление есть антиградиент в точке  :
) Теперь определяем шаг:
Так как  ,
то 
Получаем, что до следующей точки равен 
) Получаем следующую точку:
Итерация 1:
Вычислим градиент в этой точке:
) Проверим точку на принадлежность
ограничениям. Точка принадлежит ограничения, причем есть одно активное
ограничение 
) Для нахождения возможного направления
составляем экстремальную задачу:
Преобразуем задачу к необходимому виду:
Решаем задачу симплекс-методом:
Выбираем максимальную положительную оценку и
минимальное неотрицательное симплексное отношение:
|
    u1u2ПЧ
|
|
|
|
|
|
|
|
2
|
-2
|
3
|
-3
|
1
|
0
|
0
|
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
|
2/7
|
-2/7
|
1
|
-1
|
0
|
0
|
0
|
|
u1u2ПЧ
|
|
|
|
|
|
|
|
2/3
|
-2/3
|
1
|
-1
|
1/3
|
0
|
0
|
|
1/3
|
5/3
|
0
|
2
|
-1/3
|
1
|
1
|
|
-8/21
|
8/21
|
0
|
0
|
-1/3
|
0
|
0
|
|
u1u2ПЧ
|
|
|
|
|
|
|
|
4/5
|
0
|
1
|
-1/5
|
1/5
|
2/5
|
2/5
|
|
1/5
|
1
|
0
|
6/5
|
-1/5
|
3/5
|
3/5
|
|
-48/105
|
0
|
0
|
-16/35
|
-9/35
|
-8/35
|
-8/35
|
|
|
|
|
|
|
|
|
|
|
|
Получаем направление:
) Теперь найдем шаг:
Получаем, что шаг: 
) Получаем следующую точку:
Итерация 2:
) Выбираем начальной точкой точку:
Вычисляем градиент:
) Проверим точку на принадлежность
ограничениям. Точка принадлежит ограничения, причем есть одно активное
ограничение
) Находим направление  :
Составляем экстремальную задачу.
Преобразуем к виду:
Решим симплекс-методом. Составляем таблицу
|
u1u2ПЧ
|
|
|
|
|
|
|
|
2
|
-2
|
3
|
-3
|
1
|
0
|
0
|
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
|
2
|
-2
|
1
|
-1
|
0
|
0
|
0
|
|
u1u2ПЧ
|
|
|
|
|
|
|
|
1
|
-1
|
3/2
|
-3/2
|
1/2
|
0
|
0
|
|
0
|
2
|
-1/2
|
5/2
|
-1/2
|
1
|
1
|
|
0
|
0
|
-2
|
2
|
-1
|
0
|
0
|
|
u1u2ПЧ
|
|
|
|
|
|
|
|
1
|
1/5
|
6/5
|
0
|
1/5
|
3/5
|
3/5
|
|
0
|
4/5
|
-1/5
|
1
|
-1/5
|
2/5
|
2/5
|
|
0
|
-8/5
|
-8/5
|
0
|
-3/5
|
-4/5
|
-4/5
|
Получаем направление:
) Находим шаг:
Получаем шаг:
) Следующая точка: 
Итерация 3:
) Берем точку с прошлой итерации:
Вычисляем градиент:
) Проверим точку на принадлежность
ограничениям. Точка принадлежит ограничения, причем есть одно активное
ограничение:
) Находим направление:
Составляем таблицу
|
u1u2ПЧ
|
|
|
|
|
|
|
|
2
|
-2
|
3
|
-3
|
1
|
0
|
0
|
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
|
2/3
|
-2/3
|
1
|
-1
|
0
|
0
|
0
|
|
u1u2ПЧ
|
|
|
|
|
|
|
|
2/3
|
-2/3
|
1
|
-1
|
1/3
|
0
|
0
|
|
1/3
|
5/3
|
0
|
2
|
-1/3
|
1
|
1
|
|
0
|
0
|
0
|
0
|
-1/3
|
0
|
0
|
Получаем, что  следовательно,
т.к.  свободные
переменные, равные нулю, то направление:
 , следовательно,
точка -
решение поставленной задачи. Переведя дроби в действительные числа, получаем:
Данная точка совпадает с ответом, полученным в
результате программной реализации задачи методом внешних штрафных функций.
9. Вывод
В данной курсовой работе были рассмотрены
различные методы оптимизаций поставленных задач , а именно, рассматривались
задачи:
Задача линейного программирования, которая
решалась двухэтапным симплекс-методом.
Условной и безусловной оптимизации:
Задача безусловной оптимизации решалась с
применение основных теорем математического анализа, а так же написанной
программой одномерной оптимизации реализующей метод «золотого сечения» отрезка
локализации минимума.
Задачи условной минимизации решались:
) С применением теоремы Джона-Куна-Таккера
) Методом возможных направлений
Зойтендейка
) Методом внешних штрафных функций
(программная реализация; использовался метод Дэвидона-Флетчера-Пауэлла)
Оптимизация квадратичных и неквадратичных
функций:
Функции минимизировались программой, реализующей
метод Дэвидона-Флетчера-Пауэлла.
В качестве квадратичной функции бралась функция
из пункта исследования на овражность. Не смотря на значимую степень овражности
функции, программа находила точки ее минимума, при различных исходных данных.
В случае неквадратичной функции программа
находила минимум, только при задаваемых точках, лежащих в окрестности начала
координат, т.к. собственные числа зависят от двух переменных и меняются по
экспоненциальному закону, что приводит к быстрому росту овражности функции, при
движении от начала координат. Это приводило к резкому увеличению количества
итераций, за которые метод находит минимум.
В программе был написан критерий проверки
функции на выпуклость (через определитель матрицы Гессе), т.е. в точках, где он
не положительна программа завершала процесс и выводила соответствующее
оповещение.
Метод внешних штрафных функций был добавлен в
описанную программу. Минимум функции с задаваемым допустимым множеством
находился примерно за 7 итераций в каждом случае. Ответ, полученный через
программу, совпал с значение полученным на этапе решения задачи условной
минимизации методом Зойтендейка.
Так же производилось исследование множеств на
выпуклость, функций на выпуклость и овражность.
10. Список литературы
оптимизация
нелинейный функция
1.Пантилеев А.В., Летова Т.А.,
«Методы оптимизации в примерах и задачах», «Высшая школа», 2002 г.
.Лутманов С.В., «Курс лекций по
методам оптимизации», 2001
.Ларичев О.И., Горвиц Г.Г., «Методы
поиска локального экстремума овражных функций», «Наука», 1990
.Амосов А.А., Дубинский Ю.А.,
Копченова Н.В., «Вычислительные методы для инженеров», «Высшая школа», 1994
.Бушуев А.Ю., Кутыркин В.А.,
Мозжорина Т.Ю., Тимофеев В.Н., «Введение в оптимизацию» «МГТУ им. Н.Э.Баумана»,
2008
11.Приложения
Одномерный поиск. Метод «золотого сечения».
Описание программы:
Задача состоит в минимизации затрат на
производство закрытого цилиндрического бака, при заданном объеме V;
В программе производится минимизация функции
одного аргумента S(R)=2*PI*r^2+2*V/r;
При выполнении программы вводится значение
объема V;
Решением задачи является пара чисел (Rmin;Hmin);
Высота H находится по формуле H=V/(PI*r^2);
Используется метод «золотого сечения» .
Программа написана в среде Microsoft
Visual Studio
2010.
Листинг
#include <iostream>;
#include <math.h>;namespace
std;main()
{
//Повторить программу или
нетchose[4]="no";
//Включаем вывод русских символов в консоль;
setlocale(LC_ALL,"Russian");
//Число
PI;
const double pi=3.1416;
//Инициализация границ отрезка локализации
минимума, т.е. два значения радиуса [R1;R2] в милиметрах;R1=0, R2=100000;
//Константы золотого сечения;const1=0.381966,
const2=0.618033;
//Точки, осуществляющие золотое сечение;alfa=0,
bett=0;
//Значения функции для двух точек золотого
сечения(нужны для сравнения);S1=0,S2=0;
//Точность,объем, минимальный радиус и
соответствующая ему высота;
double eps=0,V=0,Rmin=0,Hmin=0;
{<<"В программе производится
минимизация функции одного аргумента:"<<endl;
cout<<"S(r)=2*PI*r^2+2V/r;"<<endl;
cout<<"При выполнении программы
вводится значение объема V;"<<endl;<<"Решением задачи
является пара чисел (r*;H*);"<<endl<<endl;
loop:<<"Введите объем V:\t";>>V;<<"Задайте
точность eps:\t";>>eps;<<endl;
}
//Вычисляем начальные точки золотого сечения;
{=R1+const1*(R2-R1);=R1+const2*(R2-R1);
}
//Далее следует реализация метода;
while(const2*(R2-R1)>=eps)
{
S1=2*(pi*pow(alfa,2)+V/alfa);=2*(pi*pow(bett,2)+V/bett);
//Т.к. функция унитарна, изменяем границы
отрезка локализации минимума;
if
(S1>S2){=alfa;=bett;=R1+const2*(R2-R1);
}{=bett;=alfa;=R1+const1*(R2-R1);
}
};
//Обработка конечных данных;
{
//Далее сравниваются два значения S1 S2;
S1=2*(pi*pow(R1,2)+V/R1);=2*(pi*pow(R2,2)+V/R2);(S1>S2)=alfa;
else=bett;
//Минимальная высота: H=V/(pi*R^2);
Hmin=V/(pi*pow(Rmin,2));
}
//Вывод
ответа;<<"Решением
задачи
в
виде
(Rmin;Hmin):
("<<Rmin<<";"<<Hmin<<")"<<endl<<endl;
//Закольцовка
{
cout<<"Запустить
заново?"<<endl;
cout<<"1.
yes"<<endl;<<"2. no"<<endl;<<"Выбор:\t";>>chose;<<endl<<endl;(chose[0]=='y'&&chose[1]=='e'&&chose[2]=='s')
{goto loop;}
}
}
Многомерный поиск минимума функций и добавленный
метод внешних штрафных функций. Метод Дэвидона-Флетчера-Пауэлла.
Описание программы:
Программа реализует метод
Дэвидона-Флетчера-Пауэлла. Находится минимум функций двух переменных.
В меню программы можно выбрать ход программы, а
именно:
. Запуск тестовой (квадратичной) функции
двух переменны, взятой из задания на исследование овражности функции.
. Запуск поиска минимума неквадратичной
функции овражной структуры, овражность которой усиливается при увеличении
значений переменных  . (См. раздел 7)
. Запуск поиска минимума задачи на
условный минимум квадратичной функции. Реализуется метод внешних штрафов с
применение метода многомерного поиска минимума Дэвидона-Флетчера-Пауэлла.
По завершению программа выдает точку минимума и
значение функции в этой точки. Все промежуточные выводы вычислений, которые
помогают отследить правильность выполнения программы, изъяты, т.к. не являются
обязательными.
Программа написана в среде Microsoft
Visual Studio
2010.
Листинг:
#include <iostream>;
#include <math.h>;
using namespace std;
//размерность Евклидова пространстваint n=2;
//создание нестандартных наименований типов
typedef int counters;int
number_of_iteration;double step;double fine;double accuracy;double
norm_gradient;double point [n];double difference_of_points [n];double gradient
[n];double difference_of_grad [n];double direction [n];double matrix
[n][n];double Hessian_matrix [n][n];double Determ_Hess_matr;phi(fine p,point x)
{g1=0,g2=0;=2*x[0]+3*x[1]-6;=2*x[0]+x[1]-4;(p*0.125)*(
(abs(g1)+g1)*(abs(g1)+g1)+(abs(g2)+g2)*(abs(g2)+g2) );
}f(char var,fine p,point &x)
{(var=='1') return
x[0]*x[0]-3*x[0]*x[1]+10*x[1]*x[1]+5*x[0]-3*x[1];(var=='2') return
sqrt(1+2*x[0]+x[1]*x[1])+exp(x[0]*x[0]+2*x[1]*x[1])-x[0]-x[1];(var=='3') return
x[0]*x[0]-2*x[0]-x[1]+phi(p,x);
}psy(char var,fine p,step s,point
&x, direction &d)
{sum1=0,sum2=0,sum3=0;g1=0,g2=0;(var=='1')
{=d[0]*d[0]-3*d[0]*d[1]+10*d[1]*d[1];=2*x[0]*d[0]-3*x[1]*d[0]-3*x[0]*d[1]+20*x[1]*d[1]+5*d[0]-3*d[1];=x[0]*x[0]-3*x[0]*x[1]+10*x[1]*x[1]+5*x[0]-3*x[1];s*s*sum1+s*sum2+sum3;
}(var=='2')
{=sqrt( (1+2*x[0]+x[1]*x[1]) +
2*s*(d[0]+x[1]*d[1]) + s*s*(d[1]*d[1]) );=exp(
(x[0]*x[0]+2*x[1]*x[1])+2*s*(x[0]*d[0]+2*x[1]*d[1])+s*s*(d[0]*d[0]+2*d[1]*d[1])
);=x[0]+x[1]+s*(d[0]+d[1]);sum1+sum2-sum3;
}(var=='3')
{=2*x[0]+3*x[1]+s*(2*d[0]+3*d[1])-6;=2*x[0]+x[1]+s*(2*d[0]+d[1])-4;=2*x[0]*d[0]-2*d[0]-d[1];=x[0]*x[0]-2*x[0]-x[1];=(p*0.125)*(
(abs(g1)+g1)*(abs(g1)+g1)+(abs(g2)+g2)*(abs(g2)+g2) );(
s*s*d[0]*d[0]+s*sum1+sum2+sum3 );
}
}diff(char &var,fine p,counters
i,counters j, point &x)
{h=0.000000001;dx;(j=0;j<n;j++)
{dx[j]=x[j];}[i]=dx[i]+h;((f(var,p,dx)-f(var,p,x))/h);
}d_diff(char &var,fine
p,counters i,point &x)
{h=0.00001;result=0;f1=0,f2=0,f3=0;dx[n];j=0;(j=0;j<n;j++){dx[j]=x[j];}[i]=x[i]+h;
f1=f(var,p,dx);=f(var,p,x);[i]=x[i]-h;
f3=f(var,p,dx);=(f1-2*f2+f3)/(h*h);(abs(result)<0.001) result=0;result;
}mixdiff(char &var,fine
p,counters i,counters j,point &x)
{h=0.00001;result=0;f1=0,f2=0,f3=0,f4=0;dx[n];k=0;(k=0;k<n;k++)
{dx[k]=x[k];}=f(var,p,x);[i]=dx[i]-h; f2=f(var,p,dx);[j]=dx[j]-h;
f4=f(var,p,dx);[i]=dx[i]+h;
f3=f(var,p,dx);=(f1-f2-f3+f4)/(h*h);(abs(result)<0.001) result=0;result;
}Hessian(char &var,fine p,point
&x,Hessian_matrix &H,Determ_Hess_matr &dH)
{(j=0;j<n;j++)
{[i][j]=mixdiff(var,p,i,j,x);[i][i]=d_diff(var,p,i,x);<<"
"<<H[i][j];
}<<endl;
}=H[0][0]*H[1][1]-H[0][1]*H[1][0];<<"Определитель
матрицы
Гесса:
"<<dH<<endl;
}step_0(char &var,counters i,
counters j, accuracy &eps, point &x, matrix &D)
{<<endl<<"Список:
"<<endl<<endl;
cout<<"1.Тестовая функция
"<<endl;<<"2.Неквадратичная (основная) функция
"<<endl;<<"3.Условная минимизация.Метод внешних штрафных
функций"<<endl;
repeat:<<endl<<"Пункт:
";>>var;((var=='1')||(var=='2')||(var=='3'))
{;}{cout<<endl<<"Выберете
пункт
из
списка!"<<endl;
goto repeat;}
cout<<endl<<"Задайте
точность:\t";>>eps;<<endl<<"Ввод начальной точки Х
в "<<n<<"-мерном
Евклидовом";<<endl<<"пространстве, при k=0(можно в
строчку, разделяя пробелами)";
cout<<endl;(i=0;i<n;i++) {
cin>>x[i]; if (i==n-1) {break;} }
//присвоение вида D=Е (при k=0)
for (i=0;i<n;i++) {for
(j=0;j<n;j++) {D[i][j]=0; D[i][i]=1;}}
}step_1(counters i, counters j,
gradient &g, direction &d, matrix &D)
{(i=0;i<n;i++){d[i]=0;}(i=0;i<n;i++){
for(j=0;j<n;j++){ d[i]=d[i]+D[i][j]*g[j]; } }(i=0;i<n;i++){ d[i]=-d[i]; }
cout<<"Направление{ d(x)=-D*f'(x) }:
"<<endl;
for(i=0;i<n;i++){cout<<d[i]<<endl;}
}step_2(char &var,fine p,step
&s,point &x,direction &d)
{a=-1000, b=1000;const1=0.381966,
const2=0.618033;alfa=0,
bett=0;F1=0,F2=0;eps=0.000000001;=a+const1*(b-a);=a+const2*(b-a);(const2*(b-a)>=eps)
{=psy(var,p,alfa,x,d);=psy(var,p,bett,x,d);(F1>F2)
{=alfa;=bett;=a+const2*(b-a);
}
{=bett;=alfa;=a+const1*(b-a);
}
};=psy(var,p,alfa,x,d);=psy(var,p,bett,x,d);(F1>F2)
s=bett;s=alfa;<<"Шаг
S: "<<s<<""<<endl;
}step_3(char &var,fine
p,difference_of_points &U,difference_of_grad &V,step s,point
&x,direction &d)
{i=0,j=0,k=1;g;(i=0;i<n;i++)
{U[i]=-x[i];}(i=0;i<n;i++){g[i]=diff(var,p,i,j,x); if (abs(g[i])<0.0001)
g[i]=0;}(i=0;i<n;i++) {V[i]=-g[i];}(i=0;i<n;i++)
{x[i]=x[i]+s*d[i];}(i=0;i<n;i++)
{U[i]=U[i]+x[i];}(i=0;i<n;i++){g[i]=diff(var,p,i,j,x); if
(abs(g[i])<0.0001) g[i]=0;}(i=0;i<n;i++) {V[i]=V[i]+g[i];}(i=0;i<n;i++)
{cout<<x[i]<<endl;}
cout<<endl<<"Разность точек U:
"<<endl;
for(i=0;i<n;i++)
{cout<<U[i]<<endl;}
cout<<endl<<"Разность
градиентов V: "<<endl;
for(i=0;i<n;i++)
{cout<<V[i]<<endl;}k++;
}step_4(counters i,norm_gradient
&norm,gradient &g)
{=0;(i=0;i<n;i++)
{norm=norm+g[i]*g[i];}=sqrt(norm);
}step_5(difference_of_points
U,difference_of_grad V,matrix &D)
{ counters i=0, j=0;l,m;A1=0,B1=0;A,
B;(i=0;i<n;i++) { m[i]=0; l[i]=0; }(i=0;i<n;i++) { A1=A1+U[i]*V[i];
}(i=0;i<n;i++) { for(j=0;j<n;j++) { A[i][j]=(U[i]*U[j])/A1; }
}(i=0;i<n;i++) { for(j=0;j<n;j++) { m[i]=m[i]+D[i][j]*V[j]; }
}(i=0;i<n;i++) { B1=B1+V[i]*m[i]; }(i=0;i<n;i++) { for(j=0;j<n;j++) {
l[i]=l[i]+V[j]*D[j][i]; } }(i=0;i<n;i++) { for(j=0;j<n;j++) {
B[i][j]=((-1)*(m[i]*l[j]))/B1; } }(i=0;i<n;i++) { for(j=0;j<n;j++) {
D[i][j]=D[i][j]+A[i][j]+B[i][j]; } }<<endl<<"Матрица
A: "<<endl;(i=0;i<n;i++)
{for(j=0;j<n;j++){cout<<"
"<<A[i][j]<<"
";}cout<<endl;}<<endl<<"Матрица
В:
"<<endl;(i=0;i<n;i++)
{for(j=0;j<n;j++){cout<<"
"<<B[i][j]<<" ";}cout<<endl;}<<endl<<"Матрица
D (k=k+1): "<<endl;(i=0;i<n;i++)
{for(j=0;j<n;j++){cout<<"
"<<D[i][j]<<" ";}cout<<endl;}
}main()
{
//Включаем вывод русских символов в консоль
setlocale(LC_ALL,"Russian");var;i=0,
j=0;_of_iteration k=0;c=5;s=0;p=0.1;eps=0;fine_eps;_gradient
norm=0;x;_of_points U;g;_of_grad V;d;D;_matrix H;_Hess_matr
dH;_0(var,i,j,eps,x,D);(var=='3')
{<<endl<<"Точность
метода
штрафных
функций:
";>>fine_eps;
}<<endl;(var,p,x,H,dH);
(dH<=0)
{
cout<<endl<<”Функций
в данной области не имеет минимума: ”<<endl;
goto end;
}<<endl<<"Градиент
при
k="<<k<<": "<<endl;(i=0;i<n;i++)
{[i]=diff(var,p,i,j,x);(abs(g[i])<0.0001)
g[i]=0;<<g[i]<<endl;
}_4(i,norm,g);<<endl<<"Норма
градиента
при
k="<<k<<": "<<norm<<endl;
//Реализация метода внешних штрафных функций(3
пункт)
switch (var)
{case '3': while
(phi(p,x)>=fine_eps)
{
{<<endl; for (i=0;i<20;i++)
cout<<"|||";<<endl<<"Итерация:
"<<k<<endl<<endl;_1(i,j,g,d,D);_2(var,p,s,x,d);
cout<<endl<<"Следующая точка
при k="<<k+1<<": "<<endl;
step_3(var,p,U,V,s,x,d);<<endl<<"Градиент:
"<<endl;(i=0;i<n;i++)
{[i]=diff(var,p,i,j,x);(abs(g[i])<0.0001)
g[i]=0;<<g[i]<<endl;
}_4(i,norm,g);
cout<<endl<<"Норма
градиента:
"<<norm<<endl;
step_5(U,V,D);++;
}(norm>eps);=c*p;(i=0;i<n;i++)
{[i]=diff(var,p,i,j,x);(abs(g[i])<0.0001)
g[i]=0;
}_4(i,norm,g);
} break;: while (norm>eps)
{<<endl; for (i=0;i<20;i++)
cout<<"|||";<<endl<<"Итерация:
"<<k<<endl<<endl;_1(i,j,g,d,D);_2(var,p,s,x,d);
cout<<endl<<"Следующая точка
при k="<<k+1<<": "<<endl;
step_3(var,p,U,V,s,x,d);
cout<<endl<<"Градиент:
"<<endl;(i=0;i<n;i++)
{[i]=diff(var,p,i,j,x);(abs(g[i])<0.0001)
g[i]=0;<<g[i]<<endl;
}_4(i,norm,g);<<endl<<"Норма
градиента:
"<<norm<<endl;_5(U,V,D);++;
}break;
}<<endl; for (i=0;i<20;i++)
cout<<"|||";<<endl<<endl<<"Конец
вычислений:
"<<endl;
cout<<endl<<"Точка минимума при
k="<<k<<": "<<endl;
for(i=0;i<n;i++)
{cout<<x[i]<<endl;}
cout<<endl<<"Значение функции
k="<<k<<": "<<endl;
cout<<f(var,p,x)<<endl;
end:;
}
Похожие работы на - Модели и методы конечномерной оптимизации
|