Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

Положим c xT	f (xk )xT .
k
Рассмотрим задачу линейного программирования

			c	k	xT		min
				k
	Обозначим				zk	-	решение			к- той ЗЛП. Тогда направление
lk	zk xk		в исходной задаче							будет подходящим.	Формула
пересчета имеет вид
			xk		1	xk	k	lk ,	,
							k
где шаг		k	ищется по правилу наискорейшего спуска с учетом
		k
условия
			0		k		1
					k
(при	таком		выборе			k	точка		xk 1 будет выпуклой		линейной
комбинацией точек					zk	и xk , что обеспечивает ее допустимость).

В качестве критериев останова алгоритма применяются стандартные критерии:

	\|\|	f (x k 1 ) \|\|			, \|\| x k 1		x k \|\| .
Алгоритм
Шаг 0. Зафиксировать x0						начальное приближение.
	Положить к=0.
Шаг 1.	Решить задачу линейного программирования
	c xT		f (xk )xT			min,
		k
	найти zk . .
Шаг 2.	Зафиксировать вектор lk zk						xk в качестве
	направления поиска.
Шаг 3.	Вычислить
	k	arg min f (xk				l k ).
	k
		0	1
Шаг 4.	Положить
	xk	1 xk	k	lk .
			k

143

Шаг 5. Проверить условия останова и, если они выполнены,

вычисления прекратить и взять точку xk 1 в качестве искомого решения. Иначе положить k=k+1 и перейти на шаг1.

Пример 1. Решить методом линеаризации задачу нелинейного программирования

f (x, y)		(x 4)2 ( y 2)2	min,
x	y 3,
x	2 y	4,

x, y 0.

Решение. Данная задача была графически решена в п.3.2: x*=(5/2,1/2), рис.5.3.1. Для решения задачи методом линеаризации

выберем x0 , например, x0=(0,0). Вычислим

f (x) (2x 8, 2 y 4)

Итерация 1

2	Ω
2

1			x*


				x1

1		2	3

Рисунок 5.3.1. Графическое решение задачи 5.3.1

144

f (x0 ) (	8, 4).	Рассмотрим задачу линейного
программирования
f (x0 )xT	8x	4x	min .
	1	2

Решив еѐ графически, получаем

xmin0	(3,0),		l 0	(3,0) ,	x1 (3	0 , 0),
где
0	arg min		f (3	,0)
0	0	1
	0	1		.
Запишем задачу одномерной оптимизации
(3	4)2	min
0	1.
Решением этой задачи будет				0 1,	тогда x1	xmin0	(3,0).

Итерация 2

f (x1 ) ( 2, 4) .

Рассмотрим задачу

f (x1 )xT 2x1 4x2 min .

Решением этой ЗЛП является отрезок, соединяющий точки

(2,1) и (0,2) (рис.5.3.1).

Выберем одну из них, например, xmin					(2,1). Тогда
l0	(2,1)	(3,0)	( 1,1)
x2	(3	1, 1 ) .
Запишем задачу одномерной оптимизации
(	1)2	(	2) 2	min
0	1
Решением	этой	задачи		будет	0	1/ 2,	тогда
					0

x2 (5 / 2,1/ 2).

145

Итерация 3

f (x2 ) ( 3, 3) .

Рассмотрим задачу

f (x2 )xT 3x1 3x2 min .

Решением этой ЗЛП является отрезок, соединяющий точки

(2,1) и (3,0) (рис.5.3.1).

	Выберем одну из них, например,														x2	(3,0). Тогда
															min
	l2		(3,0)				(5 / 2,1/ 2)								(1/ 2, 1/ 2) .
	x2		(		5		2		, 1				2	)
	x2		(		5				, 1				2	)	.
					2		2			2			2		.
	Запишем задачу одномерной оптимизации
	(			3	)	2	(				3	)	2		min
	(	2	2		)		(	2		2		)			min
		2	2					2		2
	0					1
	Решением		этой				задачи						будет			2	0,	тогда
																2
x3	x2 (5 / 2,1/ 2).			Останов.						Получено						оптимальное		решение
x*	(5 / 2,1/ 2).

Задачи для самостоятельного решения

Решить методом линеаризации следующие задачи:

5.3.1)	x	2	2x	3x	min
	1		1	2
	4x1		5x2	80,
	2x1		x2	34,
	x1, x2 0
5.3.2)	x	1	2x	x2	min
		1	2	2
	4x1		5x2	x3	80,
	2x1		x2	x4	34,
	xi		0,	i

146

ЗАКЛЮЧЕНИЕ

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

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

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

147

Источник: https://studfile.net/preview/16565974/

Смотрите также:



_1966(~1
_Антонян Ю.М., Сексуальные преступления. Чикатило и другие
_РГР № 1 (2)
- Габариты и масса 27
'Образ–Я' и его развитие средствами диалога
"Логистическая технология JIT"
"Особенности правовой системы Российской Федерации" по дисциплине "Теория государства и права"
«Анализ ликвидности и платежеспособности предприятия» (на материалах ОАО Московская кондитерская фабрика «Красный Октябрь»)