ТОП 10:

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



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

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

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

, xÎХ (5.1)

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

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

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

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

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

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

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

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

 

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

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

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

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

 

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

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

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

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

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

Оценки x1,1, x1,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 £ (5. 15)
x1 + x2 £ (5. 16)
4 x1 5 x2 £ (5. 17)
x1³ 0 x2 ³ 0     (5. 18)
x1, x2 – целые     (5. 19)

0ой шаг. Множество X0,1состоит из всех целочисленных решений задачи (5.14)(5.19). Для получения оценки x0,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

 

Оценка x0,1=7. Решение x1=4.44, x2=2.56 не является целочисленным. Дерево разбиения примет вид

1–ый шаг. Разбиваем множество X0,1 на подмножества X1,1, X1,2. В качестве переменной, по которой проводим разбиение, берем переменную x1, которая имеет нецелочисленное значение. Можно взять и переменную x2.

Для подмножества X1,1 дополнительное ограничение будет иметь вид x1£4. Добавляем его к последней симплекс-таблице подмножества X0,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

x1,1=6.2, x1=4, x2=2.2.

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

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

На подмножестве X3,1 получаем целочисленное решение x1=3, x2=2 со значением функционала, равным 5, которое принимаем за рекордное. Все подмножества Xr,t, у которых значения xr,t>5, отбраковываем, тогда x1=3, x2=2 становится оптимальным решением.

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

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

 







Последнее изменение этой страницы: 2016-06-29; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.228.10.64 (0.005 с.)