Общая постановка задачи оптимизации

Общая постановка задачи оптимизации

f(x) ! min; x 2 X Rⁿ

f(x) целевая функция

X допустимое множество

в частном случае может быть X = Rⁿ

ИО Однокритериальная оптимизация 2

Виды однокритериальных оптимизационных задач

Задачи безусловной оптимизации.

Задачи условной оптимизации:

классическая задача условной оптимизации

(с ограничениями типа равенств);

задача математического программирования

(с ограничениями типа равенств и неравенств).

ИО Однокритериальная оптимизация 3

Безусловная оптимизация
f(x) ! min; x 2 Rn

Теорема Ферма (необходимое условие минимума)

Пусть функция f(x) дифференцируема в точке x 2 Rⁿ. Если x локальное решение задачи безусловной оптимизации (локальный минимум), то f⁰(x ) = 0.

Теорема (необходимые и достаточные условия минимума)

Пусть функция f(x) дважды дифференцируема в точке

x 2 Rⁿ и f⁰(x ) = 0. Чтобы x был (локальным) решением задачи безусловной оптимизации необходимо f⁰⁰(x ) 0 и достаточно f⁰⁰(x ) 0.

ИО Однокритериальная оптимизация 4

Обобщение понятия производной для x 2 Rⁿ

Вектор первых частных производных (градиент):

				2	@f(x)			3
	df(x)						@x
				6		@x1		7
						@f(x)
f0(x) =			=		...2
	dx
				6	@f(x)			7
				6				7
				6		@xn		7
				4				5

Матрица вторых частных производных (гессиан):

					2				@2f(x)
	2f(x)							@2f(1x)
					6				@x2
	d
f00(x) =			=					@x2..@x1
	dx2
					6	.
					6				@2f(x)
					6
					6	@xn@x1
					4

@²f(x)

@x₁@x₂ @²f(x)

@x²₂

^.._.

• ²f(x) @x_n@x₂

^.._.

@²f(x)

@x₁@x_n @²f(x)

@x₂@x_n

^.._.

• ²f(x) @x²_n

3

7

7

7

7

7

5

ИО Однокритериальная оптимизация 5

Неотрицательно (положительно) определённая матрица

Матрица A 2 R^{n n} называется неотрицательно (положительно) определённой (будем обозначать A 0 и A 0 соответственно) если h^T Ah 0 (h^T Ah 0) 8h 2 Rⁿ; n 6= 0.

Критерий Сильвестра

Симметричная матрица неотрицательно (положительно) определена тогда и только тогда, когда все её главные (угловые) миноры неотрицательны (положительны).

Для двумерных задач

Чтобы матрица A 2 R^{2 2} была неотрицательно (положительно) определена её диагональные элементы (элемент a₁₁) и определитель jAj должны быть неотрицательны (положительны).

ИО Однокритериальная оптимизация 6

Постановка задачи условной оптимизации

f(x) ! min; x 2 X Rⁿ; X 6= Rⁿ

Если x внутренняя точка множества X, то решение задачи условной минимизации совпадает с решением задачи безусловной минимизации.

В противном случае решение достигается на границе множества X.

ИО Однокритериальная оптимизация 7

Классическая задача условной оптимизации

f(x) ! min; x 2 X = fx 2 Rⁿjg_j(x) = 0; j = 1; : : : ; mg

или

f(x) ! min; g_j(x) = 0; j = 1; : : : ; m

ИО Однокритериальная оптимизация 8

Функция Лагранжа

Позволяет свести классическую задачу условной оптимизации

• задаче безусловной оптимизации. Обобщённая функция Лагранжа

L(x; ₀; ) = ₀f(x) + g(x)

где x 2 Rⁿ, 2 R^m, ( ₀; ) вектор множителей Лагранжа.

m

X

L(x; ₀; ) = ₀f(x) + _jg_j(x)

j=1

ИО Однокритериальная оптимизация 9

Условие регулярности

Для поиска экстремума приравняем к нулю производную функции Лагранжа:

		m
		Xj
L0	(x; 0; ) = 0f0	(x) +jgj0(x) = 0
		=1

Условие регулярности

Градиенты функций-ограничений g⁰(x) должны быть линейно независимы в точке минимума x :

m

X

_jg_j⁰(x ) 6= 0

j=1

ИО Однокритериальная оптимизация 10

Выполнение условия регулярности

Если условие регулярности не выполнено:

₀ = 0.

Если условие регулярности выполнено:

₀ 6= 0 и вместо обобщённой можно рассматривать классическую функцию Лагранжа.

Классическая функция Лагранжа

m

X

L(x; ) = f(x) + _jg_j(x)

j=1

ИО Однокритериальная оптимизация 11

Метод множителей Лагранжа

Принцип множителей Лагранжа (необходимые условия)

Пусть функции f(x), g_j(x) (j = 1; : : : ; m) дифференцируемы в точке x 2 Rⁿ и непрерывно дифференцируемы в некоторой её окрестности. Если x локальное решение задачи условной оптимизации, то существует ненулевой вектор множителей Лагранжа ( ₀; ) такой, что

L⁰(x ; ₀; ) = 0:

Если при этом градиенты g_j⁰(x ), j = 1; : : : ; m линейно независимы, то ₀ 6= 0.

ИО Однокритериальная оптимизация 12

Необходимые и достаточные условия

Необходимые условия минимума второго порядка Если x регулярная точка минимума, то второй дифференциал функции Лагранжа, вычисленный в

стационарной точке (x ; ) неотрицателен: d²L(x ; ) 0

для всех dx 2 Rⁿ, таких, что dg_j(x ) = 0, j = 1; : : : ; m.

Достаточные условия минимума

Пусть имеется стационарная точка (x ; ). Если в этой точке d²L(x ; ) 0 для всех ненулевых dx 2 Rⁿ таких, что

dg_j(x ) = 0, j = 1; : : : ; m, то точка x является точкой локального минимума.

ИО Однокритериальная оптимизация 13

Формулы вычисления дифференциалов

Второй дифференциал функции Лагранжа

n	n	@2L(x; )
Xi	X			dxidxj
			@xi@xj
d2L(x; ) =
=1 j=1

Первый дифференциал ограничений

n

dg_j(x) = ^{X @gj(x)} dx_i; j = 1; : : : ; m

_i=1 ^@xi

ИО Однокритериальная оптимизация 14

Метод множителей Лагранжа. Алгоритм

Записать обобщённую функцию Лагранжа.

Выписать необходимые условия экстремума первого порядка и дополнить их ограничениями-равенствами.

Решив полученную систему найти стационарные точки, в которых не все _j (j = 1; : : : ; m) равны нулю. При этом проверить условие регулярности и при необходимости рассмотреть два случая:

₀ = 0 (найденные решения нерегулярные);

₀ 6= 0 (в этом случае можно использовать классическую

функцию Лагранжа).

Среди регулярных стационарных точек найти решения или показать, что решений нет.

ИО Однокритериальная оптимизация 15

Постановка задачи математического программирования

Задачи математического программирования являются наиболее общим классом задач условной оптимизации.

x 2 X =	x 2 Rn	f(x) ! min;
		hjj(x) 6 0; j = k + 1; : : : ; m
			g (x) = 0; j = 1; : : : ; k;

Ограничения-неравенства могут быть:

активными (выполняются как равенства); пассивными (выполняются как строгие неравенства).

ИО Однокритериальная оптимизация 16

Задача математического программирования. Пример

f(x) = x2	! min;		x 2 R2;
x1 + x2		= 0;
x12 + x22		6 1;
	x1 x22:
Или:			x 2 R2;
f(x) = x2	! min;

g(x) = x₁ + x₂; (g(x) = 0)

h (x) = x² + x² 1; (h (x) 6 0)

_{1 1 2 1}

ИО Однокритериальная оптимизация 17

Задача математического программирования. График

		x2
		2	h2(x) 6 0
	g(x) = 0
f(x) = 1		1
h1(x) 6 0
f(x) = 0		0
				x1
2		1
1		1	x
f(x) = p	2
		2
ИО		Однокритериальная оптимизация			18

Решение задачи математического программирования

Используется метод множителей Лагранжа

Обобщённая функция Лагранжа

k	m
X	j X
L(x; 0; ; ) = 0f(x) +jgj(x) +	jhj(x)
j=1	=k+1

ИО Однокритериальная оптимизация 19

Необходимые условия минимума первого порядка

Если x локальное решение задачи мат. программирования, то существует ненулевой вектор множителей Лагранжа ( ₀; ; ) такой, что выполняются условия:

стационарности обобщённой функции Лагранжа:

L⁰(x ; ₀; ; ) = 0:

неотрицательности множителей Лагранжа:

_j 0; j = k + 1; : : : ; m:

дополняющей нежёсткости

_j h_j(x ) = 0; j = k + 1; : : : ; m:

Если при этом выполняется условие регулярности, то ₀ 6= 0.

ИО Однокритериальная оптимизация 20

Достаточные условия минимума первого порядка

Пусть имеется точка (x ; ; ), удовлетворяющая условию стационарности функции Лагранжа при ₀ 6= 0, при этом суммарное число активных ограничений-неравенств в этой точке и ограничений-равенств совпадает с числом переменных n.

Если все множители Лагранжа для активных ограничений-неравенств в этой точке положительны, то точка x является точкой условного локального минимума.

ИО Однокритериальная оптимизация 21

Необходимые и достаточные условия второго порядка

Необходимые условия минимума второго порядка

Если x регулярная точка минимума, то d²L(x ; ; ) 0 для всех dx 2 Rⁿ, таких, что dg_j(x ) = 0, j = 1; : : : ; k, а для активных ограничений-неравенств верно dh_j(x ) = 0 при

0 и dh_j(x ) 6 0 при = 0.

Достаточные условия минимума второго порядка

Пусть имеется точка (x ; ; ). Если в этой точке

d²L(x ; ; ) 0 для всех ненулевых dx 2 Rⁿ таких, что dg_j(x ) = 0, j = 1; : : : ; k, а для активных ограничений-неравенств верно dh_j(x ) = 0 при 0 и dh_j(x ) 6 0 при = 0, то точка x является точкой локального минимума.

ИО Однокритериальная оптимизация 22

Замечания по алгоритму решения

Используется метод множителей Лагранжа.

При решении системы, полученной из необходимых условий минимума первого порядка (с учётом ограничений-равенств и ограничений-неравенств), нужно проверить условие регулярности: при необходимости рассмотреть два случая ₀ = 0 и ₀ 6= 0.

Для каждого из этих случаев решение начинается с рассмотрения всех возможных комбинаций нулевых и ненулевых значений , удовлетворяющих условию дополняющей нежёсткости.

Для найденных точек проверить выполнение достаточных условий минимума первого порядка.

Если достаточные условия первого порядка не выполняются, проверить выполнение достаточных условий второго порядка.

ИО Однокритериальная оптимизация 23

Постановка задачи линейного программирования (ЛП)

f(x) ! min;

_{x 2 X = x 2 R}n ^gj^{(x) = 0; j = 1; : : : ; k;}

h_j(x) 6 0; j = k + 1; : : : ; m

При этом f(x), g_j(x) (j = 1; : : : ; k;), h_j(x) (j = k + 1; : : : ; m) линейные функции.

ИО Однокритериальная оптимизация 24

Формы задач линейного программирования

Общая форма задачи ЛП:

n n

X X

c_jx_j ! max; a_ijx_j = b_i; i = 1; : : : ; k;

j=1

j=1

n

Xj

~

a~ijxj 6 bi; i = k + 1; : : : ; m; xj 0; j = 1; : : : ; n

=1

Стандартная форма задачи ЛП:

n

n

Xj

! max;

X

xj 0; j = 1; : : : ; n

cjxj

aijxj 6 bi; i = 1; : : : ; m;

=1

j=1

Каноническая форма задачи ЛП:

n

n

Xj

! max;

X

xj 0; j = 1; : : : ; n

cjxj

aijxj = bi; i = 1; : : : ; m;

=1

j=1

ИО Однокритериальная оптимизация 25

Матричная запись задач линейного программирования

Общая форма задачи ЛП

~ ~

c x ! max; Ax = b; Ax 6 b; x 0:

Стандартная форма задачи ЛП

c x ! max; Ax 6 b; x 0:

Каноническая форма задачи ЛП

c x ! max; Ax = b; x 0:

Все три формы задач эквивалентны в том смысле, что каждую из них можно простыми преобразованиями привести к любой из двух остальных.

ИО Однокритериальная оптимизация 26

Пример задачи ЛП
Решить задачу:	Стандартная форма:
f(x) = x1 2x2 ! min;	f(x) = x1 + 2x2 ! max;
2x1 + x2 2;	2x1 x2 6 2;
x1 + 3x2 3;	x1 3x2 6 3;
x1 x2 1;	x1 + x2 6 1;
3x1 x2 6 6;	3x1 x2 6 6;
x1 + x2 6 5;	x1 + x2 6 5;
x1 0; x2 0:	x1 0; x2 0:

ИО Однокритериальная оптимизация 27

Геометрическая интерпретация задач ЛП

x2
3		h3(x)		h4(x)
h1(x)			x
			f(x) = 4
2	f0	(x)
				h5(x)
h2(x)1
				f(x) = 1:1
0					x1
1	0	1	2	3
1			f(x) = 0
ИО		Однокритериальная оптимизация				28

Графический метод решения задач ЛП. Алгоритм

Построить множество допустимых решений.

Найти градиент целевой функции и изобразить вектор градиента на графике.

Провести одну из линий уровня целевой функции.

Передвигать линию уровня параллельно самой себе до касания с множеством допустимых решений.

Классифицировать точки касания с использованием свойств градиента.

ИО Однокритериальная оптимизация 29

Примеры задач линейного программирования

Задача планирования производства.

Транспортная задача.

Задача о рационе кормления.

ИО Однокритериальная оптимизация 30

Алгоритм построения оптимизационной модели

Выбрать управляемые переменные и ввести для них обозначения.

Составить целевую функцию задачи.

Представить ограничения задачи в виде системы уравнений и неравенств, содержащих выбранные переменные.

ИО Однокритериальная оптимизация 31

Пример задачи

Фабрика производит два вида красок: для наружных и внутренних работ. Для производства красок используются два ингредиента (A и B). Максимально возможные суточные запасы этих ингредиентов составляют 6 и 8 тонн соответственно.

Для производства 1 тонны краски первого вида расходуется 1 тонна ингредиента A и 2 тонны ингредиента B. Для производства 1 тонны краски второго вида расходуется 2 тонны ингредиента A и 1 тонна ингредиента B.

Изучение рынка сбыта показало, что спрос на краску второго вида никогда не превышает 2 тонны в сутки.

Оптовые цены красок: 3000 руб. за 1 тонну краски первого вида, 2000 руб. за 1 тонну краски второго вида.

Составить оптимизационную модель, позволяющую решить задачу максимизации дохода при заданных условиях.

ИО Однокритериальная оптимизация 32