x2 7	Задача 1		x2 8
		x	;
		x	. ;
Задача 2		Q .		Задача 3

x

. ;

x

. ;

x

;

x

;

x

x

x

x

Q .

Q .

Задача 4

Задача 5

Задача 6

Задача 7

x

x

x

;

;

;

не

x

;

x

;

x

;

совместна

Q

Q

Q

Рис. 5.2. Иллюстрация метода ветвей и границ

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

Обязательное условие метода – наличие верхних границ d j на значе-

ния переменных x j . Если d j не назначена, то ее определяют по зависимости

				n
			bi aij d j
	d j			j
			min		j ,...,n n,
				aij
			i ,..., m

где d j — минимальные значения всех x j , для которых определяется верхняя граница d j .

5.3.Задача выбора вариантов

Перейдем теперь к частному случаю задач целочисленного программирования — задаче выбора вариантов [4].

119

В этом частном случае искомая переменная x j в результате решения

может принимать не любое целое значение, а только одно из двух: либо 0, либо 1. Чтобы такие переменные отличать от обычных и каждый раз не писать x j [0; 1], будем их вместо x j обозначать j . И это уже будет означать,

что в результате решения задачи j может быть равным или 0 или 1, т.е. всегда j [0; 1]. Такие переменные обычно называют булевыми (в честь пред-

ложившего их английского математика Джорджа Буля, 1815-1864).

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

Пример 5.2. В задаче выбора вариантов примем, что для получения результата в виде максимально возможной прибыли необходимы два вида ресурсов: материальные и трудовые. Возможны четыре варианта расхода ресурсов и получения прибыли (табл. 5.3). Необходимо выбрать сочетание любых трех вариантов задачи, обеспечивающих максимум прибыли.

Таблица 5.3

Условия задачи выбора вариантов

	Показатели		Варианты			Наличие
		1	2	3	4	ресурса
	Прибыль	65	80	90	210	-
	Материальные ресурсы	200	180	240	250	800
	Трудовые ресурсы	10	15	22	28	50

Решение. Для составления модели примем, что j-му варианту будет соответствовать булева переменная j j ,..., . При этом

,	если j-й вариант принят;
j
0,	если j-й вариант не принят.

Тогда математическая модель задачи запишется

max Q( ) ,

,

,

.

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

120

Попытаемся решить пример 5.2 с помощью функций Mathcad (рис.

5.3).

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

Для решения задачи разработаем программу в среде Mathcad на основе следующего алгоритма:

1)положить Qmax (заведомо меньше maxQ( ) );

2)организовать цикл расчетов k ,...,m ;

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

интервале , и функцией Хевисайда Ф(x) , если x и Ф(x) , если

x;

4)проверить выполнение ограничений задачи и если хотя бы одно условие не выполнено, то переход к п. 3) и выбор следующего случайного набора, иначе к п. 5);

5) рассчитать значение целевой функции, и если это значение

Qz Qmax , то Qmax Qz ;

6)запомнить данный набор булевых переменных и номер итерации k;

7)переход к п.3);

8)составной массив z, x, k содержит только решение поставленной

задачи.

Q(x1 x2 x3 x4) 65x1 80x2 90x3 210x4
x1 0	x2 0	x3 0 x4 0			- начальная точка поис ка
Given	0 x1 1	0 x2 1		0 x3 1						0 x4 1
200x1 180x2 240x3 250x4 800
10x1 15x2 22x3 28x4 50
x1 x2 x3 x4 3									1
x MaximizeQ( x1 x2 x3 x4)						x		0.8
Q x0x1x2x3 339									0
									1
С дополнительным ус ловием=x							4
					2
Given	0 x1 1		0 x2 1			0 x3 1				0 x4 1
200x1 180x2		240x3 250x4 800
10x1 15x2 22x3			28x4 50

Рис. 5.3. Решение задачи выбора вариантов стандартными средствами Mathcad

121

	x1 x2 x3 x4 3
	x2 x4			0						0.7
											1
	xx MaximizeQ( x1 x2 x3 x4)						xx						Q xx xx xx xx		335.5
											0		0	1 2 3
											1
	С дополнительным ус ловием+x							4	=1
							3
	Given	0 x1 1				0 x2 1	0 x3 1					0 x4 1
	200x1 180x2 240x3 250x4 800
	10x1 15x2 22x3 28x4 50
	x1 x2 x3 x4 3
	x3 x4				1						1
										0.8			Q xy0xy1xy2xy3 339
	xy MaximizeQ( x1 x2 x3 x4)						xy
											0
											1

Рис. 5.3. Окончание

Текст программы и результаты расчетов представлены на рис. 5.4, 5.5 и в табл. 5.4.

Из результатов решения этой задачи (первый столбец табл. 5.4) видно, что наибольшая прибыль maxQ будет получена в том случае, если

будут приняты третий и четвертый варианты.

Таблица 5.4

Результаты решения задачи выбора вариантов

Оптимальное			Дополнительные условия
решение		нет
		0				0					0
		0				1					1
		1				0					0
		1				1					1
Прибыль max Q		300			290						290

С помощью булевых переменных можно накладывать дополнительные логические связи между вариантами. Например, требуется, чтобы четвертый вариант был принят только в том случае, если принят второй, а если же второй вариант не принят, то и четвертый не должен быть принят. Это условие можно записать так: или в форме записи ограничений (ре-

зультат решения этой задачи во втором столбце табл. 5.4).

122

Может быть сформулирован и другой вариант дополнительных условий. Например, требуется, чтобы был принят либо третий вариант, либо четвертый, т.е. (результат решения в третьем столбце).

Сравнивая значение прибыли в оптимальном решении maxQ с

прибылью при выполнении дополнительных условий (см. табл. 5.4), можно сделать вывод, что они, как всегда, приводят к снижению прибыли.

					65		200			10			1
	n 3	M 100	cc		80	a	180		b	15		d	1
					90			240			22		1
					210			250			28		1

n			n	a x	n	b x
					q2(x)
Q(x) cc ixi		q1(x)
			i 0	i i	i 0	i i
i 0
n	dixi
q3(x)

i 0

( Z X k )

k 4

Z 300

Qmax 1000
kmax 0
for	k 0 M
	for		j 0 n
			pj rnd(2) 1
			yj pj
	l if(q1(y) 800 q2(y) 50 q3(y) 3 0 1)
	Qz if(l					0 Q(y) 1000)
	xmax if(l							0 Qz Qmax y xmax)
	kmax if(l							0 Qz Qmax k kmax)
	Qmax if(Qz Qmax Qz Qmax)
	Z Qmax
	X xmax
	kk kmax
( Z	X		kk)
			0
X			0
			1
			1

Рис. 5.4. Решение примера 5.2 без дополнительных условий

123

%Решение примера 5.2 в Matlab

A=[200 180 240 250;10 15 22 28;1 1 1 1]; b=[800;50;3];

c=[65;80;90;210]; [x,Q]=bintprog(-c,A,b)

x = 0 0 1 1

Q = -300

%Решение примера 5.2 с доп. условием в Matlab

A=[200 180 240 250;10 15 22 28;1 1 1 1]; b=[800;50;3];

c=[65;80;90;210]; A1=[0 1 0 -1]; b1=[0];

[x,Q]=bintprog(-c,A,b,A1,b1)

prim52a

Optimization terminated.

x = 0 1 0 1

Q = -290

Рис. 5.4. Окончание

124

					65		200			10			1
	n 3	M 100	cc		80	a	180		b	15		d	1
					90			240			22		1
					210			250			28		1

n	cc ixi	n	aixi	n	bixi
Q(x)		q1(x)		q2(x)
i 0		i 0		i 0
n	dixi
q3(x)
i 0

( Z X k )

k 7

Z 290

Qmax 1000 kmax 0

for k 0 M for j 0 n

pj rnd(2) 1 yj pj

l if q1(y) 800 q2(y) 50 q3(y) 3 y1 y30 1

	Qz if(l			0 Q(y) 1000)
	xmax if(l					0 Qz Qmax y xmax)
	kmax if(l					0 Qz Qmax k kmax)
	Qmax if(Qz Qmax Qz Qmax)
	Z Qmax
	X xmax
	kk kmax
( Z X kk)

			0
	X		1
			0
			1

Рис. 5.5. Решение примера 5.2 с дополнительным условием δ2=δ4

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

так:

125