1.5. Лабораторная работа №5: Задача о рюкзаке (14.1)

Имеются элементы, обладающие весом и полезностью, из которых необходимо составить набор («собрать рюкзак»). Данный набор должен обладать максимальной полезностью при условии соблюдения ограничений по допустимому весу рюкзака.

Компоненту a_i ставится в соответствие полезностьu_iи вес v_i. Максимально допустимый вес рюкзакаM. Задача составить набор компонент, максимизирующий суммарную полезность U при условии ∑v_i<= M .

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

В многокритериальном (многомерном) случае компоненту a_iставится в соответствие вектор полезности u_i=(u₁…u_n) и вес v_i. Простой одномерный случай можно непосредственно обобщить на многомерный случай, тогда u_iесть некоторая функция полезности от вектора полезности u_i=f(u_1…u_n).

Пример.Имеется 10 элементов с полезностью 12, 53, 14, 73, 33, 51, 53, 50, 54, 78 и весом 6, 2, 5, 6, 4, 8, 7, 8, 2, 2 соответственно. Составить рюкзак, вес которого не должен превышать 18.

Решение.Внесем условия задачи в таблицуExcelв столбцы «i» (номер элемента), «u_i» (полезностьi-го элемента) и «v_i» (весi-го элемента). Добавим также столбцы «Включен» (1 – если элемент включается в рюкзак, 0 – если элемент не включается в рюкзак), «U» и «V» (умножение столбца «Включен» на, соответственно, полезность и весi-го элемента). В итоге, просуммировав столбцы «U» и «V», получим суммарную полезность и вес включенных в рюкзак элементов.

Для решения задачи воспользуемся Поиском решения. Нам необходимо определить, какие элементы должны включаться в рюкзак, т.е. какие ячейки в столбце «Включен» должны равняться единице. При этом сумма полезности включенных в рюкзак элементов должна быть максимальной, а сумма весов этих элементов должна быть <= 18.

Обратите внимание на ограничение «D2:D11 = двоичное». Оно означает, что в этом диапазоне ячейки могут принимать значения только 0 или 1.

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

Таким образом, в рюкзак необходимо включить элементы 2, 4, 5, 9, 10, при этом вес рюкзака составит 16, а полезность 291.

Самостоятельное задание №8

Имеется 10 элементов с полезностью u_iи весомv_iсоответственно (i= 1…10). Составить рюкзак, вес которого не должен превышатьM.

Вар.	u1	u2	U3	u4	u5	u6	u7	u8	u9	u10	v1	v2	v3	v4	v5	v6	v7	v8	v9	v10	M
1	11	94	61	52	47	78	73	90	91	97	6	9	4	6	10	10	4	2	3	3	14
2	77	36	44	18	70	21	38	60	99	32	3	4	4	5	6	7	6	10	9	10	19
3	48	58	29	35	39	56	60	77	61	47	10	9	5	5	4	7	4	10	9	1	17
4	79	27	68	52	20	52	55	87	15	48	1	6	5	2	3	10	1	2	2	5	13
5	93	18	55	86	48	32	85	31	89	91	7	7	6	2	1	6	2	6	3	9	12
6	49	66	86	10	36	75	13	61	59	24	3	6	6	4	7	6	7	2	8	1	14
7	15	36	20	35	88	22	79	73	89	48	9	9	6	6	5	6	1	7	8	1	16
8	52	78	37	95	22	37	89	45	52	97	9	7	6	10	1	3	9	10	4	2	22
9	29	19	31	48	50	86	44	71	80	33	6	9	6	2	3	3	5	4	8	5	16
10	77	17	53	59	83	68	11	41	38	14	7	3	7	2	7	6	2	1	2	5	11
11	63	23	63	92	32	13	51	66	65	66	2	3	8	9	5	8	7	2	6	7	17
12	21	64	45	73	87	86	91	64	44	85	8	1	8	4	5	10	6	9	3	8	21
13	44	38	61	77	21	68	13	31	69	22	2	2	5	10	2	3	8	4	3	6	16
14	61	91	41	18	92	67	12	36	30	52	3	7	6	2	7	7	2	3	6	5	14
15	54	74	15	38	44	18	43	37	29	96	9	7	8	4	2	5	4	2	4	3	13
16	74	85	62	66	22	17	78	99	76	90	2	4	4	8	7	5	7	1	10	6	15
17	71	28	43	89	17	59	33	98	64	92	2	7	3	10	3	7	6	4	9	10	22
18	71	52	57	92	53	30	34	59	57	60	3	6	7	3	9	5	5	7	8	3	18
19	64	12	66	99	29	20	94	49	74	13	1	5	8	5	2	10	6	8	3	6	17
20	73	14	75	39	39	65	32	68	89	47	7	3	8	9	7	2	7	4	9	8	24
21	92	27	89	84	22	12	91	63	17	19	9	9	8	5	7	9	4	3	3	10	16
22	57	30	91	12	39	54	75	78	52	15	8	8	8	6	5	7	5	5	10	4	18
23	31	24	81	41	64	43	77	77	82	28	2	9	1	3	7	8	2	2	4	9	15
24	45	31	26	86	58	80	85	57	13	32	9	1	8	10	2	3	8	3	2	4	14
25	38	93	100	97	63	11	22	21	32	23	10	6	5	9	6	4	8	10	2	2	18
26	78	90	60	59	27	41	66	84	55	37	8	4	4	7	7	8	3	4	2	2	13
27	69	51	23	48	24	84	66	62	58	20	2	6	7	6	6	1	5	8	8	5	16
28	20	33	99	71	97	44	15	98	80	87	10	10	6	3	6	8	7	6	1	8	19
29	38	45	62	20	46	28	32	27	89	48	9	4	6	7	4	8	3	1	8	3	14
30	80	37	65	96	34	64	40	64	96	43	10	5	5	8	10	4	8	2	7	4	20
31	41	87	66	26	50	42	35	69	52	39	6	8	8	3	9	6	10	5	8	1	24
32	15	23	62	33	56	41	52	71	38	34	3	3	4	9	2	3	9	5	7	5	18
33	80	48	32	47	49	11	57	48	62	54	5	9	5	6	6	2	3	1	6	8	18
34	18	38	36	92	86	82	47	81	52	50	6	8	10	3	4	2	5	8	4	6	16
35	51	42	99	73	17	63	33	57	83	82	7	2	1	6	1	4	6	3	7	4	11
36	43	45	75	99	15	90	90	57	57	40	5	3	8	5	7	10	2	4	9	8	20
37	84	21	22	96	17	70	75	42	36	84	6	10	3	2	2	3	7	10	6	8	20
38	28	77	27	18	13	56	53	41	57	22	6	7	7	1	7	4	8	6	3	2	17
39	13	52	36	32	96	76	47	60	71	53	3	4	4	6	5	2	3	4	9	4	15
40	96	97	83	19	86	81	72	12	60	55	8	5	7	2	4	9	2	6	9	4	21
41	25	67	29	25	78	30	38	96	31	29	9	6	6	8	2	1	5	6	6	8	18
42	71	12	94	60	88	97	23	45	59	43	7	5	4	7	6	9	9	5	9	8	22
43	99	85	70	43	35	89	10	98	40	17	6	4	7	9	9	4	7	8	6	1	21
44	81	78	59	98	86	44	42	93	85	42	8	6	9	3	5	2	9	1	4	5	18
45	63	19	59	85	76	61	75	34	32	43	8	7	9	5	8	10	9	3	9	3	26
46	50	11	65	61	72	98	43	14	15	87	10	9	1	1	8	3	4	7	5	3	13
47	21	11	69	42	11	23	93	16	22	28	9	2	7	7	9	7	1	1	3	4	14
48	32	86	99	14	78	52	71	59	84	20	4	3	7	9	1	9	2	5	3	1	11
49	24	95	15	63	73	99	99	53	54	32	4	3	3	9	2	4	7	2	7	9	12
50	82	31	69	96	26	60	74	39	77	42	9	5	7	5	6	4	10	6	3	1	22
51	17	53	99	26	22	78	44	69	10	39	2	5	8	7	8	10	9	8	6	8	20
52	12	71	78	52	21	77	91	70	14	44	8	5	6	3	5	4	5	8	4	5	18
53	83	42	96	66	63	57	23	98	87	44	8	5	8	9	7	8	2	2	5	3	19
54	74	49	77	94	84	82	25	80	92	21	7	5	9	9	5	5	4	8	8	4	16
55	39	70	36	85	66	74	27	14	59	20	3	2	4	5	6	7	8	5	1	2	13
56	60	30	74	27	25	48	29	56	95	64	7	1	4	6	8	9	2	6	3	3	13
57	76	44	46	76	74	34	12	38	55	92	1	7	4	2	8	9	9	2	10	10	18
58	50	16	63	47	40	21	42	46	94	72	4	10	7	2	3	1	8	7	6	4	16
59	72	46	87	32	21	54	33	11	63	39	6	6	3	9	7	5	8	8	8	2	19
60	61	14	86	80	66	69	13	76	45	82	9	9	7	6	8	5	1	2	6	9	17