Решение многомерной задачи о ранце методом ветвей и границ

Процедура оценок.

Рассмотрим многомерную задачу о ранце

v(i,j) x(i) b(j), j=1,2,...,m, (1)

x(i) {0,1}, (2)

F(x) = c(i) x(i) max. (3)

Назовем j-ой подзадачей о ранце задачу о ранце с ограничениями

v(i,j) x(i) b(j), (4)

x(i) {0,1}, (5)

F(x) = c(i) x(i) max. (6)

Рассмотрим новые ограничения

0 x (i) 1, i=1,2,...,m. (7)

Назовем j-ой непрерывной задачей о ранце задачу (4), (6), (7).

Для ее решения могут быть использованы рекуррентные соотношения теоремы Данцига (для этого задачу надо сделать приведенной).

Пусть x (j) - оптимальное решение j-той непрерывной задачи. Тогда в качестве верхней оценки исходной многомерной целочисленной задачи о ранце можно взять величину

V= min F(x (j)), (8)

где min берется по всем j=1,2,...,n.

Для уменьшения значения верхней оценки, в случае, когда все значения c(i), i=1,2,...,m, целые, можно взять целую часть правой части выражения (8).

Для определения нижней оценки рассмотрим m- мерный вектор y, с компонентами y(i) = 1, если все i -тые компоненты векторов x (j) равны 1 и y(i) = 0 в противном случае. Тогда нижняя оценка определяется величиной:

H= F(y).

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

Процедура ветвления.

В качестве направления для ветвления выбирается та переменная, которая является дробной в оптимальном решении непрерывной j-ой подзадачи о ранце, где j - номер той подзадачи, на котором достигается минимум выражения (8) при определении верхней оценки. Если такой переменной нет, то в качестве направления для ветвления может быть выбрана любая ещё не рассмотренная переменная.

Дата добавления: 2017-02-01; Просмотров: 76; Нарушение авторских прав?; Мы поможем в написании вашей работы!