Меню
Главная
Авторизация/Регистрация
 
Главная arrow Экономика arrow Исследование операций в экономике

Модели динамического программирования

Общая постановка задачи динамического программирования

Динамическое программирование (ДП) метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги). Такие операции называются многошаговыми. Начало развития ДП относится к 50-м г. XX в. Оно связано с именем Р. Веллмана[1].

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

В реально функционирующих больших экономических системах еженедельно требуется принимать микроэкономические решения. Модели ДП ценны тем, что позволяют на основе стандартного подхода с использованием ЭВМ при минимальном вмешательстве человека принимать такие решения. И если каждое взятое в отдельности такое решение малосущественно, то в совокупности эти решения могут оказать большое влияние на прибыль.

Приведем общую постановку задачи ДП. Рассматривается управляемый процесс, например экономический процесс распределения средств между предприятиями, использования ресурсов в течение ряда лет, замены оборудования, пополнения запасов и т.п. В результате управления система (объект управления) S переводится из начального состояния 50 в состояние s. Предположим, что управление можно разбить на η шагов, т.е. решение принимается последовательно на каждом шаге, а управление, переводящее систему S из начального состояния в конечное, представляет собой совокупность η пошаговых управлений.

Обозначим через Xk управление на k-м шаге = 1, 2,..., η). Переменные Xk удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (Хк может быть числом, точкой в "-мерном пространстве, качественным признаком).

Пусть X (X,, Х2,..., Хп) – управление, переводящее систему 5 из состояния s0 в состояние s. Обозначим через sk состояние системы после /"'-го шага управления. Получаем последовательность состояний s0, st,..., sk_v sk,..., sn_ -, которую изобразим кружками (рис. 11.1).

l

Рис. 11.l

Показатель эффективности рассматриваемой управляемой операции – целевая функция зависит от начального состояния и управления:

(11.1)

Сделаем несколько предположений.

1. Состояние sk системы в конце к-го шага зависит только от предшествующего состояния sk , и управления на к-м шаге Хк (и не зависит от других предшествующих состояний и управлений). Э го требование называется "отсутствием последействия". Сформулированное положение записывается в виде уравнений:

(11.2)

которые называются уравнениями состояний.

2. Целевая функция (11.1) является аддитивной от показателей эффективности каждого шага [3]. Обозначим показатель эффективности ⅛-го шага через

(11.3)

тогда

(11.4)

Задача пошаговой оптимизации (задача ДП) формулируется так: определить такое допустимое управление X, переводящее систему S из состояния s0 в состояние при котором целевая функция (11.4) принимает наибольшее (наименьшее) значение.

Выделим особенности модели ДП.

  • 1. Задача оптимизации интерпретируется как п-шаговый процесс управления.
  • 2. Целевая функция равна сумме целевых функций каждого шага.
  • 3. Выбор управления на k-м шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (нет обратной связи).
  • 4. Состояние sk после к-го шага управления зависит только от предшествующего состояния sk ↑ и управления Хк (отсутствие последействия ).
  • 5. На каждом шаге управление Хк зависит от конечного числа управляющих переменных, а состояние sk – от конечного числа параметров (смысл замечания 5 станет ясным из рассмотренных ниже примеров).

Следует вспомнить, что существуют различные способы решения подобных задач, применяемые в зависимости от вида функций, ограничений, размерности и т.п. Рассмотрим вычислительную схему ДП, которая окажется безразличной к способам задания функций и ограничений. Вычислительная схема связана с принципом оптимальности и использует рекуррентные соотношения.

  • [1] Р. Э. Беллман (р. 1920 г.) – американский математик.
 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы