ММ. ПР4. Задача динамического программирования. Задача о замене. Лабораторная работа 4 Задача динамического программирования. Задача о замене оборудования

Название	Лабораторная работа 4 Задача динамического программирования. Задача о замене оборудования
Дата	05.07.2022
Размер	0.54 Mb.
Формат файла
Имя файла	ММ. ПР4. Задача динамического программирования. Задача о замене .pdf
Тип	Лабораторная работа #625355

Лабораторная работа №4 «Задача динамического программирования.
Задача о замене оборудования»
Цели работы: научиться решать задачи динамического программирования, научиться разбивать весь процесс решения задачи на этапы, научиться выбирать оптимальную стратегию поведения.
Краткая теория
1. Понятие задачи динамического программирования
Рассматриваемые ранее задачи характеризуются тем, что в них не учитываются изменения оптимизируемых параметров во времени – процессы считаются статичными.
Выбирается некоторый период времени, и для него определяются проектируемые или планируемые значения показателей. При этом предполагается, что управляемые или неуправляемые параметры системы в течение всего планового времени не будут изменяться или, по крайней мере, не претерпят серьѐзных изменений, требующих пересмотра принятых решений.
Однако в реальной жизни есть задачи, в которых необходимо учитывать изменения параметров систем во времени. Эти параметры могут меняться непрерывно или дискретно – от этапа к этапу. Например, из года в год меняется возраст машин и оборудования, изменяется производственная мощность и производительность труда на предприятиях. Очевидно, что необходимо принимать оптимальные решения на год (или другой срок) и одновременно на весь рассматриваемый период в целом с учѐтом возможных изменений параметров. Для решения такого вида задач, которые получили название
многошаговые, разработан соответствующий математический аппарат, который получил название
динамическое
программирование.
Задача может быть сформулирована следующим образом:
Задача динамического программирования – определить u i
* (u i
* не только число, а может быть вектором, функцией) на каждом шаге, i = 1, 2 …, m, и тем самым u* всей операции в целом.
Рассмотрим подход к решению данной задачи. Характерным для динамического программирования является то, что переменные рассматриваются вместе, а не последовательно – одна за другой. При этом вычислительная тема строится таким образом, что вместо одной задачи с n переменными решается серия задач с небольшим числом, а чаще с одной переменной. Сам же вычислительный процесс производится на основе метода последовательных приближений в два круга:
1. От последнего шага к первому.
2. От первого шага к последнему или же наоборот, в зависимости от исходных
данных.
На первом круге ищется так называемое условное оптимальное решение. Оно выбирается так, чтобы все предыдущие шаги обеспечили максимальную эффективность последующего. Основу такого подхода составляет принцип оптимальности Беллмана, который формулируется следующим образом:
Нельзя получить оптимальное значение целевой функции i-шагового процесса, если для
любого u
i
,
выбранного на шаге i, значение целевой функции для оставшихся i-1 шагов не
является оптимальным при этом выбранном на i-шаге значении u
i
Такой процесс продолжается до тех пор, пока решение не потеряет свой условный характер, т. е. до первого шага или последнего. Для него решение просто оптимально. Поэтому второй круг начинают именно с этого шага и последовательно переходят от условных к оптимальным решениям, тем самым обеспечивается оптимальность операции в целом.
Оптимальное распределение ресурсов
Пример:
Капитал 40 млн.руб. инвестор должен вложить в четыре инвестиционных проекта так,
чтобы получить максимальный доход. Доходность проектов дана в таблице (вложения кратны
8 млн. руб.)

Решение:
Это задача динамического программирования. Решение состоит из двух этапов. На первом этапе (от конца к началу) ищем условное оптимальное решение, на втором (от начала к концу) – ищем оптимальное решение задачи.
1 этап.
Распределяем капитал между четырьмя проектами и считаем получаемую прибыль
L(i), i=
8,16,24,32,40.
1 шаг: Денежные средства вкладываются в четвертый проект.
L(8)=55
L(16)=58
L(24)=90
L(32)=100
L(40)=140
2 шаг: Денежные средства вкладываются в четвертый и третий проекты.
u
Прибыль от внедрения
1 шаг
f3(u)
8
55
39
16 58 53 24 90 80 32 100 120 40 140 145
 














175 145
;
175
;
138
;
143
;
139
;
140
max
145
;
120 55
;
80 58
;
53 90
;
39 100
;
140
max
)
40
(
135 120
;
135
;
111
;
129
;
100
max
120
;
80 55
;
53 58
;
39 90
;
100
max
)
32
(
108 80
;
108
;
97
;
90
max
80
;
53 55
;
39 58
;
90
max
)
24
(
94 53
;
94
;
58
max
53
;
39 55
;
58
max
)
16
(
55 39
;
55
max
)
8
(
40 0
32 8
24 16 16 24 8
32 0
40 32 0
24 8
16 16 8
24 0
32 24 0
16 8
8 16 0
24 16 0
8 8
0 16 8
0 0
8


















































L
L
L
L
L
3 шаг: Денежные средства вкладываются в четвертый, третий (2 шаг) и второй проекты.
u
Прибыль от внедрения
2 шаг
f2(u)
8 55 35 16
94
76 24 108
120
32 135 135 40 175 158

 














214 158
;
190
;
214
;
184
;
170
;
175
max
158
;
135 55
;
120 94
;
76 108
;
35 135
;
175
max
)
40
(
175 135
;
175
;
170
;
143
;
135
max
135
;
120 55
;
76 94
;
35 108
;
135
max
)
32
(
131 120
;
131
;
129
;
108
max
120
;
76 55
;
35 94
;
108
max
)
24
(
94 76
;
90
;
94
max
76
;
35 55
;
94
max
)
16
(
55 35
;
55
max
)
8
(
40 0
32 8
24 16 16 24 8
32 0
40 32 0
24 8
16 16 8
24 0
32 24 0
16 8
8 16 0
24 16 0
8 8
0 16 8
0 0
8


















































L
L
L
L
L
4 шаг: Денежные средства вкладываются в четвертый, третий, второй (3 шаг) и первый проекты.
u
Прибыль от внедрения
3 шаг
f1(u)
8 55 32 16 94 68 24 131 115 32 175 134 40
214
147
 














214 147
;
189
;
209
;
199
;
207
;
214
max
147
;
134 55
;
115 94
;
68 131
;
32 175
;
214
max
)
40
(
175 134
;
170
;
162
;
163
;
175
max
134
;
115 55
;
68 94
;
32 131
;
175
max
)
32
(
131 115
;
123
;
126
;
131
max
115
;
68 55
;
32 94
;
131
max
)
24
(
94 68
;
87
;
94
max
68
;
32 55
;
94
max
)
16
(
55 32
;
55
max
)
8
(
40 0
32 8
24 16 16 24 8
32 0
40 32 0
24 8
16 16 8
24 0
32 24 0
16 8
8 16 0
24 16 0
8 8
0 16 8
0 0
8
















































L
L
L
L
L
2 этап:
На четвертом шаге выбираем максимальное из полученных значений прибыли
L(40)=214.
И возвращаясь в обратном порядке от таблицы к таблице (от 4 шага к 1) выбираем такие значения доходов, при которых и получено значение 214.
Максимальный доход 214 млн. руб. от вложенных средств может быть получен при следующем распределении средств:
1 проект – 0 млн. руб.
2 проект – 24 млн. руб.
3 проект – 8 млн. руб.
4 проект – 8 млн. руб.
Задание
Задание 1. Распределите оптимальным образом денежные средства инвестора величиной 5 у.е. между четырьмя предприятиями. Доход каждого предприятия от вложения в него и у.е.определяется функцией дохода f(u). Эти функции приведены в таблице. u
Прибыль от внедрения по предприятиям f4(u)
f3(u)
f2(u)
f1(u)
1
f4(1)
6 3
4 2
10
f3(2)
4 6
3 11 11
f2(3)
8 4
12 13 11
f1(4)
5 18 15 18 16

Вариант
1
2
3
4
f4(1)
9 5
6 8
f3(2)
10 10 7
7
f2(3)
7 5
8 9
f1(4)
10 9
13 15
Задание 2. Из пункта А в пункт В необходимо проложить автомобильную трассу по самому экономичному пути.
Вариант 1
Вариант 2
Вариант 3

Контрольные вопросы:
1. Какие задачи можно решать методами динамического программирования?
2. В чем заключаются достоинства и недостатки динамического программирования?
3. Объясните алгоритм решения задач динамического программирования.
4. Укажите принцип выбора направления движения.
5. В чем заключается принцип оптимальности?
6. Каков алгоритм распределения ресурсов?
Вариант 4