Оптимальная загрузка транспортного средства
(задача о рюкзаке)
Транспортное средство грузоподъёмностью M=101 усл. ед. массы загружается предметами трёх типов Т1, Т2, Т3, масса m и стоимость r усл. ден. ед. каждого из которых известны и представлены в таблице в соответствии с вариантом. Найдите такой способ загрузки, при котором стоимость перевозимого груза была бы максимальной.
M Т1
Т2
Т3
m r m r m r
101 18 22 23 31 33 48
Решение:
Поиск оптимального решения включает 3 этапа (по числу загружаемых типов предметов).
Условная оптимизация
1 этап. Грузим предметы первого типа. При загрузке предметами Т1 на их долю х теоретически может остаться любая часть грузоподъёмности от 0 до 101 (так мы учитываем возможные состояния системы на предпоследнем шаге). В зависимости от этой доли, переменная, характеризующая последний шаг, т.е. u1 может принимать целый набор значений. Например, при х = 15 u1 = 0, т.к. предмет 1-го типа весит 18, а при х = 52 u1 может принять значения 0, 1, 2. Ясно, что в последнем случае максимальная эффективность достигается при u1 = 2 и составляет φ1 (52) = 22*2=44. Это значение u1 будем считать условно-оптимальным для данного значения х и обозначать u01.
Составим таблицу значений φ1(x) для х от 0 до 101 с шагом 1, в которую будем вносить соответствующее u01. Поскольку одно и то же значение φ1(x) и u01 будем получать для целого промежутка значений х, то для краткости вместо нескольких строк в соответствующей графе таблицы укажем этот промежуток (таблица 1). Уравнение Беллмана для 1-го этапа имеет вид
Таблица 1
Условно-оптимальные решения первого этапа
x u01
0-17 0 0
18-35 22 1
36-53 44 2
54-71 66 3
72-89 88 4
90-101 110 5
2 этап. Переходим к переменной u2, используя рекуррентное соотношение Беллмана
т.е. загружаем оптимально предметами 1-го и 2-го видов. Чтобы не загромождать изложение, покажем, как рассчитать только для некоторых значений доли грузоподъёмности х, приходящейся на предметы 1-го и 2-го типов, а затем приведём всю таблицу целиком. Например, при х = 50 переменная u2 может принимать значения только 0, 1 или 2, т.к. 2. Итак, если u2 = 0 (т.е. мы можем не брать предметы Т2), то все 50 единицы массы приходятся на предметы Т1. По таблице 1 находим, что в этом случае максимальная эффективность φ1 (50) равна 44. Если u2 = 1 (берём один предмет второго типа), то на долю предметов Т1 останется грузоподъёмность 50 – 23 = 27, и по таблице 1 находим, что в этом случае φ1 (27) =22, следовательно, согласно уравнению Беллмана, эффективность такого размещения равна 31*1+22=53. Если u2 = 2 (берём два предмета второго типа), то на долю предметов Т1 останется грузоподъёмность 50-2*23 =4, и по таблице 1 находим, что в этом случае φ1 (4) =0, следовательно, согласно уравнению Беллмана, эффективность такого размещения равна 31*2+0=62.
Для всех возможных значений х получим таблицу и u02
Таблица 2
Условно-оптимальные решения второго этапа
x u02
0 17 0 0
18 22 22 0
23 35 31 1
36 45 44 0
46 53 62 2
54 68 66 0
69 71 93 3
72 89 93 3
90 91 115 3
92 101 124 4
3 этап. Переходим к переменной u3, т.е. загружаем оптимально предметами 1-го, 2-го и 3-го видов. Для расчёта значений используем рекуррентное соотношение Беллмана
Проводя рассуждения, аналогичные рассуждениям этапа 2, получаем таблицу
Таблица 3
Условно-оптимальные решения второго этапа
x u03
0 17 0 0
18 22 22 0
23 32 31 0
33 35 48 1
36 45 48 1
46 53 62 0
54 65 70 1
66 68 79 1
69 71 96 2
72 89 96 2
90 91 127 2
92 98 127 2
99 101 144 3
Таким образом, максимальная стоимость погруженных предметов при
