Моделирование многошаговых процессов

Многошаговый процесс принятия решения часто применя­ется при решении задачи распределения определенного количе­ства ресурса (R) во времени (по годам) или между предприяти­ями одной фирмы с целью получения наибольшего полезного эффекта.

При этом целевая функция задачи является нелинейной, обычно заданной в виде таблицы, а возможные варианты пла­нов оказываются дискретными величинами.

В общей форме задача динамического программирования трактуется как проблема управления экономической системой на некотором промежутке времени (в несколько лет). Путем осуществления некоторого управления система (например, фир­ма) переходит из некоторого начального состояния в заданное конечное состояние.

Например, выполнен некоторый инвестиционный проект, построен новый производственный объект. Этот переход может быть реализован различными способами. Задача состоит в том, чтобы из множества возможных уравнений выбрать то, которое дает максимальное значение полезного эффекта (дополнитель­ного дохода, прибыли и т.п.).

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

Фирма выделяет капитальные средства в размере R рублей для использования их для строительства крупного промышленного объекта в течение п лет (t₁,…,t_n ). Этот объект вводится в эксплу­атацию по частям и, таким образом, фирма получает дополни­тельный доход по мере готовности той или иной части объекта.

Обозначим объем средств, выделяемых для стройки в году t_j через x_j а ожидаемый дополнительный доход (локальную целе­вую функцию) — через fj(Xj).

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

Математическая постановка задачи состоит в определении наибольшего значения нелинейной функции

(1)

при условиях

(2)

(3)

План распределения капиталовложений являющийся реше­нием поставленной задачи, называется оптимальным планом распределения.

2.4.3. Принцип оптимальности

При решении математической задачи (1)—(3) исходят из того, что максимальный доход за п лет может быть представлен как максимум суммы максимального дохода за (я - 1) первых лет и дохода года п. Максимум определяется по всем возможным вариантам капиталовложений х_п в течение года п. Таким обра­зом,

(4)

где F_n-1— функция максимального дохода за (я - 1) лет, кото­рая строится по формуле аналогичной (4). Здесь существенным является то, что в формуле (4) фигурирует не максимальный до­ход за (n - 1) лет, а значение функции максимального дохода (интервальной целевой функции), зависящее от решения на по­следнем шаге (величины х_п).

Это замечание распространяется на любой шаг j процесса принятия решений (определение величины xj) и формулирует­ся обычно в виде принципа оптимальности Р. Беллмана:

Каково бы ни было состояние системы перед очередным шагом j, надо выбрать управление (x_j) на этом шаге так, чтобы полезный эффект на данном шаге плюс оптимальный полезный эффект на всех предыдущих шагах был максимальным.

Исходя из принципа оптимальности можно построить следующие рекуррентные соотношения:

(5)

(6)

…

(7)

…

(8)