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

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

vj	6	-1	6		2	4
ui	6	-1	6		2	4
ui

0	-1	-5		3	*	-1
				3
-3	*	-8	*		-6	*
-6	*	-11	-2		-7	-8
2	-3	*	*		*	1

1.3(i0 , j0 ) (1,3) .

1.413 3 0 .

1.5Отмечаем звездочкой элемент (1,3) и по правилу вычеркивания определяем цикл.

								*		*
*								*					*
*
				*				*		*
	Цикл образуют элементы (1,3)								(1,4)		(4,4)	(4,3) .
		{(4,4)} ,				{(1,4),(4,3)} .
1.6		min(6,5)				5 .
1.7	x130			5 , x141		6	5	1 , x143	5 5		0 , x144	5 1 6 ,
		x210	0 , x123			2 , x125		6 , x311	12 , x142 8 .
1.8 Имеется только один элемент (4,3) из											, для которого x0			0 .
												43
	Поэтому он становится небазисным. Новая базисная точка имеет
	вид
		0	0		5	1	0
	x1	0	0		2	0	6 .
		12	0		0	0	0
		0	8		0	6	0
1.9 L(x1)			L(x0 )			x131	13	76 5*3	61
Итерация 2.
2.1, 2.2

128

vj	3	-1	3	2	1
ui	3	-1	3	2	1
ui

0	-4	-5	*	*	-4

0	*	-5	*	-3	*

-3	*	-8	-2	-4	-8

2	-2	*	-3	*	-2

2.3, 2.4.	i0	max	ij	2	0 .
		j0
Решение закончено.			x* x1 ,		L(x* ) 61.

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

Решить следующие задачи методами потенциалов, минимального элемента и “северо – западного угла”:

4.6.1	a\b	25	40	50	35	45
	20	7	3	4	8	6
	60	5	7	2	3	5
	45	1	4	5	2	6
	70	3	4	2	7	8

4.6.2	a\b	35	30	50	25
	50	8	6	7	3
	50	7	4	9	3
	55	6	1	4	5
	50	7	8	3	4

4.6.3	a\b	10	40	20	60	20
	30	5	1	5	2	4
	70	5	7	6	3	2
	25	1	5	4	2	6
	25	1	6	3	3	5

129

4.6.4	a\b	70	40	30	60	50
	20	6	1	7	3	3
	90	7	4	4	8	4
	80	8	2	3	5	7
	60	3	4	2	8	5

4.6.5	a\b	30	90	80	20	30
	95	2	8	4	6	3
	55	3	2	5	2	6
	40	6	5	8	7	4
	60	3	4	4	2	1

4.6.6	a\b	10	30	25	15	20
	20	9	1	5	7	1
	15	2	8	4	8	1
	45	2	3	2	8	5
	20	6	1	3	4	7

4.6.7	a\b	13	13	13	13	28
	28	8	4	6	3	1
	13	9	3	8	5	7
	19	7	3	5	9	8
	20	2	1	4	5	7

4.6.8	a\b	11	13	26	10	10
	24	9	1	3	2	7
	12	6	9	4	1	5
	18	9	1	2	8	5
	16	3	3	9	6	8

4.6.9	a\b	10	35	15	25	35
	30	7	3	1	5	4
	25	7	5	8	3	2
	45	6	4	8	3	2
	20	3	1	7	6	2

130

4.6.10	a\b	30	80	65	35	40
	60	8	2	4	9	1
	55	7	5	5	3	6
	85	9	4	6	2	7
	50	5	3	2	6	4

5. ЗАДАЧА КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ

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

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

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

xT Qx bxT c min x ,

где Q (qij ) - симметричная положительно определенная матрица

размера n n , b - фиксированный вектор размера n , с - заданное число.

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

	n				_____
gi (x)			ij x j	i	0, i=1,m ,	(5.1.1)
	j 1
	1	n	n		n
f (x)			qij x j		bj x j c	min ,
f (x)	2 i		qij x j		bj x j c	min ,
	2 i	1	j 1		j 1
			____
xj 0, j=1,n .
Для данной задачи условной оптимизации можно
рассмотреть функцию Лагранжа вида:
				n	n
L(x, , )			f (x)		i gi (x)	j ( x j )
				i 1	j 1
			131

1 n		n		n
			qij x j	bj x j	c
2 i 1			qij x j	bj x j	c
2 i 1		j	1	j 1
n			n		n
	i (		ij x j	i )	i ( x j ) .
i 1		j	1	j	1

При этом условия Куна - Таккера запишутся в виде следующей системы равенств и неравенств:

x j

1, n

q ij x i

b j

0, j 1, n

x j

i 1

ij x j

0, i

1, m

j 1

(5.1.2)

i gi

ij x j

0, i 1, m

j x j

1, n

1, m,

j 1, n.

5.1.2. Использование симплексного метода для решения задачи квадратичного программирования

По теореме Куна - Таккера решение системы (5.1.2) является

искомой точкой минимума функции			f (x)		(5.1.1) на множестве .
					_____
Введя дополнительные	переменные			xn	1 , i=1,m, полученную
систему перепишем в виде системы равенств
n q ij x j	n
n q ij x j	n	i	ij	j	b j , j 1, n
i 1	i 1

132

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

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



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