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

Общая схема метода ветвей и границ Джеффриона-Марстена

Общая схема метода ветвей и границ Джеффриона-Марстена включает в себя следующие шаги:

Шаг 1.

Открыть список задач кандидатов, включив в него исходную задачу. Присвоить рекорду большое число (малое число) для задачи на минимум (для задачи на максимум).

Шаг 2.

Провести анализ задач кандидатов с целью выяснения его не пустоты.

- если список не пуст, то перейти на следующий шаг 3,

- если список пуст, то решение задачи завершено: если значение рекорда не изменилось по сравнению с первоначальным, то задача не имеет решения, в противном случае - задача решена.

Шаг 3.

Выбрать, используя принятую стратегию, текущую задачу кандидата из списка всех кандидатов.

Шаг 4.

Выбрать релаксацию задачи кандидата.

Шаг 5.

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

- если множество допустимых решений задачи кандидата пусто, то перейти к шагу 2, исключив из списка рассматриваемую задачу кандидата.

- в противном случае проверить, есть ли у кандидата допустимое решение, лучше рекорда. Если есть, то перейти на шаг 6, если нет, то исключить эту задачу из списка и перейти к шагу 2.

Шаг 6.

Выяснить, получено ли оптимальное решение кандидата:

- если нет, то перейти к шагу 7.

- если да, то пересчитать значение нового рекорда, запомнить рекордное решение и перейти на шаг 2.

Шаг 7.

Продолжать поиск оптимального решения задачи кандидата?

- если нет, то перейти к шагу 8,

- если да, то модифицировать релаксацию рассматриваемого кандидата и перейти к шагу 5.

Шаг 8.

Разветвить кандидата и включить его потомки в список кандидатов, исключив из списка самого кандидата. Перейти на шаг 2.

Замечание 1.

В рассматриваемой схеме есть два блока, которые могут быть реализованы различными способами:

- выбор очередного кандидата с использованием стратегии (шаг 3),

- модернизация релаксации (блок 7).

Конкретная реализация этих блоков зависит от специфики исходной задачи.

Замечание 2.

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

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

В качестве релаксации задачи о ранце рассмотрим следующую задачу линейного программирования (здесь используются обозначения раздела 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 будет допустимым решением исходной (целочисленной) задачи о ранце.

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

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

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

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