Динамическое программирование. Пример решения задачи
Найти оптимальное распределение средств между 6 предприятиями при условии, что прибыль f(x), полученная от каждого предприятия, является функцией от вложенных в него средств х. Выписать все оптимальные управления.| N | f 1(x ) | f 2 (x) | f 3 (x) | f 4 (x) | f 5 (x) |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 6 | 5 | 3 | 4 | 2 |
| 2 | 8 | 12 | 13 | 10 | 11 |
| 3 | 10 | 15 | 16 | 15 | 14 |
| 4 | 14 | 20 | 21 | 22 | 18 |
| 5 | 18 | 22 | 26 | 25 | 21 |
| 6 | 22 | 26 | 29 | 31 | 30 |
I этап. Условная оптимизация.
Первый шаг. k = 5.
| e4 | u5 | e5 = e4 - u5 | f5(u5) | F*5(e5) | u5(e5) |
| 1 | 0 | 1 | 0 | ||
| 1 | 0 | 2 | 2 | 1 | |
| 2 | 0 | 2 | 0 | ||
| 1 | 1 | 2 | |||
| 2 | 0 | 11 | 11 | 2 | |
| 3 | 0 | 3 | 0 | ||
| 1 | 2 | 2 | |||
| 2 | 1 | 11 | |||
| 3 | 0 | 14 | 14 | 3 | |
| 4 | 0 | 4 | 0 | ||
| 1 | 3 | 2 | |||
| 2 | 2 | 11 | |||
| 3 | 1 | 14 | |||
| 4 | 0 | 18 | 18 | 4 | |
| 5 | 0 | 5 | 0 | ||
| 1 | 4 | 2 | |||
| 2 | 3 | 11 | |||
| 3 | 2 | 14 | |||
| 4 | 1 | 18 | |||
| 5 | 0 | 21 | 21 | 5 | |
| 6 | 0 | 6 | 0 | ||
| 1 | 5 | 2 | |||
| 2 | 4 | 11 | |||
| 3 | 3 | 14 | |||
| 4 | 2 | 18 | |||
| 5 | 1 | 21 | |||
| 6 | 0 | 30 | 30 | 6 |
Второй шаг. k = 4.
| e3 | u4 | e4 = e3 - u4 | f4(u4) | F*4(e3) | F3(u4,e3) | F*4(e4) | u4(e4) |
| 1 | 0 | 1 | 0 | 2 | 2 | ||
| 1 | 0 | 4 | 0 | 4 | 4 | 1 | |
| 2 | 0 | 2 | 0 | 11 | 11 | 11 | 0 |
| 1 | 1 | 4 | 2 | 6 | |||
| 2 | 0 | 10 | 0 | 10 | |||
| 3 | 0 | 3 | 0 | 14 | 14 | ||
| 1 | 2 | 4 | 11 | 15 | 15 | 1 | |
| 2 | 1 | 10 | 2 | 12 | |||
| 3 | 0 | 15 | 0 | 15 | |||
| 4 | 0 | 4 | 0 | 18 | 18 | ||
| 1 | 3 | 4 | 14 | 18 | |||
| 2 | 2 | 10 | 11 | 21 | |||
| 3 | 1 | 15 | 2 | 17 | |||
| 4 | 0 | 22 | 0 | 22 | 22 | 4 | |
| 5 | 0 | 5 | 0 | 21 | 21 | ||
| 1 | 4 | 4 | 18 | 22 | |||
| 2 | 3 | 10 | 14 | 24 | |||
| 3 | 2 | 15 | 11 | 26 | 26 | 3 | |
| 4 | 1 | 22 | 2 | 24 | |||
| 5 | 0 | 25 | 0 | 25 | |||
| 6 | 0 | 6 | 0 | 30 | 30 | ||
| 1 | 5 | 4 | 21 | 25 | |||
| 2 | 4 | 10 | 18 | 28 | |||
| 3 | 3 | 15 | 14 | 29 | |||
| 4 | 2 | 22 | 11 | 33 | 33 | 4 | |
| 5 | 1 | 25 | 2 | 27 | |||
| 6 | 0 | 31 | 0 | 31 |
Третий шаг. k = 3.
| e2 | u3 | e3 = e2 - u3 | f3(u3) | F*3(e2) | F2(u3,e2) | F*3(e3) | u3(e3) |
| 1 | 0 | 1 | 0 | 4 | 4 | 4 | 0 |
| 1 | 0 | 3 | 0 | 3 | |||
| 2 | 0 | 2 | 0 | 11 | 11 | ||
| 1 | 1 | 3 | 4 | 7 | |||
| 2 | 0 | 13 | 0 | 13 | 13 | 2 | |
| 3 | 0 | 3 | 0 | 15 | 15 | ||
| 1 | 2 | 3 | 11 | 14 | |||
| 2 | 1 | 13 | 4 | 17 | 17 | 2 | |
| 3 | 0 | 16 | 0 | 16 | |||
| 4 | 0 | 4 | 0 | 22 | 22 | ||
| 1 | 3 | 3 | 15 | 18 | |||
| 2 | 2 | 13 | 11 | 24 | 24 | 2 | |
| 3 | 1 | 16 | 4 | 20 | |||
| 4 | 0 | 21 | 0 | 21 | |||
| 5 | 0 | 5 | 0 | 26 | 26 | ||
| 1 | 4 | 3 | 22 | 25 | |||
| 2 | 3 | 13 | 15 | 28 | 28 | 2 | |
| 3 | 2 | 16 | 11 | 27 | |||
| 4 | 1 | 21 | 4 | 25 | |||
| 5 | 0 | 26 | 0 | 26 | |||
| 6 | 0 | 6 | 0 | 33 | 33 | ||
| 1 | 5 | 3 | 26 | 29 | |||
| 2 | 4 | 13 | 22 | 35 | 35 | 2 | |
| 3 | 3 | 16 | 15 | 31 | |||
| 4 | 2 | 21 | 11 | 32 | |||
| 5 | 1 | 26 | 4 | 30 | |||
| 6 | 0 | 29 | 0 | 29 |
Четвертый шаг. k = 2.
| e1 | u2 | e2 = e1 - u2 | f2(u2) | F*2(e1) | F1(u2,e1) | F*2(e2) | u2(e2) |
| 1 | 0 | 1 | 0 | 4 | 4 | ||
| 1 | 0 | 5 | 0 | 5 | 5 | 1 | |
| 2 | 0 | 2 | 0 | 13 | 13 | 13 | 0 |
| 1 | 1 | 5 | 4 | 9 | |||
| 2 | 0 | 12 | 0 | 12 | |||
| 3 | 0 | 3 | 0 | 17 | 17 | ||
| 1 | 2 | 5 | 13 | 18 | 18 | 1 | |
| 2 | 1 | 12 | 4 | 16 | |||
| 3 | 0 | 15 | 0 | 15 | |||
| 4 | 0 | 4 | 0 | 24 | 24 | ||
| 1 | 3 | 5 | 17 | 22 | |||
| 2 | 2 | 12 | 13 | 25 | 25 | 2 | |
| 3 | 1 | 15 | 4 | 19 | |||
| 4 | 0 | 20 | 0 | 20 | |||
| 5 | 0 | 5 | 0 | 28 | 28 | ||
| 1 | 4 | 5 | 24 | 29 | 29 | 1 | |
| 2 | 3 | 12 | 17 | 29 | |||
| 3 | 2 | 15 | 13 | 28 | |||
| 4 | 1 | 20 | 4 | 24 | |||
| 5 | 0 | 22 | 0 | 22 | |||
| 6 | 0 | 6 | 0 | 35 | 35 | ||
| 1 | 5 | 5 | 28 | 33 | |||
| 2 | 4 | 12 | 24 | 36 | 36 | 2 | |
| 3 | 3 | 15 | 17 | 32 | |||
| 4 | 2 | 20 | 13 | 33 | |||
| 5 | 1 | 22 | 4 | 26 | |||
| 6 | 0 | 26 | 0 | 26 |
Пятый шаг. k = 1.
| e0 | u1 | e1 = e0 - u1 | f1(u1) | F*1(e0) | F0(u1,e0) | F*1(e1) | u1(e1) |
| 1 | 0 | 1 | 0 | 5 | 5 | ||
| 1 | 0 | 6 | 0 | 6 | 6 | 1 | |
| 2 | 0 | 2 | 0 | 13 | 13 | 13 | 0 |
| 1 | 1 | 6 | 5 | 11 | |||
| 2 | 0 | 8 | 0 | 8 | |||
| 3 | 0 | 3 | 0 | 18 | 18 | ||
| 1 | 2 | 6 | 13 | 19 | 19 | 1 | |
| 2 | 1 | 8 | 5 | 13 | |||
| 3 | 0 | 10 | 0 | 10 | |||
| 4 | 0 | 4 | 0 | 25 | 25 | 25 | 0 |
| 1 | 3 | 6 | 18 | 24 | |||
| 2 | 2 | 8 | 13 | 21 | |||
| 3 | 1 | 10 | 5 | 15 | |||
| 4 | 0 | 14 | 0 | 14 | |||
| 5 | 0 | 5 | 0 | 29 | 29 | ||
| 1 | 4 | 6 | 25 | 31 | 31 | 1 | |
| 2 | 3 | 8 | 18 | 26 | |||
| 3 | 2 | 10 | 13 | 23 | |||
| 4 | 1 | 14 | 5 | 19 | |||
| 5 | 0 | 18 | 0 | 18 | |||
| 6 | 0 | 6 | 0 | 36 | 36 | 36 | 0 |
| 1 | 5 | 6 | 29 | 35 | |||
| 2 | 4 | 8 | 25 | 33 | |||
| 3 | 3 | 10 | 18 | 28 | |||
| 4 | 2 | 14 | 13 | 27 | |||
| 5 | 1 | 18 | 5 | 23 | |||
| 6 | 0 | 22 | 0 | 22 |
Поясним построение таблиц и последовательность проведения расчетов.
Столбцы 1, 2 и 3 для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 5-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
Этап II. Безусловная оптимизация.
Управлением в многошаговом процессе называется совокупность решений (управляющих переменных) uk = (uk1, ..., ukr), принимаемых на каждом шаге k и переводящих систему из состояния εk-1 = (εk-11, …, εk-1s) в состояние εk = (εk1, …, εks).
Из таблицы 1-го шага имеем F*5(e0 = 6) = 36. То есть максимальный доход всей системы при количестве средств e0 = 6 равен 36
Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e0 = 6) = 0.
При этом остаток средств составит:
e1 = e0 - u1
e1 = 6 - 0 = 6
Из таблицы 2-го шага имеем F*4(e1 = 6) = 36. То есть максимальный доход всей системы при количестве средств e1 = 6 равен 36.
Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e1 = 6) = 2.
При этом остаток средств составит:
e2 = e1 - u2
e2 = 6 - 2 = 4
Из таблицы 3-го шага имеем F*3(e2 = 4) = 24. То есть максимальный доход всей системы при количестве средств e2= 4 равен 24
Из этой же таблицы получаем, что 3-му предприятию следует выделить u*3(e2 = 4) = 2.
При этом остаток средств составит:
e3 = e2 - u3
e3 = 4 - 2 = 2
Из таблицы 4-го шага имеем F*2(e3 = 2) = 11. То есть максимальный доход всей системы при количестве средств e3 = 2 равен 11.
Из этой же таблицы получаем, что 4-му предприятию следует выделить u*4(e3 = 2) = 0.
При этом остаток средств составит:
e4 = e3 - u4
e4 = 2 - 0 = 2
Последнему предприятию достается 2.
Итак, инвестиции в размере 6 необходимо распределить следующим образом:
1-му предприятию выделить 0;
2-му предприятию выделить 2;
3-му предприятию выделить 2;
4-му предприятию выделить 0;
5-му предприятию выделить 2;
Что обеспечит максимальный доход, равный 36.
Пример №2. Для двух предприятий выделено A единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от x единиц средств, вложенных в первое предприятие, равен f1(х), а доход от y единиц средств, вложенных во второе предприятие, равен f2(y). Остаток средств к концу года составляет g1(x) для первого предприятия и g2(y) для второго предприятия. Задачу решить методом динамического программирования.
Решение находим через сервис распределение средств между предприятиями.
I этап. Условная оптимизация.
1-ый шаг. k = 3.
e2 | u3 | e3= e2- u3 | f3(u3) | F*3(e3) | u3(e3) |
| 2 |
1 | 1 |
8 |
| |
2 | 0 | 12 | 12 | 2 | |
|
3 | 1 |
2 | 8 |
| |
2 | 1 | 12 | |||
3 |
0 | 15 |
15 | 3 | |
| 4 | 1 | 3 | 8 | ||
|
2 | 2 |
12 |
| ||
3 | 1 | 15 | |||
|
4 | 0 |
17 | 17 |
4 | |
| 5 | 1 | 4 | 8 | ||
2 |
3 | 12 |
| ||
3 | 2 | 15 | |||
4 |
1 | 17 |
| ||
5 | 0 | 18 | 18 | 5 | |
| 6 |
1 | 5 |
8 |
| |
2 | 4 | 12 | |||
|
3 | 3 |
15 |
| ||
4 | 2 | 17 | |||
|
5 | 1 |
18 |
| ||
6 | 0 | 20 | 20 | 6 | |
|
7 | 1 |
6 | 8 |
| |
2 | 5 | 12 | |||
3 |
4 | 15 |
| ||
4 | 3 | 17 | |||
5 |
2 | 18 |
| ||
6 | 1 | 20 | |||
7 |
0 | 23 |
23 | 7 | |
| 8 | 1 | 7 | 8 | ||
|
2 | 6 |
12 |
| ||
3 | 5 | 15 | |||
|
4 | 4 |
17 |
| ||
5 | 3 | 18 | |||
|
6 | 2 |
20 |
| ||
7 | 1 | 23 | |||
|
8 | 0 |
24 | 24 |
8 | |
| 9 | 1 | 8 | 8 | ||
2 |
7 | 12 |
| ||
3 | 6 | 15 | |||
4 |
5 | 17 |
| ||
5 | 4 | 18 | |||
6 |
3 | 20 |
| ||
7 | 2 | 23 | |||
8 |
1 | 24 |
| ||
9 | 0 | 27 | 27 | 9 |
Посмотреть все итерации
Этап II. Безусловная оптимизация.
Из таблица 1-го шага имеем F*3(e0= 9) = 47. То есть максимальный доход всей системы при количестве средств e0= 9 равен 47
Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e0= 9) = 2
При этом остаток средств составит:
e1= e0- u1
e1= 9 - 2 = 7
Из таблица 2-го шага имеем F*2(e1= 7) = 33. То есть максимальный доход всей системы при количестве средств e1= 7 равен 33
Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e1= 7) = 5
При этом остаток средств составит:
e2= e1- u2
e2= 7 - 5 = 2
Последнему предприятию достается 2
Итак, выделенные инвестиции в размере 9 будут распределены так:
1-му предприятию выделить 2
2-му предприятию выделить 5
3-му предприятию выделить 2
Что обеспечит максимальный доход, равный 47
Пример №3. Планируется распределение начальной суммы средств S0 = 200 млн. руб. между четырьмя предприятиям П1, П2, П3 и П4. Предполагается, что выделенные в начале планового периода средства xk приносят доход Fk(xk) (k=1,..,4). Будем считать, что
1) доход, полученный от разных предприятий, выражается в одинаковых единицах;
2) доход, полученный от вложения средств в предприятие, не зависит от вложения средств в другие предприятия;
3) общий доход равен сумме доходов, полученных от всех средств, вложенных во все предприятия.
4) средства выделяются только в размерах кратных 50 млн. руб.
Определить какое количество средств нужно выделить каждому предприятию, чтобы суммарных доход был максимальным, если функция дохода на каждом из четырех предприятий заданы в таблице.
I этап. Условная оптимизация.
1-ый шаг. k = 4.
e3 | u4 | e4= e3- u4 | f4(u4) | F*4(e4) | u4(e4) |
| 40 |
20 | 20 |
12 |
| |
40 | 0 | 30 | 30 | 40 | |
|
60 | 20 |
40 | 12 |
| |
40 | 20 | 30 | |||
60 |
0 | 44 |
44 | 60 | |
| 80 | 20 | 60 | 12 | ||
|
40 | 40 |
30 |
| ||
60 | 20 | 44 | |||
|
80 | 0 |
51 | 51 |
80 | |
| 100 | 20 | 80 | 12 | ||
40 |
60 | 30 |
| ||
60 | 40 | 44 | |||
80 |
20 | 51 |
| ||
100 | 0 | 62 | 62 | 100 |
Посмотреть все итерации
Этап II. Безусловная оптимизация.
Из таблица 1-го шага имеем F*4(e0 = 100) = 75. То есть максимальный доход всей системы при количестве средств e0 = 100 равен 75
Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e0 = 100) = 20
При этом остаток средств составит:
e1 = e0 - u1
e1 = 100 - 20 = 80
Из таблица 2-го шага имеем F*3(e1 = 80) = 56. То есть максимальный доход всей системы при количестве средств e1 = 80 равен 56
Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e1 = 80) = 20
При этом остаток средств составит:
e2 = e1 - u2
e2 = 80 - 20 = 60
Из таблица 3-го шага имеем F*2(e2 = 60) = 62. То есть максимальный доход всей системы при количестве средств e2 = 60 равен 62
Из этой же таблицы получаем, что 3-му предприятию следует выделить u*3(e2 = 60) = 40
При этом остаток средств составит:
e3 = e2 - u3
e3 = 60 - 40 = 20
Последнему предприятию достается 20
Итак, инвестиции в размере 100 надо распределить:
1-му предприятию выделить 20
2-му предприятию выделить 20
3-му предприятию выделить 40
4-му предприятию выделить 20
Что обеспечит максимальный доход, равный 75
Перейти к онлайн решению своей задачи
Пример №4. Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X)зависит от количества реализованных партий товара Х и представлен в таблице.
| Объем товара Х (в партиях) | Доход G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Решение:
Исходные данные.
| f1 | f2 | f3 | xi |
| 0 | 0 | 0 | 0 |
| 28 | 30 | 32 | 1 |
| 41 | 42 | 45 | 2 |
| 50 | 55 | 48 | 3 |
| 62 | 64 | 60 | 4 |
| 76 | 76 | 72 | 5 |
I этап. Условная оптимизация.
1-ый шаг. k = 3.
| e2 | u3 | e3 = e2 - u3 | f3(u3) | F*3(e3) | u3(e3) |
| 1 | 0 | 1 | 0 | ||
| 1 | 0 | 32 | 32 | 1 | |
| 2 | 0 | 2 | 0 | ||
| 1 | 1 | 32 | |||
| 2 | 0 | 45 | 45 | 2 | |
| 3 | 0 | 3 | 0 | ||
| 1 | 2 | 32 | |||
| 2 | 1 | 45 | |||
| 3 | 0 | 48 | 48 | 3 | |
| 4 | 0 | 4 | 0 | ||
| 1 | 3 | 32 | |||
| 2 | 2 | 45 | |||
| 3 | 1 | 48 | |||
| 4 | 0 | 60 | 60 | 4 | |
| 5 | 0 | 5 | 0 | ||
| 1 | 4 | 32 | |||
| 2 | 3 | 45 | |||
| 3 | 2 | 48 | |||
| 4 | 1 | 60 | |||
| 5 | 0 | 72 | 72 | 5 |
| e1 | u2 | e2 = e1 - u2 | f2(u2) | F*2(e1) | F1(u2,e1) | F*2(e2) | u2(e2) |
| 1 | 0 | 1 | 0 | 32 | 32 | 32 | 0 |
| 1 | 0 | 30 | 0 | 30 | |||
| 2 | 0 | 2 | 0 | 45 | 45 | ||
| 1 | 1 | 30 | 32 | 62 | 62 | 1 | |
| 2 | 0 | 42 | 0 | 42 | |||
| 3 | 0 | 3 | 0 | 48 | 48 | ||
| 1 | 2 | 30 | 45 | 75 | 75 | 1 | |
| 2 | 1 | 42 | 32 | 74 | |||
| 3 | 0 | 55 | 0 | 55 | |||
| 4 | 0 | 4 | 0 | 60 | 60 | ||
| 1 | 3 | 30 | 48 | 78 | |||
| 2 | 2 | 42 | 45 | 87 | 87 | 2 | |
| 3 | 1 | 55 | 32 | 87 | |||
| 4 | 0 | 64 | 0 | 64 | |||
| 5 | 0 | 5 | 0 | 72 | 72 | ||
| 1 | 4 | 30 | 60 | 90 | |||
| 2 | 3 | 42 | 48 | 90 | |||
| 3 | 2 | 55 | 45 | 100 | 100 | 3 | |
| 4 | 1 | 64 | 32 | 96 | |||
| 5 | 0 | 76 | 0 | 76 |
| e0 | u1 | e1 = e0 - u1 | f1(u1) | F*1(e0) | F0(u1,e0) | F*1(e1) | u1(e1) |
| 1 | 0 | 1 | 0 | 32 | 32 | 32 | 0 |
| 1 | 0 | 28 | 0 | 28 | |||
| 2 | 0 | 2 | 0 | 62 | 62 | 62 | 0 |
| 1 | 1 | 28 | 32 | 60 | |||
| 2 | 0 | 41 | 0 | 41 | |||
| 3 | 0 | 3 | 0 | 75 | 75 | ||
| 1 | 2 | 28 | 62 | 90 | 90 | 1 | |
| 2 | 1 | 41 | 32 | 73 | |||
| 3 | 0 | 50 | 0 | 50 | |||
| 4 | 0 | 4 | 0 | 87 | 87 | ||
| 1 | 3 | 28 | 75 | 103 | 103 | 1 | |
| 2 | 2 | 41 | 62 | 103 | |||
| 3 | 1 | 50 | 32 | 82 | |||
| 4 | 0 | 62 | 0 | 62 | |||
| 5 | 0 | 5 | 0 | 100 | 100 | ||
| 1 | 4 | 28 | 87 | 115 | |||
| 2 | 3 | 41 | 75 | 116 | 116 | 2 | |
| 3 | 2 | 50 | 62 | 112 | |||
| 4 | 1 | 62 | 32 | 94 | |||
| 5 | 0 | 76 | 0 | 76 |
Этап II. Безусловная оптимизация.
Из таблицы 1-го шага имеем F*3(e0 = 5) = 116. То есть максимальный доход всей системы при количестве товаров e0 = 5 равен 116.
Из этой же таблицы получаем, что 1-му рынку следует выделить u*1(e0 = 5) = 2 партии товаров.
При этом остаток товара (в партиях) составит:
e1 = e0 - u1
e1 = 5 - 2 = 3
Из таблицы 2-го шага имеем F*2(e1 = 3) = 75. То есть максимальный доход всей системы при количестве товаров e1 = 3 равен 75.
Из этой же таблицы получаем, что 2-му рынку следует выделить u*2(e1 = 3) = 1 партию товаров.
При этом остаток товаров составит:
e2 = e1 - u2
e2 = 3 - 1 = 2
Последнему рынку достается 2 партии товаров.
Итак, объем товара Х в размере 5 партий необходимо распределить следующим образом:
1-му рынку выделить 2 партии товаров.
2-му рынку выделить 1 партию.
3-му рынку выделить 2 партии товаров.
Что обеспечит максимальный доход, равный 116.
Пример №5. Планируется распределение начальной суммы средств Е0 = 60 млн руб. между четырьмя предприятиями при условии, что средства выделяются только в размерах, кратных 10 млн руб., и функции дохода fi(x) для i-го предприятия заданы таблицей:
|
10 |
20 |
30 |
40 |
50 |
60 | |
|
f 1 |
1 |
3 |
5 |
7 |
7 |
8 |
|
f 2 |
2 |
4 |
4 |
6 |
7 |
8 |
|
f 3 |
1 |
4 |
4 |
7 |
7 |
8 |
|
f 4 |
2 |
3 |
5 |
6 |
7 |
8 |
I этап. Условная оптимизация.
1-ый шаг. k = 4.
| e3 | u4 | e4 = e3 - u4 | f4(u4) | F*4(e4) | u4(e4) |
| 10 | 0 | 10 | 0 | 0 | 0 |
| 10 | 0 | 2 | 2 | 10 | |
| 20 | 0 | 20 | 0 | 0 | 0 |
| 10 | 10 | 2 | 0 | 0 | |
| 20 | 0 | 3 | 3 | 20 | |
| 30 | 0 | 30 | 0 | 0 | 0 |
| 10 | 20 | 2 | 0 | 0 | |
| 20 | 10 | 3 | 0 | 0 | |
| 30 | 0 | 5 | 5 | 30 | |
| 40 | 0 | 40 | 0 | 0 | 0 |
| 10 | 30 | 2 | 0 | 0 | |
| 20 | 20 | 3 | 0 | 0 | |
| 30 | 10 | 5 | 0 | 0 | |
| 40 | 0 | 6 | 6 | 40 | |
| 50 | 0 | 50 | 0 | 0 | 0 |
| 10 | 40 | 2 | 0 | 0 | |
| 20 | 30 | 3 | 0 | 0 | |
| 30 | 20 | 5 | 0 | 0 | |
| 40 | 10 | 6 | 0 | 0 | |
| 50 | 0 | 7 | 7 | 50 | |
| 60 | 0 | 60 | 0 | 0 | 0 |
| 10 | 50 | 2 | 0 | 0 | |
| 20 | 40 | 3 | 0 | 0 | |
| 30 | 30 | 5 | 0 | 0 | |
| 40 | 20 | 6 | 0 | 0 | |
| 50 | 10 | 7 | 0 | 0 | |
| 60 | 0 | 8 | 8 | 60 |
Посмотреть все итерации
Таким образом, начальную сумму в размере 60 млн. руб. необходимо распределить следующим образом:
первому предприятию выделить 0 млн. руб.
Второму предприятию выделить 10 млн. руб.
Третьему предприятию выделить 20 млн. руб.
Четвертому предприятию выделить 30 млн. руб.
Данное распределение начальных средств в размере 60 млн. руб. обеспечит максимальный доход, равный 11 млн. руб.
Перейти к онлайн решению своей задачи
Пример №6. Для модернизации предприятий совет директоров инвестирует средства в объеме 25 млн. руб. с дискретностью 5 млн. руб. Прирост выпуска продукции зависит от выделенной суммы, его значения представлены предприятиями и содержатся в таблице. Найти распределение инвестиций между предприятиями, обеспечивающее фирме максимальный прирост выпуска продукции, причем на одно предприятие можно осуществить только одну инвестицию.
| Выделяемые средства, млн.руб. | Прирост выпуска продукции, млн.руб. | ||
| Предприятие №1 | Предприятие №2 | Предприятие №3 | |
| 5 10 15 20 25 | 11 16 23 28 34 | 13 15 21 29 37 | 10 17 22 28 36 |
I этап. Условная оптимизация. 1-ый шаг. k = 3.
| e2 | u3 | e3= e2- u3 | f3(u3) | F*3(e3) | u3(e3) |
| 5 | 0 | 5 | 0 | ||
| 5 | 0 | 10 | 10 | 5 | |
| 10 | 0 | 10 | 0 | ||
| 5 | 5 | 10 | |||
| 10 | 0 | 17 | 17 | 10 | |
| 15 | 0 | 15 | 0 | ||
| 5 | 10 | 10 | |||
| 10 | 5 | 17 | |||
| 15 | 0 | 22 | 22 | 15 | |
| 20 | 0 | 20 | 0 | ||
| 5 | 15 | 10 | |||
| 10 | 10 | 17 | |||
| 15 | 5 | 22 | |||
| 20 | 0 | 28 | 28 | 20 | |
| 25 | 0 | 25 | 0 | ||
| 5 | 20 | 10 | |||
| 10 | 15 | 17 | |||
| 15 | 10 | 22 | |||
| 20 | 5 | 28 | |||
| 25 | 0 | 36 | 36 | 25 |
Посмотреть все итерации
Итак, инвестиции в размере 25 млн. руб. необходимо распределить следующим образом:
1-му предприятию выделить 5 млн. руб.
2-му предприятию выделить 5 млн. руб.
3-му предприятию выделить 15 млн. руб.
Это обеспечит максимальный доход в размере 46 млн. руб.
Пример №7. Лизинговой компании необходимо сделать выбор объектов предполагаемых лизинговых сделок с определением оптимальных объемов финансирования на приобретение этих объектов в размерах кратных 100 млн. руб. Для инвестирования на эти цели компания располагает капиталом в объеме 700 млн. руб. В таблице 4 приводится среднегодовая прибыль компаний, ожидаемая от лизингополучателей при предоставлении им того или иного объекта на сумму от 0 до 700 млн. руб.
Таблица - Объем финансирования, млн. руб. Среднегодовая прибыль при предоставлении объектов, млн. руб.
| f1 | f2 | f3 | xi |
| 0 | 0 | 0 | 0 |
| 31 | 62 | 55 | 100 |
| 60 | 120 | 104 | 200 |
| 87 | 174 | 147 | 300 |
| 112 | 224 | 184 | 400 |
| 135 | 270 | 215 | 500 |
| 156 | 312 | 240 | 600 |
| 175 | 350 | 269 | 700 |
Под оптимальным объемом финансирования на приобретение объектов лизинга администрация компании понимает такое распределение суммы в 700 млн. руб. при котором среднегодовая прибыль от лизингополучателей всех этих объектов оказывается максимальной.
Используя метод динамического программирования, рассчитать такие объемы инвестиций по объектам лизинга, по которым ожидается максимальная по величине среднегодовая прибыль лизингополучателя.
Итак, инвестиции в размере 700 млн. руб. необходимо распределить следующим образом:
1-му объекту выделить 0 млн. руб..
2-му объекту выделить 500 млн. руб..
3-му объекту выделить 200 млн. руб..
Что обеспечит максимальный доход, равный 374 млн. руб.
Пример №8. Инвестор выделяет средства в размере т.д. ед, которые должны быть распределены между тремя предприятиями.Требуется, используя принцип оптимальности Беллмана, составить план распределения средств между предприятиями, обеспечивающий наибольшую общую прибыль, если каждое предприятие при инвестировании в него средств Х т.д.ед. приносит прибыль U(Х) по следующим данным:
| Инвестирование средств т/р | Прибыль т/р | ||
| Х | U1(Х) | U2(Х) | U3(Х) |
| 1 | 6,58 | 5,14 | 6,1 |
| 2 | 12,3 | 4,26 | 8,5 |
| 3 | 14,5 | 10,52 | 11,52 |
| 4 | 20,9 | 18,54 | 18,26 |
| 5 | 26,86 | 25,62 | 17,4 |
Итак, инвестиции в размере 5 необходимо распределить следующим образом:
1-му предприятию выделить 4,
2-му предприятию выделить 0,
3-му предприятию выделить 1.
Что обеспечит максимальный доход, равный 27.
Пример №9. Планируется распределение начальной суммы средств e0 = 40 млн руб., причем средства выделяются кратно 10 млн руб. между тремя предприятиями П1, П2, П3. Выделение предприятию Пk средств uk приносит доход fk(uk), который задан в табл. Определить, какое количество средств нужно выделить каждому предприятию, чтобы обеспечить максимальный суммарный доход.
| x | 0 | 10 | 20 | 30 | 40 |
| f1(x) | 0 | 4 | 5 | 7 | 8 |
| f2(x) | 0 | 3 | 3 | 4 | 6 |
| f3(x) | 0 | 4 | 4 | 5 | 6 |
Итак, максимальный доход в количестве 40 будет получен, если:
1-му предприятию выделить 20
2-му предприятию выделить 10
3-му предприятию выделить 10
Что обеспечит максимальный доход, равный 12
