Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
29
Добавлен:
19.04.2013
Размер:
161.79 Кб
Скачать

Лекция 10.

Задачи распределения капиталовложений.

Оптимальное рапределение капитала.

Схемы динамического программирования.

1. Схема динамического программирования.

Данная задача может быть сформулирована как задачà эффективного распределения капиталовложений, которая может служить основой выхода из кризисных ситуаций.

1

2

3

4

5

50

41

42

44

39

43

40

30

33

29

32

35

30

24

25

23

24

27

20

16

19

15

18

17

10

10

9

7

8

11

0

0

0

0

0

0

В представленной таблице столбцû — это номера возможных направлений, в которые можно вложить деньги; строкèсумма вкладываемых денег Х (млн.руб.) и содержимое ячеек fi(x) — функция прибыли от вложения суммы Х в i-е направление. Направления, в которые вкладываются деньги не являются взаимоисключающими.

Решение задачи здесь можно записать таким образом: <x1, x2, ... , xi, ... , xn>, где хj — размер вложенных денег в j-е направление (j=0,...,n).

В наличии имеется определенное конечное количество денег А, ò.å.

.

Предприниматель должен вложить некоторое положительное значение из ограниченной суммы так, чтобы получить максимальную прибыль, т.е.

.

Метод решения поставленной задачи основан на ïринципå оптимальности, который можно сформулировать так: любая часть оптимального решения должна быть оптимальной.

В качестве примера рассмотрим задачу, когда необходимо проложить дорогу от пункта А до пункта В. Допустим, между этими городами находятся озера и горы. Необходимо проложить эту дорогу так, чтобы затраты на ее прокладывание были бы минимальными. Пусть дорогу проложили и она является оптимальной по сумме затрат. Тогда любая промежуточная часть этой оптимальной дороги должна стоить не больше любого альтернативного варианта на этом отрезке пути, т.е. эта часть дороги должна быть оптимальной

Здесь предполагается, что стоимость дороги аддитивна, т.е. стоимость всей дороги является суммой стоимостей отдельных составляющих ее частей:

F(AB)=F(A)+F(B).

Таким образом, принцип оптимальности действует тогда, когда функция критерия оптимальности аддитивна.

Пусть в задаче оптимального распределения капиталовложений Fn(A) — оптимальное распределение суммы А по всем n направлениям. Выделим некоторое Х в n-е направление и получим fn(x). Тогда

Максимизируем полученное соотношение, ò.å.

уравнение Беллмана.

Это математическое выражение принципа оптимальности.

Представленный ниже пример показывает, что можно выделять какие-то Х в какое-либо направление, искать максимум из оставшихся направлений, а потом из найденных решений брать оптимальное.

Пусть у нас есть 50 денежных единиц и 5 различных направлений. Тогда F5(50)=F4(50-x)+f5(x) Max.

Пусть задана в табличной форме функция прибыли от распределения х по всем направлениям.

1

2

3

4

5

50

41

42

44

39

43

40

30

33

29

32

35

30

24

25

23

24

27

20

16

19

15

18

17

10

10

9

7

8

11

0

0

0

0

0

0

Задача решается следующим образом: поочередно рассматривается получение прибыли от распределения имеющихся денег в каждое направление. Затем из нее берется максимум и записывается в таблицу. Через знак слеш “/” в ячейке помечают сумму, вложенную в данное направление. Например, рассмотрим только первое направление. Здесь у нас только одна альтернатива, так как есть только одно направление. Далее допустим появляется еще возможность вложить и во второе направление. Имея сумму 10 мы можем вложить 0 в первое направление и 10 во второе и наоборот. По таблице видно, что выгоднее вложить в первое 10, а во второе 0 и получить прибыль в 10 д.е. Имея сумму 20, мы можем вложить в 1-е 0 и во 2-е 20, в 1-е 10 и во 2-е 10, в 1-е 20 и во 2-е 0. По таблице смотрим, что выгоднее всего вложить в 1-е 10 и во 2-е 10 и получить прибыль 19. Имея сумму 30 аналогично распределяем ее и получаем, что в 1-е пойдет 10 , во 2-е 10, а прибыль равна 29. Аналогично поступаем с оставшимися А=40 и А=50. Далее рассматриваем вариант, когда у нас уже имеется 3-я альтернатива. И так далее, пока не рассмотрим все 5 направлений вместе. Результаты сведем в таблицу, где в ячейках записана прибыль получаемая от вложения денег в соответствующие направления, причем через слеш записана сумма, которая идет в данное направление. Чтобы узнать сумму, идущую на остальные направления кроме данного, нужно из А вычесть сумму данного направления (записанную через слеш).

Итак, получилась следующая матрица результатов.

1

2

3

4

5

50

41

43/40

44/50

47/20

48/10

 F5(50)

40

30

35/30

36/10

37/10

30

24

29/20

29/0

29/0

20

16

19/10

19/0

19/0

10

10

10/0

10/0

10/0

0

0

0

0

0

В итоге наше оптимальное решение выглядит так: <10, 20, 0, 10, 10>.

Данный алгоритм поиска оптимального решения можно реализовать в табличном процессоре.

2. Распределение средств во взаимоисключающие направления.

Задачи такого типа, когда имеются направления, исключающие друг друга, называются «задачей о ранце».

Пусть есть альтернативы принятия каких-либо решений. Другими словами можно брать несколько предметов из ранца, но на них накладывается какое-либо ограничение. То есть можно брать определенное количество предметов из круга возможных так, чтобы они удовлетворяли имеющемуся ограничению. У каждого предмета своя ценность и свой вес.

x

1

2

3

4

5

6

а

1

2

5

4

4

4

c

3

3

4

5

4

1

с/a

3

3/2

4/5

5/4

1

1/4

Выбор

+

+

+

+

Задачу можно решить, через удельную ценность предмета, т.е. вычислив сколько стоит 1 единица предмета. Например, в таблице аi — вес предмета, сi — стоимость предмета, ci/ai — удельная стоимость предмета. Допустим, имеется ограничение на вес — в сумме предметы должны давать не более 12. То есть:

Теперь, определив удельные стоимости каждого предмета, мы ранжируем их по убыванию этой удельной стоимости и по порядку выбираем самые ценные, смотря, чтобы сумма их весов не превысила наше установленное ограничение.

В результате мы находим оптимальное решение: <1, 2, 4, 5>.

Если бы в задаче добавлялось еще одно ограничение, то мы проверяли бы сразу два ограничения. В случае множества ограничений, нужно выбирать основным то ограничение, которое более жесткое.

Кривая Парето.

Схема «ветвей и границ».

В случае наличия еще одного

ограничения его включают тем

тем же образом (т.е. расчет c/a è ò.ä.)

В качетсве исходного берется более

жесткое ограничение

()

В принципе можно решить N «задач

о ранце», но это приведет к

усложнению логики задачи.

Соседние файлы в папке 1