Лабораторная работа №9. Решение задачи целочисленного программирования методом ветвей и границ

Рассмотрим следующий пример:

 

x(1) + x(2) ® max (4. 13)

2x(1) + 11x(2) £ 38 (4. 14)

x(1) + x(2) £ 7 (4. 15)

4x(1) - 5x(2) £ 5 (4. 16)

x(1) ³ 0 (4. 17)

x(2) ³ 0 (4. 18)

x(1), x(2) - целые. (4. 19)

 

0- ой шаг. Множество X(0, 1) состоит из всех решений задачи (4.13 - 4.19). Для получения оценки x(0, 1) решаем задачу (4.13-4.18). После решения этой задачи симплекс-методом последняя симплекс-таблица будет иметь вид:

 

xb	b	x(1)	x(2)	y(1)	y(2)	y(3)
y(1) x(2) x(1)	1.00 2.56 4.44	0.00 0.00 1.00	0.00 1.00 0.00	1.00 0.00 0.00	-6.00 0.44 0.65	1.00 -0.11 0.11
d	7.00	0.00	0.00	0.00	1.00	0.00

 

Оценка x(0, 1)=7. Решение x(1)=4.44, x(2)=2.56 не является целочисленным. Дерево разбиения примет вид

 

 

x(1)=4.44

x(0, 1)=7

x(2)=2.56

1 - ый шаг. Разбиваем множество X(0, 1) на подмножества X(1, 1), X(1, 2). В качестве переменной, по которой проводим разбиение берем переменную x(1), которая имеет нецелочисленное значение. Можно взять и переменную x(2).

Для подмножества X(1, 1) дополнительное ограничение будет иметь вид x(1) £ 4.

Добавляем его к последней симплекс-таблице подмножества X(0, 1),

получим:

 

xb	b	x(1)	x(2)	y(1)	y(2)	y(3)	y(4)
y(1) x(2) x(1) y(4)	1.00 2.56 4.44 -0.44	0.00 0.00 1.00 0.00	0.00 1.00 0.00 0.00	1.00 0.00 0.00 0.00	-6.00 0.44 0.65 -0.56	1.00 -0.11 0.11 -0.11	0.00 0.00 0.00 1.00
d	7.00	0.00	0.00	0.00	1.00	0.00	0.00

 

Решив эту задачу двойственным симплекс-методом, получим таблицу:

 

xb	b	x(1)	x(2)	y(1)	y(2)	y(3)	y(4)
y(1) x(2) x(1) y(2)	5.79 2.20 4.00 0.80	0.00 0.00 1.00 0.00	0.00 1.00 0.00 0.00	1.00 0.00 0.00 0.00	0.00 0.00 0.00 1.00	2.20 -0.20 0.00 0.20	-10.8 0.80 1.00 -1.80
d	6.20	0.00	0.00	0.00	0.00	-0.20	1.80

x(1)=4, x(2)=2.2, x(1, 1)=6.2.

 

Для подмножества X(1, 2) дополнительное ограничение будет иметь вид x(1)³ 5. Добавляем его к последней симплекс-таблице подмножества X(0, 1), получим, что задача не имеет решения, т.е. подмножество X(1, 2)=Æ, x(1, 2)=M (M - достаточно большое число, M ® ¥).Дерево разбиения принимает вид:

x(1)=4.44

x(0, 1)=7

x(2)=2.56

x(1) £ 4 x(1) ³ 5

x(1)=4

x(1, 1)=6.21 x(2)=2.2 x(1, 2)=M

 

 

На последующих шагах дальнейшему разбиению будет подвергаться подмножество X(1, 1).

 

 

Полное дерево разбиения будет иметь вид

x(1)=4.44

x(0, 1)=7

x(1) £ 4 x(2)=2.56

x(1)=4 x(1) ³ 5

x(1, 1)=6.21 x(1, 2)=M

x(2)=2.2

x(2) £ 2 x(2) ³ 3

x(2, 1)=5 x(2, 2)=5

x(1) £ 3 x(1) ³ 4

x(1)=3

x(3, 1)=5 x(3, 2)=M

x(2)=2

На подмножестве X(3, 1) получаем целочисленное решение x(1)=3, x(2)=2 со значением функционала, равным 5, которое принимаем за рекордное. Все подмножества X(r, t), у которых значения x(r, t) ³ 5, отбраковываем, тогда x(1)=3, x(2)=2 становится оптимальным решением.