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

< ε,

то примем x=0,237037034153931 и y=0,407407409218273 Z(x,y)= -0,848148148148148

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

3. Условная оптимизация

Задача условной оптимизации в общем случае записывается в известном виде:

Такая задача оптимизации, кроме целевой функции, включает дополнительные условия в виде ограничений и граничных условий.

На рисунке 12 представлена фигура, объем, которой необходимо максимизировать при заданной площади поверхности

Рисунок 12 – Фигура для максимизации объема при заданной площади поверхности

Найдем полную площадь поверхности данной фигуры(без верхней поверхности):

,

найдем объем фигуры:

Эта задача представляет собой пример задачи условной оптимизации: необходимо найти максимальный объем при заданном значении площади поверхности.

Эту задачу можно решить двумя методами:

Метод преобразования целевой функции,

метод штрафных функций.

3.1 Метод преобразования целевой функции

Т.к. положено ограничение типа равенства, то из этого ограничения одну переменную выразим через другую и подставим полученную зависимость в целевую функцию и получим преобразованную целевую функцию, но без ограничений.

V = 4/3∙a2∙h2+7/3∙h1∙a2 → max (1)

S = 6∙a∙h1+4∙h2∙a (2)

Выразим a из (2) и подставим в (1), получим:

V = s2∙(4∙h2+7∙h1)/3∙(6∙h1+4∙h2)2

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

Возьмем, например, метод правильного симплекса, и зададим начальные условия: а=1м, h1=3м, h2=4м, s=34м. Для метода симплекса выберем точность ε=0,001.

Т.е максимальный объем V=12,7151461307724, при заданной площади получается при h1 = 2,946875, и h2 = 3,83229490168751

3.2 Метод штрафных функций

Методы штрафных функций относятся к группе непрямых методов решения задач нелинейного программирования:

f(x) -> min;

gi(x) 0, i 1, ..., k;

hj(x) 0, j 1, ..., m;

a x b.

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

F(x,a) f(x) +rS(x)

Здесь f(x) - целевая функция задачи оптимизации; S(x) - специальным образом выбранная функция штрафа,где r— множитель, значения которого можно изменять в процессе оптимизации.. Точку безусловного минимума функции F(x, a) будем обозначать через х(а).

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

3.2 Методы штрафных функций

Эти методы применяются для решения задач нелинейного программирования с ограничениями-неравенствами.

В рассматриваемых методах функции Ф(x, а) подбирают такими, чтобы их значения неограниченно возрастали при приближении к границе допустимой области G (Рисунок 14). Иными словами, приближение к границе “штрафуется” резким увеличением значения функции F(x, а). На границе G построен “барьер”, препятствующий нарушению ограничении в процессе безусловной минимизации F(x, a). Поиск минимума вспомогательной функции F(x, а) необходимо начинать с внутренней точки области G .

Таким образом, внутренняя штрафная функция Ф(х, а) может быть определена следующим образом:

Здесь dG -граница области G.

Рисунок 14 - Внутренняя штрафная функция

Методы внешних штрафных функций

Данные методы применяются для решения задачи оптимизации при наличии как ограничений-неравенств, так и ограничений-равенств.

В рассматриваемых методах функции Ф(х, а) выбирают такими, что их значения равны нулю внутри и на границе допустимой области G, а вне ее -положительны и возрастают тем больше, чем сильнее нарушаются ограничения (Рисунок 15). Таким образом, здесь “штрафуется” удаление от допустимой области G.

Рисунок – 15 Внешняя штрафная функция

Внешняя штрафная функция Ф(х, а) в общем случае может быть определена следующим образом:

Для данного курсового проекта штрафная функция для объема данной фигуры имеет вид:

,

где  - параметр штрафа, С – полная площадь поверхности, заданная изначально, V(a,h1,h2) = 4/3∙a2∙h2+7/3∙h1∙a2, S(a,h1,h2) = 6∙a∙h1+4∙h2∙a.

Задача была решена методом правильного трехмерного симплекса.

Мы видим, что при увеличении значения параметра штрафа, значение функции уменьшается (ухудшается), а при уменьшении – увеличивается (улучшается).

4. Симплекс таблицы

Для его применения необходимо, чтобы знаки в ограничениях были вида «меньше либо равно», а компоненты вектора b - положительны.

Алгоритм решения сводится к следующему:

Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.

Если в исходной системе ограничений присутствовали знаки «равно» или «больше либо равно», то в указанные ограничения добавляются искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума.

Формируется симплекс-таблица.

Рассчитываются симплекс-разности.

Принимается решение об окончании либо продолжении счёта.

При необходимости выполняются итерации.

7 На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Пересчитывается таблица.

Дана функция вида:

f(x)=4x1+2x2

Подберем k геометрическим способом решения так, чтобы область допустимых значений была пятиугольником. k=7

Рисунок – 16 Область допустимых значений

Приведем запись задачи линейного программирования к стандартной форме, введем новых переменных, все ограничения кроме ограничения на знак представим в виде равенств, тогда эта задача примет вид.

4у1+2у2+0у3 +0у4 +0у5

=(0;0;8;12;7) – начальные допустимые базисные решения

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

Вводим в базис у1 , а выводим из базиса у4.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11