Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

ПРИМЕРЫ ЗАДАЧ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

Одним из важнейших классов задач, для которых применение динамического программирования оказывается плодотворным, являются задачи последовательного принятия решений. Их особенностью является то, что искомые переменные х1, x2, .., хk ,... должны определяться в строгой временной последовательности и не должны меняться местами. В качестве примера опишем так называемую задачу о найме работников (задачу об использовании рабочей силы).

В данной задаче рассматривается некоторый экономический объект (фирма, магазин, завод и т. п.), функционирующий в течение конечного числа периодов, обозначаемых номерами k (k ∊ l:n). Каждый период k характеризуется нормативной потребностью в определенном количестве однотипных работников mk. Тот же объем работ может быть выполнен другим количеством сотрудников ξk, что, однако, влечет дополнительные затраты либо за счет нерационального использования рабочей силы, либо ввиду повышения оплаты за интенсивный труд. Размеры этих дополнительных издержек описываются функциями gkk - mk), где (ξk - mk) — отклонение фактической численности работающих ξk , от планово необходимой mk , причем gk (0)=0. Управленческое решение на шаге k заключается в выборе величины изменения числа сотрудников хkZ, что однозначно определяет количество работающих в течение следующего периода: ξk+1 = ξk+хk. Затраты по изменению количества работников (найму и увольнению) при переходе от периода k к периоду (k+1) задаются функцией uk (хk) , где также uk (0)=0. Тогда суммарные издержки, вызванные принятым на шаге k решением, характеризуются значением функции

План задачи (стратегия управления) х = (x1, ..., хn-1, 0) заключается в выборе поэтапных изменений количества работников, а его суммарная эффективность описывается аддитивной функцией

На основе сформулированной модели ставится задача минимизации целевой функции (издержек) (5.15). Добавим, что постановка задачи не будет корректной, если не задать начальное условие на количество работников. Существуют две модификации данной задачи, определяемые типом начального условия: в первом случае задается исходное значение на первом этапе m1, а во втором — требуемое количество в n-м периоде mn .

Рассмотрим первый случай. Поскольку фиксированным является начальное количество работников и, напротив, ничего не известно о том, каким это количество должно быть на последнем этапе, то рассмотрение процесса принятия решений удобнее начать с конца. Оптимальное управление на последнем этапе п по условию равно х*n = n(ξ)=0, поэтому минимальные издержки полностью определяются количеством работников в последнем периоде:

Для остальных предшествующих шагов основное рекуррентное соотношение примет вид

где Λk(ξ) — минимальные затраты с k-го по п-й периоды, в предположении, что количество работников в k-й период равно ξ. Точки л(ξ), в которых достигаются минимумы (5.17), определяют условное оптимальное управление на каждом шаге.

Последовательно определяя л(ξ) и дойдя до этапа 1, мы сможем найти безусловное оптимальное управление x1* из того условия, что на начало первого периода численность работников должна составлять ξ1* = m1 , a именно

Остальные компоненты оптимального плана хk* и состояния ξk*, образующие оптимальную траекторию, последовательно находятся по рекуррентным формулам

после чего не составляет труда вычислить оптимальное значение целевой функции (5.15).

Остановимся теперь на втором случае, когда задано финальное состояние управляемого объекта, т. е. желаемое количество работников на последнем периоде ξn*= mn . Очевидно, что в данной ситуации следует поступить с точностью «до наоборот» и рассмотреть процесс принятия решений от начала к концу. Наилучшее условное управление на первом шаге 1(ξ) будет найдено в процессе вычисления функции

где состояние ξ ≥0 является возможным количеством работников на начальном шаге. Соответственно, основное рекуррентное соотношение выразит минимальные издержки вплоть до k-го периода через таковые для предыдущих периодов (с первого по (k-1)-й) при условии, что численность работников в k-й период будет равна ξ:

Попутно будут найдены функции k(ξ), k∊2:n, определяющие условные оптимальные управления. На последнем периоде, в силу начального условия, ξn*= mn. Отсюда путем последовательного решения рекуррентных уравнений могут быть найдены оптимальные численности работников ξ*k и безусловные оптимальные управления:

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