ПОИСК Статьи Рисунки Таблицы Математическая формулировка принципа оптимальности для дискретных процессов из "Методы оптимизации в химической технологии издание 2" Простейшим примером такой задачи является задача о путешественнике, которому предстоит из пункта А попасть в пункт В, соединяющийся с пунктом А разветвленной сетью дорог. Двигаясь, путешественник на каждом перекрестке (стадии) должен принимать решение, по какой дороге двигаться дальше, чтобы как можно быстрее попасть в конечный пункт В. Рассматриваемую ниже комбинаторную задачу можно также интерпретировать как задачу о путешественнике. [c.262] Предположим, что существует. /V-стадийный процесс, на каждой стадии которого возможны п фиксированных состояний, и пусть из каждого состояния (i—1)-и стадии процесса можно попасть в любое из п состояний следующей i-й стадии. На рис. VI-2 показано схематическое изображение двух стадий указанного процесса для случая п = 3. [c.262] Допустим, что результат перехода из р-то состояния (i— 1)-й стадий в q-o. состояние 1-й стадии оценивается величиной п, которая может считаться функцией целых чисел р и q, т. е. [c.262] Примем, что исходное состояние процесса задано. Тогда переход из него в любое из п возможных состояний 1-й стадии, очевидно, связан с возможностью выбора одного из п вариантов перехода. Число возможных вариантов перехода из исходного состояния на вторую стадию будет равно уже п2, и, наконец, для всего ЛЛстадийного процесса число возможных вариантов перехода из исходного состояния на N-ю стадию составит nN. [c.262] Не нужно быть искушенным в математике, чтобы понять, насколько велико может быть число nN и как быстро оно возрастает с увеличением значений п и N. Например, для п = 3 и N = 10, т. е. [c.262] Таким образом, метод прямого перебора в случае решения комбинаторных задач даже при использовании современных ЭВМ им еет весьма ограниченную область применения1, поскольку возрастание числа вариантов, подлежащих проверке, при увеличе-ншгчисла стадий и возможных на них состояний может очень быстро превысить возможности любой вычислительной машины. [c.263] Рассмотрим теперь, каким образом можно решить сформулированную выше комбинаторную задачу, используя метод динамического программирования. Как отмечалось выше, процедура решения задачи оптимизации при помощи принципа оптимальности начинается с оптимизации последней стадии процесса, результатом чего является набор оптимальных решений (управлений) на ней для любых возможных состояний входа этой стадии. [c.263] В данном случае оптимизация сводится к оценке возможных вариантов перехода из п состояний предыдущей (N—1)-й стадии в п состояний последней ЛЛ-й стадии. Таким образом, обследованию подлежат п2 вариантов, что позволяет выделить п оптимальных управлений на этой стадии, соответствующих п состояниям предыдущей стадии и обеспечивающих переход на послед-, нюю стадию с максимальными значениями результатов перехода rN(p,q). Указанные значения, естественно, зависят от состояния предыдущей стадии, откуда осуществляется переход. [c.263] Ёсе возможные состояния входа N-и стадии [выхода (N—1)-й стадии]. [c.264] Теперь можно определить оптимальное управление на предпоследней стадии при любом Состоянии выхода (N — 2)-и стадии. На рис. VI-4 при изображении последней стадии оставлены только оптимальные переходы, дающие максимальный результат. [c.264] Кроме того, оказывается, что конечное состояние на последней стадии уже определено однозначно, поскольку осталось только одно состояние (3) данной стадии, куда возможен переход с (W —2)-и стадии с максимальным значением результата перехода, оцениваемым по двум последним стадиям. [c.264] После того как найдена оптимальная стратегия управления для двух последних стадий, можно перейти к выбору оптимального управления для (N — 2)-и стадии (рис. VI-5), на которой обследованию подлежат также п2 вариантов перехода, и т. д. [c.265] Если же исходное состояние не определено и может быть выбрано из совокупности п исходных состояний, то на первой стадии также необходимо исследовать п2 вариантов перехода (рис. VI-7), в результате чего можно найти одно (или несколько), исходное состояние, отвечающее максимальному значению результата для многостадийного процесса в целом. [c.265] Соотношение (VI, 23) по существу является математической формулировкой задачи оптимизации -стадийного процесса и еще не содержит указаний, как именно нужно максимизировать критерий RN, чтобы получить оптимальную стратегию (VI, 22). [c.266] Разумеется, что в выражении, заключенном в квадратных скобках, каждое слагаемое нельзя максимизировать в отдельно-, сти, вследствие того, что величины обоих слагаемых зависят от управления иР Причем на первое слагаемое управление н влияет прямо, тогда как на втором это влияние сказывается косвенно -через изменение значения jtf1). [c.267] Вернуться к основной статье