Презентация - Семенкин Е.С. Методы оптимизации
Подождите немного. Документ загружается.
Задачаоптимальногоуправления:
данасистема, поведениекоторойописываетсядифференциальнымуравнением
где x-векторфазовыхкоординат, u- векторуправления, t- время.
Навектора x и u наложеныограничения: x∈ X, u∈U.
Системарассматриваетсянаинтервале t∈[0, T].
Требуется определить вектор-функции u(t), x(t) доставляющие минимум
функционалу J=J(x, u) припереводеизначальногосостояния (x(0),0) вконечное
состояние (x(T), T).
F – дифференцируемаяфункциясвоихаргументов.
),,,( tuxf
dt
dx
=
∫
=
T
dttuxFuxJ
0
,),,(),(
Статические и динамические (оптимальное управление)
Одинизспособовклассификацииметодовоптимизациисостоитв
соотнесенииихоптимизационнымзадачам, длярешениякоторыхони
предназначены.
Потипуинформацииопроизводных, требуемойдляорганизации
процессаоптимизации, методыподразделяютсянаметоды
- методынулевогопорядка, требующиетольковычисленийзначений
функции в точках пространства оптимизации и не требующие
аналитическоговидапроизводных;
- методыпервогопорядка (градиентные), требующиекромезначений
функциивточкеещеианалитическоезаданиепроизводныхпервого
порядкадлявычисленияградиента;
- методы второго порядка (ньютоновские), для работы которых
требуютсяещеипроизводныевторогопорядка.
Классификация методов оптимизации
Другаяклассификация:
- методы прямогопоиска,
- методы линейнойаппроксимации,
- методы квадратичной аппроксимации.
По степени математической обоснованности методы делят на
эвристические и рациональные.
Методы оптимизации подразделяют на детерминированные и
стохастические. Стохастические алгоритмы используют элементы
случайности при выборе направления или длины шага в процессе
оптимизации.
Оптимизируетнекомпьютеридаженеалгоритм, введенныйвэтот
компьютер. Оптимизируетвсегдачеловек. Онинесетответственностьза
результат.
"Вжизнинепроисходитничего, вчембынебылвиденсмыслкакого-
либоминимумаилимаксимума"(ЛеонардЭйлер).
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Линейноепрограммирование (ЛП)-этонаукаометодахисследованияи
отысканиянаибольшихинаименьшихзначенийлинейнойфункции, на
неизвестныекоторойналоженылинейныеограничения
1930 г., А.Н. Толстой - составлениеоптимальногопланаперевозок,
минимизирующегокилометраж
1931 г., Б. Эгервари - задачаоназначениях ("венгерскийметод")
1939 г., Л.В. Канторович - систематическоеисследованиезадачЛП,
разработкаобщихметодов (методразрешающихмножителей), применениек
решениюрядапрактическихзадач
1941 г., Ф. Хичкок - постановкатранспортнойзадачиЛП, метод
последовательногоулучшения
1947 г., Дж. фонНейман – теориядвойственности
1947 г., Дж. Данциг – симплекс-методрешенияобщейзадачиЛП
ОбщийвидзадачиЛП:
Z = c
1
x
1
+ c
2
x
2
+ . . . + c
n
x
n
→ min (max)
приусловиях:
x
1
≥ 0, x
2
≥ 0, . . . , x
n
≥ 0,
a
11
x
1
+ a
12
x
2
+ . . . + a
1n
x
n
≤ (=, ≥) b
1
,
a
21
x
1
+ a
22
x
2
+ . . . + a
2n
x
n
≤ (=, ≥) b
2
,
. . . . . . . . . . . .
a
m1
x
1
+ a
m2
x
2
+ . . . + a
mn
x
n
≤ (=, ≥) b
m
.
Значения b
i
,c
j
,a
ij
- известны (выявленынастадиианализареальнойситуации)
Вматричныхобозначениях
.
...
,
...
,
...
,
...
....
...
...
2
1
2
1
2
1
21
22221
11211
BCXA =
=
=
=
nnnnnnn
n
n
b
b
b
c
c
c
x
x
x
aaa
aaa
aaa
Основные условия, позволяющие строить
модели ЛП
1. Пропорциональность
2. Аддитивность
3. Неотрицательность
Пропорциональность означает, чтозатратыресурсовнанекоторыйвид
деятельности, атакжевкладэтоговидадеятельностивцелевуюфункцию
прямопропорциональныегоуровню (объему).
Аддитивность указывает на то, что общая величина ресурсов,
потребляемыхвсистемевсемивидамидеятельности, равнасуммезатрат
ресурсовнаотдельныевидыдеятельности. Аналогичноинтерпретируетсяи
целеваяфункция.
Предположенияопропорциональностииаддитивностиобеспечивают
строгуюлинейностьсоответствующихфункций (ограниченийицелевой).
Неотрицательность
означает,
что
ни
одному
из
видов
деятельности
не
.0 ,0 , ≥≥−=
−+−+
iiiii
xxxxx
Каноническая и стандартная формы задач ЛП.
Переход от одной формы к другой
КаноническаяформазадачиЛП:
Z=c
1
x
1
+c
2
x
2
+...+c
n
x
n
→min(max)
приусловиях:
x
1
≥ 0,x
2
≥0,...,x
n
≥0,
a
11
x
1
+a
12
x
2
+...+a
1n
x
n
=b
1
,
a
21
x
1
+a
22
x
2
+...+a
2n
x
n
=b
2
,
. . . .. . .. . .
a
m1
x
1
+a
m2
x
2
+...+a
mn
x
n
=b
m
.
СтандартныеформызадачиЛП:
Z=C
T
⋅X → max, Z=C
T
⋅X → min,
A⋅X ≤ B, A⋅X ≥ B,
X ≥ 0. X ≥ 0.
ФормызадачиЛПэквивалентны, т.е. каждаяизнихможетбытьприведенак
Графический метод решения задач ЛП
Графическийметодоснованнагеометрическойинтерпретациизадачи
ЛП и применяется в основном при решении задач в двухмерном
пространстве.
РассмотримзадачуЛП:
z =c
1
x
1
+c
2
x
2
→min
приограничениях
Каждоенеравенство a
i2
x
1
+a
i2
x
2
≤b
i
определяетвплоскости X
1
ОX
2
полуплоскостьсграничнойпрямой a
i2
x
1
+a
i2
x
2
=b
i
.Точки, лежащиев
полуплоскости, удовлетворяютданномунеравенству.
Неравенства x
1
≥0 и x
2
≥0 определяютпервыйквадрантвсистеме
координат
.
ax ax b
ax ax b
ax ax b
x
x
111 12 2 1
211 22 2 2
311 32 2 3
1
2
0
0
+ ≤
+ ≤
+ ≤
≥
≥
,
,
,
,
.
Многоугольникрешенийможетбытьнеограниченнойобластьюили
вырождатьсявпрямую (луч, отрезок) иливточку.
Еслиобластьдопустимыхрешенийпустая, тосистемаограничений
несовместна.
ХарактерныечертызадачЛП:
1. Допустимаяобластьвсегдаявляетсявыпуклыммногогранникомдаже
вслучае, когдаонанеограничена
2. Оптимальноерешениевсегдадостигаетсяввершинахдопустимой
области
3. Еслиоптимальноерешениенеодно, тозначениефункциисовпадает
вовсехточках-решениях
Задача использования сырья
Z=50x
1
+40x
2
→max
x
1
≥0, x
2
≥0.
≤+
≤+
≤
+
,xx
,xx
,xx
21
21
21
3065
4058
2052