ЛЕКЦИЯ 16

ЛЕКЦИЯ 16

1 Метод Келли или метод отсекающих плоскостей

Пусть виде: Q x

функция

n c jx j j 1

Q x - линейная, т.е.

Q x

представима в

. Рассмотрим следующую задачу:

n Q x c jx j j 1

K x R	n	: g
		i

min , x K

x 0, i

(1)

1,..., m ,(2)

где gi x - вогнутые функции, множество K- выпуклое множество.

Алгоритм решения задачи (1)-(2) состоит в следующем: 1. Задать множество

K(0) x R n : x j x j x j , K K(0) .

Решить задачу

n Q x c jx j j 1

min
x K	(0)

.

(3)

K(0) x R n : x j x j x j , K K(0)

Задача (3) представляет собой задачу линейного программирования. Для ее решения необходимо использовать методы линейного программирования (например, симплексметод).

Пусть x	(1)	- решение задачи (3).

Для k=1,2,… выполнить следующую последовательность

шагов.
2. Вычислить индекс p I 1,2,..., m			следующим образом:
gp x	(k)	max gi x	(k)	,0 ,
		i I

где x(k) - решение задачи на k-й итерации.

		Проверить	условие окончания вычислений: если
g	p	x(k) ,	то прекратить вычисления. В противном случае

перейти к пункту 3.

3. Построить отсекающие плоскости следующего вида:

gp x; x		gp x		gp x		x x		.
~	(k)		(k)		(k)		(k)

Пусть H			(k)	- полупространство вида:
H	(k)	x R			n	: gp x, x	(k)	0 .

Сформулировать новую систему ограничений вида:

K	(k)

K	(k 1)

H	(k)

.

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

n
Q x c jx j min .
j 1	x K	( k )

Перейти к пункту 2.

В случае, если Q x нелинейная функция, то вместо задачи

Q x min ,

x K

K x R	n	: g	x 0, i
		i

рассматривается задача

v min			,
x K
K x R	n	: g
			i

Таким образом, задача линейной функцией цели.

1,..., m

(4)

x 0, i 1,..., m; Q x v . (5)

(4)-(5) представляет собой задачу с

Пример 1. Решить методом Келли следующую задачу:

x1 x2	min ,
	x X

g1 x 2x1 x22 1 0, X g2 x 9 0.8 x12 2x2

x1 0, x2 0.

0, .

Как видно из рис. 1, допустимая область этой задачи лежит в прямоугольнике

0 x	5,
1

0 x2

4

.

Функции

g	x
1

и

g	2	x

вогнутые.

Зафиксировав некоторое малое алгоритма, полагая

0

,

перейдем к пункту 1

K	(0)	x : 0	x1	5, 0 x2	4 .
			x
				2

5

4

3

2

1

~	(3)
g2(X		)	~	(X	(1)	)
			g
			2
						(2)
					X		X	(1)
								~		(2)
									(X
								g		)
									1
					(4)		(3)
							X
				X
					X		(5)
			X*

(4)) ~ (X g1

1	2	3	4	5	6	x
						1

Рис. 1.-Область допустимых решений

Итерация 1. Найдем минимум функции области

x	x	2
1

в

K	(0)	x : 0	x1	5, 0 x2	4 .

Очевидно, что решением является точка x(1) 5,4 .

Поскольку	g x(1)	7 ,	g	2	x(1)	19, наиболее сильно
	1

нарушается ограничение

g		x	(1)
	2

19

. Значит, p=2.

Отсекающая плоскость задается при помощи линеаризации

g2 x в точке

x	(1)

, так что

~		x; x	(1)	19	8 x	5 2 x
g	2						2
					1

4

.

Таким образом, необходимо добавить ограничение

19 8 x1

Заметим, что точка ограничению.

5

x	(1)

2 x2

не

4 0.

удовлетворяет этому

Теперь следует решить следующую подзадачу:

x1 x2 min ,

x K (1)

K(1) x : 29 8x1 2x2 0, 0 x1 5, 0 x2 4 .

Оптимальное решение этой задачи : x	(2)	2.625;4 .

Итерация 2. Подставляя полученное решение в ограничения имеем

g	x	(2)
1

11.75

,

g		x	(2)
	2

4.5125

.

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

Уравнение

отсекающей

плоскости

для

первого

ограничения в точке x(2) 2.625;4 имеет следующий вид:

~	x; x	(2)	11.75	2 x1	2.625 8 x2	4 .
g1

Она отделяет точку x	(2)	от допустимой области К.

Третья промежуточная подзадача ЛП:

x1 x2 min( 2) ,

x K

			x : 29		8x		2x	2	0,
						1
K	(2)			15	2x		8x		0,
								2
						1
				0 x		5, 0 x					4	.
										2
					1

Оптимальное решение этой задачи: x	(3)	2.971;2.618 .

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

Точка x	*	2.5;2 представляет собой оптимальное решение.

Результаты выполнения последовательных итераций представлены в табл.1

Таблица

Номер

подзадач

и

1

2

3

4

5

1

x(k) 1

5

2.625

2.971

2.343

2.516

2.500

x(k)

2

4

4

2.618

2.461

2.050

2.000

f x	(k)
1

-9.000

-6.625

-5.589

-4.804

-4.566

-4.500

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

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

1.Генерация минимизирующей последовательности x(k)

вметоде Келли осуществляется таким образом, что

является недопустимой точкой, то)(kxЗамечания:каждая из точек

есть	x	(k)	K k . Это является одним из недостатков

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

2. Сходимость к оптимальному решению по функционалу

метод Келли гарантирует в том случае, если	K	выпуклая
область.

3.	Последовательность	областей	K	(0)	, K	(1)	,.., K

представляет собой семейство вложенных множеств. Если это свойство выполняется k , то при этом не происходит потери части допустимой области, что возможно, если множество K невыпукло.

4.С увеличением количества итераций k растет размерность задачи линейного программирования.

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

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

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

Решить методом Келли следующие задачи.

	1.	2x1 4x		2	30 min,
									x X
	X :1 x				2		x				2	0, x
			1					2	1
		1											1
	2.	x1 3x	2	18 min,
								x X
		2			2		0, x1, x2 0.
	X : 4 x1		x2
	3.	2x1 x2		5 min,
							x X
			2	x2 0, x1, x2 0.
	X : 2 2x1
	4.	x1 3x	2	min,
							x X
	X : 8 0.8 x				2	0.4 x				2	0, x		, x
					1					2
												1

5. 2x1 5x2 min,

x X

X :1 x1 2x22 0, x1, x2 0.

, x2

2

0.

0

.