Метод обратной прогонки

Между тремя предприятиями распределить 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.

Перейти к онлайн решению своей задачи

загрузка...