Идея и общий алгоритм метода динамического программирования
Идея методов динамического программирования заключается в разбиении динамического процесса на этапы, в каждом из которых параметры этого процесса оптимизируется независимо от параметров управляемого процесса на других этапах.
Поэтому методы динамического программирования имеют следующие принципиальные отличия от методов оптимизации статических задач:
- процесс принятия решений распадается на несколько этапов, на каждом из которых принимается решение с таким условием, чтобы обеспечивалась оптимальность всего процесса в целом;
- оптимальный план не зависит от предыстории. Оптимальный план зависит от состояния управляемого процесса в исходный момент времени, а не от того, как было достигнуто исходное состояние;
- значение целевой функции процесса складывается из элементарных значений функции, рассчитываемой для каждого этапа. Это требование динамического программирования относительно критерия оптимальности называется аддитивностью.
В задачах динамического программирования управление по этапам должно выбираться с учетом всех его последствий в будущем. На каждом этапе определяется такое управление, которое обеспечивает оптимальное продолжение процесса относительно достигнутого в данный момент состояния. Этот принцип называется принципом оптимальности, он сформулирован Р. Беллманом – американским математиком, основоположником метода динамического программирования.
Другими словами, при планировании многоэтапного процесса следует исходить из интересов процесса в целом, т.е. при принятии решения на этапе необходимо иметь в виду конечную цель.
Из принципа оптимальности есть исключение. На последнем этапе можно действовать без оценки будущего этапа, поскольку его нет. На последнем этапе управление следует выбирать так, чтобы оно дало наибольший эффект и было на этом этапе наилучшим. Поэтому процесс динамического планирования проводится в обратном во времени направлении, т.е. сначала планируется последний этап. При этом необходимо сделать разные предположения о том, чем закончился предпоследний этап, и для каждого из этих направлений выбрать управление на последнем этапе.
Следовательно, задача динамического программирования решается в два этапа: на I этапе, который выполняется от конца процесса к началу, находят условные оптимальные решения; на II этапе, который выполняется от начала процесса к концу, находят безусловно оптимальное решение.
Алгоритм метода динамического программирования включает следующие действия:
- транспортный процесс разбивается на этапы;
- для каждого этапа вводятся функциональные характеристики (параметры или переменные) процесса и их числовые значения. Затем выделяются управляющие факторы, с помощью которых можно влиять на развитие процесса;
- на каждом этапе решения задачи динамического программирования имеется зависимость между рассматриваемыми переменными и функцией цели. Зависимость выражается с помощью уравнений или неравенств. Методом динамического программирования для каждого этапа устанавливают такой уровень управления, который обеспечивает оптимальность функции цели процесса в целом.
Достоинство динамического программирования заключается в том, что задача разбивается на этапы и решение осуществляется для каждого их них. Тем самым сложная многовариантная задача оптимизации сводится к совокупности более простых частных задач, что значительно упрощает процедуру расчетов. Недостатком метода динамического программирования относится отсутствие универсального алгоритма решения, пригодного для всех динамических задач.
- Назначение и классификация складов
- Требования к транспортированию и хранению массовых грузов
- Автоматическая идентификация грузов
- Пломбирование и индикация грузов
- Силы, действующие на груз при транспортировке
- Причины недостачи грузов
- Естественная убыль грузов и ее нормирование
- Виды несохранности грузов при перевозке
- Транспортная маркировка грузов
