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

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

В качестве релаксации задачи о ранце рассмотрим следующую задачу линейного программирования (здесь используются обозначения раздела 2.3):

v(i) x(i) v(0), (1)

 

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

 

 

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

 

Задачу (1) -(2) будем называть непрерывной задачей о ранце. Её решение может быть получено, например симплекс-методом, однако, специфика задачи позволяет для её решения предложить более эффективный алгоритм. Этот алгоритм основан на следующей теореме Данцига.

Непрерывную задачу о ранце назовем приведенной, если отношениявеличин c(i, j) (полезностей ) к соответствующим величинам v(i, j) (весам) не возрастают с ростом номеров i (предметов). Очевидно, что любую задачу о ранце путем перенумерации предметов, можно сделать приведенной.

 

Теорема Данцига.

Оптимальное решение непрерывной приведенной задачи о ранце находится с помощью следующих рекуррентных соотношений:

x(i) = min ( v(i), v(0) - v(j) x(j))/v(i), i=1, 2,..., m.

 

Пусть x - оптимальное решение непрерывной приведенной задачи. Тогда верхняя оценка V для исходной задачи о ранце находится следующим образом:

H= F( x ). Если все коэффициенты c(i), 1=1, 2,..., m, целые числа (этого всегда можно добиться путем приведения указанных величин к общему знаменателя), то верхняя оценка может быть уменьшена. Величина V тогда может определяться как целая часть от F( x ).

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

Пусть y - m мерный целочисленный вектор, который получается с использованием оптимального решения x непрерывной задачи о ранце следующим образом:

y(i) = x(i), если x(i) - целое, и y(i) = 0 в противном случае.

Тогда H = F( y ) - является достижимой нижней оценкой, так как вектор y будет допустимым решением исходной (целочисленной) задачи о ранце.

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

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

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

 

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

 

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

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

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) при определении верхней оценки. Если такой переменной нет, то в качестве направления для ветвления может быть выбрана любая ещё не рассмотренная переменная.

 

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. I. Предмет и задачи дидактики
2. II. Предполагаемые союзники и их задачи
3. III. Целевые установки, задачи и направления обеспечения транспортной безопасности
4. А теперь мое решение проблемы
5. А теперь мое решение проблемы
6. Алгоритм решения транспортной задачи
7. Анализ подходов и методов решения задачи
8. Анализ современного состояния АПК в России: задачи и экономическая стратегия развития
9. БИЛЕТ 1. Цели, задачи и основные принципы православной педагогики. Сотериологический характер педагогических воззрений Святых Отцов Церкви
10. БИЛЕТ 9. Вопрос 2. Психолого-педагогические задачи процесса духовно-нравственного становления личности на этапе вхождения в мир (наследство, зачатие, внутриутробное развитие, роды, новорожденность).
11. Бухгалтерский учет: его задачи, функции и
12. В итоге в Иерархии принято решение, что в Иерархию