Лекции Шкурбы В.В / Лекции Шкурбы В.В / 2 / LEC11A
.DOCЛекция 11.
РЕШЕНИЕ ЗАДАЧ.
Задача 1.
Дано табличное представление функции прибыли от капиталовложений в 5 различных направлений.
|
|
1 |
2 |
3 |
4 |
5 |
|
50 |
31 |
34 |
32 |
35 |
32 |
|
40 |
25 |
26 |
26 |
25 |
26 |
|
30 |
20 |
19 |
18 |
17 |
21 |
|
20 |
13 |
15 |
12 |
13 |
14 |
|
10 |
8 |
7 |
6 |
6 |
7 |
|
0 |
0 |
0 |
0 |
0 |
0 |
Необходимо определить оптимальное с точки зрения максимизации прибыли распределение ресурсов в количестве 50 единиц между направлениями.
Запишем уравнение Беллмана как математическое выражение принципа оптимальности:
Задача решается следующим образом: поочередно рассматривается получение прибыли от распределения имеющихся денег в каждое направление. Затем из нее берется максимум и записывается в таблицу. Через знак слеш “/” в ячейке помечают сумму, вложенную в данное направление. Например, рассмотрим только первое направление. Здесь у нас только одна альтернатива, так как есть только одно направление. Далее допустим появляется еще возможность вложить и во второе направление. Имея сумму 10 мы можем вложить 0 в первое направление и 10 во второе и наоборот. По таблице видно, что выгоднее вложить в первое 10, а во второе 0 и получить прибыль в 8 д.е. Имея сумму 20, мы можем вложить в 1-е 0 и во 2-е 20, в 1-е 10 и во 2-е 10, в 1-е 20 и во 2-е 0. По таблице смотрим, что выгоднее всего вложить в 1-е 10 и во 2-е 10 и получить прибыль 15. Имея сумму 30 аналогично распределяем ее и получаем, что в 1-е пойдет 10 , во 2-е 20, а прибыль равна 23. Аналогично поступаем с оставшимися А=40 и А=50. Далее рассматриваем вариант, когда у нас уже имеется 3-я альтернатива. И так далее, пока не рассмотрим все 5 направлений вместе. Результаты сведем в таблицу, где в ячейках записана прибыль получаемая от вложения денег в соответствующие направления, причем через слеш записана сумма, которая идет в данное направление. Чтобы узнать сумму, идущую на остальные направления кроме данного, нужно из А вычесть сумму данного направления (записанную через слеш).
Итак, получилась следующая матрица результатов.
|
|
1 |
2 |
3 |
4 |
5 |
|
|
50 |
31 |
35/20 |
35/0 |
36/20 |
37/20 |
¬ F5(50) |
|
40 |
25 |
28/20 |
29/10 |
29/0 |
|
|
|
30 |
20 |
23/20 |
23/0 |
23/0 |
|
|
|
20 |
13 |
15/10 |
15/0 |
15/0 |
|
|
|
10 |
8 |
8/0 |
8/0 |
8/0 |
|
|
|
0 |
0 |
0 |
0 |
0 |
|
|
В итоге оптимальное решение выглядит так: <10, 20, 0, 0, 20> , F5=37.
Задача 2
“Задача о ранце” задана следующими таблицей и соотношениями:
;
|
x |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
а |
4 |
3 |
5 |
2 |
2 |
2 |
18 |
|
b |
4 |
3 |
4 |
4 |
2 |
1 |
18 |
|
c |
3 |
4 |
4 |
3 |
2 |
1 |
|
|
c/b |
0,75 |
1,33 |
1 |
0,75 |
1 |
1 |
|
|
Выбор |
0,5 |
1 |
1 |
|
1 |
1 |
12,5 |
|
Целочисл. реш-е |
0 |
1 |
1 |
1 |
0 |
1 |
12 |
Ограничение b является более жестким, поэтому возьмем его за основное (удельную ценность будем определять через это ограничение). Проранжируем предметы по убыванию их удельной стоимости и по порядку выберем самые ценные, смотря, чтобы сумма их весов не превысила наше установленные ограничения (в том числе и ограничение а).
Оптимальным дробным решением является следующее <0,5;1;1;0;1;1>. Однако простым отсечением дробной части в данном случае оптимальное целочисленное решение получить невозможно, поэтому прибегнем к методу ветвей и границ.
