5.4. Задача про рюкзак (завантаження транспортного засобу)

Необхідно завантажити транспортний засіб (судно, літак, вагон, вантажний автомобіль) або рюкзак вантажоємністю, наприклад, G = 20 т наявними речами з вагою g_i та вартістю v_i таким чином, щоб сумарна вартість вантажу була максимальною. Дані про вагу g_i та вартість v_i речей наведені в таблиці. Математична модель задачі така:

цілі числа.

де x_j – кількість завантажених речей j.

Річ	Вага, т	Вартість, тис.грн	Максимальна кількість, шт
1	3	30	6 (|20/3|)
2	5	60	4 (|20/5|)
3	9	80	2 (|20/9|)

1-а ітерація (використання x₁, x₂)

Перша ітерація включає перебір всіх можливих варіантів x₁ та x₂ з метою визначення займаної ваги та вартості. Потім необхідно скласти підсумкову таблицю ітерації, впорядкувавши записи за зростанням ваги з вибором найкращих вартісних показників з першої таблиці. Ці показники знадобляться при доданні потрібної ваги з x₁ та x₂ в наступній ітерації.

Вага, т	Вартість, тис.грн	x1	x2		Вага, т	Вартість, тис.грн	x1	x2
0 3 6 9 12 15 18	0 30 60 90 120 150 180	0 1 2 3 4 5 6	0 0 0 0 0 0 0		0-2 3-4 5-7 8-9 10-12 13-14 15-17 18-20	0 30 60 90 120 150 180 210	0 1 0 1 0 1 0 1	0 0 1 1 2 2 3 3
5 8 11 14 17 20	60 90 120 150 180 210	0 1 2 3 4 5	1 1 1 1 1 1
10 13 16 19	120 150 180 210	0 1 2 3	2 2 2 2
15 18	180 210	0 1	3 3

2-а ітерація (використання x₁, x₂, x₃)

Друга ітерація полягає в поступовому збільшенні x₃ від 0 до 2 та заповненні вагового резерву значеннями з підсумкової таблиці першої ітерації (адже вони є оптимальними для x₁ та x₂). Складання підсумкової таблиці аналогічне.

Вага, т	Вартість, тис.грн.	x1	x2	x3		Вага, т	Вартість, тис.грн.	x1	x2	x3
0 3 5 8 10 13 15 18	0 30 60 90 120 150 180 210	0 1 0 1 0 1 0 1	0 0 1 1 2 2 3 3	0 0 0 0 0 0 0 0		0-2 3-4 5-7 8-9 10-12 13-14 15-17 18-20	0 30 60 90 120 150 180 210	0 1 0 1 0 1 0 1	0 0 1 1 2 2 3 3	0 0 0 0 0 0 0 0
9 12 14 17 19	80 110 140 170 200	0 1 0 1 0	0 0 1 1 2	1 1 1 1 1
18	160	0	0	2

Відповідь: x₁ = 1, x₂ = 3, x₃ = 0 з вартістю 210 тис.грн.