Сравнительный анализ методов оптимизации
Вычисляем значение функции в точках f(A), f(B), f(D) (пусть f(A)<f(B)<f(D)) и присваиваем им номера в порядке возрастания A-1, B-2, D-3.
Вершину с наибольшим номером отражаем относительно центра тяжести стороны 1-2
Координаты вершины Е:
![]()
(3.3)
Затем вычисляем f(E) и сравниваем f(E) и f(D). Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. В противном случае выполняют еще одну попытку отражения для вершины со следующим по величине значением f (х). Если и она не приводит к уменьшению функции, то сокращают длину ребра симплекса, например, вдвое и строят новый симплекс с этим ребром. В качестве базовой выбирают ту вершину х0 старого симплекса, в которой функция принимает минимальное значение. Поиск точки минимума f (x) заканчивают, когда либо ребро симплекса, либо разность между значении функции в вершинах симплекса становятся достаточно малыми.
3.2 Поиск точки min методом деформируемого симплекса
Алгоритм, описанный выше, можно модифицировать, добавив к процедуре отражения при построении нового симплекса процедуры сжатия и растяжения. Положение новой вершины находится сравнением и выбором наименьшего среди значений целевой функции в точках;
(3.5)
Так как величина a О (0; 1), то выбор точек z1 и z2 соответствует сжатию симплекса; b » 1, поэтому выбор точки z3 соответствует отражению, а g > 1 и выбор точки z4 приводит к растяжению симплекса. На практике хорошо зарекомендовал себя следующий набор параметров a, b и g для выбора пробных точек zi: a = 1/2, b = 1 и g =2.

Рис. 3.2. Пробные точки z1,z2,z3,z4 для перехода к новому симплексу


Рис. 3.3. Новые симлексы полученные в результате процедур сжатия (а,б); отражения (в); растяжения(г).
Опишем алгоритм метода поиска точки минимума функции по деформируемому симплексу.
Шаг 0 – Шаг 3 Аналогичны методу правильного симплекса.
Шаг 4.
Найти
и
пробные точки
zk
, k=1,
…, 4 пo
формулам (3.5). Найти
f
(z*)= min
f
(zk).
Если f
(z*)
< f
(zn).
то положить
xn=z*
и перейти к
шагу 2. Иначе –
перейти к шагу
5.
3.3 Поиск точки min методом циклического покоординатного спуска

Этот метод заключается в последовательной минимизации целевой функции f (x) сначала по направлению первого базисного вектора е1, затем второго – е2 и т.д. После окончания минимизации по направлению последнего базисного вектора еn цикл повторяется.
Опишем этот алгоритм.
Шаг 0. Выбрать х О En , критерий достижения точности, величину e. Найти f (x), положить j= 1.
Шаг 1.
Решить задачу
одномерной
минимизации
Ф(a)
= f
(х + aеj)®
min,
a
О
R,
т.е. найти a*.
Положить
=
х +a*еj,
вычислить f
(х).
Шаг 2. Если
j
< п, то положить
х =
,
j=j+1
и перейти к
шагу 1, иначе –
перейти к шагу
3.
Шаг 3.
Проверить
условие достижения
точности ||х–
||
< e
3.4 Поиск точки min методом Хука – Дживса
Этот алгоритм содержит две основные процедуры:
а) исследующий покоординатный поиск в окрестности данной точки, предназначенный для определения направления убывания f (х);
б) перемещение в направлении убывания.
Опишем алгоритм исследующего покоординатного поиска из заданной точки х с приращениями по каждой координате Dj , j = 1, …, n
Шаг 1.
Положить
= x
, i
= 1.
Шаг 2. Сделать
пробный шаг
y=
–
Dje
j, где
e j –j–й
базисный вектор.
Если f (
)
Ј
f (y),
то перейти к
шагу 3, иначе –
к шагу 4.
Шаг 3. Сделать
пробный шаг
y=
+Dje
j . Если
f (
)
Ј
f (y),
то перейти к
шагу 5, иначе –
к шагу 4.
Шаг 4. Положить
=
у.
Шаг 5. Положить
j = j
+ 1. Если j
Ј
n, то перейти
к шагу 2. В противном
случае исследующий
поиск окончен
– получена
точка
для которой
f (
)
< f (y),
если
№ х.
3.5 Пример решения методами правильного симплекса, деформируемого симплекса, покоординатного спуска, Хука – Дживса
Дана
функция
,
с=7; d=7.
Найти минимум функции с точностью ε=0,001
Метод правильного симплекса
Выбираем длину стороны треугольника l=10ε=0,0001
Вершины треугольника находим следующим образом:
A(
);
B(![]()
);
D(![]()
).
A(1,065; 0,918);
B(1,07,0,927);
D(1,075,0,918).
Шаг 0
F(A)=10,903; F(B)=11,081; F(D)=11,051.
F1<F2<F3:
F1=F(A); F2=F(D); F3=F(B).

Отражаем вершину 3 относительно центра тяжести.

F(E)=10,873.
Значение функции в найденной точке меньше, значения функции в точке 1, поэтому принимаем новый симплекс (1,2,E).
Шаг 1
F(1)=10,903; F(2)=11,081; F(E)=10,873.
F1<F2<F3:
F1=F(E); F2=F(1); F3=F(2).

Отражаем вершину 3 относительно центра тяжести.

F(E)=10,726.
Значение функции в найденной точке меньше, значения функции в точке 1, поэтому принимаем новый симплекс (1,2,E).
,
.
В результате получаем x1=0,125, x2=0,208, f(x1, x2)=-0,41.
Метод деформируемого симплекса
Выбираем длину стороны треугольника l=5ε=0,005
Вершины треугольника находим следующим образом:
A(
);
B(![]()
);
D(![]()
).
A(1,065; 0,918);
B(1,07,0,927);
D(1,075,0,918).
Принимаем коэффициенты выбора пробных точек k1=0,5, k2=1, k3=2.
Шаг 0
F(A)=10,903; F(B)=11,081; F(D)=11,051.
F1<F2<F3:
F1=F(A); F2=F(D); F3=F(B).
Находим центр тяжести вершины 3 относительно вершин 1 и 2:

Выбираем пробные точки:

F(z1)=10,966.

F(z2)=11,018.

F(z3)=11,044.

F(z3)=11,097.
Значение функции в z1 точке меньше, значения функции в точке 3, поэтому принимаем новый симплекс (1,2,z1).
Шаг 1
F(1)= 10,903; F(2)= 11,051; F(z1)=10,966.
F1<F2<F3:
F1=F(1); F2=F(z1); F3=F(2).

Выбираем пробные точки:

F(z1)=10,955.

F(z2)=10,998.

F(z3)=11,019.

F(z3)=11,062.
Значение функции в точке z1 меньше, значения функции в точке 3, поэтому принимаем новый симплекс (1,2,z1).
,
.
В результате получаем x1=-0,012, x2=0,419, f(x1, x2)=-0,014.
Метод покоординатного спуска
(1,065; 0,918).
![]()
α=5ε=0,005.
Шаг 1
Координату
закрепляем,
![]()
![]()
Т.к.![]()
,
Следовательно
![]()
![]()
![]()
![]()
![]()
![]()
Получим
x1=0,012,
![]()
Шаг 2
Принимаем
и закрепляем,
![]()
![]()
Т.к.![]()
,
![]()
![]()
![]()
![]()
![]()
![]()
Получим
x2=0,199,
![]()
Продолжаем
поиск до тех
пор, пока не
будет выполнено
условие
![]()
В результате получаем x1=0,117, x2=0,189, f(x1, x2)=-0,411.
Метод Хука-Дживса
x0: (1,065; 0,918).
![]()
Δ1=5*ε=5*0,001, Δ2=5*ε=5*0,001.
λ=2.
Шаг 1
Принимаем k1=-1, k2=-1 – коэффициенты, определяющие направление поиска.
![]()
![]()
![]()
В данном направлении функция убывает.
Шаг 2
Принимаем k1=-1, k2=-1.
![]()
![]()
![]()
В данном направлении функция убывает.
Продолжаем
поиск до тех
пор, пока не
будет выполнено
условие
![]()
В результате получаем x1=0,115, x2=0,198, f(x1, x2)=-0,411.
4. Основы линейного программирования
Если в задаче оптимизации целевая функция и все ограничения заданы в виде линейных функций, то этот класс задач носит название задач линейного программирования.

Примечание: если переменных две, то задача может быть решена и геометрически.
Точка оптимального решения является крайней точкой пересечения выпуклых множеств,
4.1 Симплекс-метод решения задачи ЛП
Допустим, что есть базисное решение. Не трудно заметить, что в качестве базисного решения можно принять:
,![]()
Суть симплекс-метода заключается в переходе решения к другим базисным допустимым решениям, при которых значение целевой функции не убывает.
Предполагаем, что базисная точка найдена, тогда:
![]()
![]()
,![]()
![]()
![]()

– значение
функции в базисной
точке (базисе).
Тогда значение функции:
![]()
– симплекс-разность
Тогда в скалярной форме:
![]()
Для того, чтобы при переходе к следующей точке значение целевой функции было неубывающим на выбор симплекс-разности ставится несколько условий, которые позволяют производить замену столбцов базиса.
![]()
,
Если
,
то
быть не может,
следовательно
,
т.к. при отрицательном
коэффициенте
может стать
отрицательным.
Это условие необходимое.
Max значение базисной переменной определяется:
,![]()

где
– номер столбца,
который выводится
из базиса.
Если
,
то функция
может возрастать
неограниченно.
Процедуру поиска решения задачи линейного программирования, записанной в стандартной форме, симплекс-методом при известном базисном решении можно представить в качестве нескольких шагов:
по известному
базисному
решению строятся
матрицы и находим
;
вычисляется симплекс-разности. Из них выделяются положительные наибольшие. Соответствующая переменная вводится в базис;
для выбора
выводимой
переменной
из базиса вычисляется
и max значение
новой базисной
переменной
Вычисляются значения новых базисных переменных:
![]()
4.2 Пример решения задач ЛП симплекс – методом
Дана функция
и ограничения

a=3, b=6, c=4, k подобрать таким образом, чтобы область была пятиугольной.
Графическое решение задачи линейного программирования
Чтобы получить пятиугольную область допустимых значений выберем k=11.2.
Подставив коэффициенты a, b, c, k, получим функцию

Построим область допустимых значений

Рисунок 4.1 – Область допустимых значений
Чтобы получить максимум целевой функции будем ее переносить параллельно самой себе до пересечения с крайней точкой области допустимых значений. В данном случае максимум находится в точке пересечения функций 6x1+x2=12 и 2x1+4x2=11,2.
Решим систему уравнений:

Получим точку максимума целевой функции:
Значение функции в этой точке f(x1,x2)=15,927
Решение задачи линейного программирования симплекс-методом
Приведем задачу к стандартной форме записи:

Начальный базис y0(0 0 8 12 11.2).
Процедура поиска оптимальной точки симплекс-методом сведена в таблицу 1.
Таблица 1. Симплекс-таблица
| Номер итерации | Базисные переменные | Значение | y1 | y2 | y3 | y4 | y5 | отношения |
| 0 | y3 | 8 | 1 | 3 | 1 | 0 | 0 | 0,125 |
| y4 | 12 | 6 | 1 | 0 | 1 | 0 | 0,5 | |
| y5 | 11,2 | 2 | 4 | 0 | 0 | 1 | 0,17857143 | |
| -f' | 0 | 6 | 3 | 0 | 0 | 0 | ||
| 1 | y3 | 6 | 0 | 2,833333 | 1 | -0,16667 | 0 | 0,4722 |
| y1 | 2 | 1 | 0,166667 | 0 | 0,166667 | 0 | 0,0833 | |
| y5 | 7,2 | 0 | 3,666667 | 0 | -0,33333 | 1 | 0,5093 | |
| -f' | -12 | 0 | 2 | 0 | -1 | 0 | ||
| 2 | y3 | 0,436363636 | 0 | 0 | 1 | 0,090909 | -0,77273 | |
| y1 | 1,672727273 | 1 | 0 | 0 | 0,181818 | -0,04545 | ||
| y2 | 1,963636364 | 0 | 1 | 0 | -0,09091 | 0,272727 | ||
| -f' | -15,92727273 | 0 | 0 | 0 | -0,81818 | -0,54545 |
На шаге 2 нет положительных коэффициентов в симплекс разности, значит, решение прекращаем.
Получаем оптимальное значение целевой функции
![]()
5. Определение оптимальных параметров технического объекта

Рисунок 5.1-Модель сосуда
Параметры сосуда (рис.5.1):
Высота цилиндров – h1
Высота параллелепипеда – h2
Высота усеченного конуса – h3
Длина параллелепипеда – а
Ширина параллелепипеда – а
Радиус нижнего основания усеченного конуса – R
Радиус верхнего основания усеченного конуса – r
Соотношения параметров:
2h1 = 2h2 = h3 = H
a = 2R = 4r = x
Для того, чтобы рассчитать максимальный объем при заданной площади поверхности надо найти общую площадь сосуда
Площадь
поверхности
цилиндра:
![]()
Площадь
поверхности
параллелепипеда: