Решение задач динамического программирования

Распределить 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

2-ой шаг. k = 2.

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

 

 

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

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

 

 

Поясним построение таблиц и последовательность проведения расчетов.
Столбцы 1, 2 и 3 для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода от продаж, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.

 Этап 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.

загрузка...