 |
 |
 |
 |
|
 |
 |
94
обстоятельство позволяет осуществить декомпозицию задачи и сделать возможным ее практическое
решение.
В то же время, говоря о динамическом программировании как о методе решения оптимизационных
задач, необходимо отметить и его слабые стороны. Так, в предложенной схеме решения задачи (5.3)-
(5.4) существенным образом используется тот факт, что система ограничений содержит только одно
неравенство, и, как следствие, ее состояние задается одним числом — нераспределенным ресурсом ? .
При наличии нескольких ограничений состояние управляемого объекта на каждом шаге
характеризуется уже набором параметров ?1, ?2, ..., ?
m
, и табулировать значения функций
?
k
(?1, ?2, ...,
?
m
) необходимо для многократно большего количества точек. Последнее обстоятельство делает приме-
нение метода динамического программирования явно нерациональным или даже просто невозможным.
Данную проблему его основоположник Р. Беллман эффектно назвал «проклятием многомерности». В
настоящее время разработаны определенные пути преодоления указанных трудностей. Подробную
информацию о них можно найти в специальной литературе [4, 5].
5.2. ПРИМЕРЫ ЗАДАЧ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
5.2.1. Задача о найме работников. Приступим к рассмотрению вопросов применения методов
динамического программирования в конкретных экономико-математических моделях.
Отдельно
отметим, что данные вычислительные схемы, вообще говоря, достаточно часто используются для
решения некоторых задач, которые уже были затронуты в других главах. Это, прежде всего, задача о
ранце, задача о кратчайшем пути, задачи транспортного типа.
Одним из важнейших классов задач, для которых применение динамического программирования
оказывается плодотворным, являются задачи последовательного принятия решений. Их особенностью
является то, что искомые переменные х1,
x2, ..,
х
k
,... должны определяться в строгой временной по-
следовательности и не должны меняться местами. В качестве примера опишем так называемую задачу о
найме работников (задачу об использовании рабочей силы).
В данной задаче рассматривается некоторый экономический объект (фирма, магазин, завод и т. п.),
функционирующий в течение конечного числа периодов, обозначаемых номерами
k (k ? l:n). Каждый
период
k характеризуется нормативной потребностью в определенном количестве однотипных
работников m
k
. Тот же объем работ может быть выполнен другим количеством сотрудников
?
k
, что,
однако, влечет дополнительные затраты либо за счет нерационального использования рабочей силы,
либо ввиду повышения оплаты за интенсивный труд. Размеры этих дополнительных издержек
описываются функциями g
k
(?
k
- m
k
), где (
?
k
- m
k
) — отклонение фактической численности работающих
?
k
, от планово необходимой m
k
, причем
g
k
(0)=0. Управленческое решение на шаге k заключается в
выборе величины изменения числа сотрудников х
k
?Z, что однозначно определяет количество
работающих в течение следующего периода:
?
k+1
= ?
k
+х
k
. Затраты по изменению количества работников
(найму и увольнению) при переходе от периода k к периоду (k+1) задаются функцией u
k
(х
k
) , где также
u
k
(0)=0. Тогда суммарные издержки, вызванные принятым на шаге k решением, характеризуются
значением функции
План задачи (стратегия управления) х
= (x1, ..., х
n-1
, 0) заключается в выборе поэтапных изменений
количества работников, а его суммарная эффективность описывается аддитивной функцией
На основе сформулированной модели ставится задача минимизации целевой функции (издержек)
(5.15). Добавим, что постановка задачи не будет корректной, если не задать начальное условие на
количество работников. Существуют две модификации данной задачи, определяемые типом начального
условия:
в первом случае задается исходное значение на первом этапе
m1, а во втором — требуемое
количество в n-м периоде m
n
.