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

⇐ ПредыдущаяСтр 6 из 8Следующая ⇒

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

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.

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

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.

Решение задачи о ранце методом динамиического программирования (табличная форма).

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

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

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

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

Все параметры задачи целые неотрицательные числа.

Обозначим через Z (k, p) - задачу, при условиях, что предметов k, k m (для нашей задачи m=4), а вместимость ранца p, p v(0) (для нашей задачи v(0)=9 ). Пусть R(k, p) - оптимум задачи Z(k, p). Тогда оптимум исходной задачи совпадает с оптимумом задачи Z(m, v(0)) и равен R(m, v(0)). Для определения величин R(m, v(0)) построим следующие рекуррентные соотношения:

R(k+1, p) = R(k, p), если v(k+1) > p, (1)

R(k+1, p) = max { R(k, p), c(k+1) + R(k, p- v(k+1)}, если p> v(k+1) + 1.

Эти рекуррентные соотношения, с учетом граничных условий

R(1, p) = 0, если с(1) > p, (2)

R(1, p) = c(1), если c(1) < p+1,

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

Результаты вычислений по рекуррентным соотношениям будем представлять в виде таблицы с m=4 строками и v(0)=9 столбцами, в которой приводятся значения соответственных величин R(k, p). Для того чтобы решить исходную задачу о ранце необходимо заполнить клетку таблицы с координатами: m=4, v(0)=9. Для этого не требуется заполнить все клетки таблицы, а лишь те, которые используются для вычиcления значений величины R(4, 9).

				v(i)	c(i)
5(1)	5(1)	5(1)	5(1)
5(1)	7(2)		12(1, 2)
5(1)			13(2, 3)
			13(2, 3)

Таблица заполняется следующим образом.

R(4, 9)=max { R(3, 9), c(4)+ R(3, 9-v(4))}= max { R(3, 9), c(4)+ R(3, 9 - 7}=

max { R(3, 9), c(4)+ R(3, 2}. Таким образом, для заполнения ячейки (4, 9) необходимо заполнить ячейки (3, 9) и (3, 2). В свою очередь для заполнения этих ячеек необходимо заполнить другие ячейки. Первой заполняется ячейка (1, 1). В ней, согласно граничным условиям (2), значение R(1, 1)=0. Затем, используя рекуррентные соотношения (1) заполняются остальные ячейки, пока ячейка с номером (4, 9) не будет заполнена. Решение задачи о ранце, согласно содержанию ячейки (4, 9), будет иметь вид:

x’(1)=0, x’(2)=1, x’(3)=1, x’(4)=0. Значение оптимума задачи F( x’ )=13.

Решение задачи о ранце методом динамического программирования (рекуррентная схема).

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

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

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

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

Множество предметов G={1, 2, 3, 4} - множество номеров предметов.

Обозначим через W(G’, p) - суммарную полезность тех предметов, которые будут положены в ранец из предметов множества G’, при вместимости ранца p, и наилучшем способе выбора предметов ( с точки зрения функционала задачи),

G’ G, p v(0).

Обозначим через S = { i/ c(i) p, i G’}.

Тогда

W(G’, p) = max [ c(i) + W(G’\{i}, p - v(i)], (1)

где максимум берется по предметам из множества S.

Рекуррентные соотношения (1), с учетом граничных условий:

W(G’, p) = 0, если S - пустое множество, позволяют решить задачу о ранце.

W(G={1, 2, 3, 4}, p=9) =max [5+ W({2, 3, 4}, 7), 7+ W({1, 3, 4}, 6), 6+ W({1, 2, 4}, 4), 3+ W({1, 2, 3}, 2)];

Отдельно найдем величины:

W({2, 3, 4}, 7)=max [7+ W({3, 4}, 4), 6+ W({2, 4}, 2), 3+ W({2, 3}, 0)=max(7, 6, 3)=7(2).

W({1, 3, 4}, 6)=max[5+ W({3, 4}, 4), 6+ W({1, 4}, 1), ]=max(5, 6)=6(3).

W({1, 2, 4}, 4)=max[5+ W({2, 4}, 2), 7+ W({1, 4}, 1)]=max(5, 7)=7(2).

W({1, 2, 3}, 2)=5(1).

Таким образом, получили:

W(G={1, 2, 3, 4}, p=9)=max(5+7, 7+6, 6+7, 3+5)=13(2, 3).

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

x’ =(0, 1, 1, 0). F( x’ )=13.

Решить следующие задачи о ранце:

а)Методом ветвей и границ.

б)Методом динамического программирования (табличная форма).

в)Методом динамического программирования (рекуррентная схема).

Задача 1.1.

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

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

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

Задача 1. 2.

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

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

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

Задача 1.3.

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

5x(1)+1x(2)+3x(3)+5x(4) 8

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

Задача 1.4.

10x(1)+7x(2)+8x(3)+4x(4) max,

2x(1)+5x(2)+6x(3)+7x(4) 11

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

Задача 1.5.

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

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

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

Задача 1.6.

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

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

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

Задача 1.7.

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

2x(1)+4x(2)+3x(3)+6x(4) 7

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

Задача 1.8.

4x(1)+8x(2)+7x(3)+3x(4) max,

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

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

Задача 1.9.

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

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

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

Задача 1.10.

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

3x(1)+2x(2)+6x(3)+5x(4) 8

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

⇐ Предыдущая 1 2 3 4 567 8 Следующая ⇒