Задача о ранце методом ветвей и границ

Задача о загрузке (задача о ранце) и различные её модификации широко применяются на практике в прикладной математике, криптографии, экономике, логистике, для нахождения решения оптимальной загрузки различных транспортных средств: самолетов, кораблей, железнодорожных вагонов и т.д.

С помощью математических моделей ранцевого типа

описываются следующие прикладные задачи:

- задача загрузки уникального оборудования,

- задача формирования портфеля заказов, обеспеченного

ресурсами,

- задача объемного планирования для предприятия,

- задачи загрузки контейнеров и др.

Существует несколько модификаций задачи.

1. классическая

2. классическая в обратной постановке

3. с дробимыми предметами

4. задача с двумя ранцами

5. многомерная

6. бикретериальная

1.Классическая задача о ранце

Имеется ранец, в который можно поместить n предметов. У каждого предмета есть свой вес(v_i) и своя стоимость (c_i). В ранец может влезть вес не больше W. Все предметы взять нельзя. Предметы не дробимы.

Вводим переменные х₁, х_2,… х_n

1, предмет в ранце

x_i=

0, предмет не в ранце

i=1…n

Математическая формулировка задачи:

(1)

(2)

x_i {0,1}, c_i>0, v_i>0, i=1..n (3)

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

Вводим переменные у₁, у_2,… у_n

1, предмет вне ранца

у_i=

0, предмет в ранце

(1)

(2)

у_i {0,1}, c_i>0, v_i>0, i=1..n (3)

3.Задача о ранце с дробимыми предметами

(1)

(2)

x_i [0,1], c_i>0, v_i>0, i=1..n (3)

4.Задача о двух ранцах

В первый ранец нельзя вложить больше W₁

Во второй ранец нельзя вложить больше W₂

Есть n предметов. У каждого своя стоимость (с_i) и свой вес(v_i).

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

Вводим переменные:

x_i- для 1 ранца.

у_i – для 2 ранца.

(1)

(2)

(3)

(4)

у_i {0,1}, x_i {0,1}, c_i>0, v_i>0, i=1..n(5)

5.Многомерная задача о ранце(m-мерная)

(1)

(2)

x_i {0,1}, c_i>0, _i>0, i=1..n

_i, - m –мерные вектора

6.Бикретериальная задача о ранце

(1)

(2)

(3)

x_i {0,1}, c_i>0, v_i>0, i=1..n (4)

Классическая задача о ранце методом ветвей и границ.

Основан на трёх компонентах:

1. способ получения верхних оценок

2. способ получения нижних оценок

3. способ ветвления

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

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

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

Вершину называют закрытой, если ветвление выполнено. Остальные - открытые.

Пример 1(однокритериальная)

x_i {0,1}

x₁=1 x₂=1 x₃=1 x₅=1 x₄=3/4

2+2+4+5+4*3/4=13+3=16

1)Если x₄=1

x₁=1 x₃=1 x₅=1 x₂=1/2

2+4+4+5+2*1/2=15+1=16

Если x₄=0

Нижняя граница совпадает с верхней и равна 13

2)Если x₂=1

x₁=1 x₃=1 x₅=3/4

2+2+4+4+5*3/4=12+5=17

Если x₂=0

Нижняя граница совпадает с верхней и равна 15

3)Если x₅=1

x₁=1 x₃=2/3

2+2+4+5+4*2/3=13+4=17

Если x₅=0

Нижняя граница совпадает с верхней и равна 12

3)Если x₃=1

Нижняя граница совпадает с верхней и равна 15

Если x₃=0

Нижняя граница совпадает с верхней и равна 13

Ответ: 15

x₁=1 x₂=0 x₃=1 x₄=1 x₅=1.

Пример 2(бикритериальная)

Список литературы

1.Коган Д.И. «Динамическое программирование и дискретная многокритериальная оптимизация». Нижний Новгород: Изд-во ННГУ, 2004

2.Коган Д.И. «Многокритериальные задачи принятия решений в системах управления». Москва: МГУПИ,2008

3. Методическое пособие по курсу "Математические основы информатики" для студентов факультета ВМК, специальность "Прикладная информатика".