Метод обратной прогонки
Между тремя предприятиями распределить 120 единиц ограниченного ресурса. Значения получаемой предприятиями прибыли в зависимости от выделенной суммы Х приведены в таблице. Найти оптимальный план распределения методом обратной прогонки. (см. также решение задачи методом прямой прогонки)| Объем ресурса Х | Величина прибыли Z(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 40 | 25 | 24 | 27 |
| 80 | 38 | 40 | 45 |
| 120 | 60 | 55 | 58 |
Решение:
Задачи динамического программирования решаются методом прямой прогонки и методом обратной прогонки.
Процесс нахождения решения разбивается да две стадии:
условная оптимизация;
безусловная оптимизация.
На стадии условной оптимизации определяются условные оптимальные выигрыши и условные оптимальные управления.
Прямая прогонка: от первого шага к последнему.
Обратная прогонка: от последнего шага к первому.
На стадии безусловной оптимизации строится оптимальное решение исходной задачи и определяется max (min).
Прямая прогонка: от последнего шага к первому.
Обратная прогонка: от первого шага к последнему.
I этап. Условная оптимизация.
1-ый шаг. k = 3.
e2 | u3 | e3= e2- u3 | f3(u3) | F*3(e3) | u3(e3) |
| 40 |
0 | 40 |
0 |
| |
40 | 0 | 27 | 27 | 40 | |
|
80 | 0 |
80 | 0 |
| |
40 | 40 | 27 | |||
80 |
0 | 45 |
45 | 80 | |
| 120 | 0 | 120 | 0 | ||
|
40 | 80 |
27 |
| ||
80 | 40 | 45 | |||
|
120 | 0 |
58 | 58 |
120 |
e1 | u2 | e2= e1- u2 | f2(u2) | F*2(e1) | F1(u2,e1) | F*2(e2) | u2(e2) |
| 40 |
0 | 40 |
0 | 27 |
27 | 27 |
0 |
40 | 0 | 24 | 0 | 24 | |||
|
80 | 0 |
80 | 0 |
45 | 45 |
| |
40 | 40 | 24 | 27 | 51 | 51 | 40 | |
80 |
0 | 40 |
0 | 40 |
| ||
| 120 | 0 | 120 | 0 | 58 | 58 | ||
|
40 | 80 |
24 | 45 |
69 | 69 |
40 | |
80 | 40 | 40 | 27 | 67 | |||
|
120 | 0 |
55 | 0 |
55 |
|
e0 | u1 | e1= e0- u1 | f1(u1) | F*1(e0) | F0(u1,e0) | F*1(e1) | u1(e1) |
| 40 |
0 | 40 |
0 | 27 |
27 | 27 |
0 |
40 | 0 | 25 | 0 | 25 | |||
|
80 | 0 |
80 | 0 |
51 | 51 |
| |
40 | 40 | 25 | 27 | 52 | 52 | 40 | |
80 |
0 | 38 |
0 | 38 |
| ||
| 120 | 0 | 120 | 0 | 69 | 69 | ||
|
40 | 80 |
25 | 51 |
76 | 76 |
40 | |
80 | 40 | 38 | 27 | 65 | |||
|
120 | 0 |
60 | 0 |
60 |
|
Поясним построение таблиц и последовательность проведения расчетов.
Столбцы 1, 2 и 3 для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
Этап II. Безусловная оптимизация.
Из таблицы 1-го шага имеем F*3(e0 = 120) = 76. То есть максимальный доход всей системы при количестве средств e0 = 120 равен 76
Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e0 = 120) = 40
При этом остаток средств составит:
e1 = e0 - u1
e1 = 120 - 40 = 80
Из таблицы 2-го шага имеем F*2(e1 = 80) = 51. То есть максимальный доход всей системы при количестве средств e1 = 80 равен 51
Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e1 = 80) = 40
При этом остаток средств составит:
e2 = e1 - u2
e2 = 80 - 40 = 40
Последнему предприятию достается 40
Итак, инвестиции в размере 120 необходимо распределить следующим образом:
1-му предприятию выделить 40
2-му предприятию выделить 40
3-му предприятию выделить 40
Что обеспечит максимальный доход, равный 76.
Пример №2. Между тремя предприятиями распределить 120 единиц ограниченного ресурса. Значения получаемой предприятиями прибыли в зависимости от выделенной суммы Х приведены в таблице. Найти оптимальный план распределения методом обратной прогонки. (см. также решение задачи методом прямой прогонки)
| Объем ресурса Х | Величина прибыли Z(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 40 | 25 | 24 | 27 |
| 80 | 38 | 40 | 45 |
| 120 | 60 | 55 | 58 |
I этап. Условная оптимизация.
1-й шаг: k = 3.
Предположим, что все средства в количестве x3 = 120 отданы 3-у предприятию. В этом случае максимальный доход, как это видно из таблицы 1*, составит 58, следовательно:
F3(c3) = g3(x3)
Таблица 1.
| 0 | x1 | 0 | 0 | 0 | 0 |
| x3 | f0(x0) / F3(x3) | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 40 | 27 | 0 | 0 | 27 | 0 |
| 80 | 45 | 0 | 45 | 0 | 0 |
| 120 | 58 | 58* | 0 | 0 | 0 |
Таблица 1*.
| c1 | 0 | 40 | 80 | 120 |
| F0(c1) | 0 | 27 | 45 | 58 |
| x1 | 0 | 40 | 80 | 120 |
2-й шаг: k = 2.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F2(c2) = max [ g2(x2) + F3(c2 - x2)]
Таблица 2.
| 0 | x2 | 0 | 40 | 80 | 120 |
| x2 | f3(x3) / F2(x2) | 0 | 27 | 45 | 58 |
| 0 | 0 | 0 | 27* | 45 | 58 |
| 40 | 24 | 24 | 51* | 69* | 0 |
| 80 | 40 | 40 | 67 | 0 | 0 |
| 120 | 55 | 55 | 0 | 0 | 0 |
Заполняем таблицу 2*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x2.
Таблица 2*.
| c2 | 0 | 40 | 80 | 120 |
| F3(c2) | 0 | 27 | 51 | 69 |
| x2 | 0 | 0 | 40 | 40 |
3-й шаг: k = 1.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F1(c1) = max [ g1(x1) + F2(c1 - x1)]
Таблица 3.
| 0 | x3 | 0 | 40 | 80 | 120 |
| x1 | f4(x4) / F1(x1) | 0 | 27 | 51 | 69 |
| 0 | 0 | 0 | 27* | 51 | 69 |
| 40 | 25 | 25 | 52* | 76* | 0 |
| 80 | 38 | 38 | 65 | 0 | 0 |
| 120 | 60 | 60 | 0 | 0 | 0 |
Заполняем таблицу 3*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x3.
Таблица 3*.
| c3 | 0 | 40 | 80 | 120 |
| F4(c3) | 0 | 27 | 52 | 76 |
| x3 | 0 | 0 | 40 | 40 |
II этап. Безусловная оптимизация.
1-й шаг: k = 1.
По данным таблицы 3* максимальный доход при распределении 120 между предприятиями составляет c1 = 120, F1(120) = 76. При этом 1-му предприятию нужно выделить x1 = 40.
2-й шаг: k = 2.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c2 = c1 - x1 = 120 - 40 = 80.
По данным таблицы 2* максимальный доход при распределении 80 между предприятиями составляет c2 = 80, F2(80) = 51. При этом 2-му предприятию нужно выделить x2 = 40.
3-й шаг: k = 3.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c3 = c2 - x2 = 80 - 40 = 40.
По данным таблицы 1* максимальный доход при распределении 40 между предприятиями составляет (40) = 27. При этом 3-му предприятию нужно выделить x3 = 40.
Таким образом, оптимальный план инвестирования предприятия:
x 1 = 40
x 2 = 40
x 3 = 40
который обеспечит максимальный доход, равный:
F(120) = g1(40) + g2(40) + g3(40) = 25 + 24 + 27 = 76.
