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

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

загрузка...