Ознакомление с методами решения оптимизационных задач. Алгоритм метода ломанных. Определение наименьшего значения целевой функции. Описание метода анализа математической модели. Расчет поиска минимума по методу ломаных. Листинг программы, интерфейс.
Аннотация к работе
Оптимум (от лат. optimum - наилучшее) - совокупность наиболее благоприятствующих условий; наилучший вариант решения задачи или путь достижения цели при данных условиях и ресурсах. Оптимизация - это процесс выбора наилучшего варианта или процесс приведения системы в наилучшее (оптимальное) состояние, который состоит в нахождении всех максимизирующих или минимизирующих элементов или седловых точек. Методы оптимизации - методы поиска экстремума функции (в практических задачах - критериев оптимальности) при наличии ограничений или без ограничений очень широко используются на практике. Отыскать наименьшее значение целевой функции f(x) на интервале [a,b], используя метод, соответствующий варианту студента. Выбираем произвольно точку и строим функцию ;В ходе выполнения данного курсового проекта было составлено две программы по двум заданиям. Составлены программы в VBA в среде Microsoft Office Excel.
Введение
Термин «оптимизация» имеет очень широкое употребление, а потому может зависеть от контекста. Оптимум (от лат. optimum - наилучшее) - совокупность наиболее благоприятствующих условий; наилучший вариант решения задачи или путь достижения цели при данных условиях и ресурсах.
Оптимизация - это процесс выбора наилучшего варианта или процесс приведения системы в наилучшее (оптимальное) состояние, который состоит в нахождении всех максимизирующих или минимизирующих элементов или седловых точек.
Методы оптимизации - методы поиска экстремума функции (в практических задачах - критериев оптимальности) при наличии ограничений или без ограничений очень широко используются на практике. Это, прежде всего оптимальное проектирование (выбор наилучших номинальных технологических режимов, элементов конструкций, структуры технологических цепочек, условий экономической деятельности, повышение доходности и т. д.), оптимальное управление построением нематематических моделей объектов управления (минимизации невязок различной структуры модели и реального объекта) и многие другие аспекты решения экономических и социальных проблем (например, управление запасами, трудовыми ресурсами, транспортными потоками и т. д.).
Методы оптимизации являются разделом математического моделирования. Эти темы охватывают широкий спектр различных задач математического моделирования, возникающих при исследовании реальных объектов промышленного производства, экономических, финансовых и других проблем.
Модель - это такой материальный или мысленно представляемый объект, который в процессе исследования замещает объект-оригинал так, что его непосредственное изучение дает новые знания об объекте-оригинале.
1. Цель, задачи и этапы выполнения курсовой работы
Цель курсовой работы - ознакомление с методами решения оптимизационных задач, а так же приобретение навыков интерпретации и использования результатов математических вычислений для решения конкретных практических задач.
Задачи курсовой работы: 1. Знакомство с методами оптимизации и вычислительной геометрии;
2. Овладение навыками построения и анализа алгоритмической модели метода;
3. Закрепление навыков программирования.. Основная часть
2.1 Постановка задачи задание 1
Метод ломаных - это простейший численный метод нахождения глобального минимума (максимума) липшицевой функции, заданной на компакте. Прост в реализации и имеет достаточно простые условия сходимости. Подходит для широкого класса функций, производную которых, например, мы можем ограничить. В практике вычислений используется весьма редко изза невысокой точности.
Отыскать наименьшее значение целевой функции f(x) на интервале [a,b], используя метод, соответствующий варианту студента.
1. , [7;11], ?=0,01
2.1.1 Математическая модель задачи
Алгоритм метода ломанных
1. Выбираем произвольно точку и строим функцию ;
2. Следующая точка выбирается из условия (очевидно, что, или );
3. Строится функция ;
4. Очередная точка находится как ;
5. Рассмотрим шаг , т. - известны, т.е. , а определяем из условия и строим ;
Процесс останавливается по достижении точности: (тип 1) или Блок -схема
2.1.2 Описание метода анализа математической модели
Программа написана на языке программирования VBA в среде Microsoft Office Excel.
Программа имеет понятный интуитивный графический интерфейс (рис. 1.1).
Рисунок 1.1 Главное окно программы
После запуска необходимо ввести требуемую точность вычислений и границы отрезка (рис. 1.2).
Рисунок 1.2 Ввод входных значений
Затем программа рассчитывает точки приближения и находит для данных ограничений точку минимума (рис. 1.3).
Рисунок 1.3 Вывод результатов расчета
Таблица расчетов приведена в таблице 1.1.
Таблица 1.1 Расчет поиска минимума по методу ломаных
8,920247 9,902179 -0,011 -0,00906
9,359152 10,20743 -0,01139 -0,00681
9,660416 10,42042 -0,01042 -0,00501
9,895489 10,57502 -0,0091 -0,00365
10,08922 10,68873 -0,00773 -0,00264
10,25261 10,77255 -0,00644 -0,00191
10,39123 10,83424 -0,00526 -0,00137
10,50841 10,87947 -0,00424 -0,00098
10,60659 10,91254 -0,00337 -0,0007
10,68791 10,93663 -0,00265 -0,00049
10,75444 10,95414 -0,00206 -0,00035
10,80823 10,96684 -0,00159 -0,00024
10,85122 10,97604 -0,00122 -0,00016
10,88524 10,9827 -0,00093 -0,00011
10,91193 10,98751 -0,0007 -6,7E-05
10,93271 10,99098 -0,00053 -3,8E-05
10,94879 10,99349 -0,00039 -1,7E-05
10,96115 10,99531 -0,00029 -2,2E-06
10,97061 10,99661 -0,00021 8,6E-06
10,97783 10,99756 -0,00015 1,64E-05
10,98331 10,99824 -0,0001 2,2E-05
10,98746 10,99873 -6,7E-05 2,61E-05
10,99059 10,99908 -4,1E-05 2,9E-05
2.1.3 Решение задачи
Листинг программы математический программа интерфейс
Private Sub COMMANDBUTTON1_Click()
Dim a, b, e, L, x1, x2, fx1, fx2 a = Val(TEXTBOX1.Value) b = Val(TEXTBOX2.Value) e = Val(TEXTBOX3.Value)
L = Abs((a * Sin(a) 2 * Cos(a)) / (a * a * a))
For i = a To b Step 0.01
If Abs((i * Sin(i) 2 * Cos(i)) / (i * i * i)) > L Then
L = Abs((i * Sin(i) 2 * Cos(i)) / (i * i * i))
End If
Next i
Cells(5, 11) = L x0 = (a b) / 2 (Cos(a) / (a * a) - Cos(b) / (b * b)) / (2 * L)
Cells(2, 11) = x0 k = 0
For i = 0 To 100
Cells(2 i, 12) = ""
Cells(2 i, 13) = ""
Cells(2 i, 14) = ""
Cells(2 i, 15) = ""
Next i
Do While Abs(a - b) >= e x1 = (a x0) / 2 (Cos(a) / (a * a) - Cos(x0) / (x0 * x0)) / (2 * L) x2 = (x0 b) / 2 (Cos(x0) / (x0 * x0) - Cos(b) / (b * b)) / (2 * L) fx1 = Cos(x1) / (x1 * x1) fx2 = Cos(x2) / (x2 * x2)
Cells(2 k, 12) = x1
Cells(2 k, 13) = x2
Cells(2 k, 14) = fx1
Cells(2 k, 15) = fx2
If fx1 < fx2 Then a = x1 x0 = x2
Else b = x2 x0 = x1
End If k = k 1
Loop
If (Cos(x1) / (x1 * x1)) < (Cos(x2) / (x2 * x2)) Then
TEXTBOX5.Value = Round(x1, 4)
TEXTBOX4.Value = Round(Cos(x1) / (x1 * x1), 5)
Else
TEXTBOX5.Value = Round(x2, 4)
TEXTBOX4.Value = Round(Cos(x2) / (x2 * x2), 5)
End If
Cells(18, 7) = TEXTBOX5.Value
Cells(18, 8) = TEXTBOX4.Value
End Sub
2.1.4 Интерпретация результатов
2.2 Постановка задачи задание 2
Задание 2. Найти наименьшее (наибольшее) значение функции при методом наискорейшего спуска.
.
Метод наискорейшего пуска
Суть метода наискорейшего спуска состоит в следующем. Как и прежде, в начальной точке определяется антиградиент минимизируемой функции. Однако теперь в направлении антиградиента делается ни один шаг, а движутся в данном направлении до тех пор, пока целевая функция убывает, достигает в некоторой точке минимума. В этой точке опять определяют антиградиент и ищут новую точку минимума целевой функции и так далее. В данном методе спуск имеет более целеустремленный характер, производится более крупными шагами и градиент функции вычисляется в меньшем числе точек.
Описание программы
Программа предназначена для нахождения точек минимума функций нескольких переменных - другими словами для минимизации этих функций.
В программе реализован один из методов спуска - градиентный метод спуска с выбором шага. Изменение шага осуществляется по схеме: если если Вычисление градиента происходит по методу с парными пробами, это улучшает поиск за счет более точного вычисления градиента.
Метод наискорейшего спуска по сравнению с обычным градиентным методом дает некоторое ускорение, метод хорошо "работает" при минимизации гладких функций и если начальное приближение выбрано достаточно далеко от оптимума. Если же очередная точка окажется в окрестности оптимума, то уменьшение целевой функции будет очень медленным. Это происходит изза того, что для получения оптимума с высокой точностью необходимо выполнить большое число мелких шагов.
Метод наискорейшего спуска хотя не дает особенного ускорения сходимости он свободен от параметров и на практике может дать некоторый выигрыш, особенно на начальных итерациях.
В связи с этим в программе был реализован более точный метод градиентного спуска.
В качестве условия окончания поиска задается требуемая малость модуля градиента функции, т.е. должно выполнятся условие (в области оптимума градиент равен 0, но достичь этого значения практически не возможно, поэтому задается требуемая малость близкая к 0).
2.2.1 Математическая модель задачи
Блок схема
2.2.2 Описание метода анализа математической модели
Программа написана на языке программирования VBA в среде Microsoft Office Excel.
Программа имеет понятный интуитивный графический интерфейс (рис. 2.1).
Рисунок 2.1 Главное окно программы
После запуска необходимо ввести требуемую точность вычислений (рис. 2.2).
Рисунок 2.2 Ввод входных значений
Затем программа рассчитывает точки приближения и находит для данных ограничений точку минимума (рис. 2.3).
Рисунок 2.3 Вывод результатов расчета
Таблица расчетов приведена в таблице 2.1.
Таблица 2.1 Расчет поиска минимума по методу наискорейшего спуска
0,013868 -0,29863 0,660911
0,072739 -0,30816 0,611609
0,116095 -0,31354 0,585191
0,147855 -0,31632 0,571146
0,170995 -0,31758 0,563737
0,187777 -0,31797 0,559853
0,199903 -0,31792 0,557829
0,208643 -0,31768 0,556777
0,214929 -0,31738 0,556232
0,219445 -0,31708 0,555951
0,222686 -0,31682 0,555805
0,225011 -0,31661 0,55573
0,226678 -0,31643 0,555692
0,227873 -0,3163 0,555672
0,22873 -0,3162 0,555662
0,229344 -0,31612 0,555656
0,229784 -0,31606 0,555654
0,230099 -0,31602 0,555652
0,230326 -0,31599 0,555652
0,230488 -0,31597 0,555651
0,230604 -0,31595 0,555651
0,230687 -0,31594 0,555651
2.2.3 Решение задачи
Private Sub COMMANDBUTTON1_Click()
Dim e, L, x(1000), y(1000), f(1000) As Double, modgrad e = Val(TEXTBOX3.Value) x(0) = 1 y(0) = 1 h = 1 f(0) = x(0) ^ 2 2 * y(0) ^ 2 Exp(x(0) ^ 2 y(0) ^ 2) - x(0) 2 * y(0)
В ходе выполнения данного курсового проекта было составлено две программы по двум заданиям.
Составлены программы в VBA в среде Microsoft Office Excel. Подробное описание программ представлено основной части КП.
В данном курсовом проекте все поставленные мною задачи были выполнены. Разработана основная часть программы. Имеется введение, заключение, список использованных источников.
Выполняя данную работу, необходимо было ознакомиться с нужной информацией и изучить предметную область на основе специализированной литературы.
Полученный мною опыт работы позволит в дальнейшем разрабатывать более сложные проекты.
Список литературы
Нормативно-технические документы
1 ГОСТ 19402-78. Описание программы
2 ГОСТ 19404-79. Пояснительная записка. Требования к содержанию и оформлению.
3 Метод ломаных - http://studopedia.net/7_22267_metod-lomanih.html
4 Метод наискорейшего спуска - http://matlab.exponenta.ru/optimiz/book_2/2_2.php
5 Метод наискорейшего спуска http://otherreferats..ru/mathematics/00188334_0.html
6 Метод наискорейшего спуска - http://dit.isuct.ru/ivt/sitanov/Literatura/M171/Pages/Glava2_3_2_1.htm
7 Программирование на VBA в Microsoft Office - http://excelvba.ru/books/3