Динамическое программирование. Основные понятия динамического программирования. Принципы динамического программирования

Страницы работы

24 страницы (Word-файл)

Фрагмент текста работы

множество управлений (решений), которые могут быть приняты в начале -го года. Множество состоит из двух элементов «сохранение» и «замена»;

 – прибыль в -ом году от использования оборудования;

 – условно-оптимальная прибыль от использования оборудования в период с -го по -й год с принятым решением ;

 – условно-оптимальная прибыль от использования оборудования в период с -го по -й год;

Имеем основное функциональное уравнение 2.1 или в виде 2.2.

                                         (2.1)

                                           (2.2)

Прибыль в -ом году принимает вид 2.3.

                         (2.3)

Для -ого планового года имеем 2.4.

                                  (2.4)

Прибыль в -ом году принимает вид 2.5.

                            (2.5)


2.2 Решение задачи о замене оборудования

Так как , что приняли для упрощения задачи, то начнём рассмотрения с последнего 4-го года.

Поясним обозначения:

 – множество состояний (1,2,3,4,5,0) оборудования перед 4-ым годом;

 – множество состояний (1,2,3,4,5,0) после выбора управления в 4-ом году;

 – множество решение (сохранение, замена) в начале 4-ого года.

 – прибыль в 4-ом году от использования оборудования;

 – условно-оптимальная прибыль от использования оборудования в период с 4-го по 5-й год с принятым решением ;

Из последнего видно, что целесообразнее на 4-ом году сохранить оборудование, так как при этом прибыль будет больше, чем при замене (31>27).

Сведём полученные значения прибылей  и условно-оптимальных прибылей  для 4-ого года использования оборудования с возрастом 1, 2, 3, 4, 5 лет в таблицу 2.2.

Таблица 2.2 – Прибыли в начале 4-ого плавного периода

(было перед 4-ым)

(решение в начале)

 

(в начале состояние)

(прибыль)

(оптимально)

1

Сохранение

1

31

31

Замена

0

27

2

Сохранение

2

28

28

Замена

0

27

3

Сохранение

3

27

27

Замена

0

27

4

Сохранение

4

27

27

Замена

0

27

5

Сохранение

5

24

27

Замена

0

27

Перейдем к анализу 3-его года планового периода, записываем функциональное уравнение.

 

       

Рассчитаем , :

         

        

        

        

        

Поясним обозначения:

 – множество состояний оборудования перед -ым годом. Элементами множества могут быть числа , характеризующие возраст оборудования, при чем  – после выбора управления в -ом году и  – в конце -го года;

 – множество управлений (решений), которые могут быть приняты в начале -го года. Множество состоит из двух элементов «сохранение» и «замена»;

 – прибыль в -ом году от использования оборудования;

 – условно-оптимальная прибыль от использования оборудования в период с -го по -й год с принятым решением ;

 – условно-оптимальная прибыль от использования оборудования в период с -го по -й год;

Рассмотрим таблицу 2.3.

Таблица 2.3 – Для пояснений

 (из предыдущей таблиц по 1-ой колонке)

1

2

0

1

Из таблицы имеем: во второй строке цифры 1, 2 означают возраст оборудования на начало 3-его года – 1 год, к концу 3-его года – 2 года, т.е. постарело.

В третьей строке цифры 0, 1 означают возраст оборудования на начало 3-его года 0 лет (т.е. после замены), к концу 3-его года – 1 год, т.е. постарело (эксплуатировалось 1 год).

Составим таблицу 2.4 с получением прибыли за 3 и 4 плановые периоды.

Таблица 2.4 – Прибыли за 3,4 плановые периоды

 (из предыдущей таблиц по 1-ой колонке)

 (из предыдущей таблицы соответственно )

1

Сохранение

1

2

31

28

59

59

Замена

0

1

27

31

58

2

Сохранение

2

3

28

27

55

58

Замена

0

1

27

31

58

3

Сохранение

3

4

27

27

54

58

Замена

0

1

27

31

58

4

Сохранение

4

5

27

27

54

58

Замена

0

1

27

31

58

5

Сохранение

5

-

24

-

58

Замена

0

1

27

31

58

Продолжим вычисления, которые сведем в таблицы 2.5 и 2.6.

Таблица 2.5 – Прибыли со 2-ого по 4-ый плановые периоды

 (из предыдущей таблиц по 1-ой колонке)

 (из предыдущей таблицы соответственно )

1

Сохранение

1

2

31

58

89

89

Замена

0

1

27

59

86

2

Сохранение

2

3

28

58

86

86

Замена

0

1

27

59

86

3

Сохранение

3

4

27

58

85

86

Замена

0

1

27

59

86

4

Сохранение

4

5

27

58

85

86

Замена

0

1

27

59

86

5

Сохранение

5

-

24

-

86

Замена

0

1

27

59

86


Таблица 2.6 – Прибыли для всего 4-ого периода

 (из предыдущей таблиц по 1-ой колонке)

 (из предыдущей таблицы соответственно )

0

Сохранение

0

1

31

89

120

120

1

Сохранение

1

2

31

86

117

117

Замена

0

1

27

89

116

2

Сохранение

2

3

28

86

114

116

Замена

0

1

27

89

116

3

Сохранение

3

4

27

86

113

116

Замена

0

1

27

89

116

4

Сохранение

4

5

27

86

113

116

Замена

0

1

27

89

116

5

Сохранение

5

-

24

116

Замена

0

1

27

89

116

Составим таблицу 2.7 максимальных прибылей по предыдущим расчетам.

Таблица 2.7 – Матрица максимальных прибылей

Возраста оборудования, -лет

Годы планового периода

1-4

2-4

3,4

4

Максимальная прибыль, ден.ед.

0

120

-

1

117

89

59

31

2

116

86

58

28

3

116

86

58

27

4

116

86

58

27

5

116

86

58

27

Из таблицы 2.7 имеем, все элементы выше жирной линии, находятся в «области сохранения», все элемент ниже жирной линии – в «области замены».

Каждый столбец таблицы 2.7 соответствует столбцам таблиц прибылей .


2.3 Выводы по результатам решения

Из условия задачи п.2.1 пусть на начало планового периода имеется оборудование в возрасте 4-е года. Тогда по таблице максимальных прибылей 2.7 п.2.2 на пересечении  и столбца  находится элемент 116 – максимальная прибыль за четыре года. Этот элемент расположен в зоне замены. Заменив оборудование и использовав его в течение года, к началу третьего второго года окажемся с оборудованием в возрасте 1 год. На пересечении  и столбца  расположен элемент 89 – максимальной прибыли в зоне сохранения. Продолжая политику, как показано на рисунке, к 4-ому году оборудование необходимо сохранить.

Рисунок 2.1 – Политика использования оборудования

Из условия п.2.1. пусть на начало планового периода имеется оборудование в возрасте 1-о года. Следуя политике, как показано на рисунке, к 4-ому году оборудование необходимо также сохранить.

Рисунок 2.2 – Политика использования оборудования

Заключение

В результате курсовой работы для решения поставленной задачи рассмотрены основные понятия и принципы динамического программирования в п.1.1 – п.1.2.

Рассмотрен принцип оптимальности Беллмана в задаче о замене оборудования, который записывается функциональными уравнениями 1.2 – 1.6 рекуррентного характера, которые рассмотрены в п.1.3.

На примере рассмотренной задачи из сборника [1] решена задача

Похожие материалы

Информация о работе