1. Постановка задачи поиска оптимального решения. Основные понятия, используемые при решении задач оптимизации. Классификация задач оптимизации. Суть задач математического программирования и основные трудности при их решении.
Постановка задачи поиска оптимального решения. Основные понятия, используемые при решении задач оптимизации.
Везде снизу min приписывать |
!!! |
(Необходимо определить:) |
|
1)n-мерное Евклидово пространство
2)мн-во
3)отображение
4)критерий оптимизации: минимум либо максимум
Формулировка задачи: |
при |
(либо |
при |
) |
|
Решить задачу оптимизации значит. (Пусть ищем min): |
|
|
|||
1) |
найти |
, т.е. |
|
при |
|
2) |
либо (если не можем найти |
) найти значение ф-ии |
|
при |
|
3)либо доказать, что f(x) не ограничена снизу
4)либо доказать, что X= , т.е. Х является пустым мн-вом
Поиск max всегда можно свести к поиску min: |
при |
f(x) - целевая ф-ия |
|
X– мн-во допустимых точек, допустимая область
-глобальный экстремум
;- множество оптимальных точек.
Локальный экстремум (для min):
называется локальным экстремумом, если Любой глобальный min является локальным min.
Если у ф-ии есть лок. экстремумы, то необх. их все найти и выбрать меньший
Задание множества X:
- ограничение, в общем случае нелинейное Типы ограничений:
1)Ограничения в виде неравенств
2)Ограничения в виде равенств
Особенности допустимой области Х:
1.1) Односвязное мн-во (т.е. все точки области модно соединить не выходя за границу) 2) Многосвязное мн-во
2.Выпуклость и вогнутость
X выпуклое, если Х-ки ф-ии:
1.Выпуклость и вогнутость f(x) - выпуклая, если
2.Унимодальность (если 1 экстремум)
Методы оптимизации классифицируются в соответствии с задачами оптимизации: 1)Методы одномерной безусловной оптимизации Ограничений на доп. область нет, т.е.
2)Методы многомерной безусловной оптимизации (для унимодальных и многомодальных ф-ций)
1
3) Методы линейного программирования |
|
|
, |
, |
, , –коэф-ты |
4) Методы квадратичного программирования f(x) явл квартичной, т.е.
–линейные
5)Методы выпуклого программирования f(x)–выпуклая, –вогнутые Х–выпуклое мн-во
6)Методы нелинейного программирования
f(x) – нелин. ф-ия, – нелинейные
7) Методы целочисленного программирования f(x) любая, Х–мн-во целых чисел
Математическое программирование – это математическая дисциплина, в которой разрабатываются методы отыскания экстремальных значений целевой функции среди множества ее возможных значений, определяемых ограничениями.
Особенности решения задач оптимизации с использования численных методов 1) выбор начальной точки – процесс выбора не формализован 2) ошибки вычислений
3)нахождение оценки экстремумов (точные значения найти невозможно) Отметим, что решение задач оптимизации будет очень трудоемко при следующих особенностях ф-ии
1)нечувствительность f(x) к значениям каких-то переменных
2)значения f(x) близки к бесконечности
3)овражные функции
2
2.Постановка задачи линейного программирования. Основные формы задачи линейного программирования. Симплекс-таблица и критерий оптимальности. Прямой симплекс-метод и метод искусственного базиса.
Общая форма ЗЛП (постановка задачи):
,–целевая ф-ия
–вектор-строка
–вектор-столбец
n–размерность пространства
– ограничения Х
,
кол-во ограничений m
- неотрицательные переменные (остальные - свободные)
– матрица mxn |
|
–вектор-столбец |
|
Формы описания ЗЛП |
|
1.общая (приведена выше) |
|
2.каноническая |
|
, т.е. свободных переменных нет |
|
Все ограничения в форме равенств ( |
) |
3.стандартная
Все ограничения в форме неравенств ( |
) |
Симплекс-таблица
(–базис)
,
,
,–столбец матрицы А
3
|
|
... |
|
|
|
|
|
… |
|
|
|
|
… |
… |
|
|
… |
|
|
|
|
… |
… |
|
|
… |
|
|
|
–базисное решение |
|
– допустимое базисное решение |
|
Опр.Симплекс-таблица называется прямо допустимой, если |
, i=1..m |
Опр.Симплекс-таблица называется двойственно допустимой, если |
, j=1..n |
Утв.Если ЗЛП разрешима, то существует прямо и двойственно допустимая симплекс-таблица (ЗЛП разрешима, если х не и ф-ия ограничена снизу)
Утв.(достаточное условие оптимальности) если симплекс-таблица явл прямо и двойственно допустимой, то соответствующее базисное решение оптимальное.
Прямой симплекс-метод
0.построить нормальную симплекс-таблицу |
|
|
|
1.если с.-т. является двойственно допустимой (т.е. |
, j=1..n), то решение оптимальное и |
||
конец, иначе переход к шагу2 |
|
|
|
2.определяем ведущий столбец, т.е. находим такое j=s, что |
(если их несколько, то |
||
выбираем любой из них) |
|
|
|
3.если |
, то конец (ЗЛП решения не имеет), иначе определяем ведущую строку |
||
r: |
, –ведущий элемент |
|
|
4.преобразуем симплекс-таблицу с ведущим элементом |
. |
(Заменяем |
|
соответствующую базисную переменную на небазисную) и переходим к шагу1 (в результате
с.-т. остается всегда прямо допустимой) |
|
||
Метод искусственного базиса |
|
|
|
Пусть |
, все |
|
|
Введем целевую ф-ию |
, ( |
–искусственный базис |
|
ограничения: |
|
|
|
0.Формулировка задачи и построение симплекс-таблицы 1.Выполняем шаги 1-4 прямого симплекс-метода, находим оптимальное б.д.р
2.Если (для оптимального б.д.р.), то и конец (ЗЛП не имеет решения), иначе
:
1)удаляем нулевую строку в симплекс-таблице
2)удаляем все столбцы искусственного базиса 3.если среди переменных б.д.р. останутся только переменные исходной задачи, то переходим к шагу7, иначе к шагу4
4.выбираем строчку r, соответствующую искусственной переменной
5.выбор ведущего столбца: если |
, то выбираем |
, осуществляем элементарное |
преобразование базиса и переходим к шагу3, иначе к шагу6 |
|
|
6.удаляем строку, для которой |
и переходим к шагу3 |
|
7.достраиваем нулевую строку в соответствии с исходной задачей, таким образом получаем прямо допустимую симплекс-таблицу исходной задачи 8.выполняем шаги 1-4 для полученной прямо допустимой симплекс-таблицы
4
3.Суть двойственных задач линейного программирования. Теоремы двойственности линейного программирования. Двойственный симплекс-метод.
Ограничения:
–сущ.ограничения |
|
- неотрицательные переменные (остальные , |
- свободные) |
, |
|
Двойственная задача ЛП 1.вводим двойственные переменные 2.целевая ф-ия
3.,
,–свободные
5.
–двойственная задача
Теоремы двойственности Свойства:
1.если x и y явл. допустимыми решениями соотв. прямой и двойственной ЗЛП, то всегда
2.если x и y явл. допустимыми решениями соотв. прямой и двойственной ЗЛП и
,то x и y являются оптимальными решениями прямой и двойственной ЗЛП Первая теорема двойственности Прямая и двойственная к ней ЗЛП либо одновременно разрешимы, либо одновременно неразрешимы.
Причем в первом случае опт. знач. прямой и двойственной целевой ф-ии совпадают. Во втором случае по крайней мере одна из задач не разрешима из-за несовместности ограничений Вторая теорема двойственности
Допустимы решения прямой и двойственной ЗЛП оптимально тогда и только тогда, когда:
Двойственный симплекс-метод 0.Для прямой ЗЛП строим симплекс-таблицу, которая будет двойственно допустимой
1. если построенная симплекс-таблица явл. прямо допустимой, то решение оптимальное и конец, иначе шаг2
2.выбираем ведущую строку r: |
|
|
3.если |
, то ЗЛП не разрешима и конец, иначе выбираем ведущий |
|
столбец s: |
|
|
4.преобразуем симплекс-таблицу, |
, переход к шагу1 |
|
5
4.Постановка задачи одномерной нелинейной оптимизации без ограничений и классификация методов ее решения. Основные методы решения задач одномерной безусловной оптимизации: деления интервала пополам, дихотомии, золотого сечения, чисел Фибоначчи, парабол.
Постановка задачи: найти min f(x), |
, x конечном отрезке [a,b] – интервал |
неопределенности |
|
Группы методов: |
|
1)методы пассивного поиска (значения предыдущих итераций не используются)
2)методы активного поиска (инф-ия об экстремуме, кот. получили на предыдущих итерациях используется)
3)методы, основанные на аппроксимации целевой ф-ии (в основе аппроксимации – разложение в ряд Тейлора)
Алгоритм деления интервала пополам 1.задаем значения a,b,
2.вычисляем |
|
|
|
, |
|
|
|
|
|
|
|
3.выч-м |
|
|
|
, |
|
|
, |
, |
|
|
|
находим |
|
|
при i=1..3 |
|
|
|
|
|
|
||
-точка, в кот. мин. значение среди этих 3-х точек |
|
|
|
||||||||
тогда |
|
|
|
( – конечный интервал неопределенности) |
|
|
|||||
4.переобозначаем: |
|
, |
, |
, |
при i=0, при i=4 |
|
|
||||
5.если |
|
|
, то конец, |
, иначе переход к шагу3 |
|
|
|
||||
Алгоритм, основанный на дихотомии |
|
|
|
|
|
||||||
1.задаем a,b, |
( |
|
) |
|
|
|
|
|
|
|
|
2.выч-м |
|
|
|
|
|
|
|
|
|
|
|
3.выч-м |
|
|
, |
|
, |
|
, |
|
|
|
|
если |
|
, то |
|
, |
|
|
|
|
|
|
|
иначе |
|
|
|
, |
|
|
|
|
|
|
|
4.если |
|
|
, то конец, |
|
, |
–min, иначе переход к шагу2 |
|
||||
Метод золотого сечения |
|
|
|
|
|
|
|
||||
1.задаем a,b, |
( |
|
|
) |
|
|
|
|
|
|
|
2.выч-м |
|
|
|
|
, |
|
, |
, |
|
|
|
3.если |
|
, то |
|
, |
, |
|
, |
, |
, |
|
|
иначе |
|
, |
, |
|
, |
|
, |
, |
|
|
|
4.если |
|
|
, то конец и если |
|
, то |
, иначе |
, |
|
|
||
иначе переход к шагу3 |
|
|
|
|
|
|
|
||||
Метод Фибоначчи |
|
|
|
|
|
|
|
|
|||
N–число вычислений ф-ии задано(!) |
|
|
|
|
|
||||||
, |
|
|
|
|
|
|
|
|
|
|
|
1.задаем a,b,N, k=1? k-номер итерации |
|
|
|
|
|
||||||
|
|
|
|
|
, |
|
|
, |
, |
|
|
2.если |
|
, то |
|
, |
, |
|
, |
, |
, |
|
|
если |
|
, то |
|
, |
, |
|
, |
, |
, |
|
|
3.если |
|
, то k=k+1 и повторяем шаг2, иначе конец и если |
, то |
, иначе |
|||||||
Метод парабол |
|
|
|
|
|
|
|
|
|
||
1.задаем значения a,b,c, |
(a<c<b), выч-м f(a),f(b),f(c) и строим параболу |
|
|
||||||||
2. t–минимум параболы |
|
|
|
|
|
|
|
||||
если |
, то x=t |
|
|
|
|
|
|
|
|
|
|
если t=c, то |
|
|
|
|
|
|
|
|
|
|
|
выч-м f(x) |
|
|
|
|
|
|
|
|
|
|
|
3.переобозначаем: a)x<c
если f(x)<f(c), то a=a, c=x, b=c если f(x)>f(c), то a=x, c=c, b=b
6
если f(x)=f(c), то a=x, b=c, c=(x+c)/2 a)x>c
если f(x)<f(c), то a=c, c=x, b=b если f(x)>f(c), то a=a, c=c, b=x
если f(x)=f(c), то a=c, b=x, c=(x+c)/2
4. если , то конец и –одна из 3-х точек (с мин. значением ф-ии), иначе переход к шагу2
7
5. Сравнительный анализ эффективности методов решения задач одномерной нелинейной оптимизации без ограничений. Стратегии выбора исходного интервала неопределенности и поиска глобального экстремума.
N– кол-во вычислений целевой ф-ии f(x)
–конечный интервал неопределенности
,где – точность
I)Алгоритмы пассивного поиска 1. Алгоритм равномерного поиска
II) Алгоритмы активного поиска
2.Алгоритм равномерного блочного поиска
;n - число точек в блоке, m - число итераций
3.Деление интервала пополам
4.Метод дихотомии
5.Метод золотого сечения
6.Метод чисел Фибоначчи
по эфф-ти примерно одинаков с методом золотого сечения III) Методы основанные на аппроксимации функции 7.метод парабол Невозможно получить выражение для
В общем случае можно говорить, что он достаточно эффективен Стратегии выбора исходного интервала неопределенности и поиска глобального экстремума.
Исх. данные: |
|
поиска |
|
1. k=0; |
, если |
, то переход к шагу 2, |
|
иначе h = -h; |
|
|
|
Если |
, то переход к шагу 2, иначе |
, |
|
2. |
|
|
|
2.1. |
|
|
|
Если |
, то |
|
|
|
|
8 |
|
2.2. |
|
|
|
Если |
, то переход к шагу 2.1, k=k+1, иначе |
, переход к |
|
шагу 3. |
|
|
|
3. |
|
|
|
Анализ точек |
. Если |
, то |
|
иначе |
, останов |
|
|
9
6. Постановка задачи многомерной безусловной оптимизации и классификация методов ее решения. Прямые методы поиска: Гаусса, конфигураций, вращающихся координат, деформируемого многогранника.
Постановка задачи
,, задана функция . Необходимо найти min (или max)
исходные данные: Классификация методов: 1) Прямые методы поиска
Знание целевой ф-ии не нужно, необходимо только уметь вычислять ее в точках 2) Методы первого порядка (градиентные методы)
Нужно знать вид функции, уметь вычислять первую производную. Выбор направления основан на вычислении градиента 3) Методы второго порядка
Нужно знать вид функции, уметь вычислять градиент и матрицу Гесса Особенности прямых методов:
1)нет необходимости знать вид ф-ии
2)не требуется регулярность и непрерывность
3)не требуется вычисление производной первого порядка Метод Гаусса
На каждом этапе осуществляем движение по осям координат. Двигаемся по напр. находим min. Из новой точки идем вдоль другой оси координат и т.д.
Критерии остановки: а) б)
1. задаем . k=0–номер итерации
2.
…………………………………………………………….
3.если , то ; f( )=f( )
Иначе k=k+1, перейти к шагу 2. Недостатки метода:
1)Если линии равного уровня вытянуты (ф-ии овражного типа), то сходимость данного метода будет очень плохой.
2)Если вид такой, то алгоритм даст неправильную точку
Метод конфигураций
10