методичкаМОСС

(1.6)

есть отрицательно определенная квадратичная форма, функция f имеет в точке а максимум, если d 2 f есть положительно определенная квадратичная форма, то функция f имеет в точке а минимум. Если квадратичная форма не определена, экстремума в точке а нет.

В свою очередь, квадратичная форма является положительно определенной, если все

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

(1.7)

Пример 1.4. Найти экстремумы функции двух переменных

z = 3x3 - x+ y3 - 3y2 - 1.

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

Решение системы: ;

Координаты четырех стационарных точек приведены в табл.2.

									Таблица 2
Координаты стационарной точки				Номер стационарной точки j
		1		2		3			4
xj
yj		0		0		2			2

11

Для анализа достаточных условий оптимальности находим вторые производные от целевой функции:

Уравнение для отыскания собственных значений матрицы вторых производных в соответствии с (1.7) выглядит так:

(1.8)

Результаты решения уравнения (1.8) для каждой из стационарных точек и определяемые ими характеристики экстремумов приведены в табл. 3.

Таблица 3

Параметр

Номер стационарной точки, j

1

2

3

4

Собственые

6

–6

6

6

значения

–6

–6

6

–6

Характер extr

extr нет

max

min

extr нет

1.2 Условная оптимизация

1.2.1. Правило множителей Лагранжа

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

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

f (x) = f (x1, x2, ..., xn) extr,

(1.9)

i (x) = i(x1, x2, ..., xn) = 0,

, m < n.

(1.10)

Необходимые условия локальной оптимальности для этой задачи известны как правило множителей Лагранжа и формулируются по отношению к функции Лагранжа

(1.11)

12

(где j – множители Лагранжа), а именно: если x* – локальное решение задачи (1.9), (1.10), то существует вектор такой, что

,

(1.12)

где – вектор производных от функции Лагранжа по компонентам вектора х.

Любая точка x*, удовлетворяющая при некотором * условиям (1.12), а также условиям допустимости (1.10), называется стационарной точкой задачи (1.9), (1.10). Как и в случае безусловной задачи оптимизации, стационарные точки не обязаны быть решениями задачи (1.9), (1.10). Здесь также существуют достаточные условия оптимальности с привлечением вторых производных.

1.2.2. Достаточные условия оптимальности

Если функции f, 1, 2,..., m дважды дифференцируемы в допустимой точке x* Rn(удовлетворяющей системе (1.10)) и при некотором * выполняются условия (1.12), а также условия

(

)>0 или (

)<0

(1.13)

при всех ненулевых h Rn, удовлетворяющих условиям

,

,

(1.14)

то x* – строгий локальный минимум (максимум) задачи (1.9), (1.10).

В условиях (1.13)

(1.15)

– матрица вторых производных функции Лагранжа по координатам вектора х.

Пример 1.5. Найти локальные решения задачи

	(1.16)
.	(1.17)

Последовательность решения следующая:

13

1) формируем функцию Лагранжа

;

(1.18)

2) находим вектор первых производных функции Лагранжа

; (1.19)

3) формируем систему уравнений для отыскания координат стационарных точек

(1.20)

4) решаем систему (1.20); результаты приведены в табл. 4;

Таблица 4

Координаты		Номер стационарной
стационаной
				точки, j
точки
	1		2		3
x1j	0		1
x2j	1		0
j

5) находим матрицу вторых производных функции Лагранжа

(1.21)

Для стационарных точек 1–3 эта матрица принимает соответственно следующий вид:

14

,

,

;

(1.22)

б) находим вектор h, уравнение (1.14) в данном случае выглядит так: .

Результаты его решения приведены в табл. 5.

Таблица 5

		Номер стационарной
Значения компонентов
			точки, j
вектора h
	1	2		3
h1j	0	=0		0
h2j	=0	0
	(ah11, 0)	(0,bh22)		(-ah13, -bh23)

7)находим произведение матрицы на вектор h (см. третью строку табл. 1.5). Это вектор, r-й компонент которого равен скалярному произведению r-й строки матрицы на вектор-сомножитель;

8)находим скалярное произведение векторов и h для выяснения смысла условия

(1.13):

Таким образом, в первой и второй стационарной точке достигается локальный минимум, а в третьей – локальный максимум.

Контрольное задание

Тип и формулировка задачи для контрольной работы выбираются из табл. 6 в соответствии со значением предпоследней цифры номера зачетной книжки студента, конкретные виды функций (для цифр 2, 3 и 5), а также значения параметров целевых

15

функций и ограничений – по последней цифре номера зачетной книжки из табл. 8. Исходные данные для решения задачи Л. Клейнрока выбираются из табл. 7.

Таблица 6

Предпоследняя				Формулировка задачи
цифра номера		Тип
зачетной		задачи
книжки

0

1

2

3

4

5

6

7

8

9

f(x) = xn - xm

f(x, y) = m1x3 - x + m2y3 - y2 - 1

Безусловная

оптимизация Найти экстремум унимодальной функции методом

золотого сечения (по алгоритму 1)

Найти экстремум унимодальной функции мето дом

чисел Фибоначчи (по алгоритму 2)

Решить задачу распределения пропускных способностей Л. Клейнрока (см. пример 2 в разд. “Справочная информация”):

, x2 + y2 = r2

Условная

оптимизация

,

,

,

,

16

Таблица 7

Параметр				Номер канала связи, j
		1		2		3		4		5		6		7
j		2,5		11,1		6,7		13,0		15,3		4,8		5,9
S j		9,5		8,2		8,8		1,8		3,2		5,9		5,3
					;								.

Дополнительные указания следующие:

1.При решении задач (кроме задач отыскания экстремума унимодальной функции) предусмотреть выполнение следующих этапов:

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

1.2.Из полученного уравнения (системы уравнений) найти координаты стационарных точек. Присоединить к ним для задач по пункту 0 (номер пункта – предпоследняя цифра номера зачетной книжки) координаты граничных точек.

1.3.Исследовать наличие и характер (min или max) экстремума в каждой из стационарных точек. Для этого воспользоваться достаточными условиями оптимальности. Для граничных точек использовать такое правило:

1.4.Для задач по пп. 2, 3 и 4 произвести необходимые расчеты. Их можно выполнить вручную или на ПЭВМ. В последнем случае в отчет по контрольному заданию необходимо включить листинг разработанной студентом программы. Программа может быть написана на любом доступном студенту алгоритмическом языке.

2.В задаче по п. 7 обратить внимание на то, что неизвестными считаются не только

величины x j, , но и значение n. Рекомендуется первоначально зафиксировать n и определить условно оптимальные значения x j, которые окажутся зависящими от n. Далее необходимо подставить полученные значения x j в выражение для целевой функции и решить задачу на экстремум (максимум) ее по n. Полученное оптимальное значение n подставить в выражения для x1. Этим решение задачи завершается

17

Таблица 8

Предпоследняя цифра номера зачетной книжки

0

1

2 и 3

4

5

6

7

8

9

Параметр

n

m

[a,b]

m1

1

m2

2

функция

[a,b]

тип extr

S0

F(xy)

m

m

m

n

Последняя цифра номера зачетной книжки

0		1		2		3			4					5				6		7		8				9
2		3		4		5			6					7				8		9		10			11
2		3		2		5			3					7				4		9		5			11
1		1		2		1			2					1				2		1		2				1
[0,2]		[-2,2]		[-2,2]		[-2,2]		[-2,2]					[-2,2]					[-2,2]		[-2,2]		[-2,2]		[-2,2]
4/3		4/3		1		1/3		16						1				25		36		49			64
1		1		3		4			3					1				3		3		3				3
1		1		1/3		1/3		2/3						2				5		2		2				2
3/2		3/2		1/2		2			1					3				4		6		9			12
						sin x		cos x										x2-2x		x sin x		x( -
																						2x)2
[-1,1]		[0,1]		[0,1]		[0, ]							[-1,1]					[0,2]						[-2,2]
0,010		0,005		0,005		0,005		0,005					0,200					0,010		0,010		0,030		0,010
max		max		min		max		min					min					min		max		max		max
1,3 .		1,5 .		1,7 .		2 .		2,2	.	10	5		2,5	.	10	5		2,7 .		2,8 .		2,9 .		3	.	10	5
105		105		105		105												105		105		105
xy		exp(xy)		(xy)2		(xy)3		(xy)4					(xy)5					(xy)6		(xy)7		(xy)8		(xy)9
1		2		3		4			5					6				7		8		9			10
1		2		3		4			5					6				7		8		9			10
2		3		4		5			6					7				8		9		10			11
2		4		6		8		10					12					14		16		18			20

18

3.При решении задач по пп. 2 и 3 пользоваться только алгоритмами 1 и 2. Необходимые и достаточные условия оптимальности не использовать.

4.При решении задач условной оптимизации (пп. 4–9) выполнению всех этапов предшествует формирование функции Лагранжа. На последующих этапах (пп. 1.1–1.3) вместо целевой функции использовать функцию Лагранжа.

Тема 2. Неклассическая оптимизация (математическое программирование)

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

Общая задача математического программирования формулируется так:
f (x) extr,	(2.1)
	(2.2)
x0.	(2.3)

Если целевая функция f(x) и функция ограничений i (x) линейны относительно компонентов вектора x = (x1, x2, ...,xn) то задачу относят к линейному программированию, наиболее изученному и освещенному в литературе. Подавляющее большинство задач, возникающих при оптимизации сетей связи, относится к другим классам, в частности, к выпуклому программированию. Для отыскания максимума – это задачи, в которых целевая функция f(x) вогнута, а функции ограничений i (x) образуют выпуклое множество, т.е. прямая, соединяющая любые две точки множества, целиком ему принадлежит. Для задач на минимум функция f(x) должна быть выпуклой. Установить характер функции f(x) можно, используя два следующих утверждения.

1. Функция многих переменных

(2.4)

вогнута, если вогнута каждая из функций f j(x j), .

2. Функция одной переменной f(x) вогнута, если

f'' (x) < 0

(2.5)

для всех допустимых значений х.

19

Необходимые условия оптимальности решения задачи (2.1)–(2.3) дает основная теорема математического программирования (ОТМП): для того чтобы х был оптимальным вектором (решением) задачи (2.1)–(2.3) на максимум, необходимо существование вектора

m такого, что

Ф'x(x, ) 0	, x 0,	(2.6)
,	, 0,	(2.7)

где

(2.8)

– функция Лагранжа; i – неопределенные множители Лагранжа.

Для задачи на минимум знаки неравенств для производных от функции Лагранжа в соотношениях (2.6) и (2.7) меняются на противоположные.

Для задач выпуклого программирования необходимые условия (2.6) и (2.7) являются также и достаточными. В связи с этим любой найденный с помощью ОТМП локальный экстремум является в данном случае и глобальным экстремумом задачи.

2.2. Распределение однотипных каналов по направлениям связи

Простейшей является следующая оптимизационная задача. В cети имеется n направлений связи. Каждое направление характеризуется своей относительной важностью v j (как

правило, величины v j нормированы, т.е. ) и надежностью w j функционирования одного канала. В распоряжении оператора имеется N каналов, которые необходимо так распределить по направлениям, чтобы обеспечить наилучшее в определенном смысле функционирование сети.

Эффективность использования сети на j-м направлении определяется величиной
W j(x j) = 1 - (1 - w j)x j,	(2.9)
где x j – количество каналов, выделяемых на j-е направление.

Общая эффективность сети может быть охарактеризована математическим ожиданием числа надежно функционирующих направлений связи с учетом их важности:

. (2.10)

Математическая формулировка задачи следующая:

20