Практическая работа 12 Решение задачи о рюкзаке приближенными и точными алгоритмами

Задача о рюкзаке и ее варианты широко используются для моделирования большого числа практических задач управления, таких как выбор проектов, распределение капитала, комбинаторные аукционы, расположение предметов в системах сборки по заказу и др. [3, 6, 7].

Одним из частных случаев задачи о рюкзаке является одномерная булева задача о рюкзаке, которая может быть сформулирована следующим образом. Рассмотрим рюкзак с объемом равным b. Пусть существует n различных предметов. Предмет j занимает объем a_j, при этом его ценность равна c_j. Цель задачи состоит в максимизации выгоды от помещенных в рюкзак предметов. Таким образом, задача может быть сформулирована как задача булева линейного программирования в следующем виде:

Если условие  заменить условием , то получим задачу об одномерном целочисленном рюкзаке. В этом случае имеется n типов предметов и требуется определить, сколько предметов каждого типа нужно поместить в рюкзак, чтобы они имели максимальную суммарную ценность.

Для решения задачи о рюкзаке разработан целый ряд алгоритмов и методов: динамическое программирование [6], метод ветвей и границ [3], метод перебора L-классов [2] и другие.

В случае небольших n   одномерная задача о рюкзаке может быть также решена в табличном процессоре MS Excel. При этом исходные данные задачи записываются также, как и для задачи ЛП, но в окне Поиск решения, Ограничения необходимо указать, что переменные являются целыми, либо булевыми (рис. 10).

Рис. 10. Диалоговое окно Поиск решения для задачи о рюкзаке.

 При больших n точное решение задачи может потребовать значительных затрат машинного времени. Поэтому актуальной является разработка приближенных алгоритмов. Самый известный приближенный алгоритм – это так называемый  “жадный” алгоритм. Опишем этот алгоритм по шагам для булевого случая.

«Жадный» алгоритм.

Шаг 1. Упорядочить предметы по не возрастанию удельной полезности c_j / a_j,

т.е. так, чтобы выполнялось соотношение

                              ,  

положить   k:=1  и перейти на шаг 2.

Шаг 2. Если    a_k ≤ b,  то положить   x_k:=1, b:=b – a_k, иначе x_k:= 0.

Увеличить k на единицу и перейти на шаг 3.

Шаг 3. Если   k > n,  то алгоритм завершает работу, иначе перейти на шаг 2.

Задание Решить задачу о рюкзаке в пакете MS Excel. Разработать алгоритм полного перебора и «жадный» алгоритм для задачи о рюкзаке [8]. Найти точное и приближенное решение задачи о рюкзаке, используя реализованные алгоритмы.