METODY_REShENIYa_ZNLP

Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Томский Государственный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

, j 1, k }.

, j 1, k }.

.pdf

Скачиваний:

Добавлен:

30.05.2015

Размер:

1.12 Mб

Скачать

☆

1 / 61 2 3 4 5 6 > Следующая >>>

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

В.И. Рюмкин

МЕТОДЫ РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Томск

2007

УДК 519.6

Рюмкин В.И. Методы решения задач нелинейного программирования: Учебное пособие. – Томск: ТГУ, 2006. – 56 с.

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

Учебное пособие разработано для студентов экономического факультета дневной и вечерней форм обучения ТГУ и студентов Высшей школы бизнеса ТГУ.

УДК 519.6

Рецензент – профессор С.Н. Колупаева

ВВЕДЕНИЕ

Задачи прикладной математики имеют дело с математическими моделями объектов или процессов. Математической моделью называются формальные математические соотношения, устанавливающие связь принятого критерия эффективности с действующими факторами модели. Решением задачи, связанной с выбранной математической моделью, называется конкретный набор значений кон-

тролируемых параметров. Задачей математического программиро-

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

Критерий эффективности выражается некоторой функцией F , называемой целевой, аргументами которой являются как действующие факторы c1 , c2 , , так и элементы решения x1, x2 , :

F f (c1, c2 , , x1, x2 , ) .

Тогда задача математического программирования может быть

представлена в следующей записи:
F	f (c1, c2 , , x1, x2 , ) max(min);
ci Ci , i 1,2, ,			(*)
	X j ,	j 1,2, ,
x j
где множества Ci	и X j	задаются равенствами и неравенствами и

представляют собой множества допустимых значений действую-

щих факторов и элементов решений. В зависимости от вида целевой функции, а также особенностей множеств Ci и X j , задача (*) при-

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

В данном пособии рассматриваются методы решения задач нелинейного программирования. К задачам такого класса относится задача (*), если либо целевая функция f (c1, c2 , , x1, x2 , ) не явля-

ется линейной1, либо множества допустимых значений Ci и X j за-

даются нелинейными равенствами и неравенствами, либо то и другое вместе.

1 Определения линейной и нелинейной функций см. в разделе 1.2

1. ОСНОВЫ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

Задачей математического программирования (ЗМП), или опти-

мизационной задачей, называется любая задача вида
	(1.1)
f (x) max(min) ,	(1.1)

где f (x) – это целевая


	D Rn ,			(1.2)
x
функция,			– вектор аргументов целевой
		x

функции; множество D Rn – область ограничений (область допустимых решений, допустимое множество, множество определения) ЗМП.

Решением, или оптимальным планом ЗМП называется любой та-

кой вектор из области ограничений, который доставляет x D

максимальное (минимальное) значение целевой функции. Решить ЗМП означает найти все ее решения либо установить ее неразрешимость (факт отсутствия решений).

В качестве целевой функции f (x) могут выступать функции,

выражающие собой прибыль, убытки, затраты, производственные функции и т.д.

Универсальных методов решения ЗМП не существует. Можно выделить несколько классов (разновидностей) ЗМП, определяемых

особенностями целевой функции f (x) и допустимого множества

D Rn . Для каждого класса ЗМП применяются соответствующие методы решения.

1.2. Разновидности ЗМП

Приведем в порядке возрастания сложности решения несколько классов ЗМП.

а) ЗМП при отсутствии ограничений.

	(1.3)
f (x) max(min) .

Для задач этого класса область ограничений совпадает со всем векторным пространством ( D Rn ). Решением может служить лю-

бая точка n (ограничений нет, кроме естественного требования x

о принадлежности решения области определения целевой функции).

б) ЗМП с ограничениями-равенствами:

			(1.4)
f (x) max(min);


gi (x) bi , i 1, m .			(1.5)

Для задач этого класса область ограничений определяется как

множество решений системы уравнений:
	Rn : g

D {x		(x) b , i 1, m} .
	i		i
в) ЗМП с ограничениями-неравенствами:
				(1.6)
	f (x) max(min);			(1.6)


	hj (x) j , j 1, k .			(1.7)

Для задач этого класса область ограничений определяется как множество решений системы неравенств:

г) ЗМП со смешанными ограничениями (ограничениями сме-

шанного типа):
		max(min);	(1.8)
f (x)		max(min);	(1.8)
g

	(x) b , i 1, m,
i		i	(1.9)
			(1.9)
h j	(x) j , j 1, k,

когда область ограничений представляется совокупностью уравне-

ний и неравенств:

, j

1,k } .

D {x Rn : g

(x) b , i 1,m; h

(x)

называется линейной функцией, если она может

Функция (x)

быть представлена в виде (x) c x

x c x cT x ,

1 1

где c1, c2 , , cn , заданные

числовые

константы.

В противном

случае функция (x) называется нелинейной.

ЗМП называется задачей

линейного

программирования (ЗЛП),

если целевая функции f (x) и все функции ограничений являются

линейными функциями. В противном случае ЗМП называется зада-

чей нелинейного программирования (ЗНЛП).

1.3. Базовые понятия и терминология математического программирования

Множество D Rn

называется ограниченным множеством, ес-

между любыми двумя его точками

ли расстояние (x, y)

x, y

меньше некоторого числа l :

max

l .

max (x, y)

max | x y |

x, y D

i 1

называется множе-

Эпсилон-окрестностью O (z) точки

ство точек, отстоящих от точки

z на расстоянии меньшем, чем :

O (z) {x

Rn : (x, z)

| x

z |

i 1

Точка

называется

предельной

точкой

множества

z Rn

D Rn ,

если существует последовательность принадлежащих D

точек xn

, сходящаяся к

z , то есть если выполняется условие

0 N : n N xn O (z) D lim xn z .

(1.10)

Множество

D Rn

называется замкнутым множеством,

если

оно содержит все свои предельные точки.

Множество

D Rn

называется компактным множеством,

если

оно ограничено и замкнуто.

D называется внутренней точкой множества D ,

если

Точка x

существует 0 такое, что

O (x) D . В противном случае точка

D .

x D называется граничной точкой множества

D называется точкой условного локального максимума

Точка z

(локального минимума) функции

D , если существу-

f (x) в области

D из этой

ет окрестность

O (z)

такая, что для любой точки

окрестности значение

f (x) не больше (не меньше), чем f (z) :

x O

(z) D

f (x)

f (z)

( f (x) f (z)

для минимума).

(1.11)

D называется точкой условного глобального максиму-

Точка z

в области

D , если зна-

ма (глобального минимума) функции f (x)

не меньше (не больше), чем

D :

чение f (z)

f (x)

для любого x

f (x)

f (z)

( f (x)

f (z) для минимума).

имеет в точке

Говорят, что функция f (x)

z D условный ло-

кальный (глобальный) экстремум на множестве D , если точка

z D является точкой локального (глобального) максимума или минимума.

Говорят, что функция		имеет в точке		Rn локальный
	f (x)		z
(глобальный) безусловный экстремум, если точка				является точкой
			z

локального (глобального) максимума или минимума на всем про-

странстве Rn .
Говорят, что функция		дифференцируема в точке		Rn ,
	f (x)		z

если в этой точке существуют все ее частные производные первого

порядка
					f (z1, z2 , , z j 1, z j		j , z j 1, , zn ) f (z1, z2 , , zn )
	f (z)			lim				.
	x						j
		j		j 0

	Говорят, что функция						непрерывно дифференцируема в
						f (x)
точке			Rn , если все ее частные производные первого порядка не-
		z
прерывны в этой точке.
	Точка
				z Rn , в которой равны нулю все частные производные
первого порядка функции
						f (x) , называется стационарной точкой
этой функции.
	Точка
				z Rn называется седловой точкой (седлом) функции

f (x) , если она является стационарной точкой, но не является точ-
кой безусловного экстремума.
	Говорят, что функция
						f (x) дважды дифференцируема в точке

	Rn , если в этой точке существуют все ее частные производные
z
второго порядка

	2
		f (z)			f (z)
x x				x	x		, i, j 1, n .
			j			j
		i		i

Замечание 1.1. Значение частной производной второго порядка не зависит от порядка дифференцирования по переменным, то есть


	2 f (z)			2 f (z)
	2 f (z)			2 f (z)			, i, j 1, n .
	x x		j	x	j	x	, i, j 1, n .
	x x			x		x
	i					i

Квадратная матрица		H (z) (hij (z)) , элементы которой опреде-

ляются значениями частных производных второго порядка функции

		Rn , то есть
f (x) в точке	z	Rn , то есть

2 f (z)

hij (z)

xi x j

называется матрицей Гессе функции

f (x) в точке z .

Выражение

где

H (h )

–

G(H , x)

xT Hx

h x x

n n

i 1 j 1

ij i

квадратная

матрица,

Rn , называется

квадратичной формой

матрицы H .

Квадратная матрица

называется положительно (неотрица-

тельно) определенной, если справедливо

(1.12)

x Rn , x 0

G(H, x)

Hx 0

(G(H, x) xT

Hx 0) .

Квадратная матрица

называется отрицательно (неположи-

тельно) определенной, если справедливо

x Rn , x 0 G(H, x) xT Hx 0

(G(H, x) xT Hx 0) . (1.13)

Квадратная матрица H называется неопределенной матрицей, если она не является ни положительно, ни отрицательно определенной.

Квадратная матрица H называется симметрической, если для всех ее элементов справедливо hij hji (симметрия относительно

главной диагонали). Матрица Гессе всегда симметрическая. Установить тип определенности матрицы Гессе в стационарной

точке позволяет следующая теорема.

Теорема об условиях определенности матрицы (критерий Сильвестра). Справедливы следующие утверждения:

1)симметрическая квадратная матрица положительно определена тогда и только тогда, когда значения всех ее главных миноров положительны.

2)симметрическая квадратная матрица отрицательно определена тогда и только тогда, когда знак ее k-го главного минора

определяется знаком ( 1)k .

Пример 1.1. Матрицы 5 ,	1	1	определены положительно;
Пример 1.1. Матрицы 5 ,			определены положительно;
		3
	1	3

матрицы 5 ,	1		1	определены отрицательно.
матрицы 5 ,				определены отрицательно.
		1
		1	3

Функция g(x) называется m-мерной вектор-функцией, если она представляет собой m-мерный вектор, компоненты которого суть

вещественные функции, то есть

(x)

(g (x), g

(x), , g

(x)) .

Матрицей Якоби

назы-

(x)

m-мерной вектор-функции g(x)

m n ,

вается матрица размера

элементы rij (x)

которой определя-

ются формулами

gi (x)

, i 1, m; j

1, n .

rij (x)

x j

Функция

называется выпуклой в области D Rn , если

f (x)

x, y

(1 ) y)

f (x) (1 ) f ( y) , [0, 1] .

Функция

называется вогнутой в области D , если

f (x)

x, y

(1 ) y)

f (x) (1 ) f ( y) , [0, 1] .

является вогнутой в области D ,

Замечание 1.2. Функция f (x)

если функция

выпукла в этой области.

g(x) f (x)

Свойства выпуклых функций

1. Сумма выпуклых функций является выпуклой функцией.

2. Если

f (x) выпукла и

0 , то g(x) f (x) тоже выпукла.

3. Если

выпукла и

f (x)

0 , то h(x) f (x) вогнута.

1.4. Производная по направлению. Градиент

Rn произвольный вектор единичной длины, то есть

Пусть u

функции

| u | 1 . Производной

f (x)

в точке y

по направлению u

называется предел

f ( y)

lim

f ( y

tu)

f ( y)

t 0

По сути

f ( y)

это скорость изменения значения функции

f (x)

в точке y при перемещении аргумента в направлении вектора u .

Градиентом функции		в точке		называется вектор
	f (x)		y		f ( y) ,

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

данной функции в точке y :

T f ( y)

f ( y) ;x


f ( y)		f ( y)
	;		.
	;		.
x2		xn
x2		xn

Теорема о производной по направлению. Производная функ-

						может быть найдена по
ции f (x)	в точке y по направлению				u	может быть найдена по
формуле

	f ( y)	n f ( y)		u j T
			x j	u j T		f ( y) u .			(1.14)
	u	j 1	x j
									указыва-
Теорема о градиенте. Градиент f ( y) функции f (x)									указыва-
ет направление наискорейшего роста функции
ет направление наискорейшего роста функции							f (x)	в точке y .

При этом максимальная скорость роста равна модулю градиента в

этой точке:

		f ( y)
	max		\| f ( y) \| .	(1.15)
u R n : \|u\| 1		u

Пример 1.2. Найти производную функции								x5 x6				в точке
Пример 1.2. Найти производную функции						f (x)		x5 x6				в точке
										1	2
					2).
yT (1; 1) по направлению вектора			vT (3;		2).

										v
Решение. Вектор v	задает единичный вектор						u					того же
									\| v \|
	1	3	1	3			1				3
направления. Имеем u


				2
	\| v \|	2	9 4	2			13				2 .

Градиент				в	произвольной				точке		равен
Градиент			f (x)	в	произвольной				точке	x	равен
	5x4 x6					5
f (x)	1	2	, поэтому f ( y)				. Подставляя найденные зна-
	5	5
	6x1 x2					6
чения компонент f ( y) и u в (1.14), получаем
					3		2	3
			f ( y)	5	3	6	2	3
									.
									.
			u		13		13	13

1.5. Касательные гиперплоскости и нормали

1 / 61 2 3 4 5 6 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
08.11.20195.83 Mб5Material.doc
#
30.05.20151.46 Mб9math_2012_abiturienti-i_varianti_rus.pdf
#
26.11.2019358.4 Кб2metodichka ХИСТОРИ.doc
#
30.05.2015427.01 Кб126metodichka1.doc
#
08.05.2019171.52 Кб4metodizka po praktike.doc
#
30.05.20151.12 Mб15METODY_REShENIYa_ZNLP.pdf
#
24.12.2018192.82 Кб3Mezhdunarodnoe_chastnoe_pravo.docx
#
31.07.201943.16 Кб2Mezhdunarodnoe_pravo.docx
#
15.11.2019253.6 Кб9Mezhdunarodnoe_publichnoe_pravo_Barnashov_Alexa...docx
#
09.09.201969.63 Кб1MEZhDUNARODN_J_KODEKS.doc
#
30.05.2015494.08 Кб12MIKROSOTsIOLOGIYa_-_2009_Kurs_lektsy_doc.doc