Презентация - Семенкин Е.С. Методы оптимизации
Подождите немного. Документ загружается.
1. БандиБ.Методыоптимизации. Вводныйкурс.-М.: Радиоисвязь,1988.-128 с.
2. БандиБ.Основылинейногопрограммирования.-М.: Радиоисвязь,1989.-176 с.
3. ХиммельблауД.Прикладноенелинейноепрограммирование.-М.: Мир,1975.-
534 с.
4. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое
программирование.-М.: Высшаяшкола,1976.-352 с.
5. Мышкис А.Д. Математика для ВТУЗов. Специальные курсы – СПб.:
Издательство «Лань», 2002.
6. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф.
Математическаятеорияоптимальныхпроцессов.–Издательство «Наука» гл. ред.
физико-математическойлитературы,3изд.,1976г.
7. ИнтриллигаторМ.Математическиеметодыоптимизациииэкономическая
теория.–М.: Айрис-Пресс,2002.–576 с.
Литература
F(X) →
F={f
1
,f
2
,...,f
k
}-оптимизируемаяфункция (целеваяфункция, целевой
функционал, критерий качества и т.п.), численно выражает степень
достиженияцелейфункционированияоптимизируемогообъекта.
X=(x
1
,x
2
,...,x
n
)
T
-векторнезависимыхпеременных, егокомпоненты -
неизвестныезадачиоптимизации (переменныеоптимизации)-являются
управляемыми входамиобъектаоптимизации.
D - множество допустимых значений неизвестных, определяемое
налагаемыми на неизвестные ограничениями (допустимая область,
допустимоемножество).
S-пространствооптимизации.
minF(X)=-max(-F(X))
F ={f
1
,f
2
,..., f
k
}
k=1-задача однокритериальной или скалярной оптимизации,
k>1-задача многокритериальной или векторной оптимизации.
o
p
t
XDS
∈⊆
Классификация задач оптимизации
F(X) →
X =(x
1
,x
2
,...,x
n
)
T
n=1-задача одномерной (иногда - линейной) оптимизации,
n>1-задача многомерной оптимизацииили задача оптимизациисо
многимипеременными.
o
p
t
XDS
∈⊆
Допустимаяобласть
D=S -задача безусловной оптимизацииили задача оптимизации без
ограничений (какие-либоограничениянанеизвестныеотсутствуют).
D ⊂ S-задача условной оптимизацииили задачасограничениями (т.е. в
задаченевсезначенияпеременныхдопустимы).
Пространствооптимизации
S=R
n
-задача оптимизации снепрерывнымипеременными.
S=Z
n
-задача целочисленнойоптимизации.
S = B
n
- задача булевой оптимизация (частный случай задачи
целочисленнойоптимизации, прикоторойпеременныемогутпринимать
толькодвазначения - нольиединица). Еслиприэтом f(X) принимаетзначения
из R
n
, то - задача псевдобулевойоптимизации.
Еслизначениецелевойфункциизависитотнекоторыхкомбинаций
объектовизконечногонабора, ихразмещенияилиспособаупорядочения, то
такиезадачиназываютсязадачами комбинаторнойоптимизации.
Задачицелочисленнойикомбинаторнойоптимизацииобъединяются
понятиемзадач дискретнойоптимизации.
Взадачах смешаннойоптимизации могутодновременноприсутствовать
переменныенесколькихилидажевсехтипов (наиболееизвестныйчастный
случай - задачи смешанного целочисленного программирования с
целочисленнымиинепрерывнымипеременными).
Целеваяфункцияимеетболееодноголокальногоэкстремума - задача
глобальной или многоэкстремальной оптимизации (еслитребуетсянайтивсе
локальныеэкстремумыилинаилучшийизних).
Взадачах локальной оптимизациитребуетсянайтиодинлокальный
экстремум (единственныйдляодноэкстремальнойцелевойфункцииили
любойдлямногоэкстремальной).
Свойства функций, входящих в постановку задачи оптимизации
Целеваяфункцияи/илифункции, описывающиеограничения, заданыне
аналитически (ввидекомпьютерныхпрограмм, имитационныхмоделей,
человеко-машинныхпроцедуриликаквыходреальнойсистемы)-задачи
оптимизацииснеявнымифункциями (поисковыезадачиоптимизации)
Всефункции, входящиевпостановкузадачи, записываютсявявном
аналитическомвиде - задача математическогопрограммирования
Общаяформулировказадачиматематическогопрограммирования:
f(X) → ,
приограничениях
h
i
(X)=0, i =1,...,m,
g
i
(X) ≥ 0, i =m+1,...,p.
Все функции, входящие в постановку, являются непрерывно
дифференцируемыми - задача дифференцируемой оптимизации, иначе –
задача недифференцируемойоптимизации
m
n
X
i
(
max
)
Целеваяфункциявыпукла, функции-ограниченияобразуютвыпуклую
допустимуюобласть - задача выпуклойоптимизации
Целевая функция сепарабельна, ограничения линейны - задача
сепарабельногопрограммирования
Целевая функция квадратичная, ограничения – линейны - задача
квадратичногопрограммирования
Всефункцииобщеговида - общаязадача нелинейногопрограммирования
Целевая функция и функции-ограничения являются линейными
относительнонезависимыхпеременных - задача линейногопрограммирования
Более узкие постановки задачи линейного программирования -
транспортная задача, задача оназначениях, задача целочисленноголинейного
программирования ит.п.
Задачаиспользованиясырья. ДляиспользованиядвухвидовпродукцииР1и
Р2используюттривидасырья S1,S2 и S3. Запасысырьявколичествоединиц
сырья, затрачиваемыхнаизготовлениеединицыпродукции, иприбыльотединицы
продукцииприведенывтаблице. Необходимосоставитьпланвыпускапродукции,
максимизирующийприбыль.
Примеры задач ЛП
x
1
≥ 0,x
2
≥0,
z=50⋅x
1
+40⋅x
2
→ max.
2 5 20
8 5 40
5 6 30
1 2
1 2
1 2
x x
x x
x x
+ ≤
+ ≤
+ ≤
,
,
,
Вид сырья Запасы Затраты сырья
Р1 Р2
S1 20 2 5
S2 40 8 5
S3 30 5 6
Прибыль от единицы
продукции
50 40
Задачасоставлениярациона ("оптимальнойсмеси"). Приоткормекаждое
животноеежедневнодолжнополучатьнеменее 9 единицпитательноговещества S1,
неменее 8 единицвещества S2 инеменее 12 единицвещества S3. длясоставления
рационаиспользуютдвавидакорма. Содержаниеколичестваединицпитательных
веществв1кгкормаприведенывтаблице. Необходимосоставитьдневнойрацион
нужнойпитательности, причемзатратынанегодолжныбытьминимальными.
Вещества
Кол-во ед. питат. веществв 1 кг
корм 1 корм 2
S1 3 1
S2 1 2
S3 1 6
Стоимость 1 кг корма 4 6
x
1
≥ 0,x
2
≥0.
≥+
≥+
≥+
,126
,82
,93
21
21
21
xx
xx
xx
Z=4x
1
+6x
2
→ min,
ОбщийвидзадачиЛП:
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
- известны (выявленынастадиианализареальнойситуации)
Вматричныхобозначениях
ЗадачаЛПзаписываетсяввиде:
z =C
T
⋅X→min(max),
приусловиях:
X ≥ 0,
A⋅X ≤ (=, ≥) B.
.
...
,
...
,
...
,
...
....
...
...
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
Параметрическиезадачиоптимизации (параметрическоепрограммирование)-
функцииикоэффициенты, входящиевпостановкузадачизависятотнекоторого
параметраилипараметров
Вся исходная информация задачи оптимизации определена однозначно –
детерминированныезадачиоптимизации
Всеилинекоторыепараметрымоделиносятвероятностныйхарактер - принятие
решения в условиях риска (стохастические задачи, стохастическое
программирование, стохастическаяаппроксимация)
Неопределенностьданныхимеетневероятностныйхарактер - оптимизацияв
условиях неопределенности (нечеткое математическое программирование или
нечеткаяоптимизация)
Конечномерные (матпрограммирование) и бесконечномерные
(вариационноеисчисление)
Наплоскости xOy даныдветочкиА
1
(x
1
,y
1
)иА
2
(x
2
,y
2
). Найтикривуюкратчайшей
длины, соединяющуюэтиточки.
y(x
1
) = y
1
, y(x
2
) = y
2
.
dxyS
x
x
∫
′
+=
2
1
2
1