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

Решение задачи о ранце

ЗАДАЧНИК С РЕШЕНИЕМ ТИПОВЫХ ЗАДАЧ

Задачи о назначениях с индивидуальными предпочтениями

Рассматривается задача о назначении исполнителей по работам при условиях, что исполнителями на множестве работ заданы предпочтения, т.е., каждый исполнитель упорядочивает все работы в порядке своих индивидуальных предпочтений независимо от производительностей.

Решение задачи о назначениях назовем некомпроментируемым, если не существует другого решения задачи о назначениях, при котором ни одному из исполнителей не будет назначена работа “худшая” по его предпочтениям, а хотя бы одному - “лучшая”.

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

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

Индивидуальные процедуры метода.

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

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

Назначаем очередного исполнителя на “лучшую” для него (в смысле его индивидуальных предпочтений) работу, еще не назначенную другим исполнителям.

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

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

Из начальной вершины необходимо осуществить ветвление по n направлениям, где n - количество работ), причем i -ое направление соответствует назначению исполнителя с номером i на работу, “лучшую” по его индивидуальным предпочтениям. Далее ветвление осуществляется из очередной вершины по s направлениям, где s - количество исполнителей, ещё не назначенных на работы.

Рассмотрим задачу о ранце с четырьмя предметами.

5x(1)+7x(2)+3x(3)+ 6x(4) max,

2x(1)+3x(2)+7x (3)+5x(4) 9,

x(i) {0,1}, i=1,2,3,4.

Переходим к релаксации задачи о ранце, сделав её приведенной (5/2>7/3>6/5>3/7):

5x(1)+7x(2)+6x(3)+3x(4) max,

2x(1)+3x(2)+5x(3)+7x(4) 9,

0 x (i) 1, i=1,2,3,4.

Строим оптимальное решение полученной задачи, используя рекуррентные соотношения из теоремы Данцига:

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

Получим x’(1)=1, x’(2)=1, x’(3)=4/5, x(4)=0.

Верхняя оценка V для исходной задачи о ранце находится следующим образом:

H= F(x’). Так как все коэффициенты целевой функции целые числа, то верхняя оценка может быть уменьшена. Величина V тогда определяется как целая часть от F(x’):

V= [5+7+6*4/5] = 16.

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

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

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

Для нашего примера: y(1)=1, y(2)=1, y(3)=0, y(4)=0.

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

H=5+7=12.

Таким образом, мы установили, что оптимум исходной задачи (значение критерия на оптимальном решениями) находится в интервале от 12 до 16.

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

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

Для нашего примера, так как переменная x’(3)=4/5, то в качестве направления для ветвления выберем переменную x(3).

Проводим зондирование в двух направлениях:

Первое направление: x(1), x(2) и x(4) - неизвестные, x(3)=1.

Второе направление: x(1), x(2) и x(4) - неизвестные, x(3)=0.

В первом направлении, решая непрерывную приведенную задачу, находим оптимальное решение: x’(1)=1, x’(2)=2/3, x’(3)=1, x’(4)=0.

Верхняя оценка в этом направлении V=15, нижняя оценка в этом направлении H=11.

Во втором направлении, решая непрерывную приведенную задачу о ранце алгоритмом Данцига, получим оптимальное решение: x’(1)=1, x’(2)=1, x’(3)=0, x’(4)=4/7.

Верхняя оценка в этом направлении V=13, нижняя оценка в этом направлении H=12.

Для первого направления будем проводить зондирование по переменной x(2), так как значение этой переменной в оптимальном решении непрерывной задачи о ранце дробное (x’(2)=2/3).

В первом направлении:

Случай 1.

x(1), x(4) - неизвестные, x(2)=1, x(3)=1. Оптимальное решение непрерывной задачи о ранце имеет в этом случае вид: x’(1)=1/2, x’(2)=1, x’(3)=1, x’(4)=0.

Оценки, соответствующие этому решению, принимают значения: V=15, H=13.

Случай 2.

x(1), x(4) - неизвестные, x(2)=0, x(3)=1. Оптимальное решение непрерывной задачи о ранце имеет в этом случае вид: x’(1)=1, x’(2)=0, x’(3)=1, x’(4)=2/7.

Оценки, соответствующие этому решению, принимают значения: V=11, H=11.

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

Анализ полученных результатов позволяет применить процедуру отбрасывания:

- так как в случае 2, где V=11 и H=11 значение верхней оценки V=11 (лучшее, что можно получить в этом направлении) меньше значения нижней оценки H=13 (существует решение исходной задачи о ранце со значением критерия 13) в случае 1, то первое направление может быть отброшено не в ущерб оптимальности;

- так как во втором направлении, где V=13, а H=12, верхняя оценка не больше нижней оценки H=13 для случая 1, то второе направление может быть отброшено не в ущерб оптимальности.

Для оставшегося случая 1 дробление необходимо осуществлять в направлении переменной x(1), так как в оптимальном решении непрерывной задачи о ранце значение этой переменной x’(1)=1/2 (дробное значение переменной).

Вариант 1.

x(4) - переменная, x(1)=1, x(2)=1, x(3)=1.

В этом случае уравнение x(4) 9-2-3-5 не имеет неотрицательного решения, отсюда это направление не рассматривается.

Вариант 2.

x(4) - переменная, x(1)=0, x(2)=1, x(3)=1.

Оптимальное решение полученной непрерывной задачи имеет вид:

x’(1)=0, x’(2)=1, x’(3)=1, x’(4)=1/7.

Оценки, соответствующие этому направлению имеют вид:

V=[7+6+3*1/7]=13.

H=7+6=13.

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

x’(1)=0, x’(2)=1, x’(3)=1, x’(4)=0.

Значение оптимума для исходной задачи о ранце равно

F(x’) = 13.

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