Задача о рюкзаке

Имеется n предметов. Вес i-го предмета равен p_i, его ценность выражается числом с_i. Требуется найти совокупность предметов минимального веса при условии, что ценность этой совокупности не должна быть меньше заданного числа С. (Другой вариант задачи – найти совокупность максимальной стоимости, вес которой не превосходит P).

Введем переменные x_i, i=1,…,n. Будем считать, что x_i=1 означает, что i-й предмет вкладывается в рюкзак, x_i=0 – не вкладывается. Тогда математическая модель задачи запишется так:

f(x) = p₁x₁+…+p_nx_n →min   (суммарный вес всех предметов в рюкзаке – минимальный),

c₁x₁+…+c_nx_n ≥ C  (суммарная ценность не меньше требуемой),

 x₁,…,x_n∈{0; 1}.

Выберем следующий метод ветвления: выбирается некоторая переменная x_k, после чего в одной части вариантов полагается x_k=0, а в другое множество поместим все планы наполнения рюкзака, в которых x_k=1.

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

Для получения оценки снизу будем находить минимум функции f(x) на более широком множестве, чем требуется в задаче: вместо условий x₁,…,x_n∈{0; 1} будем использовать условия x₁,…,x_n∈[0; 1]. При этом получается обычная задача линейного программирования, решение которой можно найти даже без применения симплекс-метода.

30. Метод ветвей и границ. Задача коммивояжера.

Классическая задача коммивояжера состоит в следующем. Имеется n населенных пунктов, соединенных дорогами. Расстояния (или в другом варианте – стоимость проезда) между всеми пунктами заданы матрицей A=(a_ij). Если между пунктами i и j нет соединяющей их дороги, то a_ij=∞.

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

Для решения данной задачи методом ветвей и границ выберем следующий способ ветвления: будем выбирать одну из дорог (например, из пункта k в пункт m) и к одному из подмножеств отнесем все маршруты, проходящие через данную дорогу, а к другому – все маршруты, не использующие ее.

В первом случае (когда мы заявим, что во всех маршрутах будет присутствовать дуга (k,m)), удалим из матрицы А k-ю строку и m-й столбец, после чего остальные звенья маршрута будем искать по оставшимся элементам матрицы.

Во втором случае (когда мы заявим, что во всех маршрутах не будет использоваться дуга (k,m)), положим a_km = ∞, т.е. рассмотрим аналогичную исходной задачу, в которой дуги (k,m) просто нет.

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

В k-й строке матрицы А указываются длины путей, выходящих из пункта k. В каждом из маршрутов мы используем ровно один из них. Поэтому, если мы вычтем из всех элементов строки число N, то мы получим другую задачу, в которой длины всех маршрутов уменьшатся ровно на N (по сравнению с такими же маршрутами в исходной задаче). То же самое касается и столбцов.

В итоге для вычисления оценки в начальной задаче необходимо:

1) в каждой строке найти минимум b(i) и вычесть его из всех элементов строки;

2) в каждом столбце получившейся матрицы найти минимум c(j) и вычесть его из всех элементов столбца;

3) сумма Z всех b(i) и c(j) дает значение оценки, которая показывает, на сколько мы уменьшили длины всех маршрутов.