Сравнительный анализ методов оптимизации (стр. 4 из 6)
Шаг 5. Уменьшить симплекс, полагая xi=( xi+ x0)/2, i=1,...,n перейти к шагу 1.
На практике хорошо зарекомендовал себя следующий набор параметров a=1/2, b=1, g=2, поэтому он и был использован в программе.
Таблица 5 – Метод деформированного симплекса
| № шага | Z(x0,y0) | Z(x1,y1) | Z(x2,y2) |
| 1 | 5,25127562399313 | 5,35273629457997 | 4,72465845389651 |
| 2 | 4,47048359472409 | 5,52371793491734 | 4,32427361628427 |
| 3 | 4,26941489330181 | 4,56183485018145 | 2,53610076197985 |
| 4 | 2,53610076197985 | 4,26941489330181 | 2,54614140634749 |
| 5 | 2,60406550474582 | 2,62414679348111 | 0,650136727095332 |
| 6 | 0,873172338270091 | 4,78102989357106 | -0,460995375774572 |
| 7 | -0,460995375774572 | -0,183165198484471 | -0,647802169588968 |
| 8 | -0,647802169588968 | -0,460995375774572 | -0,752046189909185 |
| 9 | -0,752046189909185 | -0,647802169588968 | -0,743774186218157 |
| 10 | -0,824978188986428 | -0,820842187140914 | -0,807869388437316 |
| 11 | -0,848148148136976 | -0,848148148106495 | -0,848148148103467 |
| 12 | -0,848148148146818 | -0,848148148131578 | -0,848148148135116 |
| 13 | -0,848148148146818 | -0,848148148135116 | -0,848148148139001 |
| 14 | -0,848148148136976 | -0,848148148106495 | -0,848148148103467 |
| 15 | -0,848148148148147 | -0,848148148148145 | -0,848148148148146 |
| 16 | -0,848148148148148 | -0,848148148148147 | -0,848148148148147 |
T.к.
< ε,то примем 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) будем обозначать через х(а).
Среди методов штрафных функций различают методы внутренней и внешней точки. Согласно методам внутренней точки (иначе называемым методами барьерных функций), исходную для поиска точку можно выбирать только внутри допустимой области, а для методов внешней точки как внутри, так и вне допустимой области (важно лишь, чтобы в ней функции целевая и ограничений были бы определены).
Эти методы применяются для решения задач нелинейного программирования с ограничениями-неравенствами.
В рассматриваемых методах функции Ф(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) – начальные допустимые базисные решения