Автор: Пользователь скрыл имя, 23 Июня 2013 в 18:24, контрольная работа
На объект, вмещающий не более P единиц груза(по весу) необходимо загрузить четыре вида предметов так, чтобы общая стоимость груза была максимальной. Вес и стоимость приведены в таблице.
Задача 2.
На объект, вмещающий не более P единиц груза(по весу) необходимо загрузить четыре вида предметов так, чтобы общая стоимость груза была максимальной. Вес и стоимость приведены в таблице.
Номер предмета |
1 |
2 |
3 |
4 |
Вес WN |
3 |
4 |
6 |
7 |
Стоимость Vn |
15 |
18 |
16 |
19 |
Решение.
1.Используя
уже известный принцип
Fn(P)=max(xN*yN+fN-1(P-xNwN)), где xN пробегает значения из множества целых чисел 0,1,…[p/wN]
2.Максимальная грузоподъёмность P=21 у.е. веса, а груз состоит из предметов N=4 различных типа
Этап 1: предоставить последовательно ресурс P=0, 1, 2, …, 21 для какого-либо одного типа предмета, например 1-го, и найти условную стоимость такой политики.
Этап 2: предоставить ресурс P=0, 1, 2, …, 21 для каких-либо двух типов предметов (1-го по необходимости, т.к. его мы “погрузили” на предыдущем этапе, и, например 2-го) и найти условную стоимость груза при таком решении.
Этап 3: предоставить ресурс P=0, 1, 2, …, 21 для трех типов предметов аналогично.
Этап 4: предоставить ресурс p=0, 1, 2, …, 21 для всех четырех типов предметов, поскольку на этом последнем этапе уже нет выбора типа предметов и найти стоимость груза.
На 1-м
этапе
Предположим, что уже погружены
некоторые предметы 4-го и 3-го типа и 2-ого
типа, и осталось погрузить предметы только
1-го типа. Спрашивается, какова будет стоимость
груза, если для погрузки предметов 1-го
типа осталось некоторое свободное место,
т.е. некоторое количество грузоподъемности
(или ресурса)? Т.к. мы не знаем конкретное значение
этого оставшегося свободного места, то
нyжно просто перебрать все возможные значения
остатка, т.е. z должно пробежать все дискретные
значения P=0,1,2,…,21 грузоподъемности.
При этих значениях P вычисляем соответствующую
условную стоимость f1(P), запомнив ее
значения для следующего этапа. В табл.
ниже приведены расчеты этого этапа.
Предположим, что для предметов 1-го и 2-ого типа осталось P единиц грузоподъемности |
Решение |
Условный максимальный доход |
0..4 |
X1=0 x2=0 X1=0 x2=1 X1=1 x2=0 |
0 18 15 |
5..7 |
X1=1 x2=1 X1=2 x2=0 |
33 30 |
8.. |
X1=0 x2=2 |
36 |
9..12 |
X1=2 x2=1 X1=1 x2=2 X1=3 x2=0 X1=0 x3=3 |
48 51 45 54 |
13..15 |
X1=2 x2=2 X1=1 x2=3 |
66 69 |
16..18 |
X1=3 x2=2 X1=2 x2=3 |
81 84 |
19..21 |
X1=3 x2=3 |
99 |
На 2-м
этапе
Предположим, что уже погружены предметы
4-го типа, и осталось погрузить предметы
1-го и 2-го и 3-его типов. Спрашивается, какова
будет стоимость груза, если для рассматриваемого
этапа осталось p=0, 1, 2, …, 21 единиц грузоподъемности?
Здесь также, как и на предыдущем этапе
оптимизации величина возможного остатка
грузоподъемности P пробегает все
возможные целочисленные значения от
0 до 21 и для каждого значения P вычисляется
условный максимальный доход, учитывая
результаты предыдущего, 1-го этапа. Итоговые
результаты без промежуточных вычислений
приведены в таблице
Кол-во единиц грузоподъ-емности, оставшихся для предметов 1 и 2 , 3 типа |
Решение |
Условный максимальный доход |
0..3 |
X1=1 x2 =0 x3=0 |
15 |
3..4 5..6
7..9
10..11 12..13 |
X1=0 x2 =1 x3=0 X1=0 x2 =0 x3=1 X1=2 x2 =0x3=0 X1=1 x2 =0 x3=1 X1=0 x2 =2 x3=0 X1=1 x2 =1 x3=0 X1=0 x2 =1 x3=1 X1=1 x2 =1x3=1 X1=0 x2 =0x3=2 X1=1 x2 =2x3=0 |
18 16 30 31 36 33 34 49 32 51 |
14..17 |
X1=1 x2 =2 x3=1 X1=2 x2 =1x3=1 |
67 64 |
18..21 |
X1=1 x2 =1 x3=2 |
65 |
На последнем этапе рассчитаем,
результаты условной
Кол-во единиц грузоподъ-емности, оставшихся для предметов 1 и 2 , 3 , 4 типа |
Решение |
Условный максимальный доход |
0..3 |
X1=0 x2 =0 x3=0 x4=0 X1=1 x2 =0 x3=0 x4=0 |
0 15 |
4..7 8..9
10..12
13..15 16..18 |
X1=1 x2 =1 x3=0 x4=0
X1=1 x2 =1 x3=1 x4=0 X1=2 x2 =1 x3=1 x4=0 |
33
|
19..21 |
X1=1 x2 =1 x3=1 x4=1 X1=2 x2 =1 x3=1 x4=0 X1=3 x2 =1 x3=0 x4=1 X1=4 x2 =1 x3=1 x4=1 X1=5 x2 =0 x3=1 x4=0 X1=7 x2 =0 x3=0 x4=0 |
68 64 105 79 91 105 |
Последняя таблица содержит искомое оптимальное решение, которое предписывает загрузить 7 единиц первого типа, что дает максимальную стоимость груза равную 105 единиц стоимости.
Xоптим (7,0,0,0)
Wоптим=105