Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Упростить выражение
Примеры решений Задача Джонсона Симплекс метод Метод прогонки
Задача замены оборудования Задача распределения инвестиций
Параметры сетевой модели Задача коммивояжера Многоканальные СМО

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

Между тремя предприятиями распределить 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
2-ый шаг. k = 2.

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


3-ий шаг. k = 1.

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.

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