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

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

A x = b,	(5.6)
x0n ,	(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)

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

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

x1	+ x2		max	(5. 14)
2 x1	+11 x2		38	(5. 15)
x1	+ x2		7	(5. 16)
4 x1	– 5 x2		5	(5. 17)
x1 0	x2  0			(5. 18)
x1, x2– целые				(5. 19)

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

X0,1	xb	b	x1	x2	y1	y2	y3
	y1 x2 x1	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

Оценка _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, получим:

X1,1	xb	b	x1	x2	y1	y2	y3	y4
	y1 x2 x1 y4	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

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

X1,1	xb	b	x1	x2	y1	y2	y3	y4
	y1 x2 x1 y2	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

_1,1=6.2, x₁=4, x₂=2.2.

Для подмножества X_1,2дополнительное ограничение будет иметь видx(1)5. Добавляем его к последней симплекс-таблице подмножестваX_0,1, получим, что задача не имеет решения, т.е. подмножествоX_1,2=,_1,2=. Дерево разбиения принимает вид:

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

На подмножестве X_3,1получаем целочисленное решениеx₁=3,x₂=2 со значением функционала, равным 5, которое принимаем за рекордное. Все подмножестваX_r,t, у которых значения_r,t>5, отбраковываем, тогдаx₁=3, x₂=2 становится оптимальным решением.