Целочисленная оптимизация с булевыми переменными (задача о рюкзаке)
К задачам целочисленного
программирования относят также задачи, где некоторые переменные могут принимать
всего два значения: 0 и 1. Такие переменные называют булевыми, двоичными,
бинарными. К таким задачам относится так называемая задача о рюкзаке.
В общем виде задача о рюкзаке формулируется следующим способом: имеется рюкзак определенного объема и неограниченное количество предметов. Для каждого предмета известен его объем (вес) и ценность (стоимость, эффективность). В рюкзак можно положить целое число предметов различного типа. Цель состоит в том, чтобы суммарная ценность всех находящихся в рюкзаке предметов была максимальна, а их объем (вес) не превышал заданной величины. К подобной формулировке может быть сведена задача максимального использования грузоподъемности подвижного состава, грузовместимости судна, автомобиля и т. п. Такая задача часто возникает при выборе оптимального управления в экономико-финансовых областях (например распределение бюджета отдела по проектам).
Пример. Задача о рюкзаке.
Имеются 6 предметов, каждый из которых характеризуется весом и ценой. Нужно выбрать из них такие предметы, чтобы их общий вес не превышал 12, а суммарная цена была максимальной (так называемая "задача о рюкзаке").
|
|
А |
В |
С |
D |
|
1 |
Предмет |
Вес |
Цена |
Наличие |
|
2 |
х1 |
9 |
20 |
0 |
|
3 |
х2 |
8 |
16 |
0 |
|
4 |
хЗ |
6 |
11 |
0 |
|
5 |
х4 |
5 |
9 |
0 |
|
6 |
х5 |
4 |
7 |
0 |
|
7 |
хб |
1 |
1 |
0 |
|
8 |
|
|
|
|
|
9 |
-12 |
‘=СУММПРОИЗВ(Наличие,Вес)‑12 | ||
|
10 |
|
|
|
|
|
11 |
0 |
‘=СУММПРОИЗВ(Наличие,Цена) | ||
Решение.
- В блоке А2:А6 размещены условные названия предметов, а в соседних столбцах — их вес и цена.
- В блоке D2:D6 фиксируется наличие (1) или отсутствие (0) предмета в наборе. Блокам даны имена в соответствии с их заголовками.
- В Решателе задаем: максимизировать $А$11 по переменным "наличие" при ограничениях $А$9<=0 и наличие=двоичное. Последнее ограничение задается так.
- В диалоговом окне "Добавление ограничения" сначала нажимаем F3 и вставляем имя "наличие", в выпадающем списке выбираем "двоич".
- После запуска Решателя значение целевой ячейки равно 23, а двоичные значения: 0, 1, 0, 0, 1,0, т.е. нужно выбрать второй и пятый предметы.