Автоматизация управления производством - 66 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

66
σ
Т
– термическое напряжение растяжения, Па .
13.2. Динамическое программирование
Динамическое программирование как метод решения оптимиза-
ционных задач в различных сферах человеческой деятельности
разработан Ричардом Беллманом (США, 1952).
В аналитическом представлении динамическое программирова-
ние базируется на математическом аппарате, в известной степени
эквивалентном используемому в принципе максимума. Однако с
самого начала этот метод развивался в численном представлении
с целью его непосредственной реализации с помощью средств вы-
числительной техники. При этом процедура решения оптимизаци-
онной задачи расчленяется во времени или пространстве на от-
дельные этапы (стадии), а особенность метода заключается в том,
что решение начинают с последнего этапа, постепенно приближа-
ясь к первому. На каждом из таких этапов сравнивают различные
варианты решения, отбирают оптимальный вариант, который запо-
минают, а неоптимальные варианты тут же отбрасывают, чтобы не
перегружать память компьютера.
Таким образом, в численном представлении задача динамиче-
ского программирования сводится к особого вида прибору возмож-
ных вариантов решения и выявлению оптимального варианта ре-
шения задачи в целом.
Сказанное можно иллюстрировать следующим примером.
Пример 6. Дано: k – стадийный процесс, на каждой из стадий ко-
торого принимается n решений. Пусть k = 4, n = 2.
Найти оптимальное для всех стадий (т.е. для задачи в целом)
решение.
Решение
На стрелках дерева решений (рис.13.1) обозначены показатели
оптимальности решений на отдельных стадиях задачи, например
затраты на технологический процесс, тогда как общее оптимальное
решение должно обеспечить минимум суммарных затрат.
При обычном подходе к решению задачи методом перебора всех
возможных вариантов необходимо сравнить между собой V = n
k
=
16 вариантов и выбрать из них наилучший. Отметим, что практиче-
ски суммарное число вариантов может быть значительно больше.
Например, при k = 12 и n = 4 имеем V = 16,78 · 10
6
… , что уже пред-
ставляет собой достаточно серьезную задачу.

Страницы