<<
>>

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).

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

Несмотря на перечисленные недостатки, динамическое программирование представляет определенную ценность, так как позволяет решать ряд задач, которые иначе решить нельзя или найти решение сложно. 

<< | >>
Источник: Маркин Юрий Павлович. Экономический анализ : учеб. пособие для студентов вузов, обучающихся по направлению «Экономика» и другим эконом. специальностям. 2011

Еще по теме 4.2.1. Постановка и методика решения задач динамического программирования:

  1. 4.1.2. Постановка и методика решения ассортиментной задачи симплексным методом
  2. 2.2. Стандартные методы решения задач стохастического программирования
  3. 4.2. Динамическое программирование
  4. Постановка и решение задачи оптимального распределения инвестиций
  5. Методики решения задач
  6. 7.2. Модели и задачи стохастического программирования в банковской деятельности
  7. §2. Пример задачи стохастического программирования
  8.              Сведение матричной игры к задаче линейного программирования
  9. Приведение матричной игры к задаче линейного программирования
  10. 7.3. Модели и задачи нелинейного программирования в банковской деятельности
  11. 3.1. Постановка целей и задач
  12. Постановка задач
  13. Задачи проекта по постановке маркетинга
- Бюджетная система - Внешнеэкономическая деятельность - Государственное регулирование экономики - Инновационная экономика - Институциональная экономика - Институциональная экономическая теория - Информационные системы в экономике - Информационные технологии в экономике - История мировой экономики - История экономических учений - Кризисная экономика - Логистика - Макроэкономика (учебник) - Математические методы и моделирование в экономике - Международные экономические отношения - Микроэкономика - Мировая экономика - Налоги и налолгообложение - Основы коммерческой деятельности - Отраслевая экономика - Оценочная деятельность - Планирование и контроль на предприятии - Политэкономия - Региональная и национальная экономика - Российская экономика - Системы технологий - Страхование - Товароведение - Торговое дело - Философия экономики - Финансовое планирование и прогнозирование - Ценообразование - Экономика зарубежных стран - Экономика и управление народным хозяйством - Экономика машиностроения - Экономика общественного сектора - Экономика отраслевых рынков - Экономика полезных ископаемых - Экономика предприятий - Экономика природных ресурсов - Экономика природопользования - Экономика сельского хозяйства - Экономика таможенного дел - Экономика транспорта - Экономика труда - Экономика туризма - Экономическая история - Экономическая публицистика - Экономическая социология - Экономическая статистика - Экономическая теория - Экономический анализ - Эффективность производства -