Курсовая работа: Сравнительный анализ методов оптимизации

🛑 👉🏻👉🏻👉🏻 ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

Карагандинский Государственный Технический Университет
по дисциплине "Теория принятия решений"

Тема: "Сравнительный анализ методов оптимизации"


1. Формулировка математической задачи оптимизации. Основные понятия
1.1 Формулировка математической задачи оптимизации
1.2 Минимум функции одной переменной
1.3 Минимум функции многих переменных
2. Прямые методы безусловной оптимизации
2.1 Прямые методы одномерной безусловной оптимизации
2.1.1 Метод деления отрезка пополам (дихотомии)
2.1.3 Практическое применение прямых методов одномерной безусловной оптимизации
2.2 Методы безусловной минимизации функций многих переменных
2.2.1 Метод циклического покоординатного спуска
2.2.3 Практическое применение прямых методов безусловной многомерной оптимизации
2.2.4 Минимизация по правильному симплексу
2.2.5 Поиск точки минимума по деформируемому симплексу
2.2.6 Практическая реализация симплексных методов
Задача оптимизации всегда была весьма актуальной, а в последнее время, с ускоренным развитием различных областей науки и техники, она приобрела еще более весомое значение.
Так как поведение любого физического объекта можно описать уравнением или системой уравнений (т.е. создать математическую модель реального объекта), то задачей инженера является подбор функции с заданной точностью при данных граничных условиях, которая бы могла "показать" оптимальное решение.
В данном курсовом проекте рассмотрены базовые методы оптимизации, которые дают основное представление о теории принятия решений и широко применяются в самых различных сферах.
В достаточно общем виде математическую задачу оптимизации можно сформулировать следующим образом; минимизировать (максимизировать) целевую функцию с учетом ограничений на управляемые переменные.
Под минимизацией (максимизацией) функции n переменных f (x) = (x 1
,.., x n
) на заданном множестве U n-мерного векторного пространства Е n
понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на множестве U значения f (x). При записи математических задач оптимизации в общем виде обычно используется следующая символика:
где f (x) - целевая функция, а U - допустимое множество, заданное ограничениямина управляемые переменные.
Если функция f (x) - скалярная, то задача ее оптимизации носит название задачи математического программирования. В этом случае критерий оптимизации один, и, следовательно, речь идет об однокритериальной (одномерной) оптимизации. Если же критериев несколько, то такая задача называется многокритериальной (задачей векторного программирования).
Если область допустимых значений исходной функции задана, то оптимизация называется условной, т.е. имеются ограничения.
Если же ограничений нет, т.е. областью определения является область существования функции f (x), то такая оптимизация называется безусловной.
Пусть функция f (x) определена на множестве U вещественной оси R.
1. Число х* ÎU называется точкой глобального (абсолютного) минимума или просто точкой минимума функции f (x) на множестве U, если f (x*) £f (x) для всех хÎU.
Значение f* = f (x*) = называют глобальным (абсолютным) минимумом или просто минимумом функции f (x) на множестве U.
Множество всех точек минимума f (x) на U в дальнейшем будет обозначено через U*.
2. Число ÎU называется точкой локального минимума функции f (x),если для всех xÎU, достаточно близких к , т.е. если существует e > 0 такое, что это неравенство выполняется для любого .
Глобальный минимум f (x) является и локальным минимумом, а обратное неверно.
Будем рассматривать функции многих переменных f=f (x 1
, …, x n
) как функции, заданные в точках х
n-мерного евклидова пространства Е
n
: f=f (х).
1. Точка х *
Î Е
n
, называется точкой глобального минимума функции f (х), если для всех х *
Î Е
n
выполняется неравенство f (x *
) £f (х). Значение f (x *
) = = называется минимумом функции. Множество всех точек глобального минимума функции f (х) будем обозначать через U
*
.
2. Точка называется точкой локального минимума функции f (х), если существует e-окрестность точки : U
n
( ) ={x | r (x, ) < e} такая, что для всех х *
Î U
n
( ) выполняется неравенство f ( ) £f (х).
3. Если допустимое множество U
в задаче минимизации (максимизации) функции n переменных совпадает со всем пространством E
n
, то говорят о задаче безусловной оптимизации
Если функция f (x) на множестве U имеет, кроме глобального, локальные минимумы, отличные от него, то минимизация f (x), как правило, сильно затрудняется. В частности, многие методы поиска точки минимума f (x) приспособлены только для функций, у которых каждый локальный минимум является одновременно и глобальным. Этим свойством обладают унимодальные функции.
Функция f (x) называется унимодальной на отрезке [а; b], если она непрерывна на [а; b] и существуют числа a и b, , такие, что:
1) если а < a, то на отрезке [a; a] функция f (x) монотонно убывает;
2) если b < b, то на отрезке [b; b] функция f (x) монотонно возрастает;
Множество унимодальных на отрезке [а; b] функций мы будем обозначать через Q
[а; b]. Отметим, что возможно вырождение в точку одного или двух отрезков из [a; a], [a; b] и [b; b]. Некоторые варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции показаны на рисунке 1.
Рисунок 1
- Некоторые варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции
Основные свойства унимодальных функций:
1. Любая из точек локального минимума унимодальной функции является и точкой ее глобального минимума на отрезке [а; b].
2. Функция, унимодальная на отрезке [а; b], является унимодальной и на любом меньшем отрезке [с; d] [а; b].
где х* - одна из точек минимума f (x) на отрезке [a; b].
Функция f (x), заданная на отрезке [a; b], называется выпуклой на этом отрезке, если для всех х', х" [а; b] и произвольного числа [0; 1] выполняется неравенство
f [ax'+ (1- a) x"] £af (x') + (l - a) f (x"). (1)
Перечислим основные свойства выпуклых функций.
Если функция f (x) выпукла на [a; b], то на любом отрезке [х'; х"] Ì [a; b] ее график расположен не выше хорды, проведенной через точки графика с абсциссами х' и х" (рисунок 2).
Пусть х' и х" - произвольные точки отрезка [a; b], причем х' < х". Легко проверить, что при любом aÎ [0; 1] точка x a
= ax ’
+ (1-a) x" лежит на отрезке [x’; х"] и при непрерывном изменении a от 0 до 1 пробегает этот отрезок от точки х" (при a = 0) до точки x' (при a = 1).
Рассмотрим хорду графика f (x), проходящую через точки (х',f (х')) и (х",f (х")). Ордината y a
точки этой хорды, соответствующая абсциссе c, равна. Поэтому неравенство (1) графика выпуклой функции и хорды означает, что f (x a
) £y a
, т.е. при любом расположении x a,
на отрезке [х'; х"] точка графика функции f (x) лежит не выше соответствующей точки хорды.
2. Из курса математического анализа известны следующие условия выпуклости функции:
а) для того чтобы дифференцируемая на отрезке [а; b] функцияf (x) была выпуклой на этом отрезке, необходимо и достаточно, чтобы производная f' (x) не убывала на [а; b] ;
б) для того чтобы дважды дифференцируемая на отрезке [а; b] функция f (x) была выпуклой на этом отрезке, необходимо и достаточно, чтобы при всех хÎ [а; b] выполнялось неравенство f " (x) ³ 0.
3 Условие выпуклости для дифференцируемой на отрезке [а; b] функции f (x) означает, что на этом отрезке любая касательная к графику f (x) лежит не выше этого графика (рисунок 3).
Уравнение касательной к графику f (х) в точке (x 0,
f (x 0
)), x 0
Î [а; b] имеет вид: у (х) =f (x 0
) +f’ (x 0
) (x-x 0
). По формуле конечных приращений для любогохÎ [а; b] имеем: f (х) =f (x 0
) +f’ (x) (x-x 0
), где точка x лежит междуx и x 0
. Поэтому
f (х) - у (х) = [f’ (x) - f’ (x 0
)] (x-x 0
), хÎ [а; b],
откуда с учетом того, что производная f’ (x) выпуклой функции не убывает, получаем:
4. Если f (x) - выпуклая дифференцируемая на отрезке [а; b] функция и в точке х* Î [а; b] выполняется равенство
то х* является точкой глобального минимума f (х) на [а; b].
С учетом (3) уравнение касательной у (х) =f (х 0
) +f’ (х 0
) (х-х 0
) к графику f (x) для точки x 0
=х* принимает вид у (х) =f (x*). Поэтому из (2) следует, что f (x) f (x*) для всех хÎ [а; b], т.е. х* - точка глобального минимума f (x).
Благодаря свойству 3 выпуклых функций данное свойство приобретает простой геометрический смысл: поскольку касательная к графику f (x) в точке с абсциссой х* горизонтальна, а этот график расположен не ниже касательной, то х* есть точка минимума f (x) (рисунок 3).
Таким образом, равенство (3) для выпуклой дифференцируемой функции является не только необходимым условием глобального минимума (как для всякой дифференцируемой функции), но и его достаточным условием.
5. Можно показать, что всякая выпуклая непрерывная на отрезке [а; b] функция является и унимодальной на этом отрезке. Обратное, вообще говоря, неверно (рисунок 4).
Рисунок 4 - график унимодальной, но не выпуклой функции
Таким образом, кроме перечисленных свойств, выпуклые функции обладают также и всеми свойствами унимодальных функций.
Для решения задачи минимизации функции f (х) на отрезке [а; b] на практике, как правило, применяют приближенные методы. Они позволяют найти решение этой задачи с необходимой точностью в результате определения конечного числа значений функции f (х) и ее производных в некоторых точках отрезка [а; b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации.
Большим достоинством прямых методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы прямых методов минимизации, это возможность определения значений f (х) в заданных точках.
Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума. Самым слабым требованием на функцию f (х), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать функцию f (х) унимодальной на отрезке [а; b].
Рассмотрим конкретные вычислительные алгоритмы решения задачи безусловной минимизации f (х) ®min, xÎ E
n
, которые опираются только на вычисление значений функции f (х), т.е. прямые методы минимизации. Важно отметить, что для их применения не требуется дифференцируемость целевой функции и даже ее аналитическое задание. Нужно лишь иметь возможность вычислять или измерять значения f (х) в произвольных точках. Такие ситуации часто встречаются в практически важных задачах оптимизации.
Пусть а < x 1
<х 2
e, то перейти к шагу 3, иначе - к шагу 4.
Шаг 3.
Переход к новому отрезку и новым пробным точкам. Еслиf (x 1
) £f (x 2
) то положить b=x 2,
x 2
=x 1
, f (x 2
) £f (x 1
), x 1
=b-t (b-a) и вычислить f (x 1
), иначе - положить a=x 1
, x 1
= x 2
, f (x 1
) = f (x 2
), x 2
=b+t (b-a) и вычислить f (x 2
). Перейти к шагу 2.
Сравнение методов исключения отрезков.
При сравнении прямых методов минимизации обычно учитывают количество N
значений f (x), гарантирующее заданную точность определения точки х* тем или иным методом. Чем меньше N
, тем эффективнее считается метод. При этом вспомогательные операции такие, как выбор пробных точек, сравнение значений f (x) и т.п., не учитываются. Во многих практических случаях определение значений целевой функции требует больших затрат (например, времени ЭВМ или средств для проведения экспериментов) и вспомогательными вычислениями можно пренебречь. А эффективность метода минимизации особенно важна именно в таких случаях, поскольку позволяет сократить указанные затраты.
Эффективность методов минимизации можно также сравнивать, на основании гарантированной точности e ( N
) нахождения точки х*, которую они обеспечивают в результате определения N
значений f (x). Метод золотого сечения считают более точным, чем метод дихотомии, однако разница в точности в данном случае незначительна.
Рисунок 7 - Поведение исходной функции на заданном отрезке
Проведем несколько итерации методом дихотомии:
Поскольку f (x 1
) < f (x 2
), то b: =x 2
, a оставляем прежним. Тогда для следующей итерации:
Так как f (x 1
) > f (x 2
), то a: =x 1
, b оставляем прежним. Тогда на третьем шаге:
Результаты полного решения данной задачи представлены на рисунке 8. Листинг программы представлен в приложении А.
Так как f (x 1
) < f (x 2
), то b: =x 2
, a оставляем прежним. Тогда для следующей итерации:
Поскольку f (x 1
) < f (x 2
), то b: =x 2
, a оставляем прежним. Тогда на третьем шаге:
И так далее до тех пор, пока не достигнем указанной точности. Полный расчет представлен на рисунке 9. Листинг программы представлен в приложении А.
Рисунок 9 - Получение решения методом золотого сечения
Теперь рассмотрим задачи оптимизации, сводящиеся к поиску точек минимума функции многих переменных на всем пространстве. В большинстве случаев такая задача бывает сложнее задачи минимизации функции одной переменной, так как с ростом размерности пространства переменных, как правило, возрастают объем вычислений и сложность алгоритмов, а также затрудняется анализ поведения целевой функции.
Этот метод заключается в последовательной минимизации целевой функции f (x) по направлениямx1 и x2.
Рисунок 10 - Циклический покоординатный спуск.
Шаг 0.
Выбрать х Î E
n
, критерий достижения точности e и шаг . Найти f (x1 (0),
x2 (0))
.
Шаг 1.
Принять x1 (1)
= x1 (0)
+ . Определить f (x1 (1),
x2 (0))
. Сравнить полученное значение с значением начальной функции. Если f (x1 (1),
x2 (0))
< f (x1 (0),
x2 (0))
, то перейти к шагу 5, если же f (x1 (1),
x2 (0))
> f (x1 (0),
x2 (0))
, то перейти к шагу 2.
Шаг 2.
Принять x1 (1)
= x1 (0) -
. Определить f (x1 (1),
x2 (0))
. Сравнить полученное значение с значением начальной функции. Если f (x1 (1),
x2 (0))
< f (x1 (0),
x2 (0))
, то перейти к шагу 5, если же f (x1 (1),
x2 (0))
> f (x1 (0),
x2 (0))
, то перейти к шагу 3.
Шаг 3.
Принять x2 (1)
= x2 (0)
+ . Определить f (x1 (0),
x2 (1))
. Сравнить полученное значение с значением начальной функции. Если f (x1 (0),
x2 (1))
< f (x1 (0),
x2 (0))
, то перейти к шагу 5, если же f (x1 (0),
x2 (1))
> f (x1 (0),
x2 (0))
, то перейти к шагу 4.
Шаг 4.
Принять x2 (1)
= x2 (0) -
. Определить f (x1 (0),
x2 (1))
. Сравнить полученное значение с значением начальной функции. Если f (x1 (0),
x2 (1))
< f (x1 (0),
x2 (0))
, то перейти к шагу 4, если же f (x1 (0),
x2 (1))
> f (x1 (0),
x2 (0))
, то принять исходную точку за минимум.
Шаг 5.
Проверить условие достижения точности .
Если в процессе решения с шагом не получено решения, то принять
Этот алгоритм содержит две основные процедуры:
а) исследующий покоординатный поиск в окрестности данной точки, предназначенный для определения направления убывания f (х);
б) перемещение в направлении убывания.
Трактовать данный метод можно по-разному. Рассмотрим один из многочисленных вариантов.
Опишем один из алгоритмов данного метода.
Шаг 1.
Выбираем начальную точку и находим в ней значение функции.
Шаг 2.
Обозначим координаты начального вектора: .
Тогда, соответственно, угол направления движения
Рассчитываем координаты 4-х точек в окрестности начальной по следующим формулам:
Находим в указанных точках значения функции. Если какое-нибудь из них оказалось меньше значения функции в точке x0, то принимаем его за исходное.
Шаг 3.
Сравниваем полученные значения с f (x1 (0),
x2 (0))
. Если какое-нибудь из них оказалось меньше значения функции в 0-й точке точке, то принимаем его за исходное и переходим к шагу 5.
Шаг 4.
Если же все полученные значения функции оказались больше исходного, то уменьшаем шаг и переходим к шагу5.
Шаг 5.
Проверить условие достижения точности
Если данное условие не выполнено, возвращаемся к шагу 2.
Тогда по методу циклического покоординатного спуска будет выполнен счет следующего вида:
Т. к. , будем двигаться в противоположную сторону по оси абсцисс с тем же шагом:
поэтому продолжаем двигаться дальше с тем же шагом в данном направлении до достижения указанной точности, в противном случае уменьшаем шаг ( ):
Результаты работы данного алгоритма представлены на рисунке 12. Листинг программы приведен в приложении Б.
Рисунок 12 - Решение поставленной задачи методом спуска
Перейдем к методу Хука-Дживса. Обозначим координаты начального вектора: .
Тогда, соответственно, угол направления движения
Найдем значения функции 4-х точек в окрестности начальной:
Минимальное значение функция принимает в точке2, поэтому движемся в заданном направлении 2 пока идет уменьшение функции до достижения указанной точности, в противном случае уменьшаем шаг
Конечный результат получен на ЭВМ за 36 итераций. Результат представлен на рисунке 13. Листинг программы приведен в приложении Б.
Рисунок 12 - Решение поставленной задачи методом спуска
Правильным симплексом в пространстве E
n
называется множество из n + 1 равноудаленных друг от друга точек (вершин симплекса). Отрезок, соединяющий две вершины, называется ребром симплекса.
В пространстве E
2
правильным симплексом является совокупность вершин равностороннего треугольника, в E
3
- правильного тетраэдра.
Если х 0
- одна из вершин правильного симплекса в E
n
то координаты остальных п вершин х 1
,. ., х n
можно найти, например, по формулам:
a- длина ребра. Вершину х 0
симплекса, построенного по формулам (6), будем называть бaзовой. В алгоритме симплексного метода используется следующее важное свойство правильного симплекса. По известному симплексу можно построить новый симплекс отрaжением какой-либо вершины, например, х k
симметрично относительно центра тяжести х c
остальных вершин симплекса. Новая и старая вершины
и х k
связаны соотношением:
В результате получается новый правильный симплекс с тем же ребром и вершинами
=2x c
- х k
, х i
, i= 0,. ., n, i¹k. Таким образом, происходит перемещение симплекса в пространстве Е
n
. На рисунке 13 представлена иллюстрация этого свойства симплекса в пространстве Е
2
.
Рисунок 13 - Построение нового симплексa в E 2
отрaжением точки х: a - нaчaльный симплекс х 0
, х 1
, ; б - новый симплекс х 0
, х 1
, ; центр отрaжения - точкax c
= (х 0
+ х 1
) /2
Поиск точки минимума функции f (x) с помощью правильных симплексов производят следующим образом. На каждой итерации сравниваются значения f (х) в вершинах симплекса. Затем проводят описанную выше процедуру отражения для той вершины, в которой f (х) принимает наибольшее значение. Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. В противном случае выполняют еще одну попытку отражения для вершины со следующим по величине значением f (х). Если и она не приводит к уменьшению функции, то сокращают длину ребра симплекса, например, вдвое и строят новый симплекс с этим ребром. В качестве базовой выбирают ту вершину х 0
старого симплекса, в которой функция принимает минимальное значение. Поиск точки минимума f (x) заканчивают, когда либо ребро симплекса, либо разность между значении функции в вершинах симплекса становятся достаточно малыми. Опишем один из вариантов алгоритма этого метода.
Шаг 0.
Выбрать параметр точности e, базовую точку х 0
, ребро и построить начальный симплекс по формулам:
Шаг 1.
Вычислить значения f (х) в вершинах симплекса х 1
,. ., x n
.
Шаг 2.
Упорядочить вершины симплекса х 0
,. ., х n
так, что бы f (х1 (0),
x2
(0))
£ …££f (х 1
) £f (х n-1
) £f (х n
).
Шаг 3.
Найти среднее значение функции:
Проверить условие из учета того, что:
Если оно выполнено, то вычисления прекратить, полагая х *
» х 0
, f *
»f (x 0
). В противном случае перейти к шагу 4.
и выполнить отражение вершины х n
. К примеру, для отражения вершины А следует найти точку
Тогда отраженная вершина будет иметь вид:
Если f (Е) 1 и выбор точки z 4
приводит к растяжению симплекса. Численные эксперименты показывают, что этот алгоритм хорошо работает в пространстве E
n
для n£ 6. Отметим, что при деформациях утрачивается свойство правильности исходного симплекса. Поэтому, не стремясь к правильности начального симплекса, его строят из произвольной базовой точки х 0
Î E
n
, по формулам
где e i
- i-й базисный вектор; a- параметр симплекса. На практике хорошо зарекомендовал себя следующий набор параметров a, b и g для выбора пробных точек z i
в формулах (9): a = 1/2, b = 1 и g =2.
Опишем алгоритм метода поиска точки минимума функции по деформируемому симплексу.
Шаг 0.
Выбрать параметр точности e, параметры a, b и g, базовую точку х 0
, параметр a и построить начальный симплекс. Вычислить f (х 0
).
Шаг 1.
Вычислить значения функции в вершинах симплекса х 1
,..., x n
.
Шаг 2.
Упорядочить вершины х 0
,..., x n
так, чтобы f (х 0
) £ … £f (х n
).
Шаг 3.
Проверить достижение заданной точности. Если оно выполняется, то вычисления завершить, полагая х * » х 0
, f* »f (х 0
). Иначе - перейти к шагу 4.
Шаг 4
. Найти и пробные точки z k
, k=1, …, 4 пo формулам (9). Найти f (z *
) = minf (z k
). Если f (z*) < f (z n
). то положить x n
=z *
и перейти к шагу 2. Иначе - перейти к шагу 5.
Шаг 5.
Уменьшить симплекс, полагая х i
= (х i
+ х 0
) /2, i = 1,. ., n и перейти к шагу 1.
Замечание.
Для того чтобы избежать сильной деформации симплекса, алгоритм иногда дополняют процедурой обновления. Например, после N
шагов алгоритма из точки х 0
снова строят симплекс, полагая а = ||x 0
-x n
||.
С теоретической точки зрения описанные методы минимизации слабо исследованы, однако практика показывает их работоспособность.
Наибольшее значение функция принимает в точке2, ее и будем отражать. Для этого найдем точку С, лежащую между 1-й и 3-й точками:
Находим координаты отраженной вершины Е и значение в ней функции:
Т. к. , то строим новый симплекс на вершинах Е,1 и 3 и повторяем эту операцию до тех пор, пока среднеквадратичное отклонение не примет указанной величины, в противном случае приступаем к редуцированию - уменьшению размеров симплекса.
Результат рабочей программы представлен на рисунке 17. Листинг приведен в приложении В.
Рисунок 17 - Практическая реализация симплекс-метода
Перейдем к методу деформируемого симплекса.
Введем коэффициенты уменьшения и увеличения: .
Найдем значения функции 4-х точек в окрестности начальной:
Минимальное значение функция принимает в точке1, поэтому строим новый симплекс на вершинах Е,1 и 3 и повторяем выше указанную операцию до тех пор, пока среднеквадратичное отклонение не примет указанной величины, в противном случае приступаем к редуцированию - уменьшению размеров симплекса. Результат рабочей программы представлен на рисунке 18. Листинг приведен в приложении В.
Рисунок 18 - Практическая реализация метода деформируемого симплекса
До сих пор рассматривались методы безусловной оптимизации, т.е. на параметры оптимизации не накладывались никакие ограничения, поэтому допустимая область определения определялась только лишь условием существования целевой функции.
Но в реальных задачах обязательно присутствуют ограничения типа равенств или неравенств и ограничения по пределам изменения:
Наличие ограничений приводит к изменению точки минимума, тогда как в задаче без ограничений данная точка может оказаться вне допустимой области.
Рассмотрим 2 метода решения задачи условной оптимизации:
Если наложены ограничения типа равенства, то из этого ограничения выразим одну переменную через другую (двумерный случай). Подставив полученную зависимость в целевую функцию, получим преобразованную целевую функцию без ограничений.
Целевая функция преобразуется так, чтобы эта преобразованная функция в допустимой области была бы близка к исходной, а в недопустимых областях имела бы значения, существенно большие, чем допустимые. Такие функции носят название штрафных, так как к исходной функции добавляются штрафы при приближении к недопустимым областям.
где R- параметр штрафа (некое число).
Существуют многочисленные штрафные функции для неравенств, а для равенств на практике применяется один вид, т.е. если имеем задачу , тогда формируем штрафную функцию
В данном курсовом проекте необходимо было максимизировать объемное тело, представленное на рисунке 19.
Рисунок 19 - Объем, который необходимо максимизировать
Указанное тело состоит из цилиндра и стоящего на нем сегмента сферы. Определим изменяемые параметры для данного случая (рисунок 20): r- радиус цилиндра (равен радиусу сферы), h- высота сегмента сферы и h2 - высота цилиндра.
Пусть площадь всего объема равна 200:
Выразим из формулы общей площади параметр h2:
Подставим полученное выражение в формулу объема, получим:
Обозначим r=3 и h=1. Затем следует провести двумерную оптимизацию. Ниже на рисунке 21 приведена рабочая форма программы, реализующая двумерную оптимизацию для первого случая и трехмерную - для штрафных функций по методу координатного спуска.
Для указанного случая V=260.799603505204 при r*=4.06250000000002 и h*=0.975.
Случай со штрафными функциями в общем виде можно записать как:
Таким образом, следует провести трехмерную оптимизацию для следующей функции:
Изменяемыми параметрами в данном случае являлись r- радиус цилиндра и сферы, h- высота сегмента и h2 - высота цилиндра.
Для второго случая V=260.778443852174 при r*=4.44999999999999, h*=1.025 и h2*=4.05.
Таким образом, к предложенному объему были применены оба метода решения задачи условной оптимизации. Результат рабочей программы представлен на рисунке 21, а листинг - в приложении Г.
Если целевая функция и все ограничения в задаче оптимизации являются линейными функциями, то такая задача носит название линейного программирования. В общем случае она имеет вид:
Если в общей модели присутствуют ограничения 3-х видов, то задачи, в которых есть только ограничения первого вида, не считая ограничений на знаки переменных, называются задачами распределительного типа.
Они широко распространены, поэтому будут подробно рассматриваться в рамках данного курсового проекта.
Понятно, что ограничения определяют область допустимых значений переменных, поэтому любое x из этой области являются допустимым решением, а x* - оптимальное решение, если:
Те ограничения, которые принимают вид равенства, называются активными ограничениями; соответствующий этому ограничению ресурс называется дефицитным.
Стандартная форма записи задачи линейного программирования имеет вид:
Система уравнений является базисной, то есть ранг матрицы равняется L-числу строк. Понятно, что LКурсовая работа: Сравнительный анализ методов оптимизации
Реферат: Atomic Bomb Essay Research Paper Atomic Bomb
Реферат: Внешняя политика России в конце XVIII века. Скачать бесплатно и без регистрации
Алкоголизм И Наследственность Реферат С Источниками
Сочинение По Первой Главе Капитанской Дочки
Дипломная работа: Організація маршрутних автобусних перевезень пасажирів на прикладі ВАТ "Атасс-Боріспіль"
Виды Товара Реферат
Реферат по теме Нільс Бор і яго квантавыя пастулаты
Реферат: Финансовое состояние и деловая репутация предприятия
Дипломная работа: Ассортиментная политика аптечной сети Маклер
Реферат: Особенности организации финансов малого бизнеса
Реферат по теме История болезни - хирургия (острый холецистит)
Весна Пришла Сочинения
Молитвы Ребенку На Контрольную Работу По
Курсовая работа по теме Проект совершенствования управления в сфере ЖКХ в северном округе г. Хабаровска
Дипломная работа по теме Канализационная насосная станция
Тестирование Занимающихся Физическими Упражнениями Реферат
Дипломная работа по теме Финансовый анализ хозяйственной деятельности ОАО 'Сургутнефтегаз'
Реферат: Форма государства РФ
Курсовая работа: Проектирование информационной системы сети поликлиник
Реферат: Лекции по педагогической психологии
Статья: Пять базовых зон убеждений
Дипломная работа: Розвиток ринку страхових послуг в Україні
Курсовая работа: Заключение кредитных договоров