Исследование операций. Линейное, динамическое программирование




Исследование операций - часть 68


Бывает так, что весь выигрыш, который был бы получен от точной оптимизации решения, «съедается» затратами на получение этого решения, так что «игра не стоит свеч». Здесь опять мы встречаемся с необходимостью «системного» подхода к задачам исследования операций, учета не только непосредственного выигрыша в данной операции, по и затрат па со оптимизацию.

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

ГЛАВА 4

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

§ 12. Метод динамического программирования

Динамическое программирование (иначе «динамическое планирование») есть особый метод оптимизации решений, специально приспособленный к так называемым «многошаговым» (пли «многоэтапным») операциям.

Представим себе некоторую операцию O,

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

.

Итак, рассмотрим операцию O, состоящую из т шагов (этапов). Пусть эффективность операции характеризуется каким-то показателем W, который мы для краткости будем в этой главе называть «выигрышем». Предположим, что выигрыш W за всю операцию складывается из выигрышей на отдельных шагах:

        (12.1)

где wi — выигрыш на i-м шаге.




Содержание  Назад  Вперед