|
Есть целевая функция:
n
∑cjxj->max (1)
J=1
И одно ограничение:
n
∑ajxj<=b (2)
J=1
xi ?{0,1}, i=1…n (3)
Для получения верхних оценок в корне и в следующих вершинах будем использовать теорему Данцига, относящуюся к следующей задаче линейного программирования:
n
∑cjxj->max (4)
J=1
n
∑ajxj<=b
J=1
0<=xj <=1, j=1…n
Эта задача называется непрерывной задачей о ранце.
Задача приведённая, если:
1) cj , aj =1, n и b – целые положительные числа
2) отношения cj /aj yt возрастают по мере возрастания индекса i:
(cj /aj)>=( cj+1 /aj+1), j=1…n-1 (5)
Очевидно, что для любой задачи о ранце существует эквивалентная ей приведённая задача. Сформулируем теорему Данцига.
Оптимальное решение непрерывной приведённой задачи (4)-(5) определяется с помощью следующих рекуррентных соотношений:
**************j-1
******min(aj;b-∑ ai xni)
*************i=1
xnj = _______________
**************aj
0
∑ ai xni =0
i=1
Теорема Данцига позволяет использовать приведённую задачу в качестве релаксации для исходной задачи (1-3). Целая часть максимального значения критерия оптимальности приведённой задачи является верхней оценкой максимально значения критерия в задаче (1-3): V(t)=[F(xn)]. Отметим также, что изложенный в теореме Данцига алгоритм конструирует решение x, в котором значение всех неизвестных, кроме, быть может, одного, является булевым (0 или 1). Заменив нецелочисленную координату решения нулём, получаем допустимое для задачи (1-3) решение xц, где:
xjц= (xjц, если xjц – целое число, 0, если xjц – нецелое число)
Это даёт возможность вычислить нижнею оценку оптимального значения критерия для рассматриваемой задачи: H(t)= F(xц). Если осталась неотброшенной одна вершина, в которой верхняя и нижняя оценки совпадают, то решение xц является для рассматриваемой задачи оптимальным решением. Если же оценки не совпадают, то в векторе x имеется нецелочисленная координата xi , 0<xni<1, в направлении которой и реализуется ветвление по следующему принципу: рассматриваются варианты xni=0 и xni=1; первый из них порождает задачу (1-3) с опушенной переменной xi (в суммах (1) и (3) отсутствуют слагаемые cixi и ai xi соответственно); второй вариант также порождает задачу с опущенной переменной xi, но, кроме того, в критерии (1) добавлена константа ci, а в ограничении (2) b надо заменить на (b-ai).
По обеим ветвям (xni=0 и xni=1) получаем подзадачи, по-прежнему являющиеся задачами о ранце. Таким образом, для дальнейших ветвлений может использоваться всё та же теорема Данцига.
Вершина с нижней и верхней оценками (wk, vk) считается неперспективной и отбрасывается из дальнейшего рассмотрения, если имеется какая либо другая вершина с верхней и нижней оценками (w1, v1) такими, что v1>wk
|