ТЕОРИЯ ОПТИМИЗАЦИИ И Алгоритмов / Методы_оптимизации

101

Таблица 10.6

																							↓
		Базис		Своб.							x1				x2					x3		x4						u1						u2
					член
			x1		4			4			1			0						0			1					−	1					0
								7														7							7
		x2			3						0			1						0		0						1						0
		x3			1			4			0			0						1			1					− 3		1				0
								7														7
																													7
→		u2				−		4			0			0						0		−		1				−	6					1
								7																					7
																						7
			f		59						0			0						0		1						8						0
																						7						9	1
																													3
								bu2		< 0		→		u2 выводим из базиса,
					1								6			1
		min 1		−				= 7 , 8				−		= 9				= 7		→		x4 вводим в базис.
					7								7		3
			Таким образом, Б1 = {x1, x2 , x3 , x4}. В результате приходим
к табл. 10.7.																				БР1 = (х1 = 4, х2 = 3, х3 = 1,
			Из	табл. 10.7								следует,						что
x4 = 4). БР1 является допустимым и, следовательно, оптималь-
ным решением.
			Таким образом, задача L2 имеет решение x(2)																										= (4, 3) , при
этом f (х(2) ) = 55 .
			Поскольку решение x(2) является целочисленным,																															то точ-
ка x(2)			= (4, 3)					является решением исходной задачи; поэтому по-
лагаем			х = x(2) = (4, 3) , f = f (x(2) ) = 55																			и вычисления завер-
шаются.

102

Таблица 10.7

Базис	Своб.	x	x	x	x	u	u	2
	член	1	2	3	4	1
x1	4	1	0	0	0	−1	1
x2	3	0	1	0	0	1	0
x3	1	0	0	1	0	−4	1
x4	4	0	0	0	1	6	−7
f	55	0	0	0	0	2	7

Ответ: х = (4, 3) , f = 55 .

Задачи

1. Решить методом отсечений следующую целочисленную задачу ЛП:

f (x) = x1 + 2x2 → max, 4x1 + 2x2 ≤ 13 ,

x1 ≥ 0, x2 ≥ 0 , x1 , x2 − целые.

2. Решить методом отсечений следующую целочисленную задачу ЛП:

f (x) = 2x1 + 3x2 → max, 2x1 + 5x2 ≤ 16 ,

6x1 + 5x2 ≤ 30 , x1 ≥ 0, x2 ≥ 0 ,

x1 , x2 − целые.

103

11. МЕТОД ВЕТВЕЙ И ГРАНИЦ

Метод ветвей и границ относится к группе комбинаторных методов дискретного программирования и является одним из наиболее распространенных методов этой группы. Центральную идею комбинаторных методов составляет замена полного перебора допустимого множества X частичным перебором. В случае метода ветвей и границ это осуществляется путем последовательного разбиения допустимого множества на подмножества (ветвления) и вычисления оценок (границ), позволяющих отбрасывать подмножества, заведомо не содержащие решения задачи. При реализации общей схемы метода ветвей и границ для различных задач дискретного программирования необходимо, исходя из специфики этих задач, конкретизировать правила ветвления и вычисления границ.

На практическом занятии рассматривается метод ветвей и границ для задачи целочисленного линейного программирования (ЛП) следующего вида:

n

f (x) = ∑ c j x j → max ,

j =1

n

∑ aij x j ≤ bi , i = 1, m ,

j =1

x j ≥ 0 ,	j =			,
		1, n
x j − целые,	j =				.
			1, n

Допустимое множество Х данной задачи предполагается ограниченным.

В данном случае на каждом этапе (шаге) решаются непрерывные задачи ЛП: на предварительном (нулевом) этапе – задача L0; на k-м, k = 1, 2,..., этапе − задачи L2k-1 и L2k. Задача L0 , как и в методе отсечений, представляет собой исходную задачу без учета требования целочисленности; задача Lν , ν = 1,2,..., получается в

результате добавления к задаче L0 дополнительных ограничений. Верхняя граница (оценка) ξν целевой функции f для задачи

104

Lν, ν = 0,1,2,..., определяется следующим образом:

ξν ≡ f (x(ν ) ) ,

где x(ν ) − решение задачи Lν .

Если задача Lν не имеет решения, то полагается ξν ≡ −∞ .

В процессе решения строится дерево задач, в котором ν -я, ν = 0,1,2,..., вершина соответствует задаче Lν . Обозначим

через I множество вершин, из которых возможно ветвление. Для ветвления на k-м, k =1,2,..., этапе выбирается ν-я, ν I, вершина

(задача Lν ), которая имеет максимальную верхнюю оценку ξν .

Пусть в решении x(ν ) некоторая компонента xr(ν ) , 1 ≤ r ≤ n , не является целочисленной. Допустимое, т.е. целочисленное, значение xr должно удовлетворять одному из неравенств, представляющих собой необходимые условия целочисленности xr :

либо xr ≤ [xr(ν ) ] , либо xr ≥ [xr(ν ) ] +1, где [a] − целая часть действительного числа а.

В результате задача Lν разветвляется (разбивается) на две не связанные между собой задачи L2k −1 и L2k . Задача L2k −1 пред-

ставляет			собой		задачу	Lν	с дополнительным			ограничением
x	r	≤ [x(í) ] , а задача L2k − задачу L с дополнительным ограниче-
		r					ν
нием x			≥ [x(ν )	] +1, т.е.
		r	r
			L2k −1		Lν ,		L2k		Lν ,
					(ν )	];			(ν )	] +1.
					x ≤ [xr				x ≥ [xr

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

Θ . После решения задачи Lν значение Θν определяется следующим образом:

			105
		ν −1	, если задача Lν не имеет решения либо x	(ν )
	Θ
Θν			не является целочисленным;
	=

max{Θν -1 ,ξν }, если x(ν ) является целочисленным.

При этом Θ0 ≡ −∞ .

Ветвление на k-м, k = 1,2,.., этапе из i-й, i I, вершины следует прекратить, если верхняя граница ξ i целевой функции для задачи Li не больше известной на данном шаге нижней гра-

ницы Θ2k целевой функции для целочисленного решения. Процесс решения завершается, когда отсутствуют вершины, из которых возможно ветвление, т.е. I = . При этом оптимальное зна-

чение f = Θ2k , решение x = x(ν ) , где x(ν ) определятся из условия f (x(ν ) ) = Θ2k .

Итак, алгоритм решения целочисленной задачи ЛП методом ветвей и границ заключается в следующем.

1. Решается задача ЛП L0.

Если задача L0 не имеет решения, то исходная задача не имеет целочисленного решения и вычисления завершаются.

2.Находится решение x(0) , вычисляется верхняя граница

ξ0 = f (x(0) ) .

Если решение x(0) является целочисленным, то полагается x = x(0) , f = ξ 0 и вычисления завершаются.

Если решение x(0) не является целочисленным, то полага-

ется Θ0 = −∞ , k=1 и осуществляется переход к п. 3.

3. Выбирается для ветвления ν-я вершина из I, для которой выполняется условие

ξν = max ξ i .

i I

106

4.Выбирается (произвольно) одна из нецелочисленных компонент xr(ν ) , осуществляется ветвление по переменной xr , составляются задачи L2k −1 и L2k .

5.Решается задача Lj , j = 2k −1, 2k.

Если задача L j не имеет решения, то полагается ξ j = −∞ ,

Θj = Θ j −1 и осуществляется (при j=2k) переход к п. 7.

6.Находится x( j ) , вычисляется ξ j = f (x( j) ) .

Если решение x( j ) является целочисленным, то полагается Θ j = max{Θ j −1,ξ j } и осуществляется (при j = 2k) переход к п. 7.

Если решение x( j ) не является целочисленным, то полагается Θ j = Θ j −1 и осуществляется (при j = 2k) переход к п. 7.

7.Просматриваются вершины из I и прекращается ветвление, если выполняется условие

ξi ≤ Θ2k , i I.

8.Проверяется условие окончания вычислений

I = .

Если оно выполняется, то полагается f = Θ2k , x = x(ν ) ,

где x(ν ) определяется из условия f (x(ν ) ) = Θ2k , и вычисления за-

вершаются.

Если условие не выполняется, то полагается k = k +1 и осуществляется переход к п. 3.

Пример. Решить методом ветвей и границ следующую целочисленную задачу ЛП:

f (x) = 2x1 + 3x2 → max , 5x1 + 7x2 ≤ 35 ,

4x1 + 9x2 ≤ 36 , x1 ≥ 0 , x2 ≥ 0 , x1, x2 − целые.

107

Решение.

Предварительный (нулевой) этап

Записываем задачу L0 (исходная задача без учета требо-

вания целочисленности):
			f (x) = 2x1 + 3x2 → max ,
				5x1 + 7x2 ≤ 35 ,	(1)
				4x1 + 9x2 ≤ 36 ,	(2)
				x1 ≥ 0, x2 ≥ 0.
Этой задаче соответствует нулевая вершина дерева задач
(см. ниже рис. 11.6).
Решаем графически задачу L0 (рис. 11.1).
x2
6
5
4
3				x(0)
2
1			f (x)
						x1
			1 2 3 4 5 6 7 8 9		(2)
				(1)
				Рис. 11.1
Из рис. 11.1			следует, что задача L0 имеет решение x(0) .
Точка x(0) является решением системы уравнений
			5 x1 + 7 x2 = 35 ,
				4 x1 + 9 x2 = 36 .
Находим x(0) и ξ 0				:

				108
	− 45x1 + 63x2 = 315 →									x = 63						= 312 ;
		28x1 + 63x2 = 252							1			17					17
5 63		17x1		= 63			9				280									40		6
	+ 7х = 35		→ 7х	= 35 −18					=							→		х =			= 2		;
17	2		2				17					17					2			17	17
					12					6
			x	(0) = (3			, 2				);
					17				17
	ξ 0		= f (x(0) ) = 2 3		12			+ 3 2					6		= 14			8	.
					17							17					17

Поскольку x(0) не является целочисленным, то полагаем Θ0 = −∞ и выполняем 1-й этап.

Первый этап

Осуществляем ветвление из нулевой вершины.

Выбираем для ветвления нецелочисленную компоненту x2(0) = 2 176 ; осуществляем ветвление по переменной x2 : x2 ≤ 2 , x2 ≥ 3 ; составляем задачи L1 и L2 :

L1		L0 ,		L2	L0 ,
			2;			≥ 3.
	x2 ≤				x2
Записываем задачу L1:
		f (x) = 2x1 + 3x2 → max ,
			5x1 + 7x2 ≤ 35,			(1)
			4x1 + 9x2 ≤ 36 ,			(2)
		x1 ≥ 0, 0 ≤ x2 ≤ 2.

Этой задаче соответствует первая вершина дерева задач (см. ни-

же рис. 11.6).

Решаем графически задачу L1 (рис. 11.2).

Из рис. 11.2 следует, что задача L1 имеет решение x(1) .

109

Точка x(1) является решением системы уравнений

		5 x1 + 7 x2 = 35 ,
			= 2.
		x2
x2
6
5
4
3			x(1)
2
1		f (x)

		1 2 3 4 5 6 7 8 9									x1
						(1)				(2)
		Рис. 11.2
Находим x(1)		и ξ 1 :
5х + 7 2 = 35 → 5х = 21 → х = 4									1	;
1		1				1			5
			1
		x(1) = (4				, 2);
			5
ξ1		= f (x(1) ) = 2 4		1		+ 3 2 = 14	2	.
			5				5
Поскольку x(1) не является целочисленным, то полагаем
Θ1 = Θ0 = −∞ .
Записываем задачу L2 :
		f (x) = 2x1 + 3x2 → max ,
		5x1 + 7x2 ≤ 35 ,					(1)
		4x1 + 9x2 ≤ 36 ,					(2)
		x1 ≥ 0, x2 ≥ 3.

110

Этой задаче соответствует вторая вершина дерева задач (см. ниже рис. 11.6).

Решаем графически задачу L2 (рис. 11.3).

x2
6
5
4		x(2)
3
2
1		f (x)

		1 2 3 4 5 6 7 8 9									x1
						(1)	(2)
		Рис. 11.3
Из рис. 11.3 следует, что задача L имеет решение x(2) .
						2
Точка x(2) является решением системы уравнений
		4 x1 + 9 x2 = 36 ,
		x2 = 3.
Находим x(2)		и ξ 2 :
4х + 9 3 = 36 → 4х = 9 → х = 2									1	;
1		1				1	4
			1
		x(2) = (2				, 3);
		4
ξ 2		= f (x(2) ) = 2 2		1		+ 3 3 = 13	1	.
							2
		4

Поскольку x(2) не является целочисленным, то полагаем

Θ2 = Θ1 = −∞ .

Просматриваем вершины из I = {1, 2}.