4.2.1. Постановка и методика решения задач динамического программирования
Многие процессы с последовательным принятием решений описываются как комбинаторные задачи.
Для примера рассмотрен процесс, состоящий из n этапов, в каждом из которых принимается K решений. Для каждого возможного решения, принимаемого на n-м этапе, имеется K возможных решений, принимаемых на (n — — 1)-м этапе, а для каждого возможного решения, принимаемого на (n — 1)-м этапе, существует Kвозможных решений, получаемых на (n — 2)-м этапе, и т.д. Таким образом, для определения оптимального решения должно быть проанализировано Kn возможных решений. Для получения оптимального результата по заданному критерию последовательно рассматривается каждый этап, для которого выбирается наилучшие из Kрешений. В результате на n этапах рассматривается nK возможных решений. Следовательно, динамическое программирование приводит к тем же результатам, чтои комбинаторный метод, но при этом применяются в раз
меньше усилий вычислительной работы.
Вычислительная эффективность решения задач методом динамического программирования по сравнению с полным перебором всех решений становится все более существенной с ростом n. Причина этого состоит в том, что на каждом этапе исключаются из рассмотрения все неблагоприятные комбинации.
Если предположить, что K = 3, n = 5, то комбинаторный подход требует для анализа Kn = 35 = 243 комбинации. Метод поэтапного расчета, применяемый в динамическом программировании, потребует анализа 15 комбинаций (3 х 5). Если K = 3, а n = 100, то комбинаторный подход потребует 3100 решений, тогда как, используя метод динамического программирования, необходимо проанализировать лишь 300 комбинаций (3 х 100).
Недостатки динамического программирования — отсутствие общего алгоритма, пригодного для решения всех задач, в отличие от существующего симплексного метода, являющегося универсальным в линейном программировании; трудности решения многомерных задач; сложность формулировок задач в терминах динамического программирования.
Несмотря на перечисленные недостатки, динамическое программирование представляет определенную ценность, так как позволяет решать ряд задач, которые иначе решить нельзя или найти решение сложно.
Еще по теме 4.2.1. Постановка и методика решения задач динамического программирования:
- 4.1.2. Постановка и методика решения ассортиментной задачи симплексным методом
- 2.2. Стандартные методы решения задач стохастического программирования
- 4.2. Динамическое программирование
- Постановка и решение задачи оптимального распределения инвестиций
- Методики решения задач
- 7.2. Модели и задачи стохастического программирования в банковской деятельности
- §2. Пример задачи стохастического программирования
- Сведение матричной игры к задаче линейного программирования
- Приведение матричной игры к задаче линейного программирования
- 7.3. Модели и задачи нелинейного программирования в банковской деятельности
- 3.1. Постановка целей и задач
- Постановка задач
- Задачи проекта по постановке маркетинга