Решение оптимизационных задач

Введение

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

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

Методы оптимизации - методы поиска экстремума функции (в практических задачах - критериев оптимальности) при наличии ограничений или без ограничений очень широко используются на практике. Это, прежде всего оптимальное проектирование (выбор наилучших номинальных технологических режимов, элементов конструкций, структуры технологических цепочек, условий экономической деятельности, повышение доходности и т. д.), оптимальное управление построением нематематических моделей объектов управления (минимизации невязок различной структуры модели и реального объекта) и многие другие аспекты решения экономических и социальных проблем (например, управление запасами, трудовыми ресурсами, транспортными потоками и т. д.).

Методы оптимизации являются разделом математического моделирования. Эти темы охватывают широкий спектр различных задач математического моделирования, возникающих при исследовании реальных объектов промышленного производства, экономических, финансовых и других проблем.

Модель - это такой материальный или мысленно представляемый объект, который в процессе исследования замещает объект-оригинал так, что его непосредственное изучение дает новые знания об объекте-оригинале.

1.  Цель, задачи и этапы выполнения курсовой работы

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

Задачи курсовой работы:

1.      Знакомство с методами оптимизации и вычислительной геометрии;

2.      Овладение навыками построения и анализа алгоритмической модели метода;

3.      Закрепление навыков программирования.

2. Основная часть

.1 Постановка задачи задание 1

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

Отыскать наименьшее значение целевой функции f(x) на интервале [a,b], используя метод, соответствующий варианту студента.

1. , [7;11], ε=0,01          

.1.1 Математическая модель задачи

Алгоритм метода ломанных

1.      Выбираем произвольно точку  и строим функцию ;

.        Следующая точка выбирается из условия  (очевидно, что,  или );

.        Строится функция ;

.        Очередная точка  находится как ;

.        Рассмотрим шаг , т.  - известны, т.е. , а  определяем из условия  и строим ;

Процесс останавливается по достижении точности:  (тип 1) или

Блок -схема

.1.2 Описание метода анализа математической модели

Программа написана на языке программирования VBA в среде Microsoft Office Excel.

Программа имеет понятный интуитивный графический интерфейс (рис. 1.1).

Рисунок 1.1 Главное окно программы

После запуска необходимо ввести требуемую точность вычислений  и границы отрезка (рис. 1.2).

Рисунок 1.2 Ввод входных значений

Затем программа рассчитывает точки приближения и находит для данных ограничений точку минимума (рис. 1.3).

Рисунок 1.3 Вывод результатов расчета

Таблица расчетов приведена в таблице 1.1.

Таблица 1.1 Расчет поиска минимума по методу ломаных

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)

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 Ifi(5, 11) = L

x0 = (a + b) / 2 + (Cos(a) / (a * a) - Cos(b) / (b * b)) / (2 * L)

Cells(2, 11) = x0= 0i = 0 To 100

Cells(2 + i, 12) = ""

Cells(2 + i, 13) = ""

Cells(2 + i, 14) = ""

Cells(2 + i, 15) = ""iWhile 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(Cos(x1) / (x1 * x1)) < (Cos(x2) / (x2 * x2)) Then

TextBox5.Value = Round(x1, 4)

TextBox4.Value = Round(Cos(x1) / (x1 * x1), 5)

TextBox5.Value = Round(x2, 4)

TextBox4.Value = Round(Cos(x2) / (x2 * x2), 5)If(18, 7) = TextBox5.Value(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 Расчет поиска минимума по методу наискорейшего спуска

2.2.3 Решение задачи

Private Sub CommandButton1_Click()e, L, x(1000), y(1000), f(1000) As Double, modgrad= Val(TextBox3.Value)

(0) = 1(0) = 1= 1(0) = x(0) ^ 2 + 2 * y(0) ^ 2 + Exp(x(0) ^ 2 + y(0) ^ 2) - x(0) + 2 * y(0)

i = 0 To 100

Cells(2 + i, 12) = ""

Cells(2 + i, 13) = ""

Cells(2 + i, 14) = ""i

= 1

: x(i) = x(i - 1) - h * (2 * x(i - 1) + 2 * x(i - 1) * Exp(x(i - 1) ^ 2 + y(i - 1) ^ 2) - 1)

y(i) = y(i - 1) - h * (4 * y(i - 1) + 2 * y(i - 1) * Exp(x(i - 1) ^ 2 + y(i - 1) ^ 2) + 2)

f(i) = x(i) ^ 2 + 2 * y(i) ^ 2 + Exp(x(i) ^ 2 + y(i) ^ 2) - x(i) + 2 * y(i)

Cells(1 + i, 12) = x(i)

Cells(1 + i, 13) = y(i)

R = f(i) - f(i - 1)

If R > 0 Then

 h = h / 2

 GoTo 1

End If

modgrad = Sqr((2 * x(i) + 2 * x(i) * Exp(x(i) ^ 2 + y(i) ^ 2) - 1) ^ 2 + (4 * y(i) + 2 * y(i) * Exp(x(i) ^ 2 + y(i) ^ 2) + 2) ^ 2)

If modgrad > e Then

 i = i + 1

 GoTo 1

End If

TextBox5.Value = Round(x(i), 4)

TextBox6.Value = Round(y(i), 4)

TextBox4.Value = Round(f(i), 4)

(18, 7) = TextBox5.Value(18, 8) = TextBox6.Value

Cells(18, 9) = TextBox4.ValueSub

2.2.4 Интерпретация результатов

Заключение

В ходе выполнения данного курсового проекта было составлено две программы по двум заданиям.

Составлены программы в 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

          Метод наискорейшего спуска http://otherreferats.allbest.ru/mathematics/00188334_0.html

          Метод наискорейшего спуска - http://dit.isuct.ru/ivt/sitanov/Literatura/M171/Pages/Glava2_3_2_1.htm

7       Программирование на VBA в Microsoft Office - http://excelvba.ru/books/3

8       Метод ломаных - <http://examhack.narod.ru/2_1.htm>