ПОИСК Статьи Рисунки Таблицы Оптимизация сложных многостадийных процессов из "Методы оптимизации в химической технологии" Наиболее наглядно метод динамического программирования можно демонстрировать при решении комбинаторных задач, которые могут быть представлены как многостадийные ироцессы принятия решений, т. е. выбора управления на каждой стадии из некоторого дискретного и конечного набора возможных управлений (решений). [c.248] Прсютейшим примером такой задачи является задача о путешественнике, которому предстоит из пункта А попасть в пункт В, соединяющийся с пунктом А разветвленной сетью дорог. Двигаясь, путешественник на каждом перекрестке (стадии) должен принимать решение, по какой дороге двигаться дальше, чтобы как можно быстрее попасть в конечный пункт В. Рассматриваемую ниже комбинаторную задачу можно также интерпретировать как задачу о путешественнике. [c.249] Допустим, что результат перехода из р-го состояния (I — 1)-й стадии в д-е состояние г-й стадии оценивается величиной Г , которая может считаться функцией целых чисел р и с], т. е. [c.249] Таким образом, метод прямого перебора в случае решения комбинаторных задач даже ири использовании современных ЭВМ имеет весьма ограниченную область применения, поскольку возрастание числа вариантов, подлежащих проверке, при увеличении числа стадий и возможных на них состояний может очень быстро превысить возможности любой вычислительной машины. [c.250] В данном случае оптимизация сводится к оценке возможных вариантов перехода из а состояний предыдущей (Л/ — 1)-й стадии в п состояний последней Л -й стадии. Таким образом, обследованию подлежат п вариантов, что позволяет выделить п оптимальных управлений на этой стадии, соответствующих я состояниям предыдущей стадии и обеспечивающих переход на последнюю стадию с максимальными значениями результатов перехода r,v (/ , q). Указанные значения, естественно, завнсяг от состояния прсдыдун ,ей стадии, откуда осуществляется переход. [c.250] Интересно отметить, что найденные оптимальные переходы с учетом изолированной (М — 1)-й стадии совсем пе оптимальны, так как в ее пределах существуют локальные переходы с большими значениями результатов. [c.251] Кроме того, оказывается, что конечное состояние на последней стадии уже определено однозначно, поскольку осталось только одно состояние (3) данной стадии, куда возможен переход с (Л/ — 2)-й стадш с максид1альным значением результата перехода, оцениваемым по двум последним стадиям. [c.251] После того как найдена оптимальная стратегия управления для двух последних стадий, можно перейти к выбору оптимального управления для (Л/ — 2)-й стадии (рис, VI-5), на которой обследованию подлежат также вариантов перехода, и т. д. [c.251] Таким образом, сформулированная выше комбинаторная задача решена до конца. В процессе решения потребовалось исследовать всего Мп вариантов, тогда как при применении метода прямого перебора нужно оценить п различных вариантов. Время решения комбинаторной задачи с п и N = 20 при оценке одного варианта за 1 сек с использованием принципа оптимальности будет равно 20-3 = 180 сек 3 мин, что в сравнении с 3 сек 960 тыс. ч, необходимыми для решения задачи прямым перебором, позволяет весьма ощутимо представить преимущества динамического программирования при решении подобных задач. [c.252] Соотношение (VI,23) по существу является математической формулировкой задачи оптимизации /V-стадийного процесса и еще не содержит указаний, как именно нужно максимизировать критерий Rfj, чтобы получить оптимальную стратегию (VI,22). [c.253] Общая процедура решения задачи методом динамического программирования. Проиллюстрируем процедуру решения задачи оптимизации многостадийного процесса на примере процесса, в котором размергюсть векторов состояния и управления на каждой стадии равна единице. Это позволяет повысить наглядность проводимых рассуждений при помощи графическ[1Х построений. [c.255] На этом первый этап решения задачи оптимизации миогостадий-ного процесса заканчивается. Выведенные соотиошения (VI,396) и (VI,39г),(VI,38б)и(VI,38г), (VI,376) н(VI,37г),(VI,36б) и (У1,36г) уже определяют оптима.) [,ную стратегию управления )У-стадийным процессом для любого возможного СОСТОЯ ИЯ входа первой стадии. [c.257] Соотношения, получаемые прн выборе оптимального управления па (/V—2)-й стадии. [c.257] На втором этапе решения оптимальной задачи находятся онтималь-иые управления всех стадии ) (г 1,. . Л/ , длн чего необходимо принять соответствующее значение состояния входа процесса При этом, если значение х ) не задано в исходной постановке оптимальной задачи, его можно также определить оптимальным образом из условия максимума величины/,у как функции значения (У1,39в). [c.258] Когда значенне состояния входа процесса определено (VI,40), т. е. либо задано, либо найдено из условия максимума функции /д,(х ), можно приступить к нахождению оптимальных управлений для всех стадий процесса, соответствующих выбранной величине = а . Процедура определения оптимальных управлений для всех стадий и является вторым, зЛ лючительным, этапом решения оптимальной задачи методом динамического программирования. [c.258] Вернуться к основной статье