Комбинаторные методы решения задач целочисленного линейного программирования.

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

Общая схема метода ветвей и границ.

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

, x Î Х

(5.1)

Если об этой задаче ничего неизвестно, то кроме как полного перебора для ее решения применить нельзя. Для ее решения методом ветвей и границ достаточно:

1. Уметь разбивать множество X (переобозначим его через X _0,1)на некоторые подмножества X _1,1,, X _1,2,, X _1,3, .... Каждое из полученных подмножеств, в свою очередь, может быть разбито на подмножества X _2,1, X _2,2, X _2,3, ...,и так далее, вплоть до получения одноэлементных подмножеств. Индексы (i, j) у подмножеств X_{i , j} означают следующее: i – номер уровня разбиения, j –порядковый номер в уровне. В результате такого разбиения получается дерево подмножеств:

2. На каждом из таких подмножеств X_{i , j} уметь строить верхние оценки максимального значения функционала, т.е. определять значение x_{i , j} такое, что

xi , j ³ max{ j (x) | x Î Xi , j }.

(5. 4)

Алгоритм метода ветвей и границ.

0 – шаг. Полагаем x' – пустой элемент (в него пока ничего не помещено), Fx' = M = –¥,. В дальнейшем x ' будем называть рекордом, Fx ' – рекордным значением функционала. Строим верхнюю оценку x _0,1 функционала j (x) на подмножестве X _0,1, полагаем V = x _0,1 (V – наименьшая из всех нижних оценок на всех подмножествах). Если в результате этого построения получаем некоторое x Î X _0,1, то x':= x, Fx':= j (x), в противном случае x' и Fx' оставляем без изменения. Если Fx' = V, то x' искомое решение и Fx' – оптимальное значение функционала, в противном случае переходим к следующему шагу.

k – ый шаг. Среди всех подмножеств, не подвергнутых разбиению (на дереве разбиения они концевые), ищем подмножество X_{r , t} , у которого x_{r , t} = V. Разбиваем его на подмножества X_{r+ 1, m+ 1}, X_{r+ 1, m+ 2}, X_{r+ 1, m+ 3}, ..., где m – номер последнего подмножества на (r+ 1)–ом уровне. Для каждого из этих подмножеств строим оценки x_{r+ 1, m+ 1}, x_{r+ 1, m+ 2}, x_{r+ 1, m+ 3}, ..... Обычно эти оценки находятся пересчетом (уточнением) из x_{r , t} . Легко понять, что должно выполняться:

x (r, t) ³ x (r+ 1, t), t = m+ 1, m+ 2, m+ 3, ....

(5. 5)

 

Если в результате этих построений получаем некоторое x Î X_{r , t} и j (x) >Fx', то x':= x, Fx':= j (x). Отбраковываем все подмножества X_{r , t} , для которых x_{r , t} £ Fx'.

Если в результате оказались отбракованными все подмножества, то x' и Fx' дают искомое решение и алгоритм заканчивает работу. В противном случае полагаем
V:=max x (r, t), где максимум берется по всем неотбракованным и не подвергнутым разбиению подмножествам, и переходим к следующему шагу.

Замечание 1. Нетрудно видеть, что в работе алгоритма участвуют только подмножества, не подвергнутые разбиению (концевые вершины дерева разбиения), которые можно организовывать в виде списка. Если подмножество подвергается разбиению, то оно исключается из списка и заменяется своим разбиением.

Замечание 2. Если в исходной задаче функционал минимизируется, то строятся нижние оценки x_{r , t} , т.е. x_{r , t} £max{ j (x) | x Î X_{r , t} }, и M = +¥.

 

Алгоритм Ленд–Дойг.

Исторически аналог описанного выше алгоритма разработан для задачи целочисленного линейного программирования математиками Ленд и Дойг. Несколько позже эта схема интерпретирована как метод ветвей и границ. В нем для задачи (5.2) множество X _0,1 есть множество всех целочисленных решений задачи. Оценку x _0,1 есть максимум функционала задачи (5.2.) без условий целочисленности. Если при построении x _0,1 получилось нецелочисленное решение, то множество X _0,1 разбивается на два подмножества X _1,1 и X _1,2 следующим образом. Пусть в оптимальном решении задачи (5.2.) , где не целое, тогда множество X _1,1 есть множество целочисленных решений системы

A x = b,	(5.6)
x ³ 0 n,	(5.7)
,	(5.8)
xj - целое, j =1,2,3,…, n.	(5.9)

Множество X _1,2есть множество решений системы

A x = b,	(5.10)
x³ 0,	(5.11)
,	(5.12)
xi – целые, i =1,2,3,…, n	(5.13)

Оценки x _1,1, x _1,2 получаются максимизацией функционала задачи (5.2) при ограничениях соответственно (5.6) –(5.9) и (5.10) – (5.12). Заметим, что для построения этих оценок целесообразно к последней симплекс-таблице задачи (5.2) добавлять соответственно ограничения (5.8) и (5.12) и решать задачи двойственным симплекс-методом. Дальнейшие разбиения и построение оценок проводятся аналогично.

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

x 1	+ x 2	®	max	(5. 14)
2 x 1	+ 11 x 2	£		(5. 15)
x 1	+ x 2	£		(5. 16)
4 x 1	– 5 x 2	£		(5. 17)
x 1 ³ 0	x 2 ³ 0			(5. 18)
x 1, x 2 – целые			(5. 19)

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

X 0,1	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 ₁=4. 44, x ₂=2. 56 не является целочисленным. Дерево разбиения примет вид

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

Для подмножества X _1,1 дополнительное ограничение будет иметь вид x ₁£4. Добавляем его к последней симплекс-таблице подмножества X _0,1, получим:

X 1,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

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

X 1,1	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,1=6. 2, x ₁=4, x ₂=2. 2.

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

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

На подмножестве X _3,1 получаем целочисленное решение x ₁=3, x ₂=2 со значением функционала, равным 5, которое принимаем за рекордное. Все подмножества X_{r , t} , у которых значения x_{r , t} > 5, отбраковываем, тогда x ₁=3, x ₂=2 становится оптимальным решением.

Самостоятельная работа № 11.

Решить задачу 4.2 методом Ленд и Дойг, исходные данные по вариантам взять в лабораторной работе №10.